Sunday, October 01, 2006

prisoner's dilemma for P2P

Surely I can't be the first person to notice this, but the Prisoner's Dilemma has some applications to P2P. If you want a more thorough treatment of the Dilemma, look elsewhere. Here's the shorthand. There are two independent entities called A and B (or Alice and Bob, if you like). Each has the same choice between two possibilities that are generally called cooperate and defect. A and B don't know what the other will choose. The interesting part comes in the payoffs or profit margin of the four possible outcomes:
  1. If A cooperates and B cooperates, A and B each receive medium payoffs.
  2. If A cooperates and B defects, A receives a horribly low payoff and B receives a huge payoff.
  3. Similarly, if B cooperates and A defects, B receives a horribly low payoff and A receives a huge payoff.
  4. If A and B defect, A and B each receive low (but not horribly low) payoffs.
To summarize, A and B as a whole would do better if A and B cooperated, but the great risk of the other entity defecting means that the better choice (the choice with the better average payoff) for A as well as B is defecting. The Prisoner's Dilemma simply illustrates any "game" in which cooperation would be good for both players but a cooperation-defection situation would be disastrous for the cooperating player. If it helps, think of two hostile nations who must choose whether to disarm their nuclear weapons. Analytically, the more interesting case is if there are an unknown number of successive turns and payoffs, because the result of a cooperation-defection can be recovered from.

The Prisoner's Dilemma applies to P2P transactions in a limited way, if you consider the payoff to be the difference between downloads (positive) and uploads (negative). Assume A and B are two peers who wish to download something of equal value, normalized to be 1, that the other has (and everything's legal, yahda yahda yahda).
  1. If A uploads what B wants and B uploads what A wants, A and B both upload (-1) and download (1), so the payoff for each is 0.
  2. If A uploads what B wants and B does not upload, then A ends up with a payoff of -1, and B ends up with a payoff of 1.
  3. If A does not upload and B uploads what A wants, then A ends up with a payoff of 1, and B ends up with a payoff -1.
  4. If A does not upload and B does not upload, then no transaction occurs at all, so the payoff is 0.
Now it's clear how the Prisoner's Dilemma begins to fall apart as an analogy. For instance, the payoff for each entity in outcome 1 should be greater than the payoff in outcome 4. More importantly, we've only considered the "net transaction of value", and not the end result of the transaction, which is that either you have what you wanted or you don't, so the "result payoff" for each peer is as follows (assuming you didn't upload one half of an unobserved, entangled quantum pair, in which case your copy collapsed into an undesirable state when your downloader observed his copy):
  1. A and B both have what they wanted, in addition to what they uploaded, so each have a payoff of 1.
  2. A did not get what it wanted, but B did, so A's payoff is 0 and B's payoff is 1.
  3. A got what it wanted, but B did not, so A's payoff is 1 and B's payoff is 0.
  4. A and B both got nothing, a payoff of 0.
This scenario doesn't cover the situation of a peer wanting something but not having something that the other peers want. Also, unless any analysis can take into account an arbitrary number of peers and files, it won't directly map onto a real P2P network.

Nevertheless, the Prisoner's Dilemma shows that, assuming uploading or sharing has a cost, "leeches" are merely acting in a rational manner to maximize their individual payoff. So P2P systems that make it more rational, or even mandatory, to share stand a better chance of thriving. Specifically, if a peer downloads more than one item, the iterated or repeating Prisoner's Dilemma can come into play. A peer that acted as a leech for the last item could have some sort of penalty applied for the next item the peer downloads. Through this simple mechanism, known as Tit-for-Tat, cooperation becomes more attractive. Call it filesharing karma, only with a succession of files instead of lives. Any peer downloading its very last item would rationally defect on that item, because there would be no chance to receive a future penalty.

No comments:

Post a Comment