# Tagged Questions

The game-theory tag has no wiki summary.

**65**

votes

**50**answers

18k views

### Which popular games are the most mathematical?

I consider a game to be mathematical if there is interesting mathematics (to a mathematician) involved in
the game's structure,
optimal strategies,
practical strategies,
analysis of the game ...

**48**

votes

**9**answers

7k 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 ...

**44**

votes

**5**answers

3k views

### Escape the zombie apocalypse

Consider zombies placed uniformly at random over $\mathbb{R}^2$ with asymptotic density $\mu$ zombies/area. You are placed at a random point and can move with speed $1$. Zombies move with speed $v\leq ...

**39**

votes

**5**answers

6k views

### Why was John Nash's 1950 Game Theory paper such a big deal?

I'm trying to understand why John Nash's 1950 2-page paper that was published in PNAS was such a big deal. Unless I'm mistaken, the 1928 paper by John von Neumann demonstrated that all n-player ...

**24**

votes

**6**answers

3k views

### I know that you know…

A bit unsure if the following vague question has enough mathematical content to be suitable upon here. In the case, please feel free to close it.
In several circumstances of competition, a particular ...

**22**

votes

**2**answers

1k views

### Five Front Battle

Two generals are fighting a five front battle. Each general has 1 unit of army, which he divides into five separate armies that he sends to the five fronts. If one general sends more army to a front ...

**21**

votes

**1**answer

616 views

### The density hex

Gale famously showed that the determinacy of n-player, n-dimensional Hex is equivalent to the Brouwer fixed point theorem in n dimensions.
We can (and Gale does) view this as saying that if you ...

**19**

votes

**5**answers

570 views

### $n$-in-a-row game on $\mathbb{R}^2$

For integers $n$ such that $\:3< n\:$,$\:$ what is known about the following 2-player game:
Player_1 and Player_2 take turn choosing points on $\mathbb{R}^2$ that were not previously chosen, with ...

**17**

votes

**1**answer

550 views

### A Ramsey avoidance game

Consider the following game: Given $K_n$ the complete graph on $n$ vertices, two players take turns coloring its edges. Initially no edges are colored. At his turn a player can color a prevoiusly not ...

**16**

votes

**2**answers

6k views

### Lowest Unique Bid

Each of n players simultaneously choose a positive integer, and one of the players who chose [the least number of [the numbers chosen the fewest times of [the numbers chosen at least once]]] is ...

**15**

votes

**3**answers

970 views

### Fairest way to choose gifts

Suppose that a parent brings home from a trip $2n$ gifts of roughly
equal value for his/her two children. The children get to choose one
at a time which gifts they want. What is the fairest way to do ...

**15**

votes

**1**answer

677 views

### Removing pawns - the game

Here is a simple game I've invented (if the idea is not fresh, then please let me know):
The game is played on a board.
The board has some (finite) number of lines drawn on it.
A pawn is placed on ...

**15**

votes

**6**answers

1k 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 ...

**15**

votes

**1**answer

599 views

### Paul Erdős: Determine or estimate the number of maximal triangle-free graphs on n vertices

Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
...

**15**

votes

**1**answer

462 views

### The Chow & Robbins game ≈ 0.79295350640: improvements could come from simple statistics, or from a continuous version of the game

This question seeks help with improving a numerical estimate of the value of the Chow and Robbins game. Much about this game is unknown, such as whether its value is rational, but there are two routes ...

**14**

votes

**5**answers

2k 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 ...

**14**

votes

**2**answers

2k views

### Simple proof of the existence of Nash equilibria for 2-person games?

Is there a nice elementary proof of the existence of Nash equilibria for 2-person games?
Here's the theorem I have in mind. Suppose $A$ and $B$ are $m \times n$ matrices of real numbers. Say a ...

**14**

votes

**0**answers

432 views

### The multiplication game on the free group

Fix $W\subseteq\mathbb F_2$ and consider the following two-person game: Player 1 and Player 2 simultaneously choose $x$ and $y$ in $\mathbb F_2$. The first player wins, say one dollar, iff $xy\in W$. ...

**13**

votes

**5**answers

1k views

### Finding the largest integer describable with a string of symbols of predefined length

(This question is motivated by the reading of the article Large numbers and unprovable theorems by Joel Spencer, which can be found at ...

**13**

votes

**4**answers

776 views

### Painting $n$ balls from $2n$ balls red, and guessing which ball is red, game

The game
Lucy has $2n$ distinct white colored balls numbered $1$ through $2n$. Lucy picks $n$ different balls in any way Lucy likes, and paint them red. Lucy then giftwrap all the balls so that it is ...

**13**

votes

**1**answer

326 views

### Stromquist's 3 knives procedure

(copied from math.SE)
BACKGROUND: A cake has to be divided among 3 people with possibly different tastes, such that each person receives a single connected piece, and no person prefers another ...

**12**

votes

**6**answers

1k views

### Untrustworthy people picking a random number

Inspired by the party game Mafia, in particular those situations where nobody is clearly innocent or guilty and the group wants to decide on someone random to eliminate.
Suppose n people each have ...

**12**

votes

**2**answers

702 views

### An unfair game involving an odd number of pieces of chocolate

Two greedy chocolate eaters play the following game involving $n$ pieces of chocolate
and an additional parameter $\alpha$ with initial value $1$: Each player eats either $\alpha$
pieces of chocolate ...

**11**

votes

**5**answers

3k views

### Guess a number with at most one wrong answer

Consider a game where one player picks an integer number between 1 and 1000 and
other has to guess it asking yes/no questions.
If the second player always gives correct answers than it's clear that ...

**11**

votes

**1**answer

709 views

### The Worst Possible Winner

First a little background. In racing it is possible for a player to win a tournament without winning a single race, however, how bad can a tournament winner actually be? Can a player win a tournament ...

**10**

votes

**12**answers

4k views

### Are there any interesting connections between Game Theory and Algebraic Topology?

I've been learning game theory on my own and was just curious how it connected with previous things I've learned. So are there any interesting connections between Game Theory and Algebraic Topology? ...

**10**

votes

**9**answers

2k views

### 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 best ...

**10**

votes

**2**answers

492 views

### Is quantum game theory reducible to classical game theory?

Quantum game theory is an extension of classical game theory to the quantum domain. It differs from classical game theory in three primary ways:
Superposed initial states,
Quantum ...

**10**

votes

**3**answers

252 views

### Limiting probabilities for two-player game drawing random uniform numbers

Consider this simple 2-person game I just made up:
Player A goes gets to draw a uniform U[0,1] number up to X times. At any time, he may either keep his number, or draw a brand new uniform number. ...

**10**

votes

**2**answers

853 views

### Is there an equivalent of Heisenberg's uncertainty principle in the decision sciences ?

From memories of a quantum mechanics class and Wikipedia:
In quantum mechanics, the uncertainty principle is any of a variety of mathematical inequalities asserting a fundamental limit to the ...

**10**

votes

**1**answer

265 views

### Game on the tree [closed]

There's a problem from programming competition which already finished:
http://codeforces.com/contest/458/problem/F
Two weeks already passed but still nobody solved it yet - in fact you can see here ...

**9**

votes

**3**answers

851 views

### Nim game for odd number of stones

Consider the classical Nim game with total number of stones being odd. Then the first players wins, of course, what follows from the general description of winning positions. But is there some shorter ...

**9**

votes

**3**answers

438 views

### Representing a real number as the value of a countably infinite game

Is it true that for any real number $p$ between 0 and 1, there exist finite or infinite sequences $x_m$ and $y_n$ of positive real numbers, and a finite or infinite matrix of numbers $\varphi_{mn}$ ...

**9**

votes

**2**answers

992 views

### The duel problem

The following duel problem is due to Ben Polak (maybe there's earlier origin, which I'll be glad to be informed about). The rule is as follows:
Two players 1 and 2 start a duel $N$ steps away from ...

**9**

votes

**1**answer

416 views

### M-matrix plus S-matrix is P-matrix?

I am trying to prove that a mapping has a unique fixed-point by showing that its Jacobian is a P-matrix. In this particular case the Jacobian can be decomposed as the sum of two matrices and I would ...

**9**

votes

**1**answer

273 views

### Guessing the larger integer: A game-theoretic twist

The starting point for this question is the old chestnut, already discussed on MO, about a game show on which the host has chosen two distinct integers and the contestant gets to reveal one of them at ...

**8**

votes

**3**answers

951 views

### Weighted Regular Graphs

The following graph theoretic notion appeared in an economics paper entitled: "Prize competition under limited comparability, by Michele Piccione and Ran Spiegler which studies models of economics ...

**8**

votes

**2**answers

388 views

### A competitive root finding game

Inspired by a question about bisection I wondered about the following: The are two players X and Y and a moderator Z who knows two (random,independent, uniformly chosen) hidden reals $x$ and $y$ from ...

**8**

votes

**0**answers

2k views

### Group Theory, Game Theory, a bit of Philosophy and a post in Tao's blog

I've decided to write this post after reading the incredibly beautiful and highly recomended post by Terence Tao ...

**7**

votes

**4**answers

1k views

### Infinite games: are they well defined?

It is just my curiosity about this question where we have an infinite game and (according to the answers) winning strategies for both players. I am familiar with terminating games only, and I am ...

**7**

votes

**3**answers

247 views

### Can we efficiently compute a third Nash Equilibrium, given two?

A finite, two-player, nondegenerate, symmetric game is defined by a nondegenerate $n \times n$ payoff matrix $A$. If player 1 plays strategy $i$ and player 2 plays strategy $j$, then player 1's ...

**7**

votes

**1**answer

220 views

### Optimum Tournament Strategy

Consider a symmetric N-player game in which all players partition one total unit of
energy among individual games. The probability of winning each game is simply proportional to the spent energy ...

**7**

votes

**2**answers

183 views

### Are sums of 0-1 Pareto efficient vectors Pareto efficient?

Does there exist $m,n\ge1$, an $m \times n$ matrix $A$, and a vector $x \in \mathbb{R}^n$ such that:
The entries of $A$ are $\in \{0, 1\}$.
For all pairs of columns $u, v$ of $A$ the entries of $u - ...

**6**

votes

**1**answer

501 views

### Determinantal formula for the nullspace of a singular matrix

In June 2012, Bill Press and Freeman Dyson published a remarkable paper on the iterated prisoner's dilemma. A key step in their derivation is a simple fact from linear algebra that I feel I should ...

**6**

votes

**1**answer

322 views

### Explicit examples of undetermined games

Suppose we have a game between two players in which they take alternating turns. The game can have finite length, length $\omega$ or any transfinite number of steps (however, I'm not concerning games ...

**6**

votes

**1**answer

412 views

### Cake-cutting and amenable groups

I recently heard Alan Taylor speak about envy-free fair division and started wondering if questions like these make sense if we replace finitely additive measures with invariant means on amenable ...

**6**

votes

**1**answer

755 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 ...

**6**

votes

**2**answers

252 views

### Truthful multi-unit auctions that guarantee selling all items

Suppose an auctioneer has $k$ units for sale. There are $n$ bidders, each of whom are interested in a single good, and have value $v_i$ for it. If bidder $i$ has to pay $p_i$ and gets the good, he ...

**5**

votes

**2**answers

512 views

### Gandhi's quote formalized [closed]

Hello,
I hope this question is appropriate for Mathoverflow. Gandhi said, "Be the change that you wish to see in the world". I don't understand anything in Game/optimization theory (I don't know ...

**5**

votes

**1**answer

511 views

### Decay of Relative Growth in Conway's Game of Life

Intro
The question is about Game of Life.
Let us denote the set of points obtained from initial configuration $A$ after $m$ steps as $A(m)$ (we are only interested in finite initial configuration, ...