Appendix
Calculating a Nash Equilibrium

Consider the simple game discussed in Chapter 2, where Alice and Bob compete to see how much of a debt to Alice that Bob will have to pay back. This is a zero-sum game; Alice wins exactly what Bob loses, and vice versa. The payoffs in the game matrix are the amounts Bob pays to Alice, so Bob’s “payoff” in each case is the negative value of the number indicated.

To calculate the Nash equilibrium, you must find the mixed strategies for each player that yield the best expected payoff when the other player is also choosing the best possible mixed strategy. In this example, Alice chooses Bus with probability p, and Walk with probability 1 – p (since the probabilities must add up to 1). Bob chooses Bus with probability q and Walk with probability 1 – q.

Alice can calculate her “expected payoff” for choosing Bus or Walk as follows. Her expected payoff from Bus will be the sum of:



The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement



Below are the first 10 and last 10 pages of uncorrected machine-read text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.
Intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text on the opening pages of each chapter. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.

OCR for page 225
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature Appendix Calculating a Nash Equilibrium Consider the simple game discussed in Chapter 2, where Alice and Bob compete to see how much of a debt to Alice that Bob will have to pay back. This is a zero-sum game; Alice wins exactly what Bob loses, and vice versa. The payoffs in the game matrix are the amounts Bob pays to Alice, so Bob’s “payoff” in each case is the negative value of the number indicated. To calculate the Nash equilibrium, you must find the mixed strategies for each player that yield the best expected payoff when the other player is also choosing the best possible mixed strategy. In this example, Alice chooses Bus with probability p, and Walk with probability 1 – p (since the probabilities must add up to 1). Bob chooses Bus with probability q and Walk with probability 1 – q. Alice can calculate her “expected payoff” for choosing Bus or Walk as follows. Her expected payoff from Bus will be the sum of:

OCR for page 225
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature Her payoff from Bus when Bob plays Bus, multiplied by the probability that Bob will play Bus, or 3 times q plus Her payoff from Bus when Bob plays Walk times the probability that Bob plays Walk, or 6 times (1 – q) Her expected payoff from Walk is the sum of: Her payoff from Walk when Bob plays Bus times the probability that Bob plays Bus, or 5 times q plus Her payoff from Walk when Bob plays Walk times the probability that Bob plays Walk, or 4 times (1 – q) Summarizing, Alice’s expected payoff for Bus = 3q + 6(1 – q) Alice’s expected payoff for Walk = 5q +4(1 – q) Applying similar reasoning to calculating Bob’s expected payoffs yields: Bob expected payoff for Bus = –3p + –5(1 – p) Bob expected payoff for Walk = –6p + –4(1 – p) Now, Alice’s total expected payoff for the game will be her probability of choosing Bus times her Bus expected payoff, plus her probability of choosing Walk times her Walk expected payoff. Similarly for Bob. To achieve a Nash equilibrium, their probabilities for the two choices must be such that neither would gain any advantage by changing those probabilities. In other words, the expected payoff for each choice (Bus or Walk) must be equal. (If the expected payoff was greater for one than the other, then it would be better to play that choice more often, that is, increasing the probability of playing it.) For Bob, his strategy should not change if

OCR for page 225
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature Applying some elementary algebra skills, that equation can be recast as: Which, solving for p, shows that Alice’s optimal probability for playing Bus is So Alice should choose Bus one time out of 4, and Walk 3 times out of 4. Now, Alice will not want to change strategies when Which, solving for q, gives Bob’s optimal probability for choosing Bus: So Bob should choose Bus half the time and Walk half the time.

OCR for page 225
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature Now let’s say Alice and Bob decide to play the hawk-dove game, in which the payoff structure is a little more complicated because what one player wins does not necessarily equal what the other player loses. In this game matrix, the first number in the box gives Alice’s payoff; the second number gives Bob’s payoff. Alice plays hawk with probability p and dove with probability 1 – p; Bob plays hawk with probability q and dove with probability 1 – q. Alice’s expected payoff from playing hawk is –2q + 2(1 – q). Her expected payoff from dove is 0q + 1(1 – q). Bob’s expected payoff from hawk is –2p + 2(1 – p); his expected payoff from dove is 0p + 1(1 – p). Bob will not want to change strategies when So p, Alice’s probability of playing hawk, is 1/3.

OCR for page 225
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature Alice will not want to change strategies if So q, Bob’s probability of playing hawk, is also 1/3. Consequently the Nash equilibrium in this payoff structure is to play hawk one-third of the time and dove two-thirds of the time.