Basic prisoner's dilemma?

[theglazeb]

Hi there!

I was wondering if you were able to help with me a basic prisoner's
dilemma strategy? How would I implement a basic tit for tat strategy?
And perhaps try to avoid the "death spiral" from occurring when two
players use the tit for tat strategy?

See below

Thanks!

/*
* File: PDStrategy.java
* ---------------------
* This class encapsulates the strategy for an Iterated Prisoner's
* Dilemma game. To enter the contest, all you have to do is change
* the definition of chooseAction so that it takes account of the
* history and does something more clever than cooperating (or
* defecting) all the time.
*/

import java.util.*;

class PDStrategy {

/*
* Method: chooseAction
* --------------------
* This method determines the player's action for the current
* game, based on two ArrayLists containing the history of play:
* one for your algorithm and one for the opponent. Each of these
* ArrayLists contains strings, which are guaranteed to be one of
* the uppercase strings "COOPERATE" or "DEFECT". Your method
* should look at the history and return one of those two strings
* representing the action you take on the current round.
*/

public String chooseAction(ArrayList<String> myHistory,
ArrayList<String> oppHistory) {
return "COOPERATE"; //currently, it is only cooperating
}

}

 

[Lew]

I was wondering if you were able to help with me a basic prisoner's
dilemma strategy? How would I implement a basic tit for tat strategy?
And perhaps try to avoid the "death spiral" from occurring when two
players use the tit for tat strategy?

See below

Thanks!

/*
* File: PDStrategy.java
* ---------------------
* This class encapsulates the strategy for an Iterated Prisoner's
* Dilemma game. To enter the contest, all you have to do is change

Tell us more about this contest. Where is it held? Do you have a link? What
can you win?

 

[Esmond Pitt]

Tell us more about this contest. Where is it held? Do you have a link?
What can you win?

.... and then tell us why we should help *you* rather than try to win it
ourselves. Prisoner's dilemma in fact ;-)

 

[theglazeb]

... and then tell us why we should help *you* rather than try to win it
ourselves. Prisoner's dilemma in fact ;-)

Thanks for the messages! This is a sample question from a competition
a couple of years ago. Someone passed it to me in my university
department passed it to me and suggested I try it out in order to
think more about prisoner's dilemma and learn java (I'm still a
novice, I'm afraid) I believe it may have been from
http://www.prisoners-dilemma.com/competition.html

So I am trying to figure out how I could create a tit for tat strategy
using an Arraylist. Or even a set of random outcomes based on the
history. Any help would be appreciated. The "win" for me in this case
is a better understanding of java.

You don't need to help if you don't want to, but of course it would be
appreciated. If don't want to help, it could be great if you could
point in me in the correct direction - how could make it output random
DEFECT or COOPERATE? and then following on that, how could I start
thinking about a Tit for Tat strategy?

Thanks so much!

 

[markspace]

You don't need to help if you don't want to, but of course it would be
appreciated. If don't want to help, it could be great if you could
point in me in the correct direction - how could make it output random
DEFECT or COOPERATE? and then following on that, how could I start
thinking about a Tit for Tat strategy?

The first thing you might want to do is to have clear in your mind what
"tit-for-tat" means, and also perhaps try to understand what the
Prisoner's Dilemma is really talking about. I found the Wikipedia
article very helpful, and of course I found that with Google.

Random: you can use Math.random() to generate random numbers.

Tit-for-tat, once you understand it, is just very basic array list
manipulation. I'll let you think on that part.

 

[Bent C Dalager]

And perhaps try to avoid the "death spiral" from occurring when two
players use the tit for tat strategy?

If both players use tit for tat then the death spiral doesn't ever
occur because both players start out by cooperating, and both players
continue cooperating.

The death spiral only occurs when one player deviates from tit for tat
for whatever reason and defects, while the other player continues a
straight tit for tat strategy, and the first player then also starts
adopting either tit for tat or always defect (which is effectively the
same thing in this case).

The obvious alternative to tit for tat in this situation is to
sometimes cooperate in spite of tit for tat dictating defect: either
by keeping track of the play history and doing periodic cooperates; or
alternatively by randomly cooperating (say, with 5% chance anytime you
would normally defect) if you don't want to keep track of state.

If memory serves, I think the general conclusion is that tit for tat
is always superior to trying to be clever, unless you have some
information about your opponent's algorithm (personality) that you can
exploit to your advantage.

Cheers,

Bent D

 

[Stefan Ram]

I was wondering if you were able to help with me a basic prisoner's
dilemma strategy? How would I implement a basic tit for tat strategy?

(It's spelled »tit-for-tat strategy«.)

This depends on the interface of the game.
First, specify the game interface.
Then, specify the player's algorithm on this game interface.

class Player implements GameFramework.Player
{ public void move( final Game game )
{ if( this.opponentProvokedIn( game ))this.retaliate( game );
else this.cooperate( game ); }
(...) }

 

[Daniele Futtorovic]

Hi there!

I was wondering if you were able to help with me a basic prisoner's
dilemma strategy? How would I implement a basic tit for tat strategy?
And perhaps try to avoid the "death spiral" from occurring when two
players use the tit for tat strategy?

See below

Thanks!

/*
* File: PDStrategy.java
* ---------------------
* This class encapsulates the strategy for an Iterated Prisoner's
* Dilemma game. To enter the contest, all you have to do is change
* the definition of chooseAction so that it takes account of the
* history and does something more clever than cooperating (or
* defecting) all the time.
*/

import java.util.*;

class PDStrategy {

/*
* Method: chooseAction
* --------------------
* This method determines the player's action for the current
* game, based on two ArrayLists containing the history of play:
* one for your algorithm and one for the opponent. Each of these
* ArrayLists contains strings, which are guaranteed to be one of
* the uppercase strings "COOPERATE" or "DEFECT". Your method
* should look at the history and return one of those two strings
* representing the action you take on the current round.
*/

public String chooseAction(ArrayList<String> myHistory,
ArrayList<String> oppHistory) {
return "COOPERATE"; //currently, it is only cooperating
}

}

Basic tit-for-tat is as follows:
- if it's the first time you encounter that opponent (this implies you
keep a 'memory' of previous encounters), cooperate.
- otherwise, replicate that opponent's last move.

In code (assuming oppHistory contains only the history with "this"):

public String chooseAction(
ArrayList<String> myHistory, ArrayList<String> oppHistory)
{
return oppHistory.isEmpty() ? "COOPERATE" : oppHistory.get(
oppHistory.size());
}
(or oppHistory.get(0), depending on whether it's used as a FIFO or a LIFO).


You can add various tricks, but don't expect to get far with them,
because tit-for-tat is the evolutionary stable strategy.

If you're interested in the topic apart from the programming aspect, I
*very* strongly suggest you read Dawkins' "Selfish Gene" and "Blind
Watchmaker". Even if you're not, by the way -- those are IMHO must-reads.

 

[Daniele Futtorovic]

Well spotted. Thanks, Lew.

 

[Lew]

Lew allegedly wrote: [snip]

Well spotted. Thanks, Lew.

HTH.

As a matter of good habit, I also suggest using interface-typed parameters to
the method, but that is not germane to the point of your example.

Inevitably my mind starts spinning coder fantasies even on these toy examples:

- "Wouldn't an enum base type and return type be better than String?"
- "What if we keep a rolling buffer of choices of size N rather than recording
all history?"
- "What if there were a third response possible (thus more reason to use an
enum), say, 'PREVARICATE'?"
- "What would that even mean?"
- "What if the choices were more like Rock-Paper-Scissors?"
- "What is the reward / cost for each combination of choices?"
- "What if that reward / cost increased or decreased with k, the number of
game rounds played so far?"
- "What is the terminating condition of the game?"

I'm firing these questions out without recently having reviewed the Prisoner's
Dilemma, but the simple form you describe is only the launching point.

 

[Daniele Futtorovic]

As a matter of good habit, I also suggest using interface-typed
parameters to the method, but that is not germane to the point of
your example.

I hesitated to make it a Queue to better prove the point.

Inevitably my mind starts spinning coder fantasies even on these toy
examples:

So does mine on similar occasions, but on this here matter that would be
missing the important point, which is the model the prisoner's dilemma
represents as well as what's an evolutionary stable strategy. I didn't
modify the original code to make it cleaner, like using an enum value as
the return and interface types, because I'd daresay it's more important
to understand what's behind the prisoner's dilemma than knowing how to code.

- "What if we keep a rolling buffer of choices of size N rather than
recording all history?"

Not necessarily. It would limit strategies if they couldn't look back as
far as they wanted, for the sake of algorithmic efficiency, which isn't
the point here at all.

- "What if there were a third response possible (thus more reason to
use an enum), say, 'PREVARICATE'?"

No. There are variants of the prisoner's dilemma, in different settings.
What's important is that the choice be to cooperate or not, that it be
a non-zero-sum game, and that the length of the game be not known.

- "What would that even mean?"

- "What if the choices were more like Rock-Paper-Scissors?"

That's a zero-sum game.

- "What is the reward / cost for each combination of choices?"

Factors may vary. Different weighing will slightly affect how quickly an
evolutionary stable strategy emerges. One and I believe the canonical
example is:
Both cooperate: both get three
One betrays: betrayer gets five, betrayed gets naught.
None cooperates: both get one

- "What if that reward / cost increased or decreased with k, the
number of game rounds played so far?"

It's important that the "passes" be interchangeable, non-ordered (if you
see what I mean).

- "What is the terminating condition of the game?"

There must be none. If you're ever in a prisoner's dilemma kind of
situation, and know that there are only a limited number of passes left,
there is only one viable strategy: betray.

 

[Lew]

There must be none. If you're ever in a prisoner's dilemma kind of
situation, and know that there are only a limited number of passes left,
there is only one viable strategy: betray.

Thank you for those informative answers, but the last one leaves me wondering
still about the terminating condition of the game. Obviously if there's a
payout (3/3, 5/0, 1/1), there must be an ending. What you've described is
that the players cannot know when that ending will occur, but surely it must
still eventually occur?

So one of the terminating conditions, or attributes of those conditions, is
player ignorance. What are the rest?

This time I don't ask that you feel obligated to answer this question - I will
certainly do the research. I am deeply grateful that you answered the other
questions - your answers were focused and helpful. But I had asked them
primarily to indicate the kinds of questions one might ask, whatever their
answers, and like the one I ask in this post, answers lead in turn to even
more questions.

For example, and I just offer it as an example and not something one is
required to answer just now, what is the effect of changing the payouts? What
if partial information were leaked to the prisoner's about release times, but
the prisoner has to guess how valid that information is? What if the
information about the other prisoner's responses is distorted, as happens in
real-life prisoner situations?

And I remain curious about game choices other than COOPERATE or BETRAY.

I plan to read up on all this now that the forum has sparked my interest.

 

[markspace]

Thank you for those informative answers, but the last one leaves me
wondering still about the terminating condition of the game. Obviously
if there's a payout (3/3, 5/0, 1/1), there must be an ending.

The payout in a traditional prisoner's dilemma is 2.5 years in jail if
the prisoner betrays, and 5.25 years in prison if he doesn't. That's
assuming equal chances of his partner in crime choosing to betray or not.

It's 0 years if he betrays and his partner doesn't, or 5 years each if
they both betray. Average: 2.5.

It's 6 months if neither betrays, or 10 years if only his partner does.
Average: 5.25.

What
you've described is that the players cannot know when that ending will
occur, but surely it must still eventually occur?

The trick is knowing that there are no rounds left. If you know that,
then the best strategy at the last round is to betray, because there's
no way your partner can retaliate. However, if you and your partner
both know when the last round is, then you'll both betray.

But if you know that you'll both betray on the last round, then there's
no incentive to cooperate on the n-1 round. So betray on that round
too. And then for the n-2 round, and the n-3 round, etc. Until you
might as well betray on all of them.

So one of the terminating conditions, or attributes of those conditions,
is player ignorance. What are the rest?

It's knowing when the rounds terminate that makes the difference.
Normally, the prisoners don't know how many rounds they'll go through.
But the rounds do terminate, usually after a fixed number of iterations.
But the prisoners don't know, it's "blind," someone else makes that
determination.

And I remain curious about game choices other than COOPERATE or BETRAY.

I plan to read up on all this now that the forum has sparked my interest.

The Wikipedia article is pretty good.

 

[Michael Wojcik]

If you're interested in the topic apart from the programming aspect, I
*very* strongly suggest you read Dawkins' "Selfish Gene" and "Blind
Watchmaker". Even if you're not, by the way -- those are IMHO must-reads.

Another nice work on the subject, particularly for someone with just a
casual interest who's looking for a light treatment, is William
Poundstone's _Prisoner's Dilemma_, which combines an introduction to
and history of game theory with biographical anecdotes about von
Neumann, Nash, and others.