Artificial
Intelligence

Example 10.9: Consider the case of a penalty kick in soccer as depicted in Figure 10.7.

---

---

If the kicker kicks to his right and the goalkeeper jumps to his right, the probability of a goal is 0.9, and similarly for the other combinations of actions, as given in the figure.

What should the kicker do, given that he wants to maximize the probability of a goal and that the goalkeeper wants to minimize the probability of a goal? The kicker could think that it is better kicking to his right, because the pair of numbers for his right kick is higher than the pair for the left. The goalkeeper could then think that if the kicker will kick right, then he should jump left. However, if the kicker thinks that the goalkeeper will jump left, he should then kick left. But then, the goalkeeper should jump right. Then the kicker should kick right.

Each agents is potentially faced with an infinite regression of reasoning about what the other agent will do. At each stage in their reasoning, the agents reverse their decision. One could imagine cutting this off at some depth; however, the actions then are purely a function of the arbitrary depth. Even worse, if the kicker knew the depth limit of reasoning for the goalkeeper, he could exploit this knowledge to determine what the kicker will do and choose his action appropriately.

An alternative is for the agents to choose actions stochastically. You could imagine that the kicker and the goalkeeper each secretly toss a coin to decide what to do. You then should think about whether the coins should be biased. Suppose that the kicker decides to kick to his right with probability p_k and that the goalkeeper decides to jump to his right with probability p_j. The probability of a goal is then

0.9 p_k p_j + 0.3 p_k (1-p_j) + 0.2 (1-p_k) p_j + 0.6 (1-p_k)(1-p_j).

---

---

Figure 10.8 shows the probability of a goal as a function of p_k. The different lines correspond to different values of p_j.

There is something special about the value p_k=0.4. At this value, the probability of a goal is 0.48, independent of the value of p_j. That is, no matter what the goalkeeper does, the kicker expects to get a goal with probability 0.48. If the kicker deviates from p_k=0.4, he could do better or he could do worse, depending on what the goalkeeper does.

The plot for p_j is similar, with all of the lines meeting at p_j=0.3. Again, when p_j=0.3, the probability of a goal is 0.48.

The strategy with p_k=0.4 and p_j=0.3 is special in the sense that neither agent can do better by unilaterally deviating from the strategy. However, this does not mean that they cannot do better; if one of the agents deviates from this equilibrium, the other agent can do better by deviating from the equilibrium. However, this equilibrium is safe for an agent in the sense that, even if the other agent knew the agent's strategy, the other agent cannot force a worse outcome for the agent. Playing this strategy means that an agent does not have to worry about double-guessing the other agent. He will get the best payoff he can guarantee to obtain.

Example 10.10: In Example 10.9, there is a unique Nash equilibrium where p_k=0.4 and p_j=0.3. This has the property that, if the kicker is playing p_k=0.4, it does not matter what the goalkeeper does; the goalkeeper will have the same payoff, and so p_j=0.3 is a best response (as is any other strategy). Similarly, if the goalkeeper is playing p_j=0.3, it does not matter what the kicker does; and so every strategy, including p_k=0.4, is a best response. The only reason an agent would consider randomizing between two actions is if the actions have the same expected utility. All probabilistic mixtures of the two actions have the same utility. The reason to choose a particular value for the probability of the mixture is to prevent the other agent from exploiting a deviation.

Example 10.11: Suppose there is a resource that two agents may want to fight over. Each agent can choose to act as a hawk or as a dove. Suppose the resource is worth R units, where R>0. If both agents act as doves, they share the resource. If one agent acts as a hawk and the other as a dove, the hawk agent gets the resource and the dove agent gets nothing. If they both act like hawks, there is destruction of the resource and the reward to both is -D, where D>0. This can be depicted by the following payoff matrix:

In this matrix, Agent 1 gets to choose the row, Agent 2 gets to choose the column, and the payoff in the cell is a pair consisting of the reward to Agent 1 and the reward to Agent 2. Each agent is trying to maximize its own reward.

In this game there are three Nash equilibria:

• In one equilibrium, Agent 1 acts as a hawk and Agent 2 as a dove. Agent 1 does not want to deviate because then they have to share the resource. Agent 2 does not want to deviate because then there is destruction.
• In the second equilibrium, Agent 1 acts as a dove and Agent 2 as a hawk.
• In the third equilibrium, both agents act stochastically. In this equilibrium, there is some chance of destruction. The probability of acting like a hawk goes up with the value R of the resource and goes down as the value D of destruction increases. See Exercise 10.1.

In this example, you could imagine each agent doing some posturing to try to indicate what it will do to try to force an equilibrium that is advantageous to it.

Example 10.12: Suppose there are two people who want to be together. Agent 1 prefers they both go to the football game and Agent 2 prefers they both go shopping. They both would be unhappy if they are not together. Suppose they both have to choose simultaneously what activity to do. This can be depicted by the following payoff matrix:

In this matrix, Agent 1 chooses the row, and Agent 2 chooses the column.

In this game, there are three Nash equilibria. One equilibrium is where they both go shopping, one is where they both go to the football game, and one is a randomized strategy.

This is a coordination problem. Knowing the set of equilibria does not actually tell either agent what to do, because what an agent should do depends on what the other agent will do. In this example, you could imagine conversations to determine which equilibrium they would choose.

Example 10.13: Imagine you are on a game show with a stranger that you will never see again. You each have the choice of

• taking $100 for yourself or
• giving $1,000 to the other person.

This can be depicted as the following payoff matrix:

No matter what the other agent does, each agent is better off if it takes rather than gives. However, both agents are better off if they both give rather than if they both take.

Thus, there is a unique Nash equilibrium, where both agents take. This strategy profile results in each player receiving $100. The strategy profile where both players give results in each player receiving $1,000. However, in this strategy profile, each agent is rewarded for deviating.

Example 10.14: Consider the sharing game of Example 10.2. In this game there are infinitely many Nash equilibria. There is a set of equilibria where Andy shares, and Barb says "yes" to sharing for the center choice and can randomize between the other choices, as long as the probability of saying "yes" in the left-hand choice is less than or equal to 0.5. In these Nash equilibria, they both get 1. There is another set of Nash equilibria where Andy keeps, and Barb randomizes among her choices so that the probability of saying yes in the left branch is greater than or equal to 0.5. In these equilibria, Barb gets 0, and Andy gets some value in range [1,2] depending on Barb's probability. There is a third set of Nash equilibria where Barb has a 0.5 probability of selecting yes at the leftmost node, selects yes at the center node, and Andy randomizes between keep and share with any probability.

Suppose the sharing game were modified slightly so that Andy offered a small bribe for Barb to say "yes." This can be done by changing the 2,0 payoff to be 1.9,0.1. Andy may think, "Given the choice between 0.1 and 0, Barb will choose 0.1, so then I should keep." But Barb could think, "I should say no to 0.1, so that Andy shares and I get 1." In this example (even ignoring the rightmost branch), there are multiple pure Nash equilibria, one where Andy keeps, and Barb says yes at the leftmost branch. In this equilibrium, Andy gets 1.9 and Barb gets 0.1. There is another Nash equilibrium where Barb says no at the leftmost choice node and yes at the center branch and Andy chooses share. In this equilibrium, they both get 1. It would seem that this is the one preferred by Barb. However, Andy could think that Barb is making an empty threat. If he actually decided to keep, Barb, acting to maximize her utility, would not actually say no.