The tag has no wiki summary.

learn more… | top users | synonyms

190
votes
9answers
16k views

John Nash's Mathematical Legacy

It would seem that John Nash and his wife Alicia died tragically in a car accident on May 23, 2015 (reference). My condolences to his family and friends. Maybe this is an appropriate time to ask a ...
70
votes
52answers
21k 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 ...
49
votes
9answers
8k 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
5answers
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 ...
41
votes
5answers
9k 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
6answers
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 ...
23
votes
2answers
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
1answer
627 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
5answers
587 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
1answer
620 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
1answer
756 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 ...
16
votes
6answers
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 ...
16
votes
1answer
731 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". ...
16
votes
2answers
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
3answers
1k 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
4answers
531 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. ...
15
votes
2answers
3k 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 ...
15
votes
1answer
525 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
5answers
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
0answers
445 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
7answers
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
4answers
886 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
1answer
373 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
6answers
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
2answers
743 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
5answers
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
1answer
727 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
12answers
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
9answers
3k 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
2answers
624 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
3answers
960 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 ...
10
votes
3answers
275 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
2answers
1k 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
1answer
282 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
3answers
448 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
2answers
1k 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
1answer
489 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
1answer
310 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
3answers
981 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
2answers
401 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
0answers
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
4answers
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
3answers
274 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
1answer
223 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
1answer
104 views

Optimal strategy for game of 'online sorting' into a poset

Consider a single-player game played with an arbitrary finite poset, and a random number generator with a known distribution: Each turn, the RNG produces a number, and the player must assign that ...
7
votes
1answer
441 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 ...
7
votes
2answers
193 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
1answer
615 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
1answer
411 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
1answer
772 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 ...