Game Theory through Examples

BATTLE OF THE SEXES: A couple in the pre-phone area decides independently whether to go to soccer or to the ballet in the evening. Everybody likes to do something together with the other, but besides that, the man prefers soccer and the woman prefers ballet (sorry, this is just the way this example is communicated.) Here is the payoff matrix:

	soccer	ballet
soccer	4,2	1,0
ballet	0,1	2,4

SCHEDULING A DINNER PARTY: Ann and Beth are not on speaking terms, but have a lot of common friends. Both want to invite these friends to a dinner party this weekend. Possible are friday or saturday evening. Both slightly prefer Saturday. If both set the party at the same time, this will be considered a disaster with a payoff of -10 for both. If one plans the party on Friday and the other on Saturday, the one having the Saturday party gets a payoff of 5, and the other of 4.

CHICKEN:

	Dove	Hawk
Dove	1,1	0,2
Hawk	2,0	-1,-1

ENTRY INTO SMALL MARKET:(Chicken)

	stay	swerve
stay	-50,-50	100,0
swerve	0,100	50,50

JOINT VENTURE:(Coordination) Two firms in a joint venture should use the same supplier, but each one has a preferred supplier.

	A	B
A	100,50	0,0
B	0,0	50,100

EMPLOYEE MONITORING:

	Monitor	Not
Work	50,90	50,100
Shirk	0,-10	100,-100

SOCCER PENALTY:

	left	right
left	-1	1
right	1	-1

FOUR WAYS Two left-turning driver simultaneously arrive from opposite directions at a 4-way junction. Each one has three pure strategies: to go, to wait, or only to go if the other appears to be waiting. It takes 2 seconds to pass the junction, however if both initially go or both initially wait, then both get an additional "positioning" delay of 3 respectively 2 seconds, with 50-50 chance for each player to pass the junction first. The payoff matrix is:

-4, -4	0, -2	0, -2
-2, 0	-3, -3	-2, 0
-2, 0	0, -2	-4, -4

[Mesterton-Gibbons 99], [Mesterton-Gibbons 92]

TRAVELLER's DILEMMA: Two travellers, returning from an island, find their identical antiques they bought smashed during the flight. The airplane manager, having no idea of the value of the antiques, proposes that each traveller independently makes a cliam between $2 and $100. He then pays the minimum of the two claims to both, however, if both claims differ, he pays the one making the smaller claim $2 more and the other one $2 less than that minimum (to encourage smaller numbers). How much will the travellers claim?

SIMULTANEOUS ULTIMATUM GAME: There is a fixed number, say 5, of coins for both players. Both simultaneously tell how much of the whole they would want. If the sum of both these wishes is less or equal to 5, each one gets the wishes fulfilled. Otherwise nobody gets anything.

JOINT PROJECT: Two persons are working on a joint project. Ann puts in x hours, and Beth y hours. The cost for Ann to do so is CA(x), and the cost for Beth to do so is CB(y). The finished project is worth f(x,y) to both of them. We obtain different variants by different functions CA, CB, f. For instance, take f(x,y)=4xy, and CA(x)=x², and CB(y)=y². (Other possibilities are CA(x)=x).

CHUMP Two camels, a dromedary and a bactrian simultaneously flash x humps and guess that its opponent will flash y humps. If both players are right or both wrong, the game is a draw. If only one is right, the payoff is the sum of the humps flashed. [Mesterton-Gibbons 99]

HOUSEHOLD TIME ALLOCATION: Ann and Beth(p) share a room. Both decide to spend 0, 1, 2, 3, or 4 hours on Saturday mornings (between 8:00 and 13:00) on household matters. However, Beth(p) is a little clumsy and cannot work as efficient as Beth. Every hour Beth works is equivalent to p hours work of Ann, where p < 1. The (immaterial) payoff for each is the product of

the total time somebody worked on household matters (where Beth's time is multiplied by a factor of p), and
the free time they have between 8:00 and 13:00

GUESS THE AVERAGE(n,k): n players submit a number simultaneously (between 1 and k). Those whose number is closest to 2/3 of the average of all submitted numbers gets $1. In a tie, the win is split equally.

INVESTMENT: Ann and Beth invest their $100 either in bonds, with 6% return, or in in a risky venture. The venture requires $200 to be a success, then the return is 10%. But if the total investment is less than $200, then the venture is a failure and yields no return. There is no communication between Ann and Beth. [Kockesen]

ELECTION(a,b,c): There are three districts, A, B, and C, and similar to the election of the president of the USA, the president of this area is elected by electoral votes. There are a=3 electoral votes from district A, b=3 electoral votes from district B, and c=5 electoral votes from district C. Districts do not split electoral votes. Now there are two presidential candidates, Ann and Beth, and in their campaign they uniformly decide how to distribute 3 resources over the districts. A district votes for the candidate having put the most resources into the district, and abstains in case of a tie. How would Ann and beth distribute the resources?

SELECTING CLASS Adam, Bill, and Cindy are registering for one foreign language class independently and simultaneously. The available classes are ITA100 and FRE100. All three are almost indifferent between the two choices, but they are not indifferent with whom to share the class. More precisely, Bill and Cindy want to be in the same class, but want to avoid Adam. On the other hand, Adam wants to be in the same class as Bill and Cindy, or even better, both.

ROCK-SCISSORS-PAPER

	Rock	Scissors	Paper
Rock	0	1	-1
Scissors	-1	0	1
Paper	1	-1	0

CRASH ROCK-SCISSORS-PAPER

	Rock	Scissors	Paper
Rock	0	2	-1
Scissors	-2	0	1
Paper	1	-1	0

ROCK-SCISSORS-PAPER-FOUNTAIN ...

MORA Two players simultaneously show one or two or three fingers and call a number between two and six. The number closer to the number of fingers shown by both players together wins.

3-PERSON ROCK-SCISSORS-PAPER Ann, Beth, and Cindy simultaneously play Rock-Scissors-Paper. If all three show the same, or all three different values, then it is a draw. Otherwise there are two winners and one loser, or one winner and two loser. In these cases, every loser pays every winner $1.

3-PERSON MORA Three players put $1 each on the desk. Then they simultaneously show one or two fingers and call a number between three and six. The number closer to the sum of the number of fingers shown by the players together wins the money on the desk. In case of a tie, they share. (Analysis of the game)

The Chairman Paradox A committee with three players has to choose between three options A, B, and C. The method is majority vote---every player gives one vote--- and in case of a tie the chairman, player 1, decides among the tied options. Assume the preference lists of the three players are A,B,C for player 1, B,C,A for player 2, and C,A,B for player 3. Assume a plyer gets a payoff of 2 if the favorite is chosen, of 1 if the middle preferencxe is selected, and 0 otherwise. Therefore, if every votes honestly her first preference, every option gets exactly one vote, there is a tie, which is broken by the chairman player 1 by selecting option A. But the voters can vote strategically---not voting for their first preference to achieve a higher payoff. How would the three players play, and what option would be selected? Click here for the analysis

(Balanced) 3-Spinner Game

A 3-spinner is a spinner with three equal parts, each with a number on it. Such a 3-spinner is balanced if the three numbers sum up to 0.

The (balanced) 3-spinner game is played by two or more players. Each player brings a (balanced) 3-spinner without knowing what (balanced) 3-spinner the other players have chosen. Then the spinners are revealed and spun. HIER VERSCHIEDENE VARIANTEN---DIFFERENZ, ... The player whose spinner shows the highest number takes $1 from the other players. In case of a tie the win is shared.

Sequential, Perfect Information

SENATE RACE(compare [Kockesen]) An incumbent senator decides first whether to run an expensive ad campaign for the next election. After that, the challenger decides whether to enter the race or not. The chances for the senator to win are 5/6 with the ad campaign, and 1/2 without. The value of winning the election is 2, of losing -0.5, and the cost of the add campaign is 1. (all values in Million dollars)

SENATE RACE II(compare [Kockesen]) An incumbent senator (from a rightist party) runs agains a challenger (from a leftist party). They are first choosing a political platform, leftist or rightist. If both choose the same platform, the incumbent wins, otherwise the challenger wins. Assume that the value of winning is x and the value of compromising their political views (by choosing a platform not consistent with it) is -y. There are different variants, depending on x and y and also on whether the incumbent has to choose first, the challenger has to choose first, or whether they both have to choose simultaneously.

ULTIMATUM GAME(n): There is a fixed number n of dollar bills for both players. Ann makes an offer how to share them, which Beth can either accept or reject. If she accepts, the bills are divided as agreed upon, if she rejects nobody gets anything.

TWO-ROUND BARGAINING(n,k): There is a fixed number n of dollar bills for both players. Ann makes an offer how to share them, which Beth can either accept or reject. If she accepts, the bills are divided as agreed upon. If the rejects, n-k dollar bills are taken away and only k remain on the desk. Then Beth makes an offer how to share these three dollars, which Ann can accept or reject. If Ann accepts, the bills are divided accordingly, if she rejects, nobody gets anything.

MATCHING CHAIRS: Ann and Beth can select both 3 chairs from 7 chairs, Two L-chairs and five O-chairs. One L-chair is worth $300, but if you have a pair of L-chairs, the pair is worth even $800. O-chairs are less valuable: One is worth $100, a pair is worth $400, but three of them are worth $900. Beginning with Ann, Ann and Beth alternate selecting a chair until each of them has three.

TAKE SOME(n,p,q): At the beginning n Dollars lie on the desk. There are 5 rounds, where, starting with Ann, the two players that have not yet "finished" alternately move. A player who is to move can either take part of the money on the desk, or wait. A player can only take money once---a player who takes some money has "finished" and cannot move anymore. If one player has already finished, the other one moves every round. In the first round, the player who is to move can take p of the money, in the second round p-10%, in the third round p-20%, and so on. But in rounds where no money is taken, where the player waits, the money on the desk increases by $q.

So, on the one hand, the money increases if the players wait, on the other hand the percentage they are allowed to take decreases over time, and moreover the money can decreases when the other player takes some. So the trick is to find the right time to take money.

NIM(n): n stones lie on the desk. Beginning with White, Black and White alternate to remove either one or two stones from the desk. Whoever first faces an empty desk when having to move loses. The winner gets $1, the loser loses $1. What are the best strategies for the two players?

RANDOM NIM(n,p): n stones lie on the desk. Black and White alternate to remove either one or two stones. The player who has to move but cannot (since there is no stonde left) loses, and the payoffs are 1 for the winner and -1 for the loser.. However between these moves of White and Black, randomly either 0 or 1 stones are also removed (with probability p and 1-p respectively).

SEQUENTIAL QUIZ SHOW (n,m): Three players, Ann, Beth, and Cindy, are facing a very difficult multiple choice question with five options. Starting with Ann and continuing cyclically, the player on focus can either try to give an answer or wait. If the player tries an answer and the answer is correct, the player gets n dollars. If it is incorrect, the player has to pay m dollars and is out of the game (cannot try an answer later). If the player waits, the quiz master reveals a wrong answer (thereby decreasing the number of possible options by one) and the next player gets the focus.

1-CANDIDATE QUIZ SHOW: You play a quiz show with up to 6 questions. The questions are worth $1, $1, $2, $4, $8, and $16. After each round, you have the option to stop and take the money you have won so far, or hear the next question. If you have heard the next question, there is no way out---you have to answer it correctly, to go into the next round. If you give the wrong answer, all your money is lost. You also know that in round n the probability of giving a wrong answer is 2/(9-n). (Thus it increases from 2/8 over 2/7, 2/6, 2/5, 2/4 to 2/3 over the six rounds.) When do you stop?

5 ENVELOPES: $10000 is distributed into 5 envelopes. One envelope, the "bomb", remains empty. In the basic version the player knows how much is put into each envelope, let's say $1000, $2000, $3000, $4000, and 0. Then the envelopes are shuffled and in each round you, the player, can either choose to get one of the remaining envelopes or keep the money you have collected so far and quit. If you ask for a new envelope, randomly one of the remaining envelopes is selected and handed to the player. If this envelope contains nothing (the bomb), the player you lose all the money you collected in the previous envelopes, otherwise you add the money to the money taken so far.

Other Games

MYERSON POKER Both Ann and Beth put one dollar in the pot. Ann gets a card and looks at it privately. Then Ann either folds, in which case Ann gets the money in the pot if Ann's card is red, or Beth gets the pot otherwise. Ann can also raise by putting another dollar in the pot. Now Beth either passes, in which case Ann gets the pot, or Beth meets by putting one more dollar in the pot. If Beth meets, Ann gets the pot if she has a red card, otherwise Beth gets the pot.

STRIPPED-DOWN POKER: Both Ann and Beth put one dollar in the pot. Ann gets a card from a stack of 4 Queens and 4 Kings and looks at it privately. Then Ann either folds, in which case Beth gets the money in the pot, or raises. Raising means that Ann has to put another dollar in the pot. When Ann has raised, Beth either folds, in which case Ann gets the pot, or Beth calls by putting also one more dollar in the pot. If Beth calls, Ann gets the pot if she has a King, otherwise Beth gets the pot.

MINI LE HER 2(q,k): This game is played with a q+k cards deck, q Queens and k Kings. Ann and Beth get both randomly a card at which they look without showing it to their opponent. A third card is put, back up, on the desk. Now Ann can decide whether she wants to change cards with Beth (of course without knowing what card Black has). Next Beth has the opportunity to exchange her card with that lying on the desk. Now both players reveal their cards, the one with the higher one wins 1 unit from the other. In case of a tie nobody gets any payoff.

MINI LE HER 3(j,q,k): This game is played with a j+q+k cards deck, j Jacks, q Queens and k Kings. Ann and Beth get both randomly a card at which they look without showing it to their opponent. A third card is put, back up, on the desk. Now Ann can decide whether she wants to change cards with Beth (of course without knowing what card Black has). Next Beth has the opportunity to exchange her card with that lying on the desk. Now both players reveal their cards, the one with the higher one wins 1 unit from the other. In case of a tie nobody gets any payoff.

LEGISLATORS VOTE: Three legislators vote whether they allow themselves a salary rise of $2000 per year. Since voters are observing, a legislator would estimate the loss of face by having to vote for a rise as $1000 per year.
a) What happens if all three vote at the same time?
b) What happens if A has to vote first, then B, then C, and all votes are open. (This is a variant of a game desribed in [Kaminski].)

DIGGER: This game is played between an inmate in a prison and the guard. The inmate has three options. Behave (B), or violate the rules just a little bit (S), and violating them heavily (L). The guard has two options for a violation, he can ignore it (I) or punish it (P). The outcomes for the inmate are ranked from highest to lowest payoff as follows. Best is an ignored large violation (LI), followed by an ignored minor violation (SI), followed by behaving (B), followed by the punishment for a small violation (SP), followed by the punishment for a large violation (LP). The outcomes are also ranked for the guard. Best for him is if the inmate behaves (B), then there is no trouble. A small violation is not worth the trouble for the guard, so he ranks the outcome (SI) higher than (SP). The worst two cases are where the inmate violates the rules heavily. If the guard punishes this, there is a lot of trouble, maybe paperwork and having to secure evidence. Even worse for the guard would be to ignore a large violation (LI), since this would probably cause the administration to take action against the guard.
How would both players play? [Kaminski]

Governmental Procedure for passing a bill: The bill first goes to the House (H). If it gets less than 1/2 of the votes, it is rejected. If it gets at least 1/2 but less than 2/3 it goes to the senate (S). If it gets at least 2/3, it is reviewed by the president (P).
If the bill is in S, then it must get at least 1/2 of the votes to be reviewed by P, otherwise it is rejected.
P may veto or accept the bill.
If P accepts, the bill becomes law.
If P vetoes, the veto can be overturned by more than 2/3 both in H and S, voting sequentially, first H, then S. If the veto is not overturned, the bill is rejected. If the veto is overturned, the bill becomes law. [modified from Kaminski]

Shapely Auction Two or more players are bidding for a dollar by increments of 10 Cents. The one with the highest bid has to pay whatever she was bidding and gets the dollar. The one with the second largest bid gets nothing, but still has to pay her bid ( a little unfair, but that's the way it is).

More Complex Games

CINQUE-UNO: There are two players, and each one gets 5 cards, a "5", a "4", a "3", a "2", a "1". Then the players reveal one of the cards in their hand simultaneously in rounds. If both are identical, or if one is "1" and the other "5", both cards remain on the desk. Otherwise the player who played the higher card takes it back to her hand, whereas the lower card must remain on the desk. The player having first no card in her hand after a round (after retaking the higher card) looses.

Existing Card Games

Poker:

Poker emerged from the French card game Poque (mispronounced by the Americans) in the beginning of the ninteenth century in New Orleans. The original Poque gave each player three cards out of 32 cards, and used pairs and three of a kind. [McDonald1950]]. It is different to many other games insofar as the betting process takes more space than the process of card handling, actually the betting and bluffing is the essence of the game.

Black Jack

The expectation for players when imitating the bank strategy is -0.057. The first one to use the recently invented (1944) game theory on Black Jack was Baldwin in 1956. He showed that expectations of -0.008 could be achieved. Note that a player using this strategy would still lose in the long run, but she would lose slower. In 1961, the mathematician Thorpe apperaed in the Casino scene. He used card counting---realizing what position we are in, and using different moves for different information sets---and was able to achieve a positive expectation. He also used small computers, hidden under his clothes, for the card counting. At that time this was not forbidden yet. Thorpe püublished a book on his black Jack method, which became rather successful for a mathematics book. The casinos had to react ........

Le Her

LE HER is played with a 52 cards deck, and the ordering is A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K. Two players, White and Black, get both a card at which they look without showing it to their opponent. A third card is put, back up, on the desk. Now White can decide whether she wants to change cards with Black (of course without knowing what card Black has). Only if Black has a King she can refuse the exchange. Next Black has the opportunity to exchange her card with that lying on the desk. However, if that card was a King, she has to put it back as well. Now both players reveal their cards, the one with the higher one wins, where in case of a tie Black wins.

VNMPOKER

Von Neumann and Morgenstern discussed in their monograph variants of (Stud) Poker in much detail (pages 186-219). Although these games did not exist, they were not supposed to be toy examples, rather the authors claimed that these versions, though simplified, still would carry many of the characteristics of real Poker. In particular, the results they got shed light on the role of bluffing and why it is necessary.

The authors only concentrated on Poker as a two-players game in their book (although they presented quite a bit of theory of n-person zero-sum games. The reason why they didn't try to extend their analysis to 3 or more players for Poker was maybe that a full solution like in their versions of the 2-player Poker would not have been possible for more players.

Maybe the least severe simplification was their assumption that insted of getting five cards, both players receive only one card ouit of a large deck of cards labeled from 1 to S. Their point of view was that all (2598960) possible hands are linearly ordered from good to bad, all of them are equally likely to get, and for Stud Poker they don't consider the procedure of trying to upgrade your hand. There is a slight flaw in that argument: Seeing your hand, you can exclude some other hands for your opponent, which is not the case if you play it on the cards from 1 to S basis, but the amount of this effect is probably neglectable for large S.

VNMPOKER(S/m,n,r):
VNMPOKER([0,1]/m,n):
SIMULTANEOUS VNMPOKER(S/m,n,r)

The idea is simple for all versions. There are two players, Ann and Beth. Each player randomly gets a card between 1 and S (in the S-version) from a deck of r*S cards, or gets a random number between 0 and 1 (in the [0,1] version). Each player looks at her card but doesn't know the opponent's card. There is a minimum amount of money m the players are betting, but this could be raised to the higher level n. As S and r, the numbers n and m are parameters that could be changed to get different versions of the game, all of them with different strategies. The last difference between the versions is whether the game is simultaneous or not. In the ordinary version Ann starts playing the game by either passing (playing for m) or betting (playing for n).

If Ann passes, both cards are revealed and the player with the higher card wins the money 2m. In case of a draw---both cards showing the same number---the money is split equally.
If Ann bets, she increases the money to n. Then Beth has two options, she can either fold or call.
- If she folds, Ann gets the money m. Beth's card is not revealed in that case.
- If Beth calls, she also increases her EINSATZ to n. Then both cards are revealed again, and the player with the higher card wins the money 2n. Again, in case of a draw the money is split equally.

In the simultaneous version both players decide simultaneously whether they want to bet for m or for n. If one of them bets for n and the other for m, the one daring the higher amount (n) wins m from the other one, regardless what the cards show. If both bet the same amount, the one with the larger card wins n respectively m from the other one, again, no win for draws of identical cards.

Existing Board Games

Chess

Chess is a typical two-player zero-sum (as most ) sequential game with complete information and no randomness. As such, it has an optimal strategy that can be found by backwards induction. However, after 40 moves there are at least 10⁵⁰ postions. which is a 50-digits number (see here), so you can maybe guess how many positions there are possible in total. With so many positions, the game obviously resists attacks by even the fastest computers so far for complete analysis.

Go, similiar in many characteristics to chess, has even 2*10¹⁷⁰ legal positions (see here).

Hex

Other Existing Games

Roulette:

Roulette is essentially a one-player game, since the opponent, the bank, doesn's decide at all. Therefore Decision Theory Techniques apply. The game can also be analyzed fairly easily, and it turns out that the expected value (per unit bet) for each move is exactly the same, namely -1/37 for european roulette, and -2/38 for american roulette. It's totally a game of luck, no skill involved.

CRAZY BETH INVESTMENT (p): Ann and Beth invest their $100 either in bonds, with 6% return, or in in a risky venture. The venture requires $200 to be a success, then the return is 10%. But if the total investment is less than $200, then the venture is a failure and yields no return. There is no communication between Ann and Beth. However, Ann is uncertain about Beth's preferences. With probability p, Ann believes that Beth is a little crazy and likes the venture, giving her satisfaction 120 in each case. [Kockesen] (compare INVESTMENT above)

DATING (Signalling: Incomplete Information but the possibility to observe your opponents moves and learn from them) Adam takes Beth out for a date. She believes the probabilities of him being smart or dump are 50% each. Adam wants Beth (2 units worth) and tries to look smart. Being funny "costs" a smart Adam 1 unit, but a dumb Adam 3 units. [Kockesen]

	number of players	simultaneous	sequential, perfect information	constant- sum	random- ness
Simultaneous Games		yes	---
TWO BARS	2	yes
R&D	2	yes
ADVERTISING	2	yes
PRISONER'S DILEMMA	2	yes
BATTLE OF THE SEXES	2	yes
SCHEDULING A DINNER PARTY	2	yes
CHICKEN	2	yes
ENTRY INTO SMALL MARKET	2	yes
JOINT VENTURE	2	yes
EMPLOYEE MONITORING	2	yes
SOCCER PENALTY	2	yes
FOUR WAYS	2	yes
TRAVELLER's DILEMMA	2	yes
SIMULTANEOUS ULTIMATUM GAME	2	yes
JOINT PROJECT	2	yes
CHUMP	2	yes
HOUSEHOLD TIME ALLOCATION	2	yes
GUESS THE AVERAGE(n,k)	2	yes
INVESTMENT	2	yes
ELECTION(a,b,c)	2	yes
SELECTING CLASS	3	yes
ROCK-SCISSORS-PAPER	2	yes		yes
CRASH ROCK-SCISSORS-PAPER	2	yes		yes
ROCK-SCISSORS-PAPER-FOUNTAIN	2	yes		yes
MORA	2	yes		yes
3-PERSON ROCK SCISSORS PAPER	3	yes		yes
3-PERSON MORA	3	yes		yes
,,,,
GUESS THE AVERAGE(n,m)
,,,,
Sequential, perfect information		---	yes
SENATE RACE	2		yes		yes
SENATE RACE II	2		yes		yes
ULTIMATUM GAME(n)	2		yes
TWO ROUND BARGAINING(n,k)	2		yes
MATCHING CHAIRS	2		yes
TAKE SOME(n,p,q)	2		yes
NIM(n)	2		yes	yes
RANDOM NIM(n,p)	2		yes	yes	yes
SEQUENTIAL QUIZ SHOW(n,m)
1-PLAYER QUIZ SHOW
5 ENVELOPES
Others		---	---
MYERSON POKER	2			yes	yes
STRIPPED-DOWN POKER	2			yes	yes
MINI LE HER
,,,,
,,,,

All Games

Simultaneous Games