Game Theory through Examples

MATCHING CHAIRS: The sceleton of the game is as follows. A certain amount of so-called L-chairs and O-chairs are available. L-chairs stand for luxury chairs, and are more worth than O-chairs (ordinary chairs). However, pairs of matching chairs are more worth than twice the worth of this chair, and triples of matching chairs are more worth than the sum of the worth of a pair and the worth of a single chair of that type. For instance, a single L-chair may be worth $300, a pair of L-chairs may be worth $800, and a triple of L-chairs may be worth $1500. The game consists of the players alternating in selecting chairs until each of them has a fixed number, like two or three.

Of course, there are different variants depending on

the number of players,
how many chairs each can choose,
the total amount of available L- and O-chairs,
and the payoffs per chair, pair, and triple for L-chairs and O-chairs,

In this chapter we will analyze a few variants of the game, using backwards induction. The results are rather unspectacular. However we will also use this example for a comparison of game trees and game digraphs as extensive formes. We will also see how sometimes backwards induction can be replaced by other forms of reasoning.

1. Two players

1.1 Two players, each selecting 2 chairs

Even without specifying the total numbers of available L- and O-chairs and the worths for single L- and O-chairs and pairs, the extensive form is more or less fixed, as given as below, to the left as a digraph, and to the right as a game tree. The vertices are labeled by the names of the chairs Ann has so far and the names of the chairs Beth has so far, separated by a "|". The payoffs are not shown yet. The digraph is obtained from the tree by identifying vertices with the same name. Note also that such an identification of two vertices, such a reduction is only possible if the corresponding vertices are really the same, meaning that both subtrees hanging at the two vertices are totally identically, including the payoffs at the end.

Some positions may not be achievable, depending on the total number of available L- and O chairs, but these situations can easily be modeled by assigning payoffs of 0 to these positions. Therefore all variants of this two players and chairs variant, all possible payoffs for one, two, or three L- or O-chairs, and all possible available numbers of L- and O-chairs, can be modeled using the digraph or the tree above.

There is an Excel sheet available, where you can analyze the situations with two players and two or three rounds, and of three players with two rounds.

If we look at a particular case, the solution is rather unspectacular. .....................

MATCHING CHAIRS: Ann and Beth can select both 3 chairs from 7 chairs, four L-chairs and four O-chairs. Single L-chairs are worth $300, but pairs and triples of them are worth $800 respectively $1500. O-chairs are less valuable: One is worth $100, a pair is worth $400, but triples are worth $900. Beginning with Ann, Ann and Beth alternate selecting a chair until each of them has three of them.

There is an Excel sheet available, where you can analyze the situations with two players and two or three rounds, and of three players with two rounds.

1.2 Digression: Game digraph versus game tree

The usefulness of the concept of a game digraph can be illustrated very well at this example. We use a little combinatorics---the art of clever counting---to count the numbers of positions.

In the tree, there is one start position, the position at Ann's first move. At Beth's first move there are two possible positions, depending on whether Ann has chosen "L" or "O". At Ann's second move there are four possible positions, and so on. The number of states doubles after each move (since in each move there are two options), therefore after 3 rounds (i.e. 6 moves) there are 2⁶=64 positions. Let me give two examples of such positions:

For the payoffs, or for the future---in case the game goes on--- it is not important how this point is achieved. Therefore in the game digraph these two different positions in the game tree are identified into one.

Let us now count the number of possible states in the game digraph in the different stages of the game. Again, of course, there is only one start position. When Beth chooses her n'th chair, Ann has already chosen n chairs, and Beth has n-1 chairs. Ann can have any number of L-chairs between 0 and n, and Beth can have any number of L-chairs between 0 and n-1. These are n+1 possibilities for Ann and n possibilities for Beth. Note that these two numbers---Ann's L-chairs so far and Beth's L-chairs so far, completely describe the situation. Therefore there are (n+1)·n different situations. When Ann chooses her n'th chair, both Ann and Beth have chosen already n-1 chairs, therefore there are n·n positions then. For instance, when Ann is about to choose her 4th chair, there are 4·4=16 possible states in the digraph approach, compared to the 64 in the tree approach.

If you think the difference between 16 and 64 is not large enough to warrant the slightly more complicated concept of a digraph, let me emphasize that this difference increases for larger number of rounds: After n rounds, there are 2²ⁿ positions in the game tree, but only (n+1)·(n+1)=n²+2n+1 positions in the game digraph. So we have exponential growth of the game tree, but polynomial growth of the game digraph in this game.

Exponential growth eventually dramatically exceeds polynomial growth. Consider the example of 10 rounds, where each player will choose 10 chairs. Then the game tree has already 2²⁰=1,048,576 positions, but the game digraph still has only quite manageable 11·11=121 positions.

The following table gives the number of states in different stages of the game in the tree and digraph model, using the two formulas above. The "cumulative" columns add all these numbers up to that level in each model. Therefore they give the total number of states so far. For instance, the two player---two round version described in section 1.1 has 22 states in the digraph model, but 31 vertices in the tree model. the two player---three round version described in section 1.3 has 50 states in the digraph model, but 127 vertices in the tree model.

1.3 Two players, each selecting 3 chairs

Again the extensive form for any payoffs and any number of available L- and O-chairs is shown, with some positions again maybe impossible, depending on these numbers of available L- and O-chairs. Note that this full digraph contains 50 vertices, according to the analysis in section 1.2.

1.4 Three players, each one selecting 2 chairs

Assume we have 3 L-chairs, worth $300 and $800 for a pair, and we have 4 O-chairs, worth $100 and $400 for a pair.

Ann will choose an L-chair, Beth any chair and Chris also any chair. If there is any L-chair left, Ann would chose another L-chair. Beth and Chris will have two O-chairs, or one L-chair and one O-chair. Therefore the payoffs for Beth and Chirs are $400 each. The expected payoff for Ann is $700.

2. The ABBAAB version

We consider the two players, three moves version. What changes if the two player don't alternate, but rather Ann chooses first, then Beth, then Beth again, then Ann again, then Ann again, and finally Beth. When Beth has two consecutive moves, of course these two moves can be combined into one, and the same for Ann later. Therefore the game can be modeled as a game where Ann chooses one chair, then Beth chooses two, then Ann chooses two, and finally Beth chooses one. The extensive form is shown below. ......