Questions tagged [game-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
60 views

Determining the first move in go using CGT

I am exploring Combinatorial Game Theory (CGT) and particularly interested in Berlekamp's book "Mathematical Go Endgames". However I am a bit puzzled by the fact that, once he uses the ...
user avatar
2 votes
0 answers
93 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 ...
user avatar
  • 2,517
-3 votes
1 answer
244 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 ...
user avatar
8 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 ...
user avatar
  • 197
1 vote
0 answers
37 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))...
user avatar
1 vote
0 answers
57 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,...
user avatar
0 votes
0 answers
102 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 $...
user avatar
  • 23.3k
1 vote
2 answers
86 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 ...
user avatar
3 votes
1 answer
244 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 ...
user avatar
-1 votes
1 answer
84 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 ...
user avatar
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 ...
user avatar
8 votes
1 answer
201 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 ...
user avatar
4 votes
1 answer
810 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. ...
user avatar
5 votes
1 answer
386 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 ...
user avatar
  • 59
6 votes
1 answer
244 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 ...
user avatar
  • 114k
1 vote
1 answer
227 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$....
user avatar
  • 2,517
5 votes
2 answers
224 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 ...
user avatar
  • 2,517
2 votes
0 answers
106 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}&=\...
user avatar
18 votes
2 answers
554 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 ...
user avatar
  • 2,517
2 votes
1 answer
86 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 ...
user avatar
  • 429
1 vote
2 answers
97 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 ...
user avatar
  • 125
1 vote
2 answers
91 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
user avatar
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 ...
user avatar
  • 2,517
6 votes
1 answer
211 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&...
user avatar
  • 171
3 votes
1 answer
219 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 ...
user avatar
  • 12.8k
2 votes
0 answers
130 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 ...
user avatar
  • 83
7 votes
2 answers
860 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 ...
user avatar
  • 12.8k
1 vote
0 answers
113 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 ...
user avatar
  • 111
3 votes
2 answers
184 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\ $...
user avatar
  • 3,379
9 votes
1 answer
259 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 ...
user avatar
27 votes
1 answer
933 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 ...
user avatar
  • 531
6 votes
1 answer
119 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 ...
user avatar
1 vote
1 answer
230 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 ...
user avatar
  • 2,517
1 vote
2 answers
46 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_{...
user avatar
  • 279
1 vote
1 answer
87 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 ...
user avatar
  • 31
9 votes
0 answers
192 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}...
user avatar
  • 2,517
5 votes
1 answer
358 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 ...
user avatar
  • 23.3k
-1 votes
1 answer
143 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) ...
user avatar
27 votes
1 answer
901 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 ...
user avatar
  • 2,517
0 votes
2 answers
170 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 ...
user avatar
2 votes
1 answer
410 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 ...
user avatar
  • 825
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 ...
user avatar
  • 279
4 votes
1 answer
158 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 ...
user avatar
  • 2,598
1 vote
0 answers
37 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 ...
user avatar
1 vote
0 answers
45 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 \...
user avatar
2 votes
1 answer
214 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: ...
user avatar
  • 2,598
1 vote
1 answer
107 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 ...
user avatar
  • 1,095
0 votes
1 answer
212 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 ...
user avatar
1 vote
1 answer
172 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?
user avatar
3 votes
1 answer
208 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 ...
user avatar

1
2 3 4 5 6