New Dilemmas for the Prisoner (2013)(americanscientist.org)
americanscientist.org
New Dilemmas for the Prisoner (2013)
http://www.americanscientist.org/issues/pub/new-dilemmas-for-the-prisoner
7 comments
A brief version of the story is contained in http://numerical.recipes/whp/on-iterated-prisoner-dilemma.ht...
Some further links:
Iterated Prisoner’s Dilemma contains strategies that dominate any evolutionary opponent
https://www.ncbi.nlm.nih.gov/pubmed/22615375
Extortion and cooperation in the Prisoner’s Dilemma
http://numerical.recipes/whp/StewartPlotkinExtortion2012.pdf
Zero-Determinant Strategies in the Iterated Prisoner’s Dilemma
https://golem.ph.utexas.edu/category/2012/07/zerodeterminant...
Iterated Prisoner’s Dilemma contains strategies that dominate any evolutionary opponent
https://www.ncbi.nlm.nih.gov/pubmed/22615375
Extortion and cooperation in the Prisoner’s Dilemma
http://numerical.recipes/whp/StewartPlotkinExtortion2012.pdf
Zero-Determinant Strategies in the Iterated Prisoner’s Dilemma
https://golem.ph.utexas.edu/category/2012/07/zerodeterminant...
Anyone have recommendation for good books on game theory or prisoner's deilemma's? I could see lots of variations on a theme, where you have:
* Precisely finite games (for example, exactly 100 games).
* Finite games where the number of games is random. How does strategy change when you know you'll be playing somewhere between 95-105 games vs. 60-140 games?
* Games where players can "pay" for awards or punishments out of their own fixed pot, instead of the externally set payoffs. What are good strategies for starting out with a small pot, vs. a large pot, and how to best cope with "inequality".
* Precisely finite games (for example, exactly 100 games).
* Finite games where the number of games is random. How does strategy change when you know you'll be playing somewhere between 95-105 games vs. 60-140 games?
* Games where players can "pay" for awards or punishments out of their own fixed pot, instead of the externally set payoffs. What are good strategies for starting out with a small pot, vs. a large pot, and how to best cope with "inequality".
Not a book, and I wish it wasn't so expensive, but this is excellent:
http://www.thegreatcourses.com/courses/games-people-play-gam...
Or a season format where only the highest scoring players make it to the championship, so there's more incentive to cooperate early.
This is low key some of the most profound research I've ever seen. It flies in the face of cold war era paranoid politics but: "the meek shall inherit the earth."
Except extortion works for a while. So while the meek wait for their inheritance, they are being kicked from pillar to post.
I'm pretty skeptical of the tournament referenced at the end of the article - specifically that tit-for-tat did so poorly.
http://lesswrong.com/lw/7f2/prisoners_dilemma_tournament_res...
http://lesswrong.com/lw/7f2/prisoners_dilemma_tournament_res...
(I wrote a fun little essay about Press & Dyson and Adami & Hintze for my scientific writing class last summer. The assignment was to write an essay of no more than 1000 words, intended for a non-scientific audience. Not sure if pasting it here is too much for HN etiquette, but it's not published anywhere else, so here goes. I hadn't read the article linked above when I wrote this, but it covers very similar ground in much simpler terms. Disclaimer: I didn't actually interview any of the researchers for the purpose of this short class assignment, so I was speculating a bit about their subjective states!)
Christoph Adami and Arend Hintze didn't believe what they were reading. The two evolutionary biologists suspected that something didn't quite add up in a 2012 article by two of the most influential physicists of our time, William Press and Freeman Dyson.[1] Press and Dyson claimed that they had discovered a mathematical trick that flew in the face of results from three decades earlier, which had so far stood the test of time.
The subject of their argument was a paradoxical "game" called the Prisoner's Dilemma. This game was invented half a century ago to challenge the tenets of game theory, a branch of mathematics beloved by economists and political scientists. In the Prisoner's Dilemma, two players face an awkward situation in which they cannot communicate but their choices affect each other. Each player must make a simple choice: Will you "cooperate" or will you "defect"?
The game is set up so that it presents a common dilemma faced in real life. The players will be better off if they both cooperate than if they both defect. But either player can gain an advantage by defecting when the other player cooperates. With every move, you are tempted to take advantage of the other player and afraid that they will take advantage of you, even though you both know that overall it's better to cooperate.
The Prisoner's Dilemma is reminiscent of any situation in which two individuals will share equally in the benefits of a shared activity. Cooperating then means giving it your all and defecting means slacking off. If you both cooperate then you both benefit from your hard work. If you both defect then there are no benefits to be had. Whenever the other player cooperates, however, you are better off defecting in order to benefit from their effort without exerting any yourself. Likewise, whenever the other player defects, then once again you are better off defecting yourself because it's not worth your effort to support them.
The paradox of the Prisoner's Dilemma is this: If it always seems better to defect, no matter what the other player does, how do we ever end up cooperating? This question, and therefore the Prisoner's Dilemma itself, is of prime interest to economists, political scientists, biologists, and many others. The standard answer from game theory was that a "rational" player would always defect, but some researchers suspected that cooperation might actually be favored by evolution in the long run.
In a crucial paper in 1981, political scientist Robert Axelrod and evolutionary biologist William Hamilton reported on a Prisoner's Dilemma tournament that Axelrod had conducted.[2] Axelrod invited dozens of researchers to submit computer programs that would play the game thousands of times. Hoping that the tournament would provide insights into how cooperation might evolve, he contacted one of its participants, biologist Richard Dawkins, who introduced him to Hamilton,[3] a biologist at Axelrod's own university who had published a research paper of his own about the Prisoner's Dilemma.
In the preceding decades, discussion of the Prisoner's Dilemma was largely philosophical. It was an interesting ethical puzzle, intriguingly simple and yet maddeningly difficult to reason about. With his computerized tournament, Axelrod advanced Prisoner's Dilemma research from mere philosophical argument to proper scientific experiment.
The result was stunning. The submitted programs displayed a wide variety of strategies -- some preferred to cooperate, some preferred to defect, some tried to outwit their opponents. But the winner was one of the simplest programs of all, called Tit-For-Tat. Its strategy was to always start out cooperating. As long as its opponent likewise cooperated, Tit-For-Tat happily went on cooperating, too. But as soon as its opponent defected, even for a single round, Tit-For-Tat followed along. Its choice for each move was whatever its opponent chose for the preceding move.
In Axelrod and Hamilton's summary of the tournament, they noted that all of the top programs shared Tit-For-Tat's preference for starting out cooperatively. The more aggressive programs effectively lost the trust of the others and missed out on the benefits of cooperation. Cooperation was vindicated once and for all. Axelrod and others have repeated the tournament with similar results.
Hence Adami and Hintze's skepticism reading Press and Dyson's claim, 31 years later, of discovering a new mathematical trick for playing the Prisoner's Dilemma along with a rigorous proof that it should beat the classic cooperative strategies. It was a fascinating mathematical theory, but how could it have gone unnoticed before?
Press and Dyson called their discovery "zero-determinant (ZD) strategies" because the technique involves causing a mathematical quantity known as a "determinant" to be zero. By manipulating this determinant, one player can limit how well the other player performs. The ZD player can choose a particular score for its opponent or can "extort" an unfair score for itself, averaged over a large number of rounds. Press and Dyson seemed to have overthrown cooperation as the star of Prisoner's Dilemma research.
ZD strategies came as a surprise to game theory experts, including Adami and Hintze. Press and Dyson's analysis was mathematically solid, but since it flew in the face of Axelrod's tournament results, something was missing. Adami and Hintze decided to run tournaments similar to Axelrod's, pitting ZD strategies against cooperative strategies to see how they evolved, publishing their results in 2013.[4]
Sure enough, coercive ZD strategies excelled in one-on-one competition but fared poorly in the tournament. Why? In a tournament, ZD strategies are competing against each other as well as non-ZD strategies. Just as Axelrod had learned three decades earlier, cooperative strategies reinforce each other while non-cooperative strategies are marginalized. Cooperation is vindicated once again!
That's not quite the end of the story, though. It turns out that ZD strategies can be generous as well as coercive. ZD players can influence their opponents to accept good scores as easily as bad scores -- and generous ZD strategies do just fine in a tournament setting. In fact, you're already familiar with one such strategy: the classic Tit-For-Tat itself is the "most fair" of all ZD strategies!
[1] "Iterated Prisoner's Dilemma contains strategies that dominate any evolutionary opponent," Proceedings of the National Academy of Sciences, volume 129, issue 26, pages 10409-10413.
[2] "The evolution of cooperation," Science, volume 211, issue 4489, pages 1390-1396.
[3] This introduction via Dawkins was described by Axelrod in 2012: "Launching 'the evolution of cooperation,'" Journal of Theoretical Biology, volume 299, pages 21-24.
[4] "Evolutionary instability of zero-determinant strategies demonstrates that winning is not everything," Nature Communications, volume 4, article number 2193.
Christoph Adami and Arend Hintze didn't believe what they were reading. The two evolutionary biologists suspected that something didn't quite add up in a 2012 article by two of the most influential physicists of our time, William Press and Freeman Dyson.[1] Press and Dyson claimed that they had discovered a mathematical trick that flew in the face of results from three decades earlier, which had so far stood the test of time.
The subject of their argument was a paradoxical "game" called the Prisoner's Dilemma. This game was invented half a century ago to challenge the tenets of game theory, a branch of mathematics beloved by economists and political scientists. In the Prisoner's Dilemma, two players face an awkward situation in which they cannot communicate but their choices affect each other. Each player must make a simple choice: Will you "cooperate" or will you "defect"?
The game is set up so that it presents a common dilemma faced in real life. The players will be better off if they both cooperate than if they both defect. But either player can gain an advantage by defecting when the other player cooperates. With every move, you are tempted to take advantage of the other player and afraid that they will take advantage of you, even though you both know that overall it's better to cooperate.
The Prisoner's Dilemma is reminiscent of any situation in which two individuals will share equally in the benefits of a shared activity. Cooperating then means giving it your all and defecting means slacking off. If you both cooperate then you both benefit from your hard work. If you both defect then there are no benefits to be had. Whenever the other player cooperates, however, you are better off defecting in order to benefit from their effort without exerting any yourself. Likewise, whenever the other player defects, then once again you are better off defecting yourself because it's not worth your effort to support them.
The paradox of the Prisoner's Dilemma is this: If it always seems better to defect, no matter what the other player does, how do we ever end up cooperating? This question, and therefore the Prisoner's Dilemma itself, is of prime interest to economists, political scientists, biologists, and many others. The standard answer from game theory was that a "rational" player would always defect, but some researchers suspected that cooperation might actually be favored by evolution in the long run.
In a crucial paper in 1981, political scientist Robert Axelrod and evolutionary biologist William Hamilton reported on a Prisoner's Dilemma tournament that Axelrod had conducted.[2] Axelrod invited dozens of researchers to submit computer programs that would play the game thousands of times. Hoping that the tournament would provide insights into how cooperation might evolve, he contacted one of its participants, biologist Richard Dawkins, who introduced him to Hamilton,[3] a biologist at Axelrod's own university who had published a research paper of his own about the Prisoner's Dilemma.
In the preceding decades, discussion of the Prisoner's Dilemma was largely philosophical. It was an interesting ethical puzzle, intriguingly simple and yet maddeningly difficult to reason about. With his computerized tournament, Axelrod advanced Prisoner's Dilemma research from mere philosophical argument to proper scientific experiment.
The result was stunning. The submitted programs displayed a wide variety of strategies -- some preferred to cooperate, some preferred to defect, some tried to outwit their opponents. But the winner was one of the simplest programs of all, called Tit-For-Tat. Its strategy was to always start out cooperating. As long as its opponent likewise cooperated, Tit-For-Tat happily went on cooperating, too. But as soon as its opponent defected, even for a single round, Tit-For-Tat followed along. Its choice for each move was whatever its opponent chose for the preceding move.
In Axelrod and Hamilton's summary of the tournament, they noted that all of the top programs shared Tit-For-Tat's preference for starting out cooperatively. The more aggressive programs effectively lost the trust of the others and missed out on the benefits of cooperation. Cooperation was vindicated once and for all. Axelrod and others have repeated the tournament with similar results.
Hence Adami and Hintze's skepticism reading Press and Dyson's claim, 31 years later, of discovering a new mathematical trick for playing the Prisoner's Dilemma along with a rigorous proof that it should beat the classic cooperative strategies. It was a fascinating mathematical theory, but how could it have gone unnoticed before?
Press and Dyson called their discovery "zero-determinant (ZD) strategies" because the technique involves causing a mathematical quantity known as a "determinant" to be zero. By manipulating this determinant, one player can limit how well the other player performs. The ZD player can choose a particular score for its opponent or can "extort" an unfair score for itself, averaged over a large number of rounds. Press and Dyson seemed to have overthrown cooperation as the star of Prisoner's Dilemma research.
ZD strategies came as a surprise to game theory experts, including Adami and Hintze. Press and Dyson's analysis was mathematically solid, but since it flew in the face of Axelrod's tournament results, something was missing. Adami and Hintze decided to run tournaments similar to Axelrod's, pitting ZD strategies against cooperative strategies to see how they evolved, publishing their results in 2013.[4]
Sure enough, coercive ZD strategies excelled in one-on-one competition but fared poorly in the tournament. Why? In a tournament, ZD strategies are competing against each other as well as non-ZD strategies. Just as Axelrod had learned three decades earlier, cooperative strategies reinforce each other while non-cooperative strategies are marginalized. Cooperation is vindicated once again!
That's not quite the end of the story, though. It turns out that ZD strategies can be generous as well as coercive. ZD players can influence their opponents to accept good scores as easily as bad scores -- and generous ZD strategies do just fine in a tournament setting. In fact, you're already familiar with one such strategy: the classic Tit-For-Tat itself is the "most fair" of all ZD strategies!
[1] "Iterated Prisoner's Dilemma contains strategies that dominate any evolutionary opponent," Proceedings of the National Academy of Sciences, volume 129, issue 26, pages 10409-10413.
[2] "The evolution of cooperation," Science, volume 211, issue 4489, pages 1390-1396.
[3] This introduction via Dawkins was described by Axelrod in 2012: "Launching 'the evolution of cooperation,'" Journal of Theoretical Biology, volume 299, pages 21-24.
[4] "Evolutionary instability of zero-determinant strategies demonstrates that winning is not everything," Nature Communications, volume 4, article number 2193.
"Last year’s big surprise in Prisoner’s Dilemma research came from two distinguished polymaths. William H. Press . . . [and] . . . Freeman J. Dyson . . . The story of how Press and Dyson came to make their discovery is almost as interesting as the result itself, but I have room here only for the latter."