Repeated Games - Revision history

Julian.garcia at 09:28, 21 October 2011

Julian.garcia — Fri, 21 Oct 2011 09:28:28 GMT

← Older revision		Revision as of 09:28, 21 October 2011
Line 1:		Line 1:
	[[Category:Repeated Games]]		[[Category:Repeated Games]]
-	This project studies the evolution of cooperation in a repeated prisoner's dilemma with discounting. A version of the paper can be downloaded [http://www.tinbergen.nl/ti-publications/discussion-papers.php?paper=1587 here] ~~The online material that accompanies the paper is [http://staff.feweb.vu.nl/j.garcia/docs/RepeatedGamesOnlineMaterial.pdf here] in PDF format.~~	+	This project studies the evolution of cooperation in a repeated prisoner's dilemma with discounting. A version of the paper can be downloaded [http://www.tinbergen.nl/ti-publications/discussion-papers.php?paper=1587 here]

	= Run the simulations =		= Run the simulations =

-	You can download the software [http://~~staff~~.~~feweb~~.vu.nl/j.garcia/~~software~~/RepeatedGamesOnline.jar here]. Once the program is running just click on the big ''play'' button to start the fun. Feel free to re-arrange and re-size the windows, zoom-in and out as the program is running. Click [[Repeated Games Simulation \| here]] if you need more information about running this program.	+	You can download the software [http://www.evolbio.mpg.de/~garcia/jars/RepeatedGamesOnline.jar here]. Once the program is running just click on the big ''play'' button to start the fun. Feel free to re-arrange and re-size the windows, zoom-in and out as the program is running. Click [[Repeated Games Simulation \| here]] if you need more information about running this program.

	= The simulation program =		= The simulation program =

Julian.garcia: /* Measures of cooperativeness and reciprocity */

Julian.garcia — Thu, 21 Apr 2011 10:37:39 GMT

Measures of cooperativeness and reciprocity

← Older revision		Revision as of 10:37, 21 April 2011
Line 36:		Line 36:

	[[File:RepeatedGamesLifecycle.png\|650px\|center\|thumb\|Lifecycle]]		[[File:RepeatedGamesLifecycle.png\|650px\|center\|thumb\|Lifecycle]]
		+
		+	= Mutations =
		+
		+	Possible mutations are adding (randomly constructed) states , deleting states (if the array has more than one state), and reassigning destination states at random. On deleting a state the transitions are rewired to the remaining states. The following video shows an example path of mutations:
		+
		+	<center>
		+	{{#ev:youtube\|mPUrB8aFFuI\|450}}
		+	</center>
		+

	= Measures of cooperativeness and reciprocity =		= Measures of cooperativeness and reciprocity =

Julian.garcia: /* What are strategies? */

Julian.garcia — Thu, 21 Apr 2011 10:36:39 GMT

What are strategies?

← Older revision		Revision as of 10:36, 21 April 2011
Line 16:		Line 16:
	[[File:grimTriggerFSA.png\|300px\|thumb\|center\|Example Finite State Automata (Grim Trigger)]]		[[File:grimTriggerFSA.png\|300px\|thumb\|center\|Example Finite State Automata (Grim Trigger)]]

		+	The computer representation of the automate above is an array with the following values:
		+
		+	<center>
		+	'''[C, 0, 1 \| D, 1, 1]'''
		+	</center>
		+
		+
		+
		+	Each array position represents a state. Every state codes for an action and two indexes, where to go on cooperation, and where to go on defection. The first state (indexed 0) codes the action for the empty game history.
	Go to [[Computer representation of strategies for repeated games]] to see more details and more ways to represent strategies.		Go to [[Computer representation of strategies for repeated games]] to see more details and more ways to represent strategies.

Julian.garcia: /* The best responder */

Julian.garcia — Mon, 06 Sep 2010 13:05:37 GMT

The best responder

← Older revision		Revision as of 13:05, 6 September 2010
Line 81:		Line 81:
	In order to be able to determine if a finite automaton - and hence a pure strategy - is a Nash equilibrium, we have constructed a small routine in the program called the best responder. This routine finds the payoff of the best response against strategy <math>S</math>, as well as a best response. If the payoff of <math>S</math> against itself equals this payoff, then <math>S</math> is a Nash equilibrium. This is a useful device, since the infinity of the strategy space does not allow us to simply compare the payoff of <math>S</math> against itself to the payoff of all other strategies against <math>S</math> one after the other.		In order to be able to determine if a finite automaton - and hence a pure strategy - is a Nash equilibrium, we have constructed a small routine in the program called the best responder. This routine finds the payoff of the best response against strategy <math>S</math>, as well as a best response. If the payoff of <math>S</math> against itself equals this payoff, then <math>S</math> is a Nash equilibrium. This is a useful device, since the infinity of the strategy space does not allow us to simply compare the payoff of <math>S</math> against itself to the payoff of all other strategies against <math>S</math> one after the other.

-	Suppose strategy <math>S</math> is an automaton with <math>K</math> states. Any state <math>k</math> is characterized by an action played by <math>S</math> when it finds itself in this state, and a list of transitions as a function of the action played by the opponent of <math>S</math>. With a slightly abusive notation - <math>S</math> is a function of histories elsewhere, while here it is easier to make it a function of states - we will write the first as <math>S:{ 1,...,K} \rightarrow A</math> and the latter as <math>t_{k}:A\rightarrow { 1,...,K}</math>, <math>k=1,...,K</math>.	+	Suppose strategy <math>S</math> is an automaton with <math>K</math> states. Any state <math>k</math> is characterized by an action played by <math>S</math> when it finds itself in this state, and a list of transitions as a function of the action played by the opponent of <math>S</math>. With a slightly abusive notation - <math>S</math> is a function of histories elsewhere, while here it is easier to make it a function of states - we will write the first as
		+
		+
		+	<math>S:{ 1,...,K} \rightarrow A</math>
		+
		+	and the latter as
		+
		+	<math>t_{k}:A\rightarrow { 1,...,K}</math>, <math>k=1,...,K</math>.

	The value of being in state <math>k</math> is denoted by <math>V(k)</math>. We aim to find a solution to the following system:		The value of being in state <math>k</math> is denoted by <math>V(k)</math>. We aim to find a solution to the following system:

Julian.garcia: /* The best responder */

Julian.garcia — Mon, 06 Sep 2010 13:03:25 GMT

The best responder

← Older revision		Revision as of 13:03, 6 September 2010
Line 81:		Line 81:
	In order to be able to determine if a finite automaton - and hence a pure strategy - is a Nash equilibrium, we have constructed a small routine in the program called the best responder. This routine finds the payoff of the best response against strategy <math>S</math>, as well as a best response. If the payoff of <math>S</math> against itself equals this payoff, then <math>S</math> is a Nash equilibrium. This is a useful device, since the infinity of the strategy space does not allow us to simply compare the payoff of <math>S</math> against itself to the payoff of all other strategies against <math>S</math> one after the other.		In order to be able to determine if a finite automaton - and hence a pure strategy - is a Nash equilibrium, we have constructed a small routine in the program called the best responder. This routine finds the payoff of the best response against strategy <math>S</math>, as well as a best response. If the payoff of <math>S</math> against itself equals this payoff, then <math>S</math> is a Nash equilibrium. This is a useful device, since the infinity of the strategy space does not allow us to simply compare the payoff of <math>S</math> against itself to the payoff of all other strategies against <math>S</math> one after the other.

-	Suppose strategy <math>S</math> is an automaton with <math>K</math> states. Any state <math>k</math> is characterized by an action played by <math>S</math> when it finds itself in this state, and a list of transitions as a function of the action played by the opponent of <math>S</math>. With a slightly abusive notation - <math>S</math> is a function of histories elsewhere, while here it is easier to make it a function of states - we will write the first as <math>S:{ 1,...,K} \rightarrow A</math> and the latter as <math>t_{k}:A\rightarrow { 1,...,K}</math>, \ <math>k=1,...,K</math>.	+	Suppose strategy <math>S</math> is an automaton with <math>K</math> states. Any state <math>k</math> is characterized by an action played by <math>S</math> when it finds itself in this state, and a list of transitions as a function of the action played by the opponent of <math>S</math>. With a slightly abusive notation - <math>S</math> is a function of histories elsewhere, while here it is easier to make it a function of states - we will write the first as <math>S:{ 1,...,K} \rightarrow A</math> and the latter as <math>t_{k}:A\rightarrow { 1,...,K}</math>, <math>k=1,...,K</math>.

	The value of being in state <math>k</math> is denoted by <math>V(k)</math>. We aim to find a solution to the following system:		The value of being in state <math>k</math> is denoted by <math>V(k)</math>. We aim to find a solution to the following system:

Julian.garcia: /* Measures of cooperativeness and reciprocity */

Julian.garcia — Wed, 28 Apr 2010 13:16:30 GMT

Measures of cooperativeness and reciprocity

← Older revision		Revision as of 13:16, 28 April 2010
Line 50:		Line 50:
	File:NegativeHandshakeFSA.png		File:NegativeHandshakeFSA.png
	File:TitForTat.png \|Tit for Tat		File:TitForTat.png \|Tit for Tat
-	~~File:TatForTitFSA.png~~
-	~~File:TatForTit.png \| Tat for Tit~~
	File:TitForTatFSA.png		File:TitForTatFSA.png
		+	File:TatForTit.png \| Tat for Tit
		+	File:TatForTitFSA.png
	File:TitForTwoTats.png \| Tit for two Tats		File:TitForTwoTats.png \| Tit for two Tats
	File:TitForTwoTatsFSA.png		File:TitForTwoTatsFSA.png

Julian.garcia: /* The best responder */

Julian.garcia — Tue, 27 Apr 2010 15:39:04 GMT

The best responder

← Older revision		Revision as of 15:39, 27 April 2010
Line 127:		Line 127:


-	The best responder gives us both the maximum payoff <math>(1-\delta) V^{\ast}(1)</math> when playing against <math>S</math>, and an optimal strategy when playing against $S$, as $a_{k}^{\ast }$ prescribes what to play when <math>S</math> is in state <math>k</math>. For numerical reasons, we actually use the latter. It is important for us to determine whether or not the payoff of <math>S</math> against itself is exactly equal to the maximum payoff when playing against <math>S</math>. The iteration with which the best responder finds the latter can have a numerical inaccuracy in it, and the evaluating the payoff of two given strategies against each other (here: <math>S</math> against <math>S</math>) can too. These are however different inaccuracies, so in order to have the ''same'' inaccuracies in both, we use the strategy that the best responder gives, first let it play that against <math>S</math>, then let <math>S</math> play against itself, and compare the two payoffs. If they are equal, then <math>S</math> is a best response	+	The best responder gives us both the maximum payoff <math>(1-\delta) V^{\ast}(1)</math> when playing against <math>S</math>, and an optimal strategy when playing against <math>S</math>, as <math>a_{k}^{\ast }</math> prescribes what to play when <math>S</math> is in state <math>k</math>. For numerical reasons, we actually use the latter. It is important for us to determine whether or not the payoff of <math>S</math> against itself is exactly equal to the maximum payoff when playing against <math>S</math>. The iteration with which the best responder finds the latter can have a numerical inaccuracy in it, and the evaluating the payoff of two given strategies against each other (here: <math>S</math> against <math>S</math>) can too. These are however different inaccuracies, so in order to have the ''same'' inaccuracies in both, we use the strategy that the best responder gives, first let it play that against <math>S</math>, then let <math>S</math> play against itself, and compare the two payoffs. If they are equal, then <math>S</math> is a best response
	to itself.		to itself.

	Note that the computer program works with phenotypes, not with genotypes, so two different ways to encode for instance the strategy <math>AllD</math> will be treated as one and the same strategy.		Note that the computer program works with phenotypes, not with genotypes, so two different ways to encode for instance the strategy <math>AllD</math> will be treated as one and the same strategy.

Julian.garcia: /* Measures of cooperativeness and reciprocity */

Julian.garcia — Tue, 27 Apr 2010 14:37:25 GMT

Measures of cooperativeness and reciprocity

← Older revision		Revision as of 14:37, 27 April 2010
Line 37:		Line 37:

	An intuition for what this measure does can be gained from the following figures. The top bar represents the empty history. The second bar represents histories of length <math>1</math>, and is split in two; the history where the other has cooperated, and the one where the other has defected. The third bar represents histories of lenth <math>2</math>, and is split in four; the histories <math>CC</math>, <math>CD</math>, <math>DC</math> and <math>DD</math>. This continues indefinitely, but for the pictures we restrict ourselves to histories of length <math>5</math> or less. If a part is blue, then that means that the strategy reacts to this history with cooperation, if it is red, then the strategy reacts with defection. Cooperativeness weighs the blueness of those pictures.		An intuition for what this measure does can be gained from the following figures. The top bar represents the empty history. The second bar represents histories of length <math>1</math>, and is split in two; the history where the other has cooperated, and the one where the other has defected. The third bar represents histories of lenth <math>2</math>, and is split in four; the histories <math>CC</math>, <math>CD</math>, <math>DC</math> and <math>DD</math>. This continues indefinitely, but for the pictures we restrict ourselves to histories of length <math>5</math> or less. If a part is blue, then that means that the strategy reacts to this history with cooperation, if it is red, then the strategy reacts with defection. Cooperativeness weighs the blueness of those pictures.
-
	<center>		<center>
	<gallery>		<gallery>
	File:AlwaysCooperate.png \| Always Cooperate		File:AlwaysCooperate.png \| Always Cooperate
		+	File:AlwaysCooperateFSA.png
	File:AlwaysDefect.png \| Always Defect		File:AlwaysDefect.png \| Always Defect
		+	File:AlwaysDefectFSA.png
	File:FirstMove.png \| Condition on first move		File:FirstMove.png \| Condition on first move
		+	File:ConditionOnFirstMoveFSA.png
	File:GrimTrigger.png \| Grim Trigger		File:GrimTrigger.png \| Grim Trigger
		+	File:GrimTriggerFSA.png
	File:NegativeHandshake.png \| Negative Handshake (DTFT)		File:NegativeHandshake.png \| Negative Handshake (DTFT)
		+	File:NegativeHandshakeFSA.png
	File:TitForTat.png \|Tit for Tat		File:TitForTat.png \|Tit for Tat
		+	File:TatForTitFSA.png
	File:TatForTit.png \| Tat for Tit		File:TatForTit.png \| Tat for Tit
		+	File:TitForTatFSA.png
	File:TitForTwoTats.png \| Tit for two Tats		File:TitForTwoTats.png \| Tit for two Tats
		+	File:TitForTwoTatsFSA.png
	File:Wsls.png \| Win stay lose shift		File:Wsls.png \| Win stay lose shift
		+	File:WslsFSA.png
	</gallery>		</gallery>
	</center>		</center>
Line 55:		Line 63:

	[[Measuring Cooperation and Reciprocity \| See in more detail how the measures are defined]].		[[Measuring Cooperation and Reciprocity \| See in more detail how the measures are defined]].
-

	= Analyzing the simulation output =		= Analyzing the simulation output =

Julian.garcia: /* What are strategies? */

Julian.garcia — Tue, 27 Apr 2010 13:34:08 GMT

What are strategies?

← Older revision		Revision as of 13:34, 27 April 2010
Line 16:		Line 16:
	[[File:grimTriggerFSA.png\|300px\|thumb\|center\|Example Finite State Automata (Grim Trigger)]]		[[File:grimTriggerFSA.png\|300px\|thumb\|center\|Example Finite State Automata (Grim Trigger)]]

-	Go to [Computer representation of strategies for repeated games] to see more details and more ways to represent strategies.	+	Go to [[Computer representation of strategies for repeated games]] to see more details and more ways to represent strategies.

	== The simulation ==		== The simulation ==

Julian.garcia: /* What are strategies? */

Julian.garcia — Tue, 27 Apr 2010 13:33:53 GMT

What are strategies?

← Older revision		Revision as of 13:33, 27 April 2010
Line 15:		Line 15:

	[[File:grimTriggerFSA.png\|300px\|thumb\|center\|Example Finite State Automata (Grim Trigger)]]		[[File:grimTriggerFSA.png\|300px\|thumb\|center\|Example Finite State Automata (Grim Trigger)]]
		+
		+	Go to [Computer representation of strategies for repeated games] to see more details and more ways to represent strategies.

	== The simulation ==		== The simulation ==