Questions tagged [game-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
2 answers
50 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 ...
Geoffrey Irving's user avatar
10 votes
0 answers
330 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 ...
Max Muller's user avatar
  • 4,435
8 votes
1 answer
332 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$...
Will Sawin's user avatar
  • 135k
0 votes
0 answers
118 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 ...
wjmccann's user avatar
  • 315
0 votes
2 answers
93 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 ...
Max's user avatar
  • 9
1 vote
1 answer
212 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 ...
Davis Yoshida's user avatar
9 votes
0 answers
355 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 ...
Veronica Phan's user avatar
2 votes
0 answers
123 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 ...
Mark Steere's user avatar
3 votes
2 answers
531 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 ...
Nick's user avatar
  • 31
0 votes
1 answer
70 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^...
Manfred Weis's user avatar
  • 12.6k
4 votes
0 answers
267 views

References and upper bounds for the SONNAT tiling game?

Introduction 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 ...
Max Muller's user avatar
  • 4,435
2 votes
2 answers
212 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 ...
Chris Gerig's user avatar
  • 17.1k
1 vote
0 answers
66 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. (...
DavideL's user avatar
  • 111
7 votes
1 answer
208 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 ...
Noah Schweber's user avatar
3 votes
0 answers
123 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 ...
Davis Yoshida's user avatar
3 votes
2 answers
138 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 ...
kehagiat's user avatar
1 vote
0 answers
37 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 ...
Vojtěch Kovařík's user avatar
2 votes
1 answer
190 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 ...
Hass Boyouk's user avatar
1 vote
0 answers
65 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 ...
wavosa's user avatar
  • 111
5 votes
2 answers
476 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, ...
Blanco's user avatar
  • 1,503
7 votes
2 answers
409 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 ...
richard jameson's user avatar
1 vote
0 answers
54 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 ...
User's user avatar
  • 208
3 votes
0 answers
72 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 ...
Wlod AA's user avatar
  • 4,686
7 votes
1 answer
564 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 ...
Wlod AA's user avatar
  • 4,686
3 votes
0 answers
148 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 ...
wcysai's user avatar
  • 31
3 votes
0 answers
134 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 ...
Eric's user avatar
  • 2,601
-3 votes
1 answer
311 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 ...
Martin Weidner's user avatar
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 ...
H.C Manu's user avatar
  • 733
2 votes
0 answers
70 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))...
Lviv Scottish Book's user avatar
1 vote
0 answers
97 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,...
Per Alexandersson's user avatar
0 votes
0 answers
110 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 $...
joro's user avatar
  • 24.2k
1 vote
2 answers
249 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 ...
Stacker Dragon's user avatar
3 votes
1 answer
269 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 ...
Hollis Williams's user avatar
-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 ...
binaryBigInt's user avatar
27 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 ...
Sin Nombre's user avatar
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 ...
Roland Bacher's user avatar
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. ...
Matt Hastings's user avatar
5 votes
1 answer
497 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 ...
magnus's user avatar
  • 59
6 votes
1 answer
323 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 ...
Will Sawin's user avatar
  • 135k
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$....
Eric's user avatar
  • 2,601
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 ...
Eric's user avatar
  • 2,601
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}&=\...
José María Grau Ribas's user avatar
20 votes
3 answers
677 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 ...
Eric's user avatar
  • 2,601
2 votes
1 answer
124 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 ...
Thomas's user avatar
  • 501
1 vote
2 answers
239 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 ...
Norman's user avatar
  • 125
1 vote
2 answers
121 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
Behrad Moniri's 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 ...
Eric's user avatar
  • 2,601
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&...
Pierre's user avatar
  • 171
3 votes
1 answer
292 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 ...
Turbo's user avatar
  • 13.6k
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 ...
Let101's user avatar
  • 83

1
2 3 4 5 6