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 ...
- 3,939
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, ...
- 3,875
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 ...
- 16.4k
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. (...
- 111
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 ...
- 19k
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 ...
- 141
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 ...
- 33
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 ...
- 41
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 ...
- 111
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, ...
- 1,493
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 ...
- 213
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 ...
- 4,315
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 ...
- 4,315
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 ...
- 31
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 ...
- 2,567
-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 ...
- 525
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))...
- 4,183
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,...
- 15.3k
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 $...
- 23.8k
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 ...
- 4,736
-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 ...
- 101
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 ...
- 459
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 ...
- 15.9k
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. ...
- 527
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 ...
- 59
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 ...
- 126k
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$....
- 2,567
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,567
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,567
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 ...
- 491
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 ...
- 125
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
- 119
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 ...
- 2,567
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&...
- 171
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 ...
- 13.2k
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 ...
- 83
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 ...
- 13.2k
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 ...
- 111
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\ $...
- 4,315
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 ...
- 46.8k
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 ...
- 591
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 ...
- 61
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 ...
- 2,567
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_{...
- 289
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 ...
- 31