Game Theory Through
Examples (2/11/04)
Games against nature 
decision theory for a single agent
Expected utility theory for a single agent is sometimes called the theory of "games against nature". Consider this example.
Example 1:
Planning a
party
Our agent is planning a party, and is worried about whether it
will
rain or not. The utilities and probabilities for each state
and
action
can be represented as follows:
Nature's states:


(p=1/3) 
(~p=2/3) 

Party planner's possible actions:  Outside 


Inside 


The expected utility of an action A given uncertainty about a
state
S = Probability(SA)*Utility(SA) + Probability(not
SA)Utility(not
SA)
Note that action A can be viewed as a compound gamble or outcome.
Also, note that the probability of a state can depend on the
agent's
choice of action, although, in the above example, it does not.
For the party problem:
EU(Outside) = (1/3)(1) + (2/3)(3) = 2.33;
EU(Inside) = (1/3)(2) + (2/3)(2) = 2
Therefore, choose Outside, the action with the higher expected
utility
(Noncooperative) game theory  decision theory for more than one agent, each acting autonomously (no binding agreements)
In the examples below, we'll assume two selfutility maximizing agents (or players), each of whom has complete information about the options available to themselves and the other player as well as their own and the other's payoffs (utilities) under each option.
Example 2  Friends hoping to see each other
Consider two people, Chris and Kim. They both enjoy each
other's
company, but neither can communicate with the other before
deciding
whether
to stay at home (where they would not see each other) or go to the
beach
this afternoon (where they could see each other).
Each
prefers
going to the beach to being at home, and prefers being with the
other
person
rather than being apart. This game can be represented by the
following
normal (or matrix) form:
Kim





Chris  Home 


Beach 


Each player has a set of strategies (={Home,Beach} for
both
players
in this example).
Specifying one strategy i for the row player (Chris) and one
strategy
j for the column player (Kim) yields an outcome, which is
represented
as
a pair of payoffs (Rij,Cij), where Rij is the utility the row
player
receives,
and Cij is the utility the column player receives.
In this example, going to the beach is a (strictly) dominant strategy for each player, because it always yields the best outcome, no matter what the other player does. Thus, if the players are both maximizing their individual expected utilities, each will go to the beach. So BeachBeach is a dominant strategy equilibrium for this game. Because of this, Kim and Chris, if they are rational, do not need to cooperate (make an agreement) ahead of time. Each can just pursue their own interest, and the best outcome will occur for both.
Example 3  "Friends" with asymmetric preferences
Now consider Betty and John. John likes Betty, but Betty
doesn't
like John that much. Each knows this, and neither wants to
call
the
other before deciding what to do this afternoon: stay at their
respective
homes or go to the neighborhood swimming pool. Here is the
normal
form:
John





Betty  Home 


Pool 


In this case, Betty's best strategy depends on what John does. But if she assumes John is rational, she will reason that he will not stay home, because going to the pool is a dominant strategy for him. Knowing this, she can decide to stay home (because 2>1). This is called iterated dominance. In this example, Betty gets higher utility than John because of their relative preferences, and John gets less utility than he would have if Betty wanted to be with him.
In this example, PoolHome (3,0), HomePool (2,1), and PoolPool (1,2) are all Pareto optimal outcomes. An outcome is Pareto optimal (or efficient) if no agent can be made better off than that outcome without making another agent worse off. The equilibrium outcomes in both this example and the previous one are Pareto optimal.
Example 4  Prisoners' dilemma
Consider Stan and Leland, two prisoners who have each been
offered a
deal to turn state's witness (defect) against the other.
They
can't
communicate. They had orginally agreed to remain in
solidarity,
i.e. not testify against each other, but since the agreement
cannot be
enforced, each must choose whether to honor it. If both
remain in
solidarity, then they will each only be convicted of a minor
chage.
If only one defects, then the state will throw the book at the
other
and
let the defector go. If they both defect, each will get
convicted
of a serious charge. The payoff matrix (higher positive
utility
implies
a better outcome) is as follows:
Leland





Stan  Solidarity 


Defection 


In this game, the strategy of defection is weakly dominant for each player, meaning that whatever the other player does, defecting yields an outcome at least as good and possibly better than remaining in solidarity would. Note that if the bottom right cell payoffs were (2,2) instead of (1,1), then defecting would be strictly dominant for each player. Either way, DefectionDefection is a dominant strategy equilibrium. However, it is not Pareto optimal. Both players could be made better off if neither defected against the other.
This is an example of a social dilemma: a situation in which each agent's autonomous maximization of selfutility leads to an inefficient outcome. Such a situation can occur for any number of people, not just two. An agreement by two people to trade with each other (involving goods, services, and/or money) set's up a prisoners' dilemmatype game whenever the agreement cannot be enforced.
Example 5  Coordination
Let's go back to Chris and Kim. They are going to the same
conference,
and each is expecting the other to be there, but they haven't seen
each
other yet. The conferees have their choice of two activities
on
the
first afternoon: swimming or hiking. They both hope to see
each
other
 if they don't they will have no fun, and each prefers swimming
over
hiking. They must each decide what to do before knowing
where the
other is going. Here is the normal form:
Kim





Chris  Swim 


Hike 


The best outcome is obviously SwimSwim, but going swimming is not dominant for either player. Both SwimSwim and HikeHike have the property that each player's strategy is the best (or tied for the best) response to the other player's strategy in that pairing. This defines a more general equilibrium notion called the Nash equilibrium. The dominance equilibria of examples 13 are all Nash equilibria as well.
A third equilibrium exists in this game involving what are called mixed strategies. A mixed strategy is a probability distribution over the pure strategies (which are Swim and Hike for each player in this example). (Note that the players do not have to have the same set of strategies available to them, even though that has been the case in all our examples.) In this example, if each player individually throws a die and goes swimming if the die comes up 1 or 2, and goes hiking if the die comes up 3, 4, 5, or 6, the resulting expected utility (2/3 for each player) cannot be improved upon for either player given that the other player uses this strategy.
In 1950, John Nash (depicted somewhat fictitiously in the film A Beautiful Mind  the book is more accurate!) proved that every finite game, involving any number of players, has at least one (Nash) equilibrium, though there might not be any that involve only pure strategies for all players. In this example, there are three equilibria: the mixed strategy equilibrium (Swim,1/3; Hike,2/3)(Swim,1/3;Hike,2/3), and two pure strategy equilibria  SwimSwim and HikeHike.
When there is more than one equilibrium, and players cannot make binding agreements, they must try to coordinate to arrive at an equilibrium outcome. When only one equilibrium is also Pareto optimal, as SwimSwim is in this case, that fact should suggest to rational players that it will be the one around which they coordinate. Many other criteria for equilibrium selection have been studied (e.g. focal points, subgame perfection, stability  see the reading on game theory).
Example 6  "Battle of the sexes"
Finally, let's consider Roy and Jen. They are going to the
same
conference as Kim and Chris in example 5. They each would
prefer
to be in the same place (the swim or the hike), but their
preferences
differ
about which it should be. Roy would rather go swimming, and
Jen
would
rather go hiking. Here is the matrix form:
Jen





Roy  Swim 


Hike 


This game has three Nash equilibria: SwimSwim, HikeHike, and (Swim,2/3;Hike,1/3)(Swim,1/3;Hike,2/3). Note that the mixed strategies differ for each player in the third equilibrium: each goes to their preferred activity with 2/3 probability.
All of the equilibria are Pareto optimal this time, so that does not help for selection. Only the mixed strategy equilibrium results in equal expected utilities for the two players, so if both value equality or symmetry, this might be the focal point. But of course it will be difficult for Roy and Jen to see that unless they have studied game theory!