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.

 

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.

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).

 

Figure 3:

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.

Biography

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.