Questions tagged [game-theory]
The game-theory tag has no usage guidance.
33
questions
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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/...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 $...