# Questions tagged [game-theory]

The game-theory tag has no usage guidance.

302
questions

6
votes

2
answers

336
views

### Mutual metric projection

Given a subset $S\subseteq \mathbb{R}^n$, the metric projection associated with $S$ is a function that maps each point $x\in \mathbb{R}^n$ to the set of nearest elements in $S$, that is $p_S(x) = \arg ...

1
vote

1
answer

95
views

### Identifying player strategies in repeated games, based on payoffs

Background
In evolutionary game theory, one can what kinds of different strategies yield the most payoff to players that play the same game repeatedly. Consider, for instance, the iterated Prisoner's ...

5
votes

0
answers

213
views

### Can Gomoku(five in a row) draw on an infinite board? What about other m,n,k-games?

My question: how to prove or disprove the following two conjectures?
Conjecture 1: (Gomoku large conjecture) there is no draw on infinite board for Gomoku with any initial opening with finite stones, ...

8
votes

0
answers

73
views

### $2$-for-$2$ asymmetric Hex

This is a crosspost from Math stackexchange as I left the question open a while and bountied it but received no answers.
If the game of Hex is played on an asymmetric board (where the hexes are ...

4
votes

1
answer

391
views

### "Infinity": A card game based on prime factorization and a question

I have been developing a card game called "Infinity", which involves a unique play mechanic based on card interactions. In this game, each card displays a set of symbols, and players match ...

14
votes

3
answers

1k
views

### Examples of concrete games to apply Borel determinacy to

I'm teaching a course on various mathematical aspects of games, and I'd like to find some examples to illustrate Borel determinacy. Open or closed determinacy is easy to motivate because it proves ...

7
votes

2
answers

813
views

### What are the Nash equilibria of the “aim for the middle” game?

Consider the following three-player game: Alice chooses an integer congruent to $0$ mod $3$, Bob chooses an integer congruent to $1$ mod $3$, and Chris chooses an integer congruent to $2$ mod $3$. (...

0
votes

0
answers

99
views

### Are gaps and loopy games interchangeable in the Surreal Numbers?

The class of surreal numbers (commonly called $No$) is not complete: it contains gaps. Some people have studied the "Dedekind completion" of the surreal numbers in order to do limits and ...

2
votes

2
answers

54
views

### Convergence of naive iteration for a stateful, iterated tabular game

Summary: Consider a stateful, two-player zero-sum game: at each state, two players pick moves simultaneously, and the reward and next state depends on those moves. We can attempt to solve such a game ...

11
votes

1
answer

451
views

### Examples of games developed purposely to analyze players' strategies for mathematics research

Background
This question is about games that were created, developed, deployed and popularized1 by researchers because they wanted to learn more about some mathematical structure, and did so by ...

8
votes

2
answers

463
views

### Optimally betting a beta-biased coin

This question is inspired by How to optimally bet on a biased coin? by Nate River but generalized slightly. I decided the generalization might be interesting enough to be its own question.
A number $p$...

0
votes

0
answers

150
views

### Optimal strategy of modified Mastermind game

The following game is a modified version of the popular game Mastermind described here in which you are only given information about the total correct guesses you have made, and nothing about how many ...

0
votes

2
answers

96
views

### Points based partial ranking

I want to rank a population $P=\{P_1,\ldots,P_n\}$. I am given a set $R=\{R_1,\ldots,R_k\}$ of partial rankings. The partial rankings may have varying sizes (e.g. the first ranking ranks only 8 ...

1
vote

1
answer

266
views

### How to show that maximizing "chip EV" is the equilibrium strategy in winner-take-all poker

This question is based on poker, but you don't need to know anything about poker to analyze it.
A while ago I asked over on math.SE how to prove that the probability of winning a head up poker match ...

9
votes

0
answers

368
views

### For which set $A$, Alice has a winning strategy?

Cross-posted from MSE: https://math.stackexchange.com/questions/4775193/for-which-set-a-alice-has-a-winning-strategy
Alice and Bob are playing a game. They take an integer $n>1$, and partition the ...

2
votes

0
answers

126
views

### Go variant: cyclic or not?

I would like to know if a cycle of moves is possible in the Go variant, Savage Go. That is, you capture my stones, I capture your stones, you capture my stones... The game never ends. A position is ...

3
votes

2
answers

570
views

### Negative of combinatorial game

I am having problem understanding what negative of a combinatorial game $G$ exactly means in combinatorial game theory. Does it mean that if I have normal game, if I create inverse, i.e., $-G = \{-G^R ...

0
votes

1
answer

73
views

### Optimality of a "shopping" heuristic

Suppose the following situation: we have to buy $n$ goods $g_1,\,\dots,\,g_n$ starting at day 1 and we can't buy more than one good per day.
On day $d$ the prices are $p_1^d,\,\dots,\,p_n^d;\quad p_i^...

2
votes

2
answers

281
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

95
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

216
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

134
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

181
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

41
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

191
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

66
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

492
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

418
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

58
views

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

Background:
While studying "Evolutionary Game Theory, Natural Selection, and Darwinian Dynamics", I am pretty confused about the notion of G-function (fitness-generating function), that is ...

3
votes

0
answers

81
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

570
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 ...

4
votes

0
answers

165
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 ...

3
votes

0
answers

137
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

313
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

2k
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

72
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

107
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

111
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

269
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

272
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

143
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 ...

28
votes

7
answers

6k
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

227
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

1k
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

535
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

330
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

281
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

287
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

122
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

684
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 ...