After watching The Dark Knight I became rather enthralled with the concept of the Prisoner's Dilemma. There must be an algorithm that that maximizes one's own gain given a situation.
For those that find this foreign: http://en.wikipedia.org/wiki/Prisoner%27s_dilemma
Very, very interesting stuff.
Edit: The question is, what is, if any, the most efficient algorithm that exists for the Prisoner's Dilemma?
The whole point of the dilemma is that the optimal solution (both prisoners stay quiet) is dangerous because part of the problem is out of your hands. So, choosing the suboptimal solution seems to maximize your gain, but it's still suboptimal
I don't see how an algorithm could supply a solution when part of the problem is the unknown.
Ah yes. This made me remember this old article about The Prisoner's Dilemma in Software Development
For an algorithmic PD competition look here
This was a good one too
The wikipedia page seems to give all the answers... for the one-time prisoner's dilemma, the most optimal solution for each prisoner (not both prisoners) is to betray.
For the iterated prisoner's dilemma, it is best to remain silent on the first go, and then after that do whatever the other prisoner did on the last go.
There isn't since you can not categorically predict the behavior of the second prisoner.
There are all sorts of "solutions" that make underlying but very restrictive assumptions about the behavior of the second prisoner, but they have little to say about the unconstrained problem (that's what makes it such a compelling dilemma).
My two cents, given that you can not rely on the second prisoners behavior is that it comes down to: are you a optimist, or a cynic? Are the two prisoners going to stick together (honor among thieves), or are they going to rat each other out at the first opportunity to save their own throat...?
Well, to my understanding, pattern recognition is a huge part of it as well. Finding the other prisoner's habit - how often he stays quiet and when he narcs. You also have to cross reference that to your own choices to determine what you did to make him react in a certain way.
I think its a little more complex than wiki explained. Its not just what the prisoner did on the last go, but on all goes before that stretching up to infinity.
Further, in an iterated prisoners' game the optimal strategy will vary based on the other strategies in play.
In a series against a player who ALWAYS defects always defecting is the best strategy. When playing against a player who might co-operate, a strategy that retaliates, but occasionally forgives is likely to be best.
I should add that this only applies in a game of unknown length. Any game of known length is identical to the single round game.
Attempting to find an optimal solution for the Prisoner's Dilemma is like trying to find one for Ro-Sham-Bo (rock-paper-scissors.) The best you can do is model your opponent and try to exploit patterns.
In the early days of game theory and computer science, John von Neumann and the Rand Corporation spent extensive amounts of skull sweat trying to come up with an optimal algorithm for resolving the Prisoner's Dilemma without success and, iirc, eventually proved mathematically that there was no optimal solution.
Since there is only one choice to make, and in the absence of any changeable inputs, your algorithm is either going to be:
cooperate = true;
...or...
cooperate = false
It's more interesting to find a strategy for the Iterated Prisoner's Dilemma, which is something many people have done. For example http://www.iterated-prisoners-dilemma.net/
Even then it's not 'solveable', since the other player is not predictable.
I recommend reading Axelrod's The Evolution of Cooperation. This is a computer experiment of competing strategies for the iterated prisoner's dilemma. When I heard of it last, the tit-for-tat strategy came out first. It may have changed.
The whole point of the prisoner's dilemma is that your optimal strategy is to betray the other prisoner. O(1)
For the one-off version of the game, the best strategy is always to defect since there is no chance of retaliation.
It gets more interesting for an iterated version since players can respond to their opponents' previous choices.
If we know in advance exactly how many rounds there will be, then the logical "best" strategy is still to defect always. This is because it always makes sense to defect on the last turn since there is no chance of retaliation. Of course, our rational opponent will know this and also always defect on the last turn. This makes it sensible for us to defect on the penultimate turn since there is no chance of cooperation on the final turn anyway. Following this logic to its natural conclusion, we should defect on every turn.
When the total number of rounds is unknown, things become more interesting. A good strategy for the game should try to predict what an opponent will do. I researched using evolutionary algorithms and simple machine learning with opponent modelling to generate strategies for the game for my masters degree. If you're really interested, you can read my thesis.
As recommended by Yuval, probably the best place to start is Axelrod's seminal book. If you're really, really interested in this stuff, there was a 20th anniversary follow-up that included a lot of the more recent work on IPD (the Iterated Prisoner's Dilemma) by other researchers.
Also, I'd thoroughly recommended William Poundstone's Prisoner's Dilemma, which is part biography of John von Neumann and part introduction to game theory.
Mathemaically the other posts answer the question, but in reality, there may be additional options. However absurd these options are, they will result in additional outcome possibilities, and they may result in increased chance of personal gains. For example, in Batman's case, it would ruin the plot, but he could have just killed the Joker -- thus ruining any additional effects the Joker would have on the outcome. By letting the Joker live, Batman unwittingly allows the Joker the only "victory" he needs.
The game becomes much more interesting when you step back and consider the whole tournament. For example, a few years back a PD tournament was won by a team from the UK which submitted multiple entries. One of them was the "master" and the other were "slaves". They would all start by playing a specific sequence of actions which would allow the masters and slaves to recognize each other. Once recognized the master would defect and the slave would cooperate for the rest of the iterations. Thus, the master won the tournament but at the cost of the slaves.
The strategy made economic sense as there was a monetary prize for first place but the cost of entry were low.
More generally, when writing a program for a TD tournament you need to look at the bigger picture:
Otherwise, yes, the dominant strategy is to defect in the one-shot PD. Axelrod, as others mentioned, showed that tit-for-tat was robust in a series of tournaments, but in these tournaments nobody thought about conspiring with other contestants.