# Questions tagged [game-theory]

The game-theory tag has no usage guidance.

286
questions

0
votes

1
answer

77
views

### References and upper bounds for the SONNAT tiling game?

In a video released about a month ago, Pembesita describes a tiling game called SONNAT: Same Orientation Neighbour Not Allowed, Tiling.
In the single-player game, the player may employ two rhombi. The ...

0
votes

0
answers

52
views

### Games of providence

Suppose I have an open information deterministic game (one may think about nim, or a tic-tac-toe on some board, or whatever).
Let's modify actions taken by players.
Instead of just taking first turn, ...

2
votes

2
answers

97
views

### Continuity of Nash equilibrium for a family of games

The question may be too vague, but ultimately in search of various (counter)examples or theorems to exhibit the following:
Do continuous families $t\mapsto G_t$ of "games" (say each $G_t$ is ...

1
vote

0
answers

38
views

### Hodge-Helmholtz decomposition for 1-form of strategic game

This question is motivated by the attempt of decomposing (in a direct sum sense) a strategic game into components in the spirit of Hodge decomposition.
Preamble
Combinatorial setting
Candogan et al. (...

7
votes

1
answer

183
views

### How complicated are 3-player clopen determinacy facts?

Say that a clopen 3-player game is a well-founded tree $T\subseteq\omega^{<\omega}$; intuitively, starting with player $1$ and continuing cyclically, the players $1,2,3$ alternately play natural ...

3
votes

0
answers

82
views

### Poker with infinite stack size

In two-player No Limit Texas Hold 'Em (NLHE), the optimal strategy depends on the "effective stack size," that is maximum amount of money held by one of the players (in the sequel I'll just ...

3
votes

2
answers

65
views

### Existence of stationary Nash equilibrium of discounted stochastic game

$N$-player discounted stochastic games with finite state and action spaces possess a Nash equilibrium in stationary strategies. This has been proved by Fink (1964) and a closely related result by ...

1
vote

0
answers

32
views

### Nash Equilibria change linearly in (some) game parameters. Already known / follows from a more general result?

EDIT: The key thing that I am wondering about is the linearity of the P2 strategy, not the constancy of P1. (The latter is straightforward.)
Question: Is the following result already known? Or is it a ...

2
votes

1
answer

173
views

### Nash equilibrium at another level

This is a variant of the Nash equilibrium. Let's say that there are 3 prizes: A Ferrari, a diamond watch, and a new boat. There are 6 players. 3 players with a motive while 3 players with another ...

1
vote

0
answers

53
views

### Representation of an N player game with 2 strategies per player as a matrix and its properties

Is there any well-studied representation of a N player game with 2 strategies per player as a matrix?
Intuitively, I think that each strategy can be represented as a binary digit, and each strategy ...

5
votes

2
answers

404
views

### A variant of Conway's Game of Life: any cell with more than 3 live neighbours becomes a live cell and no live cell dies. How to make more cells live?

In Conway's Game of Life, we got an infinite board (two-dimensional orthogonal grid of squares).
Every cell in the board interacts with its eight neighbors, which are the cells that are horizontally, ...

7
votes

2
answers

393
views

### Chasing game on the Go board

In Go (Weiqi), two players take turns placing stones on the vacant points of a board. Once placed, stones can only be removed from the board if a stone or a group of stones are surrounded by their ...

1
vote

0
answers

32
views

### How is the notion of $G$-function related to that of the replicator equation?

Disclaimer: this question was initially asked in Mathematics Stack Exchange (here), but it remained unanswered there.
Background:
While studying "Evolutionary Game Theory, Natural Selection, and ...

3
votes

0
answers

61
views

### Projective plane finite game

This is a 2-person game.
Let $\ P\ $ be any arbitrary projective space (of any dimension $\ \ge2$ and any cardinality, etc., but typically, let it be a finite plane over a field). Let $\ S_0\subseteq ...

7
votes

1
answer

547
views

### JUSTICE & INJUSTICE — two 2-player finite games

There is a non-empty finite set $\ K,\ $ say, of plates. Initially, there are $\ p_0(k)\ $ stones on the $k$-th plate, where
$\ p_0(k)\in\mathbb Z_{_{\ge0}}\ $ for each $\ k\in K.$
So far, it is like ...

3
votes

0
answers

120
views

### Two-player item picking game

Two players $A$ and $B$ play this game: There are $n$ items, where the $i$th item is of value $a_i$ to player $A$ and is of value $b_i$ to player $B$. Two players take turns picking items, and each ...

2
votes

0
answers

120
views

### Can you escape from two lions in a closed arena?

You're at the center of a circular arena. A pair of lions are at the border, planning to catch you. One of them moves as fast as you, but the other moves slower than you. The three of you are confined ...

-3
votes

1
answer

288
views

### What is a good formalization of this classic math puzzle? [closed]

Here is a classic math olympiad problem (but this is NOT my question!): Each of the girls A and B tells the teacher a positive integer but neither of them knows the other's number. The teacher writes ...

9
votes

6
answers

1k
views

### Surprising applications of the theory of games?

I am currently studying the applications of games in quantum information theory and related fields and I am aware of its uses in places like model theory and set theory. So I was curious, what are ...

2
votes

0
answers

61
views

### Equilibrium for a game with mixed strategies on a compact ultrametric space

Let $(X,d)$ be a compact ultrametric space. Hartig and de Vink considered the following ultrametric on the set $P(X)$ of probability on $X$:
$$\hat d(\mu,\nu)=\inf\{r>0:\forall x\in X\;\;\mu(B_r(x))...

1
vote

0
answers

66
views

### Game with Turing machines

Introduction
The following game is quite nice: Alice has, in secret, constructed a polynomial $P \in \mathbb{Z}[x]$.
On day $n=1,2,3,...$, she secretly writes down $P(n)$ on a piece of paper.
Each day,...

0
votes

0
answers

106
views

### Game on a square grid (part II)

Related to this question, where there the solution was unexpected for us.
Let $n,m$ be positive integers, $n \le m \le n^2/2$.
The board is $n \times n$ square grid.
Phase 1:
Two players, $A,B$ make $...

1
vote

2
answers

154
views

### Do restricted Nim-like games have winning strategies?

Considering a Nim-like game to be:
There are three piles $A,B,C$, and the amount of their elements are $|A|=2, |B|=5, |C|=6$;
There are 2 players. Each time a player can either take $x (1\leq x \leq ...

3
votes

1
answer

252
views

### Game theory approach to Trans Europa

The other day I was playing a game called Trans Europa (or Trans America) which is quite graph theoretic in flavour. The game takes place on a triangular lattice graph with certain distinguished ...

-1
votes

1
answer

102
views

### Why do two potentials of a game only differ by a constant? [closed]

Can someone explain to me the proof on page 7/20 of the original paper about potential games (https://www.cs.tau.ac.il/~mansour/sem-game-02-03/monderer-potential-96.pdf)?
It is about why two ...

26
votes

7
answers

5k
views

### Why is game theory formulated in terms of equilibrium instead of winning strategies?

Game theory, on the outset, seems to invite the questions,
"what can I do to win" or "how do I beat my opponent?"
So many people who are not familiar with game theory look to game ...

8
votes

1
answer

215
views

### Name of a game : Remove two chips from a vertex or one chip from both ends of an edge

Consider a finite graph $\Gamma$ with a positive number $n_v\geq 0$ of chips stacked at each vertex $v$ of $\Gamma$. Two players play in turn with moves consisting either of removing two chips from a ...

4
votes

1
answer

863
views

### Who wins this two player game of making squares?

Two players take turns coloring edges on an $n$-by-$n$ grid. Both players use the same color. Every time a player surrounds a square of the grid, they mark that square with their name and go again. ...

5
votes

1
answer

424
views

### Can we determine the game-theoretically best first move by White in chess without solving chess?

In turn-based board games with high branching factor (such as chess) are there any arguments that could ascertain the ideal first move but not solve the entire game?
I am asking because solving chess ...

6
votes

1
answer

294
views

### Do random asymmetric games have more complicated strategies than random symmetric games?

Let $\Delta \subset \mathbb R^n$ be the locus of vectors whose entries are nonnegative and sum to $1$.
For $M$ an $n\times n$ matrix over $\mathbb R$, let $x_M \in \Delta$ be the vector $x$ that ...

1
vote

1
answer

263
views

### Is there an equilibrium for this non-zero-sum game?

The game $G(N,M)$ is played:
$N$ ($N\geq 2$) is the number of players, labeled $1$~$N$. In the beginning they have a pot with some chips in it. Players move alternatively in the order from $1$ to $N$....

5
votes

2
answers

231
views

### Is there a dominant strategy for this game?

Alice and Bob have $N_A$ and $N_B$ warriors under their command, numbered $1$~$N_A$ and $1$~$N_B$ respectively. Alice has $1$ fighting power at her disposal, and Bob has $b$ ($b\gt 0$). Before the ...

2
votes

0
answers

113
views

### Existence and uniqueness of solution of a nonlinear system

I need a proof of the following result to calculate a Nash equilibrium in the Showcase Showdown game.
For all $n>1$, the system of equations
$$\left\{
\begin{aligned}
(1+e^{x}(-1+x))^{n-2}&=\...

20
votes

3
answers

661
views

### Escaping from infinitely many pursuers

The fugitive is at the origin. They move at a speed of $1$. There's a guard at $(i,j)$ for all $i,j\in \mathbb{Z}$ except the origin. A guard's speed is $\frac{1}{100}$. The fugitive and the guards ...

2
votes

1
answer

107
views

### special case of the minimax theorem

The minimax theorem of von Neumann says that for any payoff matrix $A$, we have
\begin{equation}
\max_x \min_y x^T A y = \min_y \max_x x^T A y.
\end{equation}
In the above, $x$ and $y$ are probability ...

1
vote

2
answers

130
views

### Should mixed strategies in normal form games be interpreted as measurable functions or probability vectors?

I have recently been stuck trying to understand how game theorists extend a normal form game (matrix game) into a game with mixed strategies (so called mixed extension). I feel like I am missing ...

1
vote

2
answers

110
views

### Variant of Parthasarathy's minimax theorem

Does there exist a variant of Parthasarathy's minimax theorem [1] that relaxes the assumption that the spaces $X$ and $Y$ are $[0,1]$?
[1] https://en.wikipedia.org/wiki/Parthasarathy%27s_theorem

45
votes

2
answers

3k
views

### Can the fugitive escape?

A fugitive is surrounded by $N$ police officers, with the nearest one at distance $1$ away. The fugitive and the officers move alternatively.
In a fugitive move, the fugitive can travel no more than ...

6
votes

1
answer

218
views

### Ordering preference for two zero mean Gaussian outcomes

Let $X\sim \mathcal{N}(0,1)$ be a standard Gaussian random variable. If we let $f_a(x)\triangleq\mathbb{E}[\max\{aX,x\}]$ for $a,x >0$, how to prove that $$f_a(f_b(1))<f_b(f_a(1))~~\text{for }0&...

3
votes

1
answer

254
views

### Games and the right mathematical framework for GANs

Generative Adversarial Networks were introduced in http://papers.nips.cc/paper/5423-generative-adversarial-nets and has more than 20000 citations.
It is an important topic within deep learning.
Are ...

2
votes

0
answers

145
views

### Finding an optimal strategy for a combinatorial sequential game

We are given a set $\{p_1, p_2, \ldots, p_n\}$ of players and a set of $\{\ell_1, \ell_2, \ldots, \ell_n\}$ of locations, where $n\in\mathbb{N}$. Each location can be either free or occupied, and each ...

7
votes

2
answers

1k
views

### Mathematics of GANs (generative adversarial networks)

Generative Adversarial Networks were introduced in http://papers.nips.cc/paper/5423-generative-adversarial-nets and has more than 20000 citations.
The paper introduced key paradigm changes which ...

1
vote

0
answers

129
views

### Nim variant with minimum number of objects?

I'm wondering where I can find in the literature (if it exists) a discussion of a Nim variant where we impose the additional condition on Nim that we can remove only up to $c$ objects before the game ...

3
votes

2
answers

189
views

### A "Markov game"

I call games similar to the one I describe below to be Markov games. I am selecting just that one or rather a 1-parameter series of games. The open challenge is to find out which of the players $\ 0\ $...

9
votes

1
answer

275
views

### An averaging game on finite multisets of integers

The following procedure is a variant of one suggested by
Patrek Ragnarsson (age 10). Let $M$ be a finite multiset of
integers. A move consists of choosing two elements
$a\neq b$ of $M$ of the same ...

27
votes

1
answer

964
views

### Players alternate moving a $\{\swarrow,\uparrow,\rightarrow\}$ piece on a chessboard

Edit $4.$ $-$ Proposing to reopen the question (the related competition should be over by now).
Edit $3.$ $-$ I have just found out that the linked competition (see the "Edit $1$.") is still ...

6
votes

1
answer

125
views

### Does is it change an auction's incentives when causing the winner to pay more makes losers pay less?

Say there are three roommates moving into an apartment with three rooms. Two of the apartment's rooms are identical, but the third one is valued higher by all three parties (say it's bigger and has a ...

1
vote

1
answer

232
views

### Brinksmanship: how to achieve the best outcome by a single statement [closed]

This game is taken from Schelling's Game Theory: How to Make Decisions by R.V. Dodge, in which contenders practice brinksmanship to their own advantages. It goes as follows:
Anderson, Barnes, and ...

1
vote

2
answers

47
views

### Cyclic inequality for 2 dimensional simplex elements

Let $p=(p_{1},p_{2},p_{3})\in\Delta$, with $\Delta:=\lbrace p\in(0,1)^{3}\ |\ p_{1}+p_{2}+p_{3}=1 \rbrace$. I aim to prove (not knowing whether it is true though) that
\begin{equation}
p_{1}^{p_{3}-p_{...

1
vote

1
answer

110
views

### Conditions for optimal stationary strategies in MDPs

I have a specific Markov decision process (MDP) which is generated from a problem in another domain. What I would like to show is that under the limit of means criterion (no discounting) the optimal ...