We recorded our discussion at UnPub 7 in Baltimore, Maryland, on Friday 17 March.
|Game tree for "Battle of the Sexes"|
Source: "Managerial Economics
Our discussion opened with a hypothetical game in which first Aaron and then Austin decides whether to go out to get ice cream. Aaron prefers ice cream but more important than that prefers not to spend time with Austin. Austin prefers ice cream. Knowing Austin's preferences (his "payoff"), Aaron "prunes" from the tree those decision branches that he knows Austin will not take, leaving Aaron with a strategy to stay home and avoid Austin's company. Austin will then go out and get ice cream.
In the sample illustration for "Battle of the Sexes," a wife and a husband are choosing whether to go to the opera or to the bullfight. The wife prefers the opera with the husband (payoff 5), but would rather go to the bullfight with her husband (4) than to the opera alone (3). Going to a bullfight alone is as bad as staying home (0). The husband's payoffs are the same except that he prefers the bullfight over the opera. In this sequential game, the wife chooses first, and then knowing the wife's choice, the husband chooses second. This is not a zero-sum game, and the wife's payoffs don't necessarily compare to the husband's. Rather, each seeks to maximize her or his own payoff in isolation. So if the wife chooses "opera (O)," the husband would rather go to the opera with his wife than to the bullfight alone (even if they would be equally miserable alone), and so chooses to go to the opera (O) as well. (Later we'll see how the social concept of "fairness" can undermine game tree analysis.)
The authors insist that a player's strategy be complete, i.e. that it include contingencies for nodes that perfect analysis says might be unnecessary. It's not clear in Chapter 3 why that's the case, but they refer to stability analysis in advanced game theory, and so we accept that a well-defined strategy for a player is a complete plan of action for all the player's decision nodes.
Interestingly, the authors stipulate that every node have only one branch leading to it. I find that interesting, inasmuch as it is possible for different decision sequences to result in a game state that poses the same player with the same decision and the same consequences. If they are treated as different nodes, then the downstream game tree branches will be identical for both. That seems an unnecessary restriction, but I don't see it as problematic, and in fact it may simplify game tree analysis.
An approach to solving a game tree, i.e. establishing a strategy for each player and predicting likely courses of a game, is to sequentially prune branches that represent decisions that are categorically not in the interest of the deciding player. So for example in the case of the Battle of the Sexes, at node b, the husband is faced with a payoff of 4 for the opera (O) or 3 for the bullfight (BF). So the BF branch may be pruned because in that case the husband will not choose BF. At node c, the husband is faced with payoffs of 0 (O) and 5 (BF), so that O branch may be pruned. The result is that now at node a, the wife's choices have payoffs of 5 (O), because she knows that the husband will also choose O in that case, or 4 (BF), because the husband will choose BF. So at node a, the lower payoff BF branch may be pruned, and the game tree has a single path in which both partners choose the opera.
Instead of pruning, a different way to represent the same technique is to highlight clearly optimal choices, such as the O choice at node b and the BF choice at node c. Then highlight the O choice at node a to complete a path from the initial node to the terminal node. In either case, this method of working backward is called rollback, or backward induction. When all players use rollback to arrive at a strategy, the resultant set of strategies is a rollback equilibrium, and the resultant terminal node is the rollback outcome. The authors stipulate that every sequential game has a rollback equilibrium - typically exactly one, except where players have equal payoffs between two choices and are indifferent to the result.
Depending on the configuration of the game tree (and the Battle of the Sexes is an example), the rollback equilibrium may result in the player at the initial node gaining the maximum possible payoff while other players gain less than their maximum. A game tree with such a configuration has first-mover advantage. In other cases, when reacting to the first decision yields the maximum payoff (as it would if rock-paper-scissors were a sequential game), the game is said to have second-mover advantage.
solved in July 2007 and, perfectly played, will always result in a draw.
Rollback analysis presupposes a clear understanding of the value of the payoffs to rational players. An "Ultimatum Game" gives 100 coins to Player A, who offers some of them to Player B. If Player B accepts the offer, both keep their shares; if not, neither keeps anything. Rollback analysis dictates that Player A offer one coin and B accept, but in social experiments, observation indicates Player A typically offers much closer to 50 and B accepts only if offered something that appears fair. So empirically, players value fairness in a way that the originally constructed game tree does not reflect. When the experiment is posed in a way that Player B does not know how the offer was derived (e.g. whether it was random, by computer, by Player A, or by some other method), Player B typically accepts much lower offers because the sense of fairness is less offended by an arbitrary opportunity. Going back to the "Battle of the Sexes," if the same game is played every week and the couple goes to the opera every week, the husband might - out of a sense of "fairness" - deliberately go to the bullfight alone rather than continue to accede to his wife's preferred event.
It will be interesting to see how rollback analysis might apply to social games where signaling might induce opponents down one branch over another. For example, if the husband signals an intent to go to the bullfight regardless of the wife's decision (and if the signal is credible), the wife may choose to go to the bullfight rather than risk going to the opera alone.
So we can approach sufficiently simple sequential games with game tree analysis as long as we correctly value payoffs. Game tree analysis still provides insight (if not explicit solution) for more complex games. Irrational play may undermine strict analysis, so strategies need to take into account unexpected paths that the game might follow.
Next time we will discuss Games of Strategy Chapter 4, "Simultaneous Move Games with Discrete Strategies."