Questions tagged [game-theory]
The game-theory tag has no usage guidance.
295
questions
27
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 ...
3
votes
1
answer
270
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
140
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 ...
8
votes
1
answer
222
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. ...
24
votes
9
answers
25k
views
Looking for a mathematically rigorous introduction to game theory
I am looking for the best book that contains a mathematically rigorous introduction to game theory.
I am a group theorist who has taken a recent interest in game theory, but I'm not sure of the ...
5
votes
1
answer
501
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
231
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&...
-1
votes
1
answer
319
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) ...
1
vote
1
answer
273
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
261
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
120
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}&=\...
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 ...
1
vote
1
answer
277
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 ...
2
votes
1
answer
128
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
240
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
122
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
86
votes
27
answers
19k
views
Which popular games have been studied mathematically?
I'm planning out some research projects I could do with undergraduates, and it struck me that problems analyzing games might be appropriate. As an abstract homotopy theorist, I have no experience with ...
15
votes
0
answers
523
views
Identification of a curious function
The following question was asked on MSE but there were no replies.
During computation of some Shapley values (details below), I encountered the following function:
$$
f\left(\sum_{k \geq 0} 2^{-p_k}\...
27
votes
1
answer
1k
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 ...
22
votes
5
answers
3k
views
Irreversible chess
Suppose we play a chess-variant, where any finite number of pieces are allowed, and the board is as large as we wish, but only two kings in total. And there is no 50 move-rule, no castling and no ...
2
votes
0
answers
161
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 ...
16
votes
5
answers
4k
views
Is a fair lottery possible?
I'm trying to come up with a scheme for a lottery where each individual has roughly the same chance of becoming the winner, regardless of the number of tickets one holds. So no individual should have ...
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
133
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
493
views
How to prove that $a + b + 4 \sqrt{1 + a^{2} + b^{2}} \leq 4 \sqrt{a^{2} + b^{2}} + \sqrt{1+b^{2}} + \sqrt{1+a^{2}} + 2 $ for all $a, b > 0$?
I'd like to prove the following:
$$ a + b + 4 \sqrt{1 + a^{2} + b^{2}} \leq 4 \sqrt{a^{2} + b^{2}} +
\sqrt{1+b^{2}} + \sqrt{1+a^{2}} + 2 $$
for all $a, b \in \mathbb{R}_{>0}$.
Question: is ...
3
votes
2
answers
200
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\ $...
8
votes
2
answers
372
views
A game of singletons
Alice and Bob play the following zero-sum game, parametrized by two integers $m$ and $k$:
Alice picks $m$ sets, each of which has $k$ items.
Bob colors some items in green.
Bob's score is the number ...
12
votes
1
answer
356
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 ...
7
votes
2
answers
965
views
Drawing lines and removing squares - an Alice and Bob game
Thought about the following while in a Complex Analysis lecture:
Let there be a $N \times N$ grid of squares and two players $A$ and $B$. First, $A$ needs to draw a line $l$ that needs to intersect ...
4
votes
1
answer
180
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
1
answer
140
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 ...
6
votes
1
answer
132
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 ...
15
votes
4
answers
803
views
Fair cake-cutting between groups
The cake-cutting game is usually played between individuals. What if we try to play it between groups?
A certain land has to be divided between two states. There are $n$ citizens in each state. ...
1
vote
1
answer
235
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
48
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_{...
9
votes
0
answers
218
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
404
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 ...
2
votes
1
answer
605
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 ...
27
votes
1
answer
979
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
172
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
86
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 ...
1
vote
0
answers
40
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
49
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 \...
3
votes
1
answer
230
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: ...
74
votes
11
answers
26k
views
Does War have infinite expected length?
My question concerns the (completely deterministic) card game known as War, played by seven-year-olds everywhere, such as my son Horatio, and sometimes also by others, such as their fathers.
The ...
1
vote
1
answer
153
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
371
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
495
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
229
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 ...