Solving Games

For a two-player game with a payoff matrix, the first thing we ask is whether it is zero-sum (or constant-sum). If so, we check to see whether it has a saddlepoint by determining the minimum number of each row and the maximum number of each column, as we did in several earlier examples. If the maximum of the row minima (maximin) is equal to the minimum of the column maxima (minimax), then the game has a saddlepoint. The resulting value, and the corresponding pure strategies, provide a solution to the game.

This value will appear in the payoff matrix as the smallest number in its row and the largest in its column. In the location/schedule game in Example 1 (page 623), this number was $26 per hour, and the corresponding strategies for Mark and Lisa were to select the suburban location and the 8 A.M. to 4 P.M. shift, respectively.

Because Mark’s strategy of selecting the rural hospital is dominated by selecting the suburban hospital, Mark has no reason to ever choose the rural hospital. Once Lisa knows that Mark will never select the rural hospital, then Lisa can eliminate the 4 P.M. to 12 A.M. shift, because the 8 A.M. to 4 P.M. shift is better from her perspective under both the suburban and downtown locations. Sometimes successively eliminating dominated strategies leads to a single outcome. Indeed, after Mark eliminates the rural location, Lisa also can eliminate the 12 A.M. to 8 A.M. shift. Once Lisa selects the 8 A.M. to 4 P.M. shift, then Mark chooses the suburban location over the downtown hospital. The successive elimination of dominated strategies leads to the saddlepoint of the game—and a saddlepoint is always a Nash equilibrium.

Unfortunately, the successive elimination of dominated strategies does not work to find the saddlepoint in all two-person zero-sum games larger than .

Recall that instead of eliminating dominated strategies in the location/schedule game, we eliminated the 8 A.M. to 4 P.M. shift, which dominated other strategies in the successive process, to obtain the restricted location game in Table 15.3. In this game, the rural location is still dominated, but no other eliminations are possible; hence, the game has no saddlepoint.

If a two-person zero-sum game does not have a saddlepoint—which was the case not only in the restricted location/schedule game but also for Matching Pennies, the second matching game, and the kicker/goalie duel—the solution will be in mixed strategies. To find the optimal mix in a game, we calculate the expected value to a player from choosing its first strategy with probability and its second with probability , assuming that the other player chooses its first pure strategy (yielding one expected value) and its second pure strategy (yielding another expected value).

652

Setting these two expected values equal to each other yields a unique value for that gives the optimal mix, , with which the player should choose its first and second strategies. Inserting the numerical solution of back into either expected-value equation gives the value of the game, which each player can guarantee for itself, whatever strategy its opponent chooses.

Several general algorithms have been developed to find mixed-strategy solutions for large constant-sum games. This work has mostly been done in the field of linear programming, using such algorithms as the simplex method of G. B. Dantzig and the more recent method of N. K. Karmarkar (see Chapter 4).

In variable-sum games, we also begin by successively eliminating dominated strategies, if there are any. The outcomes that remain do not depend on the numerical values that we attach to them but only on their ranking from best to worst by the players.

Solving variable-sum games can be fairly demanding, as it may involve considerable calculational abilities on the part of the players. Less demanding, of course, is that players simply choose their dominant strategies or weakly dominant strategies, as is possible in the Prisoners’ Dilemma and the Vickrey auction, respectively. Of course, games may not have such strategies.

In the game of Chicken, for example, neither player has a dominant (or dominated) strategy, so the game cannot be reduced. In such situations, we ascertain what outcomes are Nash equilibria. There are two (in pure strategies) in Chicken, suggesting that the only stable outcomes in this game occur when one player gives in and the other does not. In the Prisoners’ Dilemma, by comparison, the choice by the players of their dominant strategies singles out the mutual-defection outcome as the unique Nash equilibrium, which is worse for both players than the cooperative outcome.

Practical Applications

The element of surprise, as captured by mixed strategies, is essential in many encounters. For example, mixed strategies are used in various inspection procedures and auditing schemes to deter potential violators. When inspection or auditing choices are made random, they are rendered unpredictable.

Police and regulatory agencies monitor certain activities to check for illegal actions. Investigators who conduct surveillance include FBI agents, customs agents, bank auditors, insurance investigators, quality-control experts, and drug testers. The National Bureau of Standards is responsible for monitoring the accuracy of measuring instruments and for maintaining reliable standards. The Nuclear Regulatory Agency demands an accounting of dangerous nuclear material as part of its safeguards program. The Internal Revenue Service attempts to identify people who cheat on taxes.

Military or intelligence services may wish to intercept a weapon hidden among many decoys or to plant a secret agent disguised to look like a respectable individual. Because it is prohibitively expensive to check the authenticity of each and every possible item or person, efficient methods must be used to check for violations. Both optimal detection and optimal concealment strategies can be modeled as a game between an inspector trying to increase the probability of detection and a violator trying to evade detection. Since the World Trade Center attack on September 11, 2001, United States government agencies have taken much stronger measures to prevent such evasion, including the formation of the Transportation Security Administration, whose agents check for contraband when passengers board flights.

653

Some inspection games are constant-sum: The violator “wins” when the evasion is successful and “loses” when it is not. On the other hand, cheating on arms-control agreements may well be variable-sum if both the inspector and the cheater would prefer that no cheating occur rather than cheating and public disclosure of it. The latter could be an embarrassment to both sides, especially if it undermines an arms-control agreement that both sides wanted and the cheating is minor.

We alluded earlier to the strategy of bluffing in poker, used by a player to try to keep the other player or players guessing about the true nature of one’s hand. The optimal probability with which one should bluff can be calculated in a particular situation (see Exercise 21 on page 661). Besides poker, bluffing is common in many bargaining situations, whereby a player raises the stakes (e.g., labor threatens a strike in labor-management negotiations), even if it may ultimately have to back down if its “hand is called.”

Perhaps the greatest value of game theory is the framework it provides for understanding the rational underpinnings of conflict in the world today. As a case in point, a confrontation over the budget between Democratic president Barack Obama and the Republican House of Representatives resulted in the third longest shutdown of (part of) the federal government, from October 1 to 16, 2013. The shutdown occurred due to the failure to pass legislation for the 2014 fiscal year or to pass a continuing resolution to allow the government to continue spending money. Many government workers were frustrated at not being able to do their jobs, even though they realized that they would be paid for not working given past shutdowns, not to mention the many citizens who were either greatly hurt or substantially inconvenienced by the shutdown. Viewed as a game of Chicken, in which each side wanted not only to get its way for the moment but also to influence future negotiations, this conflict may not have been as foolish as it seems at first glance.

Another example in which game theory is useful is to analyze the behavior of free riders. A free rider is someone who benefits from resources, goods, services, or a policy without paying the cost of the benefit. For example, if someone hops the turnstile on a subway train and gets to ride the train for free, then the other riders are paying for his or her fare. The other riders pay for the free rider by increased fares to accommodate the extra use. If there is no repercussion for jumping the turnstile, then every rider would become a free rider and there would not be enough revenue to continue subway service. Other examples of free riding behavior include citizens who fail to pay their taxes yet continue to use services provided by the government or employees who benefit from conditions negotiated by a union without joining the union.

654

As another broad example, consider the case in which companies collude with one another on setting prices, which is definitely not advantageous to consumers. In this case, the consumers may be thought of as a collective player whose interests are represented by the government. The government can prosecute the companies for price fixing, or the consumers themselves can file a class-action suit in a “larger” game. The government has frequently been involved in antitrust suits (e.g., against Microsoft) and in setting the rules for auctions of airwaves, in which telecommunication companies—advised by game theorists—have paid billions of dollars for the right to construct cellular phone and other networks.

All in all, game theory offers fundamental insights into conflicts at all levels, especially seemingly irrational features that, on second look, are often well conceived and effective.