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

331
votes
23answers
47k 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 ...
40
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 ...
30
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 ...
30
votes
0answers
612 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 ...
26
votes
3answers
583 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 ...
22
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 ...
21
votes
7answers
4k 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
6k 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
4answers
368 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
354 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
241 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 ...
15
votes
7answers
969 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 ...
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
4answers
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
1answer
1k 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 ...
12
votes
3answers
545 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
330 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
540 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 ...
11
votes
1answer
219 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
2answers
125 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. ...
11
votes
0answers
95 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
1answer
601 views
+100

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

[There's still the strategy to go . . . ] Here's my description of the game: There's a $4\times 4$ grid with some random, numbered cards on. The numbers are either one, two, or multiples of three. ...
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
245 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
5answers
267 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
339 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
2answers
385 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 ...
9
votes
2answers
185 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, ...
9
votes
1answer
126 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. ...
8
votes
4answers
330 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
133 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
329 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
207 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
181 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
1answer
141 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
0answers
369 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
344 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
176 views

What is the name of a game that cannot be won until it is over?

Consider the following game: The game is to keep a friend's secret. If you ever tell the secret, you lose. As long as you don't you are winning. Clearly, it's a game that takes a lifetime to win. ...
7
votes
2answers
2k views

Difference between Minimax theorem and Nash Equilibrium existence

Von Neumann's Minimax theorem (quoted from Wikipedia): For every two-person, zero-sum game with finite strategies, there exists a value V and a mixed strategy for each player, such that (a) Given ...
7
votes
1answer
250 views

Determinant game - winning strategy

I came across this problem while looking at Putnam problems a while ago: "Alan and Barbara play a game in which they take turns filling entries of an initially empty 2008 x 2008 array. Alan plays ...
7
votes
2answers
305 views

Alternative strategies for the game of number guessing

I took the following game from the Peter Winkler collection (chapter "Games"): Two numbers are chosen independently at random from the uniform distribution on [0,1]. Player A then looks at the ...
7
votes
2answers
208 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, ...
7
votes
1answer
134 views

Two people are looking for each other. Is it faster for both to actively search, or for one to search while the other stays still?

Choose among two actors randomly and place the chosen actor at the origin. Place the other actor in the unit circle uniformly at random. Both actors move at the same speed. Both actors are said to ...
7
votes
2answers
242 views

Finding the payoff matrix of a game

A two player zero-sum game can be represented by a $m\times n$ payoff matrix $M$ having $m$ rows and $n$ columns with values in $[0,1]$. The value $M(x,y)$ represent the payoff given to player $1$ ...
7
votes
1answer
186 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 ...
7
votes
1answer
291 views

Optimal strategy for slice weighing game

I watched an interesting contest on a Swedish game show the other night. I have tried to find an english name of the contest but haven't found any. Two contestants were each given one large sausage ...
7
votes
0answers
134 views

Is there a totally asymmetric 2P $0$-sum game with all payoffs $\pm1$, with a unique Nash eq. which assigns positive probability to each strategy?

Is there a totally asymmetric 2-player zero-sum game with all payoffs $\pm1$, with a unique Nash equilibrium which assigns positive probability to each strategy? By totally asymmetric, I mean that ...
6
votes
3answers
325 views

Game theory games with very counter-intuitive results?

I have heard of an interesting game that produces a very counter-intuitive result. It is an auction of a 100 dollar bill, but one in which both the first person in the auction and the second need to ...
6
votes
2answers
97 views

Does there exist a finite fair gamble game with one dishonest coin?

I am thinking, maybe a well known problem, of whether there exists a fair gamble game for two persons by tossing one dishonest coin that will always stop(one winner is selected) at no more than $N$ ...