and every day thereafter if no one has
ever defected, and defects otherwise.
Now supposing both Cain and Abel
use this strategy, I claim that neither
will ever defect, and hence they each
get a payoff of $30 for every day that the
game is played.
To prove that our strategies are in
equilibrium, we must show that no deviation benefits the players. Note that
on day i, the game is played with probability (1/2)i, so the total expected payoff is as appears in Figure 1.
Suppose someone, say Cain, deviates from the prescribed strategy and
let j be the first day on which Cain defects. Then on day j Abel will cooperate
and Cain gets $35. However from day
j + 1 onward, Abel will defect, and so
Cain’s payoff from day j + 1 onward is at
best $20. The maximal total payoff this
gives Cain appears in Figure 2.
Subtracting the two gives a positive
number, proving that the deviation did
not benefit Cain in terms of his total
payoff. In other words, when the game
has a chance of being played again, it’s
a good idea to cooperate. See Figure 3
for a short mathematical proof (
requiring a useful mathematical fact that appears in Figure 4).
SOCIAL GAMES AND APPLICATIONS
TO ONLINE MARKETS
While mathematically solid, the repeated games explanation doesn’t hold
in situations in which people act under
pseudonyms, such as over the Internet.
When all interactions are online, a person who develops a reputation for being uncooperative can simply re-enter
the system with a new name.
Here’s another reason people cooperate, as explained in a recent scientific article I co-authored with Brendan
Lucier and Brian Rogers. The troublesome component of the initial Cain/
Abel model, for us, was the moment
we squinted our eyes and imagined we
saw just two people. In reality there are
many people. Some are friends, and
some are enemies, and some don’t even
know each other. People are born and
die and their relationships evolve over
their lifetime. What’s missing from the
basic model, we felt, is the presence of
this evolving social network.
So we decided to add social networks to the game. We introduced the
notion of a continuous population of
players. Each person in our society
sponsors some set of relationships,
which can be broken arbitrarily at the
discretion of either partner. When a
relationship is broken, either because
someone ended it or because one of
the partners died, the sponsoring partner gets a new friend at random from
the population—one who knows nothing about his/her past. The number
of relationships a person sponsors is
thus constant, but his/her total number of relationships is not since people
can sponsor relationships to him/her.
This simulates real-life relationships:
maintaining a relationship usually
falls more heavily on one partner than
another, and people only have enough
time to maintain (sponsor) a fixed
number of these.
Each day, people play a game simi-
lar to the one discussed here in each
of their relationships. We add the re-
striction that a person must play the
same game in every relationship (that
is, your actions are public to all your
friends since they talk about you be-
hind your back and so if you cheat one
you may as well cheat them all). What
we observe is very interesting: in this
game most rational people cooperate,
and yet, as observed in practice, some
defect! The intuition for the result is
the following: defection has a clear
short-term gain. However, it also has a
long-term risk, namely, rational people
will break relationships with defec-
tors. In other words, by cooperating, a
person can build up a larger network
of friends thereby interacting in more
relationships, albeit for a smaller profit
per relationship than a defector. The
tension between these effects causes
an equilibrium in which most people
are nice, but some are mean.
Nicole Immorlica is an assistant professor in the
theoretical computer science group at Northwestern
University. She joined Northwestern in September 2008
after postdoctoral positions at Microsoft Research
in Redmond, WA, and Centruum voor Wiskunde en
Informatica (C WI) in Amsterdam, Netherlands. She
received her Ph.D. from MI T 2005. She is currently working
in the field of algorithmic game theory, where she uses
economic and algorithmic techniques to understand social
interactions in settings such as social net works, auctions,
and t wo-sided matching.