Questions tagged [game-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
57 votes
6 answers
5k 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 ...
TROLLHUNTER's user avatar
113 votes
54 answers
53k 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 ...
21 votes
4 answers
2k 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 ...
Richard Stanley's user avatar
20 votes
5 answers
802 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 ...
user avatar
12 votes
1 answer
356 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 ...
Richard Stanley's user avatar
7 votes
1 answer
549 views

Indeterminacy of long games

Hello, all, Several months ago I sat in on a seminar on AD+, which was incredibly wonderful even though I could barely follow it at all. AD+ is a technical variant of AD, the axiom of determinacy, ...
Noah Schweber's user avatar
74 votes
11 answers
26k 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 ...
Joel David Hamkins's user avatar
27 votes
1 answer
979 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 ...
Eric's user avatar
  • 2,601
24 votes
1 answer
1k views

Forcing and Family Contentions: Who wins the disputes?

The famous game-theoretic couple, Alice & Bob, live in the set-theoretic universe, $V$, a model of $ZFC$. Just like many other couples they sometimes argue over a statement, $\sigma$, expressible ...
Morteza Azad's user avatar
22 votes
5 answers
3k 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 ...
GM2001's user avatar
  • 223
20 votes
1 answer
1k 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 ...
Daniel Soltész's user avatar
19 votes
5 answers
1k views

When is a game tree the game tree of a board game?

This question arises from what I find interesting in the recently asked question What is a chess piece mathematically? My answer to that question was that mathematically, game pieces are in general ...
Joel David Hamkins's user avatar
18 votes
2 answers
3k views

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". http://www.math.ucsd.edu/~erdosproblems/erdos/...
user avatar
16 votes
2 answers
13k 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 ...
John Baez's user avatar
  • 21.3k
16 votes
1 answer
2k views

What does "game theory" cover and how should it be called?

There seems to be a huge discrepancy in what people refer to when they speak of "game theory". I tend to think of it as including, among other things: Combinatorial game theory dealing with certain ...
Gro-Tsen's user avatar
  • 29.9k
15 votes
4 answers
1k 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 ...
Irvan's user avatar
  • 215
13 votes
2 answers
1k 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 ...
Roland Bacher's user avatar
13 votes
3 answers
1k views

Cops, Robbers and Cardinals: The Infinite Manhunt

Cops & Robbers is a certain pursuit-evasion game between two players, Alice and Bob. Alice is in charge of the Justice Bureau, which controls one or more law enforcement officers, the cops. Bob ...
Morteza Azad's user avatar
11 votes
2 answers
685 views

Pursuit-Evasion type game on graph ("Flyswatter game")

An instance of the "flyswatter game" is defined by a graph $G$ and positive integer $k$. There are two players, A (the 'fly') and B (the 'swatter'). Essentially, the fly moves around $G$ and the ...
minderbinder8's user avatar
11 votes
5 answers
7k 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 ...
user7694's user avatar
  • 121
9 votes
2 answers
520 views

Does the optimal strategy converge in poker if the SPR tends to infinity?

This a a theoretical question about poker type games. I'm sure I don't have to explain the rules - you can consider No Limit Texas Hold'em or some simple theoretical model, where each player holds a ...
domotorp's user avatar
  • 18.3k
8 votes
4 answers
2k views

Pure Mathematical Applications of Advanced Game Theory?

Games appear in pure mathematics, for example, Ehrenfeucht–Fraïssé game (in mathematical logic) and Banach–Mazur game (in topology). But the Game Theory behind those applications is not so deep, and ...
I am not Paul Erdos's user avatar
8 votes
0 answers
151 views

Pursuit-evasion with many slow pursuers

Question: Suppose that intelligent pursuers with speed $v<1$ are randomly scattered on the plane with area density $1/r$  ($r>0$ is distance from the origin). If you start at the origin ...
Dmytro Taranovsky's user avatar
7 votes
1 answer
371 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 (...
bobuhito's user avatar
  • 1,537
5 votes
0 answers
287 views

Generalization of Sprague-Grundy Theorem

In my research on Combinatorial Game Theory, I used a certain theorem that is essentially a generalization of the Sprague-Grundy theorem. Because the result hinges too much on the work of others to be ...
Halbort's user avatar
  • 1,129
5 votes
1 answer
404 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 ...
joro's user avatar
  • 24.2k
4 votes
2 answers
375 views

Study of Hex on the Torus

Hex is usually played on a parallelogram shaped board. What if you play it on a Torus? One thing I notice is that the idea of connecting opposite sides doesn't make much sense anymore, since a torus ...
Christopher King's user avatar
3 votes
1 answer
272 views

Difficulty of 3-color forest Hackenbush

"Forest Hackenbush" (for lack of a better name) is the particular case of the game of Hackenbush where the initial position (and therefore all subsequent positions) is a (finite) forest (:= disjoint ...
Gro-Tsen's user avatar
  • 29.9k
3 votes
1 answer
460 views

If non-empty player has a winning strategy in Banach-Mazur game BM(X), then it also has in BM(Y)?

Let $f:X\rightarrow Y$ be a continuous, open, surjection function and second player (non-empty) has a winning strategy (not important which one, say for simplicity stationery st.) in $BM(X)$. Then can ...
user117537's user avatar
3 votes
1 answer
252 views

Is there a moving knife procedure for envy-free cake cutting with connected pieces?

In the wikipedia page on envy-free cake cutting, continuous "moving knife" algorithms for envy free cake cutting to connected pieces is only mentioned for up to 4 players. As the wikipedia article ...
edo arad's user avatar
  • 274
2 votes
2 answers
1k views

Generalized Sprague-Grundy Theorem

Hey, I know what is Sprague-Grundy theorem, but I want to know about generalized Sprague-Grundy (GSG) theorem ( which is used for games with cycles ). Apparently there seems to be very less ...
Pranav Raj's user avatar
1 vote
0 answers
358 views

What is known about multiplayer poker with flop?

I am interested in the following simplified version of poker. Each player gets a card (for example, either A or B). Then they bet knowing their own cards (for example, the pot initially has 1 euro, ...
domotorp's user avatar
  • 18.3k
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