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.

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.

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.

Solve a particular case

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.

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^{6}=64 positions. Let me give two examples of such positions:

- One such position is obtained by Ann choosing L, Beth choosing O, Ann choosing O, Beth choosing O, Ann choosing L, and Beth choosing L.
- Another one is obtained by Ann choosing L, Beth choosing L, Ann choosing L, Beth choosing O, Ann choosing O, and Beth choosing O.

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^{2n} positions in the game tree,
but only (n+1)·(n+1)=n^{2}+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^{20}=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.

Choosing ... | tree | cumulative | digraph | cumulative |

Ann's 1. chair | 1 | 1 | ||

Beth's 1. chair | 2 | 2 | ||

Ann's 2. chair | 4 | 7 | 4 | 7 |

Beth's 2. chair | 8 | 6 | ||

Ann's 3. chair | 16 | 31 | 9 | 22 |

Beth's 3. chair | 32 | 12 | ||

Ann's 4. chair | 64 | 127 | 16 | 50 |

Beth's 4. chair | 128 | 20 | ||

Ann's 5. chair | 259 | 511 | 25 | 95 |

Beth's 5. chair | 512 | 30 | ||

Ann's 6. chair | 1024 | 2047 | 36 | 161 |

.......... | ||||

Ann's 10. chair | 1,048,576 | 2,097,151 | 121 | 946 |

Beth's 10. chair | 2,097,152 | 4,194,303 | 132 | 1078 |

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.

Solve a particular case

Let us again give the solution of a particular case.. .....................

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.

If all three are mean, then Ann, Beth, Chris will all get $400.

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. ......