Measuring Cooperation and Reciprocity - Revision history

Julian.garcia: /* Graphic interpretation */

2010-04-29T14:00:03Z

Graphic interpretation

← Older revision		Revision as of 14:00, 29 April 2010
Line 44:		Line 44:
	<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:TitForTatFSA.png
	File:TatForTit.png \| Tat for Tit		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:Wsls.png \| Win stay lose shift		File:Wsls.png \| Win stay lose shift
		+	File:WslsFSA.png
	</gallery>		</gallery>
	</center>		</center>

Julian.garcia: /* Density-dependent measures */

2010-04-22T23:51:05Z

Density-dependent measures

← Older revision		Revision as of 23:51, 22 April 2010
Line 148:		Line 148:
	In a population of <math>\alpha GRIM</math> and <math>(1-\alpha) TatForTit</math>, the reciprocity of <math>GRIM</math> is <math>\alpha +(1-\alpha) ( 1-\delta) =1-\delta +\alpha \delta </math>; in the latter interaction, <math>GRIM</math> only alters its behaviour in response to a change at <math>t=1</math>. So for not too large <math>\alpha</math> - implying that there is enough <math>TatForTit</math> to have a noticeable effect of the punishment being triggered - and not too small <math>\delta</math> <math>GRIM</math> now is actually less reciprocal than <math>TitForTat</math>.		In a population of <math>\alpha GRIM</math> and <math>(1-\alpha) TatForTit</math>, the reciprocity of <math>GRIM</math> is <math>\alpha +(1-\alpha) ( 1-\delta) =1-\delta +\alpha \delta </math>; in the latter interaction, <math>GRIM</math> only alters its behaviour in response to a change at <math>t=1</math>. So for not too large <math>\alpha</math> - implying that there is enough <math>TatForTit</math> to have a noticeable effect of the punishment being triggered - and not too small <math>\delta</math> <math>GRIM</math> now is actually less reciprocal than <math>TitForTat</math>.

-	Dependence on the population\ a strategy finds itself in can be seen as a good or a bad thing. For picking up indirect invasions, it seems to be a good thing; changes ''far off'' the current path of play between strategies do not change this reciprocity measure; it only changes if a strategy mutates into one that reacts differently to a one-step deviation. This implies that only becoming more or becoming less reciprocal in the way that is relevant for indirect invasions is picked up. On the other hand, it does not lend itself for a general, environment-independent statement of how reciprocal or cooperative a strategy is.	+	Dependence on the population a strategy finds itself in can be seen as a good or a bad thing. For picking up indirect invasions, it seems to be a good thing; changes ''far off'' the current path of play between strategies do not change this reciprocity measure; it only changes if a strategy mutates into one that reacts differently to a one-step deviation. This implies that only becoming more or becoming less reciprocal in the way that is relevant for indirect invasions is picked up. On the other hand, it does not lend itself for a general, environment-independent statement of how reciprocal or cooperative a strategy is.
		+
		+
		+	Another possibility is to only look at the actions directly after a one-step deviation. Then we would get
		+
		+	<math>R_{x}(S) =(1-\delta) \sum_{t=1}^{\infty}\delta ^{t-1} \sum_{i=1}^{N}x_{i}(\mathbf{1}_{{S(\overline{h}_{t}^{S,S_{i}},C) =C} }-\mathbf{1}_{{ S(\overline{h}_{t}^{S,S_{i}},D) =C} })</math>
		+
		+	Here the reciprocity of <math>AllC</math> is <math>0</math> again. The reciprocity of both <math>TFT</math> and <math>GRIM</math> in a population of <math>TFT</math>, <math>GRIM</math> and <math>AllC</math> is <math>1</math> here.

Julian.garcia: /* Density-dependent measures */

2010-04-22T23:46:10Z

Density-dependent measures

← Older revision		Revision as of 23:46, 22 April 2010
Line 134:		Line 134:

	<math>R_{x}(S) =(1-\delta)^{2} \sum_{t=1}^{\infty }\delta^{t-1}\sum_{i=1}^{N}x_{i}\sum_{s=0}^{\infty}\delta^{s}(\mathbf{1}_{{S(\overline{h}_{t,C,s}^{S,S_{i}}) =C} }-\mathbf{1}_{{S(\overline{h}_{t,D,s}^{S,S_{i}}) =C}})</math>		<math>R_{x}(S) =(1-\delta)^{2} \sum_{t=1}^{\infty }\delta^{t-1}\sum_{i=1}^{N}x_{i}\sum_{s=0}^{\infty}\delta^{s}(\mathbf{1}_{{S(\overline{h}_{t,C,s}^{S,S_{i}}) =C} }-\mathbf{1}_{{S(\overline{h}_{t,D,s}^{S,S_{i}}) =C}})</math>
		+
		+
		+	In a population of <math>GRIM</math> only, it is relatively easy to see that the reciprocity of <math>GRIM</math> is <math>1</math>; the path of play between <math>GRIM</math> and itself is just a sequence of <math>C</math>'s, while after a deviation <math>GRIM</math> just plays a sequence of <math>D</math>'s. So at any time <math>t</math>, the discounted difference between these sequence from then on, normalised by multiplying by one of the <math>t(1-\delta)</math>'s, is <math>1</math>. So discounting over <math>t</math> and normalizing by the other <math>( 1-\delta)</math> gives a reciprocity measure of <math>1</math>.
		+
		+	In a population of <math>TFT</math> only, the reciprocity of <math>TFT</math> is <math>\frac{1}{1+\delta }</math>. Again, the path of play between <math>TFT</math> and itself is a sequence of <math>C</math>'s, but now, on the path after any deviation, <math>TFT</math> plays a sequence of alternating <math>D</math>'s and <math>C</math>'s. So at any time <math>t</math>, the discounted and normalized difference between them is <math>(1-\delta) ( \frac{1}{1-\delta }-\frac{\delta }{1-\delta ^{2}}) =\frac{1}{1+\delta }</math>. So discounting over <math>t</math> and normalizing by the other <math>(1-\delta)</math> gives the same number.
		+
		+	This comparison is in line with what we might want from a reciprocity measure that depends on the actual population; at any stage, the threat that grim trigger poses to itself is maximal, and larger than the threat <math>TFT</math> poses to itself.
		+
		+	Another comparison shows that this measure also picks up the fact that, if the punishment in Grim Trigger is in fact triggered on the path of play, then on the remainder of the path, <math>GRIM</math> is actually not reciprocal at all anymore. With <math>TFT</math> on the other hand, reciprocity actually remains the same, whether the punishment has been triggered in the past or not. This is reflected in the following example.
		+
		+	In a population of <math>\alpha TitForTat</math> and <math>(1-\alpha) TatForTit</math>, the reciprocity of <math>TitForTat</math> is <math>\alpha \frac{1}{1+\delta }+( 1-\alpha) \frac{1}{1+\delta }=\frac{1}{1+\delta }</math>; the reciprocity of <math>TitForTat</math> against itself was computed above, and for the computation of <math>TitForTat</math> against <math>TatForTit</math> it is enough to realize that the comparison between actual and counterfactual is between <math>DCDC...</math> versus <math>CCCC...</math> at odd <math>t</math>'s and between <math>CDCD...</math> versus <math>DDDD...</math> at even <math>t</math>'s.
		+
		+	In a population of <math>\alpha GRIM</math> and <math>(1-\alpha) TatForTit</math>, the reciprocity of <math>GRIM</math> is <math>\alpha +(1-\alpha) ( 1-\delta) =1-\delta +\alpha \delta </math>; in the latter interaction, <math>GRIM</math> only alters its behaviour in response to a change at <math>t=1</math>. So for not too large <math>\alpha</math> - implying that there is enough <math>TatForTit</math> to have a noticeable effect of the punishment being triggered - and not too small <math>\delta</math> <math>GRIM</math> now is actually less reciprocal than <math>TitForTat</math>.
		+
		+	Dependence on the population\ a strategy finds itself in can be seen as a good or a bad thing. For picking up indirect invasions, it seems to be a good thing; changes ''far off'' the current path of play between strategies do not change this reciprocity measure; it only changes if a strategy mutates into one that reacts differently to a one-step deviation. This implies that only becoming more or becoming less reciprocal in the way that is relevant for indirect invasions is picked up. On the other hand, it does not lend itself for a general, environment-independent statement of how reciprocal or cooperative a strategy is.

Julian.garcia: /* Density-dependent measures */

2010-04-22T23:24:51Z

Density-dependent measures

← Older revision		Revision as of 23:24, 22 April 2010
Line 128:		Line 128:

	<math>h_{i+1}^{S,T}=(h_{i},a_{i}^{S,T}) ,\qquad ~\qquad \qquad \qquad \qquad i=t+1,...t+s</math>		<math>h_{i+1}^{S,T}=(h_{i},a_{i}^{S,T}) ,\qquad ~\qquad \qquad \qquad \qquad i=t+1,...t+s</math>
		+
		+	If <math>T(h_{i}^{S,T\leftarrow }) =a</math>, then this is <math>h_{t,a,s}^{S,T}</math> is just the actual history <math>h_{t+1+s}^{S,T}</math>, but if <math>T(h_{i}^{S,T\leftarrow }) \neq a</math>, it is a counterfactual history after a one-step deviation. The history <math>\overline{h}_{t,a,s}^{S,T}</math>, as above, just gives the actions of player <math>T</math> and ignores those of player <math>S</math>.
		+
		+	With this definition, we can make a measure for reciprocity as follows:
		+
		+	<math>R_{x}(S) =(1-\delta)^{2} \sum_{t=1}^{\infty }\delta^{t-1}\sum_{i=1}^{N}x_{i}\sum_{s=0}^{\infty}\delta^{s}(\mathbf{1}_{{S(\overline{h}_{t,C,s}^{S,S_{i}}) =C} }-\mathbf{1}_{{S(\overline{h}_{t,D,s}^{S,S_{i}}) =C}})</math>

Julian.garcia: /* Density-dependent measures */

2010-04-22T23:17:55Z

Density-dependent measures

← Older revision		Revision as of 23:17, 22 April 2010
Line 105:		Line 105:
	<math>C_{x}(S) =( 1-\delta) \sum_{t=1}^{\infty}\delta ^{t-1}(\sum_{i=1}^{N}x_{i}\mathbf{1}_{{ S(\overline{h}_{t}^{S,S_{i}}) =C}}) </math>		<math>C_{x}(S) =( 1-\delta) \sum_{t=1}^{\infty}\delta ^{t-1}(\sum_{i=1}^{N}x_{i}\mathbf{1}_{{ S(\overline{h}_{t}^{S,S_{i}}) =C}}) </math>

-	In ~~the~~ population with only <math>AllC</math>, <math>TFT</math> and <math>GRIM</math>, cooperativeness of all these three strategies is <math>1</math>. In an infinitely large population of <math>\alpha TFT</math> and <math>1-\alpha AllD</math>, cooperativeness of <math>TFT</math> is <math>1-\delta +\delta \alpha</math> .	+	In a population with only <math>AllC</math>, <math>TFT</math> and <math>GRIM</math>, cooperativeness of all these three strategies is <math>1</math>. In an infinitely large population of <math>\alpha TFT</math> and <math>(1-\alpha) AllD</math>, cooperativeness of <math>TFT</math> is <math>1-\delta +\delta \alpha</math> .
		+
		+	A reasonable way of measuring reciprocity is to compare actual histories with histories that would have unfolded after one-step deviations. So let <math>h_{t,a,s}^{S,T}</math> be the history that for the first <math>t-1</math> steps unfolds recurcively between strategy <math>S</math> and <math>T</math> - as above;
		+
		+	<math>h_{1}^{S,T}=()</math>
		+
		+	and the recursion step
		+
		+	<math>a_{i}^{S,T}=(S(h_{i}^{S,T}) ,T(h_{i}^{S,T\leftarrow}))</math>
		+
		+	<math>h_{i+1}^{S,T}=( h_{i},a_{i}^{S,T}) ,\qquad ~\qquad \qquad \qquad \qquad i=1,2,...,t-1</math>.
		+
		+	Only at time <math>t</math> the opponent plays <math>a</math>, while strategy <math>S</math> does not deviate and plays <math>S(h_{t}^{S,T})</math>;
		+
		+	<math>a_{t}^{S,T}=(S( h_{t}^{S,T}) ,a)</math>
		+
		+	<math>h_{t+1}^{S,T}=( h_{i},a_{t}^{S,T})</math>.
		+
		+	After that we go back to the normal recursion step
		+
		+	<math>a_{i}^{S,T}=(S( h_{i}^{S,T}) ,T(h_{i}^{S,T\leftarrow}))</math>
		+
		+	<math>h_{i+1}^{S,T}=(h_{i},a_{i}^{S,T}) ,\qquad ~\qquad \qquad \qquad \qquad i=t+1,...t+s</math>

Julian.garcia: /* Density-dependent measures */

2010-04-22T23:08:25Z

Density-dependent measures

← Older revision		Revision as of 23:08, 22 April 2010
Line 102:		Line 102:

	Suppose the population is given by a vector of frequencies <math>x=[x_{1},...,x_{N}]</math> where <math>x_{i}</math> is the frequency of strategy <math>S_{i}</math>. Then we define the population-dependent cooperativeness of a strategy <math>S</math> as follows:		Suppose the population is given by a vector of frequencies <math>x=[x_{1},...,x_{N}]</math> where <math>x_{i}</math> is the frequency of strategy <math>S_{i}</math>. Then we define the population-dependent cooperativeness of a strategy <math>S</math> as follows:
		+
		+	<math>C_{x}(S) =( 1-\delta) \sum_{t=1}^{\infty}\delta ^{t-1}(\sum_{i=1}^{N}x_{i}\mathbf{1}_{{ S(\overline{h}_{t}^{S,S_{i}}) =C}}) </math>
		+
		+	In the population with only <math>AllC</math>, <math>TFT</math> and <math>GRIM</math>, cooperativeness of all these three strategies is <math>1</math>. In an infinitely large population of <math>\alpha TFT</math> and <math>1-\alpha AllD</math>, cooperativeness of <math>TFT</math> is <math>1-\delta +\delta \alpha</math> .

Julian.garcia at 17:53, 22 April 2010

2010-04-22T17:53:08Z

← Older revision		Revision as of 17:53, 22 April 2010
Line 1:		Line 1:
	[[Category:Repeated Games]]		[[Category:Repeated Games]]
-	Here we formally define ~~measure~~ for cooperation and reciprocity.	+	Here we formally define measures for cooperation and reciprocity.

	= Introduction =		= Introduction =

Julian.garcia at 17:47, 22 April 2010

2010-04-22T17:47:54Z

← Older revision		Revision as of 17:47, 22 April 2010
Line 2:		Line 2:
	Here we formally define measure for cooperation and reciprocity.		Here we formally define measure for cooperation and reciprocity.

-	== Introduction ==	+	= Introduction =

	There are two reasons why we would like to have measures for cooperativeness and reciprocity. The first and most important reason is obvious; we would simply like to know how cooperative, and how reciprocal, strategies are during a run. The second reason is that these measures may serve as an indication of indirect invasions. Typically an indirect invasion is characterized by a change in reciprocity followed by a change in cooperativeness.		There are two reasons why we would like to have measures for cooperativeness and reciprocity. The first and most important reason is obvious; we would simply like to know how cooperative, and how reciprocal, strategies are during a run. The second reason is that these measures may serve as an indication of indirect invasions. Typically an indirect invasion is characterized by a change in reciprocity followed by a change in cooperativeness.

-	== Measuring cooperation ==	+	= Measuring cooperation =

	Any measure of cooperativeness will have to weigh the different histories, and as we will see, every choice how to weigh them has appealing properties		Any measure of cooperativeness will have to weigh the different histories, and as we will see, every choice how to weigh them has appealing properties
Line 36:		Line 36:
	The overall cooperativeness of a strategy <math>S</math> can then be defined as the cooperativeness at the beginning, where we have the empty history; <math>C(S) =C(S,\overline{h}_{1})</math>.		The overall cooperativeness of a strategy <math>S</math> can then be defined as the cooperativeness at the beginning, where we have the empty history; <math>C(S) =C(S,\overline{h}_{1})</math>.

-	=== Graphic interpretation ===	+	== Graphic interpretation ==


Line 55:		Line 55:
	</center>		</center>

-	=== Measure of cooperation for well-known strategies ===	+	== Measure of cooperation for well-known strategies ==

	It is obvious that <math>C(AllC) = 1</math> and that <math>C(AllD) = 0</math>. A strategy that starts with cooperation, and further conditions play on the first move entirely has cooperativeness <math>1-\frac{\delta }{2}</math>. This is sensible; if <math>\delta =0</math>, then the first move is the		It is obvious that <math>C(AllC) = 1</math> and that <math>C(AllD) = 0</math>. A strategy that starts with cooperation, and further conditions play on the first move entirely has cooperativeness <math>1-\frac{\delta }{2}</math>. This is sensible; if <math>\delta =0</math>, then the first move is the
Line 76:		Line 76:
	which is <math>1</math> at <math>\delta =0</math> for similar reasons, and goes to <math>0</math> if <math>\delta</math> goes to <math>1</math>.		which is <math>1</math> at <math>\delta =0</math> for similar reasons, and goes to <math>0</math> if <math>\delta</math> goes to <math>1</math>.

-	== Measuring reciprocity ==	+	= Measuring reciprocity =

	A measure for reciprocity can be constructed by comparing how much the cooperativeness of strategy <math>S</math> is changed if its opponent plays <math>D</math> rather than <math>C</math>. Again, histories of the same length are weighted equally here.		A measure for reciprocity can be constructed by comparing how much the cooperativeness of strategy <math>S</math> is changed if its opponent plays <math>D</math> rather than <math>C</math>. Again, histories of the same length are weighted equally here.
Line 84:		Line 84:
	In the figure above, this is visualized as the difference in blueness below two neighbouring bits that share their history up to the one before last period.		In the figure above, this is visualized as the difference in blueness below two neighbouring bits that share their history up to the one before last period.

-	=== Measure of reciprocity for well-known strategies ===	+	== Measure of reciprocity for well-known strategies ==

	Simple calculations now give that <math>R(AllC) =R(AllD) =0</math> and <math>R(TFT) =1</math>. Also, if we look at a strategy that only conditions on the first move and that defects forever if the first move of the other was <math>D</math>, and cooperates forever if the first move of the other was <math>C</math>, this strategy also has reciprocity <math>1</math>. It is not hard to see that <math>-1</math> and <math>+1</math> are in fact the lower and upper bounds for reciprocity with this equal weighing of all strategies of the same length.		Simple calculations now give that <math>R(AllC) =R(AllD) =0</math> and <math>R(TFT) =1</math>. Also, if we look at a strategy that only conditions on the first move and that defects forever if the first move of the other was <math>D</math>, and cooperates forever if the first move of the other was <math>C</math>, this strategy also has reciprocity <math>1</math>. It is not hard to see that <math>-1</math> and <math>+1</math> are in fact the lower and upper bounds for reciprocity with this equal weighing of all strategies of the same length.

Julian.garcia: /* Measuring reciprocity */

2010-04-22T17:46:30Z

Measuring reciprocity

← Older revision		Revision as of 17:46, 22 April 2010
Line 84:		Line 84:
	In the figure above, this is visualized as the difference in blueness below two neighbouring bits that share their history up to the one before last period.		In the figure above, this is visualized as the difference in blueness below two neighbouring bits that share their history up to the one before last period.

-	]=== Measure of reciprocity for well-known strategies ===	+	=== Measure of reciprocity for well-known strategies ===

	Simple calculations now give that <math>R(AllC) =R(AllD) =0</math> and <math>R(TFT) =1</math>. Also, if we look at a strategy that only conditions on the first move and that defects forever if the first move of the other was <math>D</math>, and cooperates forever if the first move of the other was <math>C</math>, this strategy also has reciprocity <math>1</math>. It is not hard to see that <math>-1</math> and <math>+1</math> are in fact the lower and upper bounds for reciprocity with this equal weighing of all strategies of the same length.		Simple calculations now give that <math>R(AllC) =R(AllD) =0</math> and <math>R(TFT) =1</math>. Also, if we look at a strategy that only conditions on the first move and that defects forever if the first move of the other was <math>D</math>, and cooperates forever if the first move of the other was <math>C</math>, this strategy also has reciprocity <math>1</math>. It is not hard to see that <math>-1</math> and <math>+1</math> are in fact the lower and upper bounds for reciprocity with this equal weighing of all strategies of the same length.

Julian.garcia: /* Density-dependent measures */

2010-04-22T17:26:57Z

Density-dependent measures

← Older revision		Revision as of 17:26, 22 April 2010
Line 99:		Line 99:
	= Density-dependent measures =		= Density-dependent measures =

-	Alternatively we could measure the cooperativeness and reciprocity of a strategy given the population it is in. In that case, we should not weight all histories of a given length equally, but in the proportions in which they do occur given the actual population of strategies. Hence the weight <math>(1/2)^{t-1}</math>, which is one divided by the number of strategies in <math>H_{t}</math>, will then be replaced by their actual proportions. For instance, in a population that consists of any mixture of <math>AllC</math>, <math>TFT</math> and <math>GRIM</math>, the only history at time <math>t</math> that occurs, is a sequences of <math>t-1</math> consecutive <math>C$'</math>. The measure for cooperativeness then simply becomes the expected times a strategy plays <math>C</math> divided by the expected number of rounds.	+	Alternatively we could measure the cooperativeness and reciprocity of a strategy given the population it is in. In that case, we should not weight all histories of a given length equally, but in the proportions in which they do occur given the actual population of strategies. Hence the weight <math>(1/2)^{t-1}</math>, which is one divided by the number of strategies in <math>H_{t}</math>, will then be replaced by their actual proportions. For instance, in a population that consists of any mixture of <math>AllC</math>, <math>TFT</math> and <math>GRIM</math>, the only history at time <math>t</math> that occurs, is a sequences of <math>t-1</math> consecutive <math>C'</math>s. The measure for cooperativeness then simply becomes the expected times a strategy plays <math>C</math> divided by the expected number of rounds.
		+
		+	Suppose the population is given by a vector of frequencies <math>x=[x_{1},...,x_{N}]</math> where <math>x_{i}</math> is the frequency of strategy <math>S_{i}</math>. Then we define the population-dependent cooperativeness of a strategy <math>S</math> as follows: