Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [algorithmic-game-theory]

Algorithmic game theory is an area in the intersection of game theory and algorithm design, whose objective is to design algorithms in strategic environments. (Def: http://en.m.wikipedia.org/wiki/Algorithmic_game_theory)

0
votes
1answer
17 views

Play Cards Game Tournament Algorithm

I am currently trying to find algorithm to minimize the total time of a tournament. The game requires $2$ teams of $2$ players in each team (total $4$ players). Then, the perfect number of ...
1
vote
0answers
12 views

End-of-the-Line (PPAD) complexity

The end-of-the-line problem (defining problem of the PPAD class) is defined on an up to exponentially large directed graph G with no isolated vertices, with each vertex having up to one predecessor ...
0
votes
1answer
30 views

Game theory problem - two towers

I'm asking that question because I still cannot figure out the solution after hours of thinking. You are given two towers where first has exactly n stones and second has exactly m stones. You are ...
0
votes
0answers
23 views

Playing a normal-form game against another player

Suppose we have the following game: Game and we need to play the game twice against another player who we do not know. First I have to play as the row player and then next as the column player ...
0
votes
0answers
29 views

How to solve this variation of nim that has division?

I ran into this problem, that consist of two stacks of coins each with different amount of coins, there are two players p1 and p2. p1 plays first and each take one turn. The turn consist of removing ...
18
votes
3answers
346 views

$3$ scorpions are chasing $1$ ant on the edges of a cube. The ant is $3$ times as fast than any scorpion. Can the ant survive?

The problem: Three scorpions are chasing a single ant on the edgegraph of a cube. The scorpions have the same speed ($v$), while the ant is $3$ times as fast ($3v$). They can move in any direction ...
1
vote
0answers
17 views

How to find potential function for any game?

I am studying Tim Roughgarden's lecture notes on algorithmic game theory. In chapter 13, he introduces the concept of potential function $$\Phi(f)=\sum_{e\in E}\sum_{i=1}^{f_e}c_e(i)$$ In the context ...
0
votes
0answers
20 views

Is the set of nash equilibria/correlated equilibria convex?

I am curious about the geometry of these sets (assuming compact, convex action space and concave utility function, so the nash must exist). Is there any general argument about when will any solution ...
0
votes
0answers
29 views

Why behavioral strategies and sequence form do not work with imperfect recall games?

The behavioural strategies assign, independently for each information set, a probability distribution over actions. The sequence form game is a game representation that, given a node W, a sequence q ...
0
votes
0answers
16 views

What is a Treeplex and how it can be used in the context of algorithmic game theory?

I would like to have some formal details on the treeplex structure, the idea behind it and how it can be useful.
0
votes
1answer
42 views

Altruistic rational agent

is there an agent in Game Theory (or even AGT), which goal is to minimizes other's costs? I've seen some agents that I would call "socialist", which goal is to minimize the sum, but including their ...
1
vote
1answer
44 views

is there a winning strategy, and if so what is it?

Player 1 and player 2 play a game which consists of a rectangular grid with 3 rows and 20 columns. During each players turn they can colour a square in the grid (either a 1 x 1, 2 x 2 or a 3 x 3 ...
0
votes
1answer
309 views

Nash equilibrium in second price sealed-bid auction

I'm trying to understand the basics of game theory and the topic of auctions has arisen. I understand the basic concepts of auctions but I'm struggling with second price sealed-bid auctions. I ...
0
votes
1answer
37 views

Objects moving on a plane

Object 1 starting at point (0,0) on the coordinate plane moves to right at 1 unit per second. Another object (object 2) starts at (x,y), moving half the distance to object 1 each second (following a ...
0
votes
0answers
37 views

proving if player 1 has a pure optimal strategy, player 2 should as well

Problem: Prove that if in a matrix game 2x2 if the player 1 has a pure optimal strategy, so has player 2 Attempt: Given: We know that player 1 has pure optimal strategy, meaning: $$P(x, \overline{...
0
votes
1answer
50 views

Prove it is impossible for every male to be paired with their last choice in the stable marriage algorithm (male proposing)

I'm trying to prove that it is impossible for every man to be paired with their last choice in the stable marriage algorithm. I have a general idea of how to approach it, which is: Suppose there ...
0
votes
0answers
64 views

calculation of probabilities in correlated equilibrium

I'm struggling to understand how to calculate the probability of each cell in a 3x3 matrics when trying to find the correlated equilibrium that maximizes the sum of players utilities?
0
votes
2answers
55 views

Pure Nash equililibrium

I’m really confused. I have the following game (zero sum). 1 2. 4 1. ...
-1
votes
1answer
136 views

Pure Nash equilibrium in Zero sum [closed]

Do zero sum games have a pure Nash equilibrium and if so how do I find the pure Nash equilibrium
2
votes
1answer
103 views

Finding the Bayes-Nash Equilibrium for First-Price Auction with 2 bidders

Let $\sigma_i$ be the strategy profile for bidder $i$ that indicates how they should bid based on their value. As we know, if there are 2 bidders both with their values $v_1,v_2$ on $U[0,1]$ in a ...
0
votes
0answers
74 views

Definition of Strong Nash equilibrium?

Let $(N,S,u)$ be a strategic form game, where i) $ N = \{ 1,2,3,... n \}$ is the set of players, ii) $S_i$ is the set of strategies for the $i^{th}$ player, and $ S = S_1 \times S_2 ... \times S_n$...
5
votes
0answers
71 views

Two players placing coins on a table- Extension

The origin of my question comes from a common job interview question where two players take turns placing coins on a round table. The coins cannot overlap and can't be moved once they've been placed. ...
1
vote
0answers
56 views

Nash equilibrium in antagonist game in a 2x5 matrix

Background Input matrix: $$ \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 4 & 3 & 2 \\ \end{bmatrix}$$ We have a game with 2 players. The game is antagonistic e.g ...
0
votes
1answer
99 views

Why is dominant strategy incentive compatibility (DSIC) named the way it is?

Dominant strategy incentive compatibility (DSIC) means truth-telling is the best policy, but why is DSIC named the way it is? My understanding is that the designer of the mechanism wants to ...
0
votes
1answer
61 views

Are there any examples of non-random games whose perfect-play outcome is proven but not solved?

My curiosity is inspired by the world-championship chess match of a couple days ago, when a supercomputer announced that mate-in-thirty-moves could be forced, but could not prove/explain it to humans ...
0
votes
1answer
98 views

Cournot duopoly market equation

What does '$a$' represent in this equation? I know what the rest means but cannot think what '$a$' represents? Consider a Cournot duopoly market with demand curve $𝑃 =a −𝑄$,where $𝑄 = 𝑞_1 +𝑞_2$...
0
votes
1answer
63 views

The complexity of finding pure Nash equilibrium in exact Potential games

Fabrikant., et al., in the paper "The complexity of pure Nash equilibria" (http://kunaltalwar.org/papers/purenash.pdf) show that finding a pure Nash equilibrium (PNE) in a Congestion game is a PLS-...
0
votes
1answer
39 views

What is the payoff function for games with more than two players?

For two player games, with payoff matrices $(A,B)$, let $x \in \Delta_x$ denote the mixed strategy of player $1$, and $y \in \Delta_y$ denote the mixed strategy of player $2$. Then the payoff ...
2
votes
1answer
129 views

How to win in this guessing game?

You and I play the following game: You write two distinct, real numbers on two different sheets of papers (in a way such that I cannot read the numbers). Then I flip one of these sheets, read the ...
1
vote
1answer
58 views

Algorithm for washing dishes

I am a math student and I would like to have your opinion about a problem I had in my life with my friends. We are a group of 7 friends, and we often eat together during the weekends. During the week ...
0
votes
0answers
114 views

Generalization of Captives Wearing Hats puzzle

I have been playing with the following puzzle on and off for a few years, but I haven't been able to address this particular generalization. Background This problem is somewhat involved, so it's ...
2
votes
1answer
124 views

Finding the Dictator in Arrow's Impossibility Theorem

Arrow's Impossibility Theorem states that if we have at least three different social states and a finite number of individuals (voters), any social welfare function that satisfies the conditions of ...
0
votes
1answer
165 views

Potential Game: Solving Prisoner's Dilemma

I am currently trying to get a hang of potential games. However I am struggeling with the Potential Functions. Especially I cant figure out how the Prisoners Dilemma Potentials are computed as it is ...
0
votes
0answers
31 views

Calculating inefficiency in second price auction with bribe

Following a previous related question of mine, regarding this paper on bribing in a second price auctions. I am interested in calculating the chance for inefficiency to occur (i.e. the chance that ...
1
vote
0answers
30 views

Is there a difference between preference order and preference relation and if yes, what?

While reading about utility theory (in context of Game theory) I came across two terms: preference order and preference relation. I am not clear about the distinction between them. Reference Link: ...
2
votes
0answers
89 views

Algorithm - Game item drop probability

My math knowledge is very limited but I came across a problem that requires some serious understanding of probabilities. That being said, I have a game which has a box and allows customizing the drop ...
0
votes
1answer
39 views

Playing game optimally

There are $n$ players in your team and for every player you know health and damage, say for $i$th player is $h_i$ and $dmg_i$. Given two types of spells: $1$: Doubles health of one player, i.e., $...
3
votes
2answers
81 views

What is the minimum number of questions to find the ring

There are 11 rings around a circle numbered from 1 to 11. We know that exactly 9 of them are fake and exactly 2 of them are real rings. In each step, we can choose 5 consecutive rings and ask the ...
2
votes
0answers
39 views

The relation between potential games and identical interest commutative utility functions

Assume a graphical game, where the utility of $i$-th player only depends on its neighboring players, i.e. $$ u_i(x_i,x_{-i})=u_i(x_i,x_{N(i,1)},...,x_{N(i,M_i)})$$ where: $N(i,j)$ denotes the $j$-th ...
0
votes
1answer
41 views

$\sum_{i=1}^n g(i) = \mathcal{O}(\sum_{i=1}^n h(i))$ imply that $g(n) = \mathcal{O}(h(n))$

Does $\sum_{i=1}^n g(i) = \mathcal{O}(\sum_{i=1}^n (h(i)))$ imply that $g(n)= \mathcal{O}(h(n))$ when $g,h : \mathbb{N} \to \mathbb{R+}$? I think this statement is wrong. Is the following a valid ...
1
vote
0answers
28 views

Non cooperative ,simultaneous 2*2 game- Is group of payments Convex?

I am given a 2*2 players infinite simultaneous game. I have some unresolved issues I'd like to discuss and confirm. Can the feasible payments group of player 1 when plays PURE strategy on his first ...
0
votes
1answer
84 views

How can I approximately solve a 2-player zero-sum game by subselecting its rows/columns?

This is rather an open-ended question, but I'm posting here since I was not able to find a good resource elsewhere. Say there's a two player zero sum game with payoff matrix $A$ that's $N \times H$. ...
3
votes
1answer
64 views

Two Player Strategy Game

I have recently been struggling on a problem involving a modified game of Nim. I have tried finding an invariant or monovariant, but to no avail. "In a game, Players X and Y take turns taking chips ...
2
votes
1answer
71 views

Who wins? From tokens marked $1$ to $N$, players alternate removing a token (marked $x$) and all tokens marked with divisors of $x$.

Two players play a game and the rules are as follows: $N$ wooden pieces (marked with numbers from $1$ to $N$) are placed in a bottle. A player takes out some piece, say "$x$", from the bottle, and ...
2
votes
2answers
94 views

Alice and Bob Multiplication Game

I am stucked in solving one problem. The problem is below. DESCRIPTION : Alice and Bob are playing a game. First, they define $N$($N$ is natural number), and a number '$x$'(initiated to 1) is given....
1
vote
0answers
37 views

Three dimensional pairing.

Like in stable roommate problem we pair roommates together according to their preferences. If the problem is changed such that the ideal partner of each student is room dependent i.e. for room 1 the ...
2
votes
0answers
78 views

Competitive square tiling game

Consider a game played on an $n$ * $n$ square grid. Player A (Alice) has 1*1 square tiles, while Player B (Bob) has 2*2 square tiles. On their turn, a player can place one of their tiles on the board, ...
1
vote
0answers
28 views

Optimal fluid maze creation

Consider a two player strategy game, played on an 9*9 square grid. Player A has one piece, which starts on the central square of the bottom side. Each turn, Player A moves his piece to an adjacent ...
1
vote
1answer
257 views

Fast Algorithm to Determine the Number of Nash Equilibria in a Bimatrix Game

Is there a "fast" algorithm or other methodology to determine the number of nash equilibria in a bimatrix game? I know of several algorithms to enumerate equilibria such as Lemke-Howson, but I'm only ...
1
vote
0answers
44 views

Any winning strategies or optimisations for this game?

So I'm writing a game and I'm supposed to implement optimal play from the computer's part, however I cannot find any strategies. The game: n*m board, in each turn a player selects a square and that ...