# 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)

197 questions
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
0answers
37 views

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 ...
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 ...
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$. ...
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 ...
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 ...
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....
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 ...
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, ...
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 ...
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 ...
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 ...