TFT KO'd by TSG in IPD

October 14, 2004 6:59 PM

Tit-for-tat dethronedin iterated prisoner's dilemma competition! But it might not work so well in RL, and what if you threw in QM? :D
posted by kliuless (10 comments total)

The summary of the Southampton approach is "self-sacrifice for the good of the group". This not only does work well in real life, it's very very common.

The only player the approach doesn't work for is the sacrificed character. Fill him up with enough well-chosen beliefs--or programming imperatives--and he'll do it anyway. Everybody else on his team profits.

However, I'm not sure it's "in the spirit of the game", so to speak. The programming competition was set up on an assumption that all characters personally want to win. If all programmers entering were explicitly allowed to field teams of characters, the competition would become more interesting and real-life applicable. Maybe they could even breed over generations ... but I think this idea is straying off the reservation and into the land of SimSomething.
posted by aeschenkarnos at 7:18 PM on October 14, 2004

[this is good]
posted by MzB at 7:37 PM on October 14, 2004

However, I'm not sure it's "in the spirit of the game", so to speak.

I thought the "spirit of the game" was to model how cooperating behaviors might be beneficial in a brutish world where competition seems the norm. In that respect, the Southampton approach seems very much in the spirit of the game.

From kliuless's "might not work so well in RL" link:

This does not seem to me at all an evolutionarily stable situation, however, since the slave agents have, by construction, exactly no incentive to participate in the arrangement.

On the contrary. Evolutionary success is determined at the gene level, not at the individual level. A prime example is sterile worker bees, who "sacrifice" (in the sense of not reproducing) themselves for the queen; this is a successful strategy because the queen shares genes with the workers. Thus, the workers' genes are passed on through their sacrifice, even though the workers themselves have no descendants.
posted by DevilsAdvocate at 7:45 PM on October 14, 2004

This is some nice lateral thinking. Selfishness is usually assumed to be one of the qualities of agents in the Prisoner's Dilemma. The idea that not everyone might be selfish is kind of revolutionary for this puzzle.
posted by Joey Michaels at 7:59 PM on October 14, 2004

One of the key tenets of the Prisoners' Dilemma [1]is that there is no way of communicating between the parties. Iterative versions change that -- you can see the results of the last exchange, and take advantage of that. Thus, the logical contradiction of the Prisoners' dilemma - that using logic to decide what to do leads you to a worse conclusion -- disappears.

Tit for Tat historically won because it tried to find strategies that would cooperate, and would cooperate with them. But Tit for Tat operated alone.

The equation changes dramatically if you can find out that a partner is involved, and work with them. Extend this to the original Dilemma -- your logical choice changes if you know what the other party chose.

That's what they've done here. It's a good hack, in the sense that "two players colluding can be one player who's not" but in terms of what we learn, it teaches us nothing we don't already know.

[1] I prefer the plural, because the Prisoners' Dilemma involves two prisoners.
posted by eriko at 7:55 AM on October 15, 2004

Once two Southampton players recognized each other, they were designed to immediately assume "master and slave" roles -- one would sacrifice itself so the other could win repeatedly.

If the program recognized that another player was not a Southampton entry, it would immediately defect to act as a spoiler for the non-Southampton player. The result is that Southampton had the top three performers -- but also a load of utter failures at the bottom of the table who sacrificed themselves for the good of the team.

Wouldn't the next step in this competition be to write a program that "mimics" a Southhampton master. Once the field is populated by mimics, it seems that tit-for-tat variations can win again. Sure, they can then change their "codes" but you'll have an endless information war escalation. Then they'll become sentient. :)
posted by vacapinta at 10:19 AM on October 15, 2004

vacapinta is exactly right. It is not too difficult to prove mathematically that there is no "best" entry in that given a specified program, it is always possible to create a new entry that will beat the specificied program. Contrary to popular wisdom, it is very easy to write a program that will beat Tit-for-tat. And the same must be true for this approach.

So the winner in one year may not be the winner next time.
posted by notme at 1:10 PM on October 15, 2004

vacapinta: Actually, that's kind of what they're getting at in the gridded version of the problem they talk about further down. The non-colluding agents adapt and become colluders... (Or, if you prefer, the hierarchical master-slave relation spreads through the population, manufacturing consent for the good of the few.)
posted by kaibutsu at 1:38 PM on October 15, 2004

What's all this about tits ? Be quiet, or the FCC will be on our ass !

( I do hope tit for tat is truly dethroned though )
posted by troutfishing at 3:42 PM on October 15, 2004

hmmmm... good points aeschenkarnos and DevilsAdvocate! i also just noticed on marginal revolution that sacrificial collusion was employed by the soviet chess team in int'l competition. so i guess the sticking point is how you define "evolutionarily stable," but i take your point that it's a practical strategy used in everyday life (if not the "long run," when we're all dead :)

Wouldn't the next step in this competition be to write a program that "mimics" a Southhampton master.

yeah, and that's actually what prof. shalizi proposed in the "might not work so well" link:

In fact, a mutant which used the coding scheme to recognize supposed masters and always defected against them, but played TFT with everyone else, should do better than a slave, and without slaves the master-type agents are not going to do well.

what was kinda intriguing to me was in the QM link:

...there is a basic problem with most of the studies of quantum games to date. Whatever the quantum game does can usually be accounted for within classical game theory, simply by appealing to a more complicated game structure. This is because quantum games can ultimately be represented by a classical number of players, strategies and pay-offs - precisely the objects studied in classical game theory. Quantum games therefore do not appear conceptually different from their classical counterparts.

which, to me, resonates with eriko's point that allowing communication removes the "dilemma" :D

Jens Eisert, Martin Wilkens and Marcus Lewenstein at the University of Potsdam in Germany proposed a quantized version of the prisoner's dilemma game (figure 3). They claimed that the resulting game possessed a unique Nash equilibrium that also yielded the maximum possible pay-offs - the game was said to be "Pareto optimal", a concept invented by the Italian economist Vilfredo Pareto. The players in the quantum game apparently managed to resolve the prisoner's dilemma!

and at that point i start to get lost... like i can sorta see how quantum entanglement and game theory (w/ info exchange allowed) can be analogous, but get to noise injection and error-correcting codes (quantum or otherwise!) and bewilderment sets in :D
posted by kliuless at 7:04 PM on October 15, 2004