Thursday, July 17, 2008

Another classic example of "dumb is smarter"

When I originally tried to come up with a list of "dumb is smarter" examples, I knew I was missing and at least one, and now I remember what it was.

The Iterated Prisoner's Dilemma is an abstract game, with many real examples or near-examples, in which
  • Two players repeatedly face a choice of acting generously, called "cooperating", or acting selfishly, called "defecting".
  • At any particular turn, they'll both do better if they both cooperate.
  • However, if only one cooperates and the other defects at that turn, the cooperator gets shafted.
  • Therefore, looking at a particular turn in isolation, the only rational choice is to defect, with the result that both players do less well than if they'd both cooperated.
  • However, since the choice is presented repeatedly, players have a chance to base their present actions on the results of previous turns.
It turns out that under these rules, rational players can agree to cooperate over the long term, even though it makes no sense in the short term ("it turns out that" is math-geek for "I don't want to go into the details"). It's an interesting result.

To probe this further, Robert Axelrod organized a tournament in which computer programs could compete with each other at the game. The tournament attracted considerable interest, and there were many competitors, some quite sophisticated in design.

And now the payoff: The winner, Anatol Rapaport's "tit-for-tat", consisted of four lines. Of BASIC. Its logic was:
  • Cooperate on the first turn.
  • After that, do whatever the other player did on the last turn.
This isn't an unbeatable strategy. It will lose, by just a bit, to "always defect", but the winner was determined by who had the best total result against all opponents. By always passing up the bigger gain of cooperating, "always defect" gets a low total score. Tit for tat does better than that when playing anyone who cooperates. It gets the best score possible when playing itself (or when playing "always cooperate" or anything else that always happens to cooperate when playing it).

In a later edition of the tournament, a team from Southampton University was able to beat tit-for-tat by having multiple copies of its program collude, but that's a different story (and even then who won depends on how you measure).

1 comment:

earl said...

Basic, f'crisake! How cool is that?