Skip to main content

Questions tagged [game-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6 votes
2 answers
336 views

Mutual metric projection

Given a subset $S\subseteq \mathbb{R}^n$, the metric projection associated with $S$ is a function that maps each point $x\in \mathbb{R}^n$ to the set of nearest elements in $S$, that is $p_S(x) = \arg ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
95 views

Identifying player strategies in repeated games, based on payoffs

Background In evolutionary game theory, one can what kinds of different strategies yield the most payoff to players that play the same game repeatedly. Consider, for instance, the iterated Prisoner's ...
Max Muller's user avatar
  • 4,665
5 votes
0 answers
213 views

Can Gomoku(five in a row) draw on an infinite board? What about other m,n,k-games?

My question: how to prove or disprove the following two conjectures? Conjecture 1: (Gomoku large conjecture) there is no draw on infinite board for Gomoku with any initial opening with finite stones, ...
hzy's user avatar
  • 151
8 votes
0 answers
73 views

$2$-for-$2$ asymmetric Hex

This is a crosspost from Math stackexchange as I left the question open a while and bountied it but received no answers. If the game of Hex is played on an asymmetric board (where the hexes are ...
volcanrb's user avatar
  • 181
4 votes
1 answer
391 views

"Infinity": A card game based on prime factorization and a question

I have been developing a card game called "Infinity", which involves a unique play mechanic based on card interactions. In this game, each card displays a set of symbols, and players match ...
mathoverflowUser's user avatar
14 votes
3 answers
1k views

Examples of concrete games to apply Borel determinacy to

I'm teaching a course on various mathematical aspects of games, and I'd like to find some examples to illustrate Borel determinacy. Open or closed determinacy is easy to motivate because it proves ...
Gro-Tsen's user avatar
  • 30.8k
7 votes
2 answers
813 views

What are the Nash equilibria of the “aim for the middle” game?

Consider the following three-player game: Alice chooses an integer congruent to $0$ mod $3$, Bob chooses an integer congruent to $1$ mod $3$, and Chris chooses an integer congruent to $2$ mod $3$. (...
Gro-Tsen's user avatar
  • 30.8k
0 votes
0 answers
99 views

Are gaps and loopy games interchangeable in the Surreal Numbers?

The class of surreal numbers (commonly called $No$) is not complete: it contains gaps. Some people have studied the "Dedekind completion" of the surreal numbers in order to do limits and ...
Farran Khawaja's user avatar
2 votes
2 answers
54 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
11 votes
1 answer
451 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,665
8 votes
2 answers
463 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
  • 141k
0 votes
0 answers
150 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
96 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
266 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
368 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
126 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
570 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
73 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.8k
2 votes
2 answers
281 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.3k
1 vote
0 answers
95 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
216 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
134 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
181 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
41 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
191 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
66 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
492 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
418 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
58 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
  • 205
3 votes
0 answers
81 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,744
7 votes
1 answer
570 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,744
4 votes
0 answers
165 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
  • 41
3 votes
0 answers
137 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
313 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
  • 743
2 votes
0 answers
72 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
107 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
111 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.7k
1 vote
2 answers
269 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
272 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
143 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
28 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 ...
Sin Nombre's user avatar
8 votes
1 answer
227 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
535 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
330 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
  • 141k
1 vote
1 answer
281 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
287 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
122 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
684 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

1
2 3 4 5
7