Repeated games - Revision history

Xdvob13 at 22:14, 31 January 2014

2014-01-31T22:14:15Z

Xdvob13 at 12:32, 31 January 2014

2014-01-31T12:32:47Z

Xdvob13 at 12:23, 31 January 2014

2014-01-31T12:23:58Z

Xdvob13 at 12:16, 31 January 2014

2014-01-31T12:16:30Z

Xdvob13 at 12:04, 31 January 2014

2014-01-31T12:04:51Z

Xdvob13 at 13:28, 29 January 2014

2014-01-29T13:28:13Z

Xdvob13: /* Introduction */

2014-01-26T23:30:47Z

‎Introduction

Xdvob13: /* Introduction */

2014-01-26T23:29:55Z

‎Introduction

Xdvob13: /* Introduction */

2014-01-26T23:28:58Z

‎Introduction

Xdvob13: /* Introduction */

2014-01-26T23:28:29Z

‎Introduction

@@ Line 183: / Line 183: @@
-In infinitely-repeated games we can consider trigger strategies. A trigger strategy essentially threatens other players with a “worse,” punishment, action if they deviate from an implicitly agreed action profile.
+In infinitely-repeated games we can consider trigger strategies. <ref name="osborne" /> <ref name="asu" /> A trigger strategy essentially threatens other players with a “worse,” punishment, action if they deviate from an implicitly agreed action profile.
 A non-forgiving trigger strategy (or grim trigger strategy) s would involve this punishment forever after a single deviation. A non-forgiving trigger strategy (for player i) takes the following form:
@@ Line 246: / Line 246: @@
-'''strategies'''
+'''Strategies'''
@@ Line 296: / Line 296: @@
 <ref name="ecobeha">Copeland, A. H. (1945). "Review: Theory of Games and Economic Behavior by John von Neumann and Oskar Morgenstern". Bull. Amer. Math. Soc. 51 (07): 498–504.</ref>
 <ref name="hyskova">Hyšková, Magdalena (2011). Přednášky - Teorie her 6. Opakované hry. FD ČVÚT v Praze.</ref>
 <references/>
 </div>

@@ Line 87: / Line 87: @@
 === Theorem ===
-Consider repeated game G T (δ) for T < ∞. Suppose that the stage game G has a unique pure strategy equilibrium a∗. Then G T has a unique SPE. In this unique SPE, at = a∗ for each t = 0,1,..., T regardless of history.
+Consider repeated game G T (δ) for T < ∞. Suppose that the stage game G has a unique pure strategy equilibrium a∗. Then G T has a unique SPE. In this unique SPE, at = a∗ for each t = 0,1,..., T regardless of history. <ref name="osborne" />
@@ Line 96: / Line 96: @@
 The game has no predetermined length. Players act as though it will be played indefinitely or it ends only with some probability. This type of game is interesting but unlike finitely repeated they are not rare. How often we find a situation that we know exactly when it gonna ends and what it will be like? On the other hand, we routinely play many games that are infinitely repeated. Our goal is to find subgame perfect equilibrias in these types of games.
-Because we eliminated backward inducion from the model, now we can see that under these circumstances (neither player knows when the game ends) cooperation (strategy vector {N,N}) becomes the equilibrium solution for both players. As we know the solution is always not only one. In this case there is more equilibrium solutions and we call this Folk Theorems.
+Because we eliminated backward inducion from the model, now we can see that under these circumstances (neither player knows when the game ends) cooperation (strategy vector {N,N}) becomes the equilibrium solution for both players. As we know the solution is always not only one. In this case there is more equilibrium solutions and we call this Folk Theorems. <ref name="osborne" />
 The first folk theorem states that any attainable individual and rational pay-vector can be repeated game Nash equilibrium. Second folk theorem says that achievable payout vector that Pareto dominates any payroff vector of single game equilibrium can be SPE of repeated game.
@@ Line 102: / Line 102: @@
 === Strategies ===
-Unlinke finitely repeated there are many possible strategies to play. We discussed some of them above in the article. Lets just sum well-known strategies for repeated PD:
+Unlinke finitely repeated there are many possible strategies to play. We discussed some of them above in the article. Lets just sum well-known strategies for repeated PD: <ref name="hyskova" />
 * Always Cooperates
@@ Line 295: / Line 295: @@
 <ref name="axelrod2">Axelrod, Robert (1984), The Evolution of Cooperation, Basic Books, ISBN 0-465-02122-0.</ref>
 <ref name="ecobeha">Copeland, A. H. (1945). "Review: Theory of Games and Economic Behavior by John von Neumann and Oskar Morgenstern". Bull. Amer. Math. Soc. 51 (07): 498–504.</ref>
 <references/>
 </div>

@@ Line 18: / Line 18: @@
 === Application of game theory ===
-Game theory and mathematical analysis of behaviour have gained great popularity mainly due to a period of the WW2 and the Cold War. In 1944 John von Neumann and Oskar Morgenstern published famous  Theory of Games and Economic Behavior. This book explained how to use game theory for analyzing and developing optimal strategies for military, economy and other purposes. The Cold War was also a great period for game theory usage. US government funded teams that should analyze possible strategies and practices against the enemy. There were two hostile countries capable of total destruction of each other. This state is from view of game theory incredibly interesting. Lets assume the situation that one side lauches nuclear rockets. Rockets gonna hit targets in minutes so second side of conflict has the opportunity to launch counterattack. But it is really necessary to launch nuclear attack? In few minutes they are gonna be dead anyway so they don´t have to care what will be after them because even their children will be dead. So retaliatory nuclear strike would only killed milions of people. So what is the point of launching it? Revenge? And if not, what is the point of even having nuclear weapons? The fact is that not having the opportunity to fatal strike is already case of loosing in the Cold War. Many people today agrue if one of side would actually use nuclear weapons in no matter how escalated situation. Reason to have nuclear weapons is most definitely the threat. But what is the point of threat if our enemy know that we are not gonna use them. Well the enemy must not know this. That is the reason why US presindents and high-ranked military officiers were instructed to act on public a little "crazy and insane" to prove that they will launch the attack no matter what.
+Game theory and mathematical analysis of behaviour have gained great popularity mainly due to a period of the WW2 and the Cold War. In 1944 John von Neumann and Oskar Morgenstern published famous  Theory of Games and Economic Behavior. <ref name="ecobeha" /> This book explained how to use game theory for analyzing and developing optimal strategies for military, economy and other purposes. The Cold War was also a great period for game theory usage. US government funded teams that should analyze possible strategies and practices against the enemy. There were two hostile countries capable of total destruction of each other. This state is from view of game theory incredibly interesting. Lets assume the situation that one side lauches nuclear rockets. Rockets gonna hit targets in minutes so second side of conflict has the opportunity to launch counterattack. But it is really necessary to launch nuclear attack? In few minutes they are gonna be dead anyway so they don´t have to care what will be after them because even their children will be dead. So retaliatory nuclear strike would only killed milions of people. So what is the point of launching it? Revenge? And if not, what is the point of even having nuclear weapons? The fact is that not having the opportunity to fatal strike is already case of loosing in the Cold War. Many people today agrue if one of side would actually use nuclear weapons in no matter how escalated situation. Reason to have nuclear weapons is most definitely the threat. But what is the point of threat if our enemy know that we are not gonna use them. Well the enemy must not know this. That is the reason why US presindents and high-ranked military officiers were instructed to act on public a little "crazy and insane" to prove that they will launch the attack no matter what.
@@ Line 35: / Line 35: @@
-In 1981 Robert Axelrod published article dealing with the fundamental question: When should a person cooperate, and when should be person selfish, in an ongoing interaction with another person? He used a simple way to represent the type of situation that gives rise to these problems. He explained everything on the particular kind of game called the iterated Prisoner´s Dilemma.
+In 1981 Robert Axelrod published article dealing with the fundamental question: When should a person cooperate, and when should be person selfish, in an ongoing interaction with another person? He used a simple way to represent the type of situation that gives rise to these problems. He explained everything on the particular kind of game called the iterated Prisoner´s Dilemma. <ref name="axelrod1" />
-In the same year Robert Axelrod also held a computer tournament in which 15 different strategies for repeated prisoner's dilemma, sent by leading game theorists, competed with each in the game of 200 routes (total of 15 × 15 games). Payout was always calculated as the sum of the basis matrix:
+In the same year Robert Axelrod also held a computer tournament in which 15 different strategies for repeated prisoner's dilemma, sent by leading game theorists, competed with each in the game of 200 routes (total of 15 × 15 games). Payout was always calculated as the sum of the basis matrix: <ref name="axelrod2" />
@@ Line 49: / Line 49: @@
 ==== Strategie in the tournament ====
-In addition to the strategies '''Always Cooperates''' and '''Always Defects''' Axelrod divided strategies used into the following groups:
+In addition to the strategies '''Always Cooperates''' and '''Always Defects''' Axelrod divided strategies used into the following groups: <ref name="axelrod2" />
@@ Line 94: / Line 94: @@
 ==Infinitely Repeated Games==
-The game has no predetermined length. Players act as though it will be played indefinitely or it ends only with some probability. This type of game is interesting but unlike finitely repeated they are not rare. How often we find a situation that we know exactly when it gonna ends and what it will be like? On the other hand, we routinely play many games that are infinitely repeated. Our goal is to find subgame perfect equilibrias in these types of games. <ref> {{citation | first = Asu | last = Ozdaglar | contribution = Game Theory with Engineering Applications | title = MIT UDU 6.254: Lecture 15: Repeated Games | place = MIT | pages = 29 | date = 2010-04-01| id = | contribution-url = http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-254-game-theory-with-engineering-applications-spring-2010/lecture-notes/MIT6_254S10_lec15.pdf | format = PPT | accessdate = 2014-01-29}}</ref>
+The game has no predetermined length. Players act as though it will be played indefinitely or it ends only with some probability. This type of game is interesting but unlike finitely repeated they are not rare. How often we find a situation that we know exactly when it gonna ends and what it will be like? On the other hand, we routinely play many games that are infinitely repeated. Our goal is to find subgame perfect equilibrias in these types of games.
 Because we eliminated backward inducion from the model, now we can see that under these circumstances (neither player knows when the game ends) cooperation (strategy vector {N,N}) becomes the equilibrium solution for both players. As we know the solution is always not only one. In this case there is more equilibrium solutions and we call this Folk Theorems.
@@ Line 294: / Line 294: @@
 <ref name="axelrod1">Axelrod, Robert (1981). Science, New Series, Vol. 211, No. 4489. (Mar. 27, 1981), pp. 1390-1396.</ref>
 <ref name="axelrod2">Axelrod, Robert (1984), The Evolution of Cooperation, Basic Books, ISBN 0-465-02122-0.</ref>
 <references/>
 </div>

@@ Line 6: / Line 6: @@
-Game theory is often quoted by politicians to gave their opinios seriousness and as a way how to look smarter that they are. And it is also a great example of repeated game. Politicians like senators often vote about laws they propose. Options for the vote are support or not to support. If the vote was only a matter of good proposal/bad proposal, politicians would vote exactly the same. But because they follow their own goals the vote depends on many different things. Lets say that senator A propose a law that after the adoption brings a great popularity to him. But he needs senator B to support his proposal. So he asks senator B for support and he agrees only on the condition that he will in return later vote for his proposal. Regardless of what they promised to each other they now have several options. Senator B can vote for proposel and than expect support for his proposal or defect already in round 1, gain some profit from senator A not having that popularity but senator A will be probably angry and not support his proposal too. If he chooses to support him now have senator A some options. He has gained popularity for his law proposal and he can now return the favor or betray. Remember he already gained popularity so he can make additional profit from betraying his opponent. But if he do so he can probably expect revenge every time he wants to cooperate with senator B. There will be surely more voting in the future so what is the best strategy to maximize the payoff? That is the knowledge we gain from studying repeated games.
+Game theory is often quoted by politicians to gave their opinios seriousness and as a way how to look smarter that they are.<ref name="politician" /> And it is also a great example of repeated game. Politicians like senators often vote about laws they propose. Options for the vote are support or not to support. If the vote was only a matter of good proposal/bad proposal, politicians would vote exactly the same. But because they follow their own goals the vote depends on many different things. Lets say that senator A propose a law that after the adoption brings a great popularity to him. But he needs senator B to support his proposal. So he asks senator B for support and he agrees only on the condition that he will in return later vote for his proposal. Regardless of what they promised to each other they now have several options. Senator B can vote for proposel and than expect support for his proposal or defect already in round 1, gain some profit from senator A not having that popularity but senator A will be probably angry and not support his proposal too. If he chooses to support him now have senator A some options. He has gained popularity for his law proposal and he can now return the favor or betray. Remember he already gained popularity so he can make additional profit from betraying his opponent. But if he do so he can probably expect revenge every time he wants to cooperate with senator B. There will be surely more voting in the future so what is the best strategy to maximize the payoff? That is the knowledge we gain from studying repeated games.
 ==The Evolution of Cooperation==
@@ Line 12: / Line 12: @@
 The '''evolution of cooperation''' can refer to:
 * the study of how cooperation can emerge and persist (also known as cooperation theory) as elucidated by application of game theory
-* a 1981 paper by political scientist Robert Axelrod and evolutionary biologist W. D. Hamilton in the scientific literature
+* a 1981 paper by political scientist Robert Axelrod and evolutionary biologist W. D. Hamilton in the scientific literature <ref name="axelrod1" />
-* a 1984 book by Axelrod that expanded on the paper and popularized the study.
+* a 1984 book by Axelrod that expanded on the paper and popularized the study. <ref name="axelrod2" />
@@ Line 291: / Line 291: @@
 <references>
 <ref name="osborne">Osborne, Martin J.; Rubinstein, Ariel (1994). A Course in Game Theory. Cambridge: MIT Press. ISBN 0-262-15041-7.</ref>
 <references/>
 </div>

@@ Line 1: / Line 1: @@
 ==Introduction==
-In previous chapters of [[Game theory]] we introduced [[One-shot games]] like [[Prisoner's dilemma]]. In other words situations when we are allowed to do one action that result in some outcome (payoff). For example a situation when someone wants to enjoy fast car ride. If he drives really fast he enjoys fast ride and he´s happy but he also rist that police will catch him and arrest. So he must choose between driving fast or not fast according to his ulitily from one decision. But in the real world we often meet situations that repeat or their consequences affect other situations. We can say that our live is set of games in some order and we are playing them. And all of us know that this games, this situations repeat very often. We go to work every day or go shopping for example. Sequence of games that affect other games and are played by  the same players is called '''repeated game.'''
+In previous chapters of [[Game theory]] we introduced [[One-shot games]] like [[Prisoner's dilemma]]. In other words situations when we are allowed to do one action that result in some outcome (payoff). For example a situation when someone wants to enjoy fast car ride. If he drives really fast he enjoys fast ride and he´s happy but he also rist that police will catch him and arrest. So he must choose between driving fast or not fast according to his ulitily from one decision. But in the real world we often meet situations that repeat or their consequences affect other situations. We can say that our live is set of games in some order and we are playing them. And all of us know that this games, this situations repeat very often. We go to work every day or go shopping for example. Sequence of games that affect other games and are played by  the same players is called '''repeated game.''' <ref name="osborne" />
@@ Line 289: / Line 289: @@
 ==References==
-<div class='references-big'>
+<references>
 <references/>
 </div>

← Older revision		Revision as of 23:30, 26 January 2014
Line 1:		Line 1:
	==Introduction==		==Introduction==
−	In previous chapters of [[Game theory]] we introduced ~~one~~-shot games like [[Prisoner's dilemma]]. In other words situations when we are allowed to do one action that result in some outcome (payoff). For example a situation when someone wants to enjoy fast car ride. If he drives really fast he enjoys fast ride and he´s happy but he also rist that police will catch him and arrest. So he must choose between driving fast or not fast according to his ulitily from one decision. But in the real world we often meet situations that repeat or their consequences affect other situations. We can say that our live is set of games in some order and we are playing them. And all of us know that this games, this situations repeat very often. We go to work every day or go shopping for example. Sequence of games that affect other games and are played by the same players is called '''repeated game.'''	+	In previous chapters of [[Game theory]] we introduced [[One-shot games]] like [[Prisoner's dilemma]]. In other words situations when we are allowed to do one action that result in some outcome (payoff). For example a situation when someone wants to enjoy fast car ride. If he drives really fast he enjoys fast ride and he´s happy but he also rist that police will catch him and arrest. So he must choose between driving fast or not fast according to his ulitily from one decision. But in the real world we often meet situations that repeat or their consequences affect other situations. We can say that our live is set of games in some order and we are playing them. And all of us know that this games, this situations repeat very often. We go to work every day or go shopping for example. Sequence of games that affect other games and are played by the same players is called '''repeated game.'''

← Older revision		Revision as of 23:29, 26 January 2014
Line 1:		Line 1:
	==Introduction==		==Introduction==
−	In previous chapters of ~~game~~ theory we introduced one-shot games like [[Prisoner's dilemma]]. In other words situations when we are allowed to do one action that result in some outcome (payoff). For example a situation when someone wants to enjoy fast car ride. If he drives really fast he enjoys fast ride and he´s happy but he also rist that police will catch him and arrest. So he must choose between driving fast or not fast according to his ulitily from one decision. But in the real world we often meet situations that repeat or their consequences affect other situations. We can say that our live is set of games in some order and we are playing them. And all of us know that this games, this situations repeat very often. We go to work every day or go shopping for example. Sequence of games that affect other games and are played by the same players is called '''repeated game.'''	+	In previous chapters of [[Game theory]] we introduced one-shot games like [[Prisoner's dilemma]]. In other words situations when we are allowed to do one action that result in some outcome (payoff). For example a situation when someone wants to enjoy fast car ride. If he drives really fast he enjoys fast ride and he´s happy but he also rist that police will catch him and arrest. So he must choose between driving fast or not fast according to his ulitily from one decision. But in the real world we often meet situations that repeat or their consequences affect other situations. We can say that our live is set of games in some order and we are playing them. And all of us know that this games, this situations repeat very often. We go to work every day or go shopping for example. Sequence of games that affect other games and are played by the same players is called '''repeated game.'''

← Older revision		Revision as of 23:28, 26 January 2014
Line 1:		Line 1:
	==Introduction==		==Introduction==
−	In previous chapters of game theory we introduced one-shot games like [[~~Prisoner´s~~ dilemma]]. In other words situations when we are allowed to do one action that result in some outcome (payoff). For example a situation when someone wants to enjoy fast car ride. If he drives really fast he enjoys fast ride and he´s happy but he also rist that police will catch him and arrest. So he must choose between driving fast or not fast according to his ulitily from one decision. But in the real world we often meet situations that repeat or their consequences affect other situations. We can say that our live is set of games in some order and we are playing them. And all of us know that this games, this situations repeat very often. We go to work every day or go shopping for example. Sequence of games that affect other games and are played by the same players is called '''repeated game.'''	+	In previous chapters of game theory we introduced one-shot games like [[Prisoner's dilemma]]. In other words situations when we are allowed to do one action that result in some outcome (payoff). For example a situation when someone wants to enjoy fast car ride. If he drives really fast he enjoys fast ride and he´s happy but he also rist that police will catch him and arrest. So he must choose between driving fast or not fast according to his ulitily from one decision. But in the real world we often meet situations that repeat or their consequences affect other situations. We can say that our live is set of games in some order and we are playing them. And all of us know that this games, this situations repeat very often. We go to work every day or go shopping for example. Sequence of games that affect other games and are played by the same players is called '''repeated game.'''