The study of competitive and non-competitive games, equilibrium concepts such as Nash equilibrium, and related subjects. Combinatorial games such as Nim are under (combinatorial-game-theory), and algorithmic aspects (e.g. auctions) are under (algorithmic-game-theory).

learn more… | top users | synonyms

369
votes
24answers
50k views

Splitting a sandwich and not feeling deceived

This is a problem that has haunted me for more than a decade. Not all the time - but from time to time, and always on windy or rainy days, it suddenly reappears in my mind, stares at me for half an ...
52
votes
3answers
5k views

Mathematical research of Pokémon

In competitive Pokémon-play, two players pick a team of six Pokémon out of the 718 available. These are picked independently, that is, player $A$ is unaware of player $B$'s choice of Pokémon. Some ...
44
votes
8answers
11k views

Why do people lose in chess?

Zermelo's Theorem, when applied to chess, states: "either white can force a win, or black can force a win, or both sides can force at least a draw [1]" I do not get this. How can it be proven? ...
43
votes
0answers
1k views

Identification of a curious function

During computation of some Shapley values (details below), I encountered the following function: $$ f\left(\sum_{k \geq 0} 2^{-p_k}\right) = \sum_{k \geq 0} \frac{1}{(p_k+1)\binom{p_k}{k}}, $$ where ...
42
votes
2answers
2k views

A non-losing strategy for tic-tac-toe $\times$ tic-tac-toe

Consider a 9 by 9 matrix that consists of 9 block matrices of 3 by 3. Let each 3 by 3 block be a game of tic-tac-toe. For each game, label the 9 cells of the game from 1-9 with order from left to ...
32
votes
1answer
1k views

Is War necessarily finite?

War is an cardgame played by children and drunk college students which involves no strategic choices on either side. The outcome is determined by the dealing of the cards. These are the rules. A ...
27
votes
3answers
653 views

Three against the devil: a combinatorial game

A team of three sinners plays a game against the devil. They confer on strategy beforehand; then they go into three separate rooms, and there is no more communication between them. The play in each ...
23
votes
4answers
1k views

rock, paper, scissors, well

Everyone knows rock, paper, scissors. Now a long time ago, when I was a child, someone claimed to me that there was not only those three, but also as fourth option the well. The well wins against rock ...
22
votes
7answers
5k views

Game theory - self study

I want to self study game theory. Which math-related qualifications should I have? And can you recommend any books? Where do I have to begin?
19
votes
3answers
7k views

How is prisoner's dilemma different from chicken?

Chicken is a famous game where two people drive on a collision course straight towards each other. Whoever swerves is considered a 'chicken' and loses, but if nobody swerves, they will both crash. So ...
18
votes
1answer
1k views

Number of moves to solve a flood-it/sock-dye game

[ Question based on the sock dye game ] [ Update: It appears that this game is better known as "Flood it" and is NP-hard. Also, "the number of moves required to flood the whole board is $\Omega(n)$ ...
17
votes
3answers
550 views

Optimal strategy for the Rope Climbing Game

Define a two-player, turn-based climbing game as follows. Each turn, players have the option to climb or tie a knot at his current position. If the player chooses to climb, there is a 50% chance ...
17
votes
4answers
374 views

Salvaging a damaged cable

Let's say we have a cable of unit length, which is damaged at one unknown point, the location of which is uniformly distributed. You are allowed to cut the cable at any point, and after a cut, you'd ...
16
votes
4answers
408 views

A Category Theoretical view of the Kalman Filter

Some basic background The Kalman filter is a (linear) state estimation algorithm that presumes that there is some sort of uncertainty (optimally Gaussian) in the state observations of the dynamical ...
16
votes
1answer
252 views

A game played on a rectangle

Suppose two players play the following game on a $m$ by $n$ rectangle. Alternatingly they have to make a cross in some empty $1\times 1$ square. They are not allowed to make a cross next to another ...
16
votes
3answers
2k views

Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
15
votes
7answers
1k views

Game theory textbooks/lectures/etc

I looking for good books/lecture notes/etc to learn game theory. I do not fear the math, so I'm not looking for a "non-mathematical intro" or something like that. Any suggestions are welcome. Just put ...
14
votes
5answers
1k views

Probability of dice sum just greater than 100

Can someone please guide me to a way by which I can solve the following problem. There is a die and 2 players. Rolling stops as soon as some exceeds 100(not including 100 itself). Hence you have the ...
13
votes
5answers
1k views

A lady and a monster

A famous problem: a lady is in the center of the circular lake and a monster is on the boundary of the lake. The speed of the monster is $v_m$, and the speed of the swimming lady is $v_l$. The goal of ...
13
votes
1answer
233 views

Optimal strategy for Jackpot Rock Paper Scissors

Jackpot Rock Paper Scissors is a gambling variant of Rock Paper Scissors, wherein ties result in the wager being carried forward into a jackpot. If a player plays the same hand (rock, paper or ...
13
votes
3answers
2k views

The Best Strategy and Highest Possible Score for the “Threes!” Game.

[There's still the strategy to go. A suitably robust argument that establishes what is statistically the best strategy will be accepted.] Here's my description of the game: There's a $4\times 4$ ...
12
votes
3answers
575 views

Best Strategy for a die game

You are allowed to roll a die up to six times. Anytime you stop, you get the dollar amount of the face value of your last roll. Question: What is the best strategy? According to my calculation, for ...
12
votes
3answers
346 views

A number guessing game

Alice chose a positive integer $n$ and Bob tries to guess it. In every turn, Bob will guess an integer $x$ $(x>0)$: If $x$ equals $n$, then Alice tells Bob that he found it, and the game ends. ...
12
votes
3answers
553 views

Formula for picking time closest to (but after) target

Let's say you have an arbitrary length of time. You are playing a game in which you want to push a button during this time span after a light comes on. If you do so, you win ($+1$), if not, you lose ...
12
votes
0answers
188 views

The Right Triangle Game

I am looking for a deeper understanding, particularly the optimum strategy and the maximum score as a function of grid size, of the following (single-player) game played with an $n$ by $m$ grid: ($6 ...
11
votes
5answers
401 views

The Price is Right optimal play

The following situation happened on the Price is Right and I was curious about the optimal response. The rules are: A contestant rolls a wheel with 5 cent increments from 5 - 100 (20 numbers total). A ...
11
votes
1answer
282 views

Determining the number of valid TicTacToe board states in terms of board dimension

I am attempting to find a closed form equation in terms of $n$, for the number of valid Tic-Tac-Toe board states (ignoring symmetry), where the board has dimension $n \times n ,\; 0 \lt n,\;n \in \Bbb ...
11
votes
4answers
157 views

How do you create a nonlinear game that the player can always win?

I thought a lot about this question — and initially, I intended to ask this on gamedev.stackexchange.com — but due to its rather theoretical aspects, I think it might be more appropriate to address a ...
11
votes
2answers
133 views

Fastest way to get \$1 million of two different currencies in a video game

This question actually relates to a video game, I came across the scenario and I realized I had no idea how to go about solving something like this or even what branch of mathematics it falls under. ...
10
votes
5answers
1k views

What is the probability of getting yahtzee?

What is the probability of getting yahtzee using N dices with X sides in Y throws in a single round? Which side of the dice one gets yahtzee with doesn't matter (e.g. it doesn't matter if it is ones ...
10
votes
2answers
235 views

Optimal Strategy for Bar Dice

This game is played in bars in Wisconsin, USA, but I'm sure variations are played many places around the world. The game has practical value, since once mathematicians figure out the best strategy, ...
10
votes
1answer
138 views

What are the relevant properties of cardinal utility functions for defining a notion of expected utility for mixed strategies in games?

For (finite) normal form games we can develop everything for pure strategies by considering ordinal utility functions to capture only a players preferences over the pure strategy space of the game. ...
10
votes
2answers
251 views

Strategy for a game of breaking sticks

Two persons have 2 uniform sticks with equal length which can be cut at any point. Each person will cut the stick into $n$ parts ($n$ is an odd number). And each person's $n$ parts will be permuted ...
9
votes
3answers
672 views

Optimal Strategy for Rock Paper Scissors with different rewards

Imagine Rock Paper Scissors, but where winning with a different hand gives a different reward. If you win with Rock, you get \$9. Your opponent loses the \$9. If you win with Paper, you get \$3. ...
9
votes
5answers
276 views

How can the observed strategies* in this actual auction be explained?

This is a "real world" question. Recently I witnessed the separate auctions of about 30 houses. The place where I went uses the following rules. The following describes the procedure for the ...
9
votes
3answers
356 views

Is there experimental evidence that people ever play mixed Nash equilibrium in real games?

Have any studies been done that demonstrate people (not game theorists) actually using mixed Nash equilibrium as their strategy in a game?
9
votes
1answer
127 views

Can we qualitatively predict the strategy of the German and US teams in today's World Cup soccer match?

In today's World Cup soccer match between Germany and the US, both teams only need a draw to advance to the next round. There's been speculation about possible collusion, especially given the friendly ...
9
votes
2answers
512 views

Determine the winner of a tic tac toe board with a single matrix expression?

Assume a tic-tac-toe board's state is stored in a matrix. $$ S=\begin{bmatrix} -1 & 0 & 1 \\ 1 & -1 & 0 \\ 1 & 0 & -1 \\ \end{bmatrix} $$ Here, $X$ is mapped to $1$, $O$ is ...
8
votes
4answers
352 views

Probability question: optimal strategy

I am really confused about how to think about this question. It was presented as a challenge by a peer. Two people seek to kill a duck at a location $Y$ meters from their origin. They walk from ...
8
votes
3answers
140 views

Seemingly similar but different probability games

Burger King is currently running its "family food" game in which each piece can be modeled as a scratch off game where exactly one of three slots is a winner and you may only scratch one slot as your ...
8
votes
1answer
332 views

Common knowledge as a fixed point

I read on a wikipedia page that from the modal logic formalization CK can be formulated as a fixed point. If it also holds for the set theory formalization? If it does, where I can find about it? ...
8
votes
3answers
242 views

number choose game

Three people A,B,C attend the following game: from 0~100, the Host will come up a number with Uniform, but he doesn't tell them the number, the attendee will guess a number and the closes one will ...
8
votes
2answers
225 views

A modified NIM game

Let's play a game of NIM, but with a catch! We have exactly three piles of stones with sizes $a$, $b$ and $c$, all of which are different. We move in turns. In every move, we can select a pile and ...
8
votes
3answers
234 views

Markov Perfect Equilibrium with Incomplete Information

Since the pathbreaking paper Stochastic Games (1953) by Shapley, people have analyzed stochastic games and their deterministic counterpart, dynamic games, by examining Markov Perfect Equilibria, ...
8
votes
1answer
145 views

Feedback loop in real-time voting of TV show?

Today, a German TV casting show ("Unser Star Fur Baku") introduced a new "real-time" voting system that works as follows: 10 contestants take part in a song competition. Viewers can call in and vote ...
8
votes
1answer
225 views

Why is the best position for LCR not the last person?

For the uninitiated, LCR is a game in which each player starts with three "tokens" and rolls up to three dice (at most as many as tokens they have). Each die has three sides which indicate that ...
8
votes
0answers
465 views

Irreversible chess [closed]

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 ...
7
votes
5answers
5k views

Help: rules of a game whose details I don't remember!

In a probability course, a game was introduced which a logical approach won't yield a strategy for winning, but a probabilistic one will. My problem is that I don't remember the details (the rules of ...
7
votes
5answers
372 views

Good non-mathematician book on Game Theory

I'm looking for a good book on Game Theory. I run a software company and from the little I've heard about Game Theory, it seems interesting and potentially useful. I've looked on Amazon.com but ...
7
votes
2answers
321 views

You are Johnny Depp 2!

An extension of this question repeated below. A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins. ...