# Questions tagged [game-theory]

The game-theory tag has no usage guidance.

251
questions

**1**

vote

**2**answers

65 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

**44**

votes

**2**answers

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

**5**

votes

**0**answers

111 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

**0**answers

148 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

123 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

464 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

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

**0**

votes

**0**answers

38 views

### The quadratic Markov game

Recently, I've asked about the linear Markov game: A "Markov game". It was solved by @JosephGordon (and I followed with a simplification). This time I'll ask about the quadratic Markov game. ...

**3**

votes

**2**answers

167 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

241 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

803 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

110 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

224 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

43 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

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

**9**

votes

**0**answers

183 views

### Can Alice ever fare the worst in this variant of the truel game?

In the well known classic three way duel puzzle, 3 players Alice, Bob and Carol take turns to shoot each other until only one survives. In his/her turn, a player can either choose to shoot or pass$^{1}...

**5**

votes

**1**answer

286 views

### Game on a square grid

Not research level, comments are welcome.
Consider the following game:
The board is the vertices of an $n$ by $n$ square grid.
Two players take moves in turns.
A move is picking two vertices and ...

**0**

votes

**1**answer

83 views

### Proving the existence of a symmetric Bayesian Nash equilibrium

I am currently faced with the following question:
Consider the public goods game. Suppose that there are $I > 2$ players and that
the public goods is supplied (with benefit of 1 for all players) ...

**27**

votes

**1**answer

833 views

### The lion and the zebras

The lion plays a deadly game against a group of $N$ zebras that takes place in the steppe (= an infinite plane). The lion starts in the origin with coordinates $(0,0)$, while the $N$ zebras may ...

**0**

votes

**2**answers

165 views

### Help with a definition of a two-person game in a referenced paper

In the paper "Finding Mixed Nash Equilibria of Generative Adversarial Networks" the authors write in equation (1) on page 2:
Consider the classical formulation of a two-player game with
finitely ...

**2**

votes

**1**answer

288 views

### When does $\min_x \max_yf(x,y) = \min_y \max_x f(x,y)$ hold for a real function $f(x,y)$?

Let $f(x,y)$ be a real function of the variables $x,y$ (which can be real vectors). Under what conditions do we have the following equality:
$$\min_x \max_yf(x,y) = \min_y \max_x f(x,y)$$
For ...

**2**

votes

**1**answer

83 views

### Dubious matrix monotonicity

Coming from a problem in game theory, I arose at some dubious monotonicity like property for matrices of the following art. Let $H=\lbrace h\in\mathbb{R}^{n}\colon h_{1}+\dots+h_{n}=0\rbrace$. I'm ...

**4**

votes

**1**answer

148 views

### Nash equilibria for “presidential election” game

Suppose, in a country there are $m$ different social issues, positions on which are being indexed with numbers $[-1; 1]$, with radicals on the opposing ends and moderates in the center. In this ...

**1**

vote

**0**answers

31 views

### Suggestions for two-choice game played in ladder graph

I was just working on counting all the possible Nash Equilibrium solutions for a two-choice game played on a ladder graph (I got my results and all that for a generic number of players).
And I was ...

**1**

vote

**0**answers

43 views

### Maschler's bargaining set-an incomplete step in a proof

I have a problem with the concept of the bargaining set which is given below in some detail.
Let $N=\{1,\ldots,n\}$ be a set of players and $v:2^N\to \mathbb{R}$
a superadditive game (meaning $S,T \...

**2**

votes

**1**answer

210 views

### Is following function a metric on the set of isomorphism classes of graphs with countably many vertices?

Suppose $\Gamma_1(V_1, E_1)$ and $\Gamma_2(V_2, E_2)$ are simple graphs with countably many vertices. And suppose $A_1$ and $A_2$ are initially empty sets. Suppose two players play the following game: ...

**1**

vote

**1**answer

69 views

### Perturbation of the value of a general-sum game at a equilibirium

Consider a general-sum game with $N$ players. Let $u_i(a_1, \ldots, a_N)\colon \prod_{i=1}^N A_i \rightarrow \mathbb{R} $ be the payoff of the player $i\in \{ 1, \ldots, N \}$ when each player takes ...

**0**

votes

**1**answer

153 views

### Prenucleolus vs. nucleolus

I want to find a cooperative, characteristic function TU game $v$ (of at best of 3 or 4 players;2 players seem impossible to me) for which the prenucleolus is different from the nucleolus.
I do not ...

**1**

vote

**1**answer

84 views

### Can backward induction be used to solve any game? [closed]

I'm new to game theory and I would like to know, if you can model any game through a payoff tree, couldn't you find the subgame perfect equillibrium for all games through backward induction?

**3**

votes

**1**answer

193 views

### Evasive maneuver game

First of all, I want to state that I'm not an expert in the game theory and searching the references for the game I just made up. Solving this game by itself seems like a decent project for strong ...

**2**

votes

**0**answers

65 views

### Extension of Standard English Peg Solitaire

An entire analysis of standard English Peg Solitaire has been given. See
Berlekamp, E. R.; Conway, J. H.; Guy, R. K. (2001) [1981], Winning Ways for your Mathematical Plays (paperback) (2nd ed.), A ...

**3**

votes

**0**answers

54 views

### Random Two-Player Asymmetric Game

About half a year ago I asked a question on MSE about a random two player game. At the time, the question received some attention and some progress was made, but was not resolved completely. I have ...

**3**

votes

**0**answers

112 views

### General way to find Nash equilibrium in continuous game

I'm really interesting how to find Nash equilibrium in a continuous game with two players in the general case.
Let's consider a game with continuous utility functions $F_1, F_2 : [0, 1] \times [0, 1]...

**8**

votes

**0**answers

117 views

### Pursuit-evasion with many slow pursuers

Question: Suppose that intelligent pursuers with speed $v<1$ are randomly scattered on the plane with area density $1/r$ ($r>0$ is distance from the origin). If you start at the origin ...

**2**

votes

**0**answers

148 views

### Reference Request: A Set-Valued Minimax Theorem?

Suppose that $\mathcal{C}$ and $\mathcal{D}$ are subsets of $L^2(X,\Sigma,\mu)\cap L^{\infty}(X,\Sigma,\mu)$, where $\mu$ is a finite-measure on $(X,\Sigma)$. Let $F:L^2(X,\Sigma,\mu)\times L^2(X,\...

**1**

vote

**0**answers

69 views

### What is the Bruss-Yor concept of no information?

A few years ago, a question related to a paper of Thomas Bruss and Marc Yor on the so-called last arrival problem received some attention on this forum.
What I'd like to know now is:
What are the ...

**56**

votes

**2**answers

3k views

### Guessing each other's coins

I recently thought about the following game (has it been considered before?).
Alice and Bob collaborate. Alice observes a sequence of independent unbiased random bits $(A_n)$, and then chooses an ...

**-1**

votes

**1**answer

88 views

### Round robin with 5 player game [closed]

Im trying to write some software for pairing players in card gaming tournaments, each player must play on a table with each other player exactly 1 time, currently there is going to be 25 players with ...

**2**

votes

**0**answers

199 views

### Combining a Nim-variation and Wyrthoff's game. How to find a winning strategy? [closed]

Wythoff's game is a variation of the classical Nim - There are two heaps and the players take turns either taking any amount from one heap, or the same amount of both heaps. The winner is the one ...

**3**

votes

**0**answers

139 views

### final coalgebra of the 𝓟${_{<κ}}$(A×X) endo-functor in $Set^*$?

In the paper Coalgebraic Games and Strategies F. Honsell, M. Lenisa, and R. Redamalla use the functor $F_A$(X) = ${\mathscr{P}_{<κ}}$(A×X) to define games coalgebraically. This is a functor from ...

**1**

vote

**1**answer

165 views

### A game theory problem mixed strategy over a continuous set

I have two players $A$ and $B$, the action of $A$ is $x_A\geq 0$ and the action of $B$ is $x_B\geq 0$. Let $c_0\in(0,1)$, $c_3>0$ and $c_2>c_1>0$ be constants. The payoff functions of $A$ and ...

**1**

vote

**0**answers

84 views

### Zero-sum games where getting information helps the opponent more

You may know of the paper on the "Memory" game - sometimes the best strategy is turning known cards (here: https://www.math.kth.se/xComb/x1.pdf). Here is a simpler toy example: You and your opponent ...

**3**

votes

**2**answers

142 views

### Satisfier-Falsifier games

In a Maker-Breaker game, there is a finite set of elements $X$, and a family $F$ of subsets of $X$ called the "winning sets". Two players, Maker and Breaker, take turns picking untaken elements from $...

**19**

votes

**3**answers

1k views

### What is the fairest order for stage-striking (and is it the Thue-Morse sequence)?

Here's a fair-sequencing problem that doesn't quite match the usual fair-division problems. I think that, like those, the answer should also be the Thue-Morse sequence ("balanced alternation"), ...

**3**

votes

**1**answer

77 views

### Optimal Strategies for a “Blind” Graph Coloring Game

By the "blind" graph coloring game I denote the following problem, which is played by two players:
player A has $k<n$ colors at hand to color the $n$ vertices of a graph $G$, but that ...

**2**

votes

**0**answers

103 views

### A community effort: equilibrium in quitting games [closed]

This thread is in the spirit of the polymath project:
a combined effort of the community to solve a difficult open problem.
It is an activity of the European Network for Game Theory
whose goal is to ...

**1**

vote

**1**answer

890 views

### Matrix tic tac toe

So we have a 3x3 matrix and two players, a player that only puts in ones and a player that only puts in zeros. A coin flip is used to decide which player goes first. The first move is always to fill ...

**1**

vote

**2**answers

88 views

### Strong Nash Equilibria in repeated games

Suppose we have a simultaneous game, that has a strong Nash equilibrium (SNA), i.e. a weak Pareto efficient Nash equilibrium (no deviation of any subset of player brings a benefit to them).
Now ...

**3**

votes

**0**answers

125 views

### Piece rank probability in this Stratego-like game

There's this game in a 9x8 board where 2 players take turns moving pieces. The players have pieces ranked 1-21. Players can't see the opponent's pieces' ranks, just positions. Pieces landing on the ...

**11**

votes

**0**answers

584 views

### Generalization of Penney's game (Penney's paradox)

The standard Penney's game is played by two players. Player $A$ chooses a sequence of $k>2$ bits and $B$ (seeing $A$'s selection) chooses a different sequence of $k$ bits. A fair coin is flipped ...