Finitely Repeated Games

11 Key excerpts on "Finitely Repeated Games"

• 

  eBook - PDF

  Game Theory

  • Michael Maschler, Eilon Solan, Shmuel Zamir(Authors)
  • 2013(Publication Date)
  • Cambridge University Press

    (Publisher)

  13 Repeated games Chapter summary In this chapter we present the model of repeated games. A repeated game consists of a base game, which is a game in strategic form, that is repeated either finitely or infinitely many times. We present three variants of this model:  The finitely repeated game, in which each player attempts to maximize his average payoff.  The infinitely repeated game, in which each player attempts to maximize his long-run average payoff.  The infinitely repeated game, in which each player attempts to maximize his discounted payoff. For each of these models we prove a Folk Theorem, which states that under some technical conditions the set of equilibrium payoffs is (or approximates) the set of feasible and individually rational payoffs of the base game. We then extend the Folk Theorems to uniform equilibria for discounted inFinitely Repeated Games and to uniform ε-equilibria for Finitely Repeated Games. The former is a strategy vector that is an equilibrium in the discounted game, for every discount factor sufficiently close to 1, and the latter is a strategy vector that is an ε-equilibrium in all sufficiently long finite games. In the previous chapters, we dealt with one-stage games, which model situations where the interaction between the players takes place only once, and once completed, it has no effect on future interactions between the players. In many cases, interaction between players does not end after only one encounter; players often meet each other many times, either playing the same game over and over again, or playing different games. There are many examples of situations that can be modeled as multistage interactions: a printing office buys paper from a paper manufacturer every quarter; a tennis player buys a pair of tennis shoes from a shop in his town every time his old ones wear out; baseball teams play each other several times every season.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Game Theory and Society

  • Weiying Zhang(Author)
  • 2017(Publication Date)
  • Taylor & Francis

    (Publisher)

  The first choice will not influence the second choice. Of course, in reality this characteristic of repeated games cannot be strictly maintained. For example, repeated games exist between firms and customers, but the products produced by the firm and customer preferences will frequently change. Repeated games exist between China and the United States, but their internal structures and relative status in international relations are different at different times. However, “Tianji’s Horse Race” 3 is not a repeated game, because the horses chosen by Tianji and the King of Qi in the first round could not be used in the second round, so the choices in the first stage will influence the choices in the next round. Of course, if Tianji and the King of Qi are willing, they could hold a second horse race, which would be a repeated game. Second, each player can observe the game’s history or the things that happened in the previous stage games. For example, each player’s choice to cheat or be honest or cooperate or not cooperate in previous games is observable. 4 Third, each player cares for the total payoff which is the discounted value of payoff flow over all stage games. The significance of this is that because the game repeats multiple times, players do not only care about the current stage’s gains, but also gains in the future. This point causes them to have an incentive to choose differently than in one-time games. Repeated games are separated into Finitely Repeated Games and inFinitely Repeated Games. So-called “Finitely Repeated Games” refer to games that end after a certain time or number of occurrences, after which the related parties do not again engage in the same game. So-called “inFinitely Repeated Games” refer to games that will continue forever

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Game Theory

  A Modeling Approach

  • Richard Alan Gillman, David Housman(Authors)
  • 2019(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Chapter 7

  Repetitious Play

  The strategic, extensive, and bargaining games we have discussed so far assume that the players’ interactions are independent of any previous or future interaction. More realistically, players interact with each other multiple times in a variety of ways, and the actions they choose in one interaction are likely to depend upon past experience and predictions about future behavior. We examine models of repetitious play and features unique to these models. In particular, we examine the multiplicity of Nash equilibria and the robustness of qualitative behavior in different models.

  Up to this point, we have examined various models of games that may have multiple stages but ultimately are assumed to be played once. In this chapter, we will introduce repeated play games as a new mathematical modeling tool. Mathematically, all of these models are extensive games once we resolve how the payoffs in individual games are to be combined into a payoff for the repeated game. Nonetheless, the special properties of repeated play lead to special considerations (such as errors in perception and implementation) and interesting results (such as the ubiquity of equilibria). The dynamics of strategy choice that are passed on in a species also become a focus. We begin with the simplest of repeated games.

  Definition 7.0.1. A finite repeated game consists of the following:

  1.A game G with all of its embedded players, outcomes, rules, and utilities.

  2.An integer m ≥ 2.

  3.In stage k = 1, 2, …, m , the game G is played with all players knowing the actions chosen in the previous stage.

  4.Utilities for each player i are defined to be the mean of the utilities player i obtained in each stage of the repeated game.

  A common example of a game that can be extended to a finite repeated game is the Prisoner’s Dilemma game. When the Prisoner’s Dilemma game is played only once, players choose strategies with little information about how their opponent might behave, leading them to the Nash equilibrium which is not efficient. However, if we imagine partners in crime that find themselves in this dilemma often, we can see that over time they might develop a more informed strategy because they know how their partner has behaved in the past. The Prisoner’s Dilemma is just one of many scenarios we call Social Dilemmas.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Game Theory for Political Scientists

  • James D. Morrow(Author)
  • 2020(Publication Date)
  • Princeton University Press

    (Publisher)

  Chapter Nine Repeated Games Many political relationships persist over time. Politicians face the electorate in elections over time, nations expect to deal with one another in the future, and political leaders in legislatures must organize their followers for each new issue. The anticipation that the players will have to deal with one another in the future can change the strategic logic of games. The actors must consider not only the immediate consequences of their choices, but also the effect of those choices on the long-term relationship. The future benefits from a contin-ued good relationship can outweigh the immediate benefits of taking advan-tage of other players. Players may be able to use the threat of breaking the long-term relationship in order to discipline short-term exploitation. When are such threats credible, and what outcomes can be achieved with such credible threats? Repeated games are a way to model such ongoing relations. The players play a game repeatedly. This game is called the stage game, and each individual play of that game is called a stage, or round, of the repeated game. There can be either a fixed, known number of rounds, or the game could be indefinitely repeated. In the latter case, either the players' payoffs must be discounted or else there must be a fixed, known chance of the game's ending after each round. Otherwise, the sum of the players' payoffs across the entire game would be infinite. If the game is infinitely repeated, a player's payoff for the entire game is the discounted sum of its payoffs for each round. If Mj is player i's payoff for round t, then its total payoff for the game is k = 0 where the game begins with round 0. If there is a chance that the game ends after each round, let p be this fixed and known probability. A player's expected payoff for all possible future rounds gives its payoff for the game. Player i's expected payoff is because 1 - p is the probability that the game continues after each round.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Common Pool Resources

  Strategic Behavior, Inefficiencies, and Incomplete Information

  • Ana Espinola-Arredondo, Felix Muñoz-Garcia(Authors)
  • 2021(Publication Date)
  • Cambridge University Press

    (Publisher)

  5 Repeated Interaction in the Commons 5.1 introduction Previous chapters discussed games where firms (e.g., fishing compa- nies or farmers sharing an aquifer) interact only once. These games are also known as “one-shot games” or “unrepeated games,” and can help us model strategic settings in which players do not anticipate interacting again in future periods. In many settings, however, the same group of firms interact several times, facing the same game repeatedly. An interesting feature of repeated games is that they can help us rationalize players’ cooperation, even when such cooperation could not be sustained in the unrepeated version of the game. Section 5.2 presents a simple model of a CPR game, highlighting its similarities with the canonical prisoner’s dilemma game. This tractable model helps us in our presentation of repeated interaction in Finitely Repeated Games (Section 5.3) or inFinitely Repeated Games (Section 5.4). Cooperative outcomes, understood as firms exploiting the resource below what they would do in an unrepeated game, cannot be sustained in the equilibrium of the finitely repeated game. Intuitively, firms anticipate that they will be appropriating as much as possible in the last period of interaction, and that such behavior will not be affected by previous history of play. In the previous- to-last period, they anticipate such exploitation in the subsequent period, which leads all firms to exploit the CPR at maximal levels on the previous-to-last period too. A similar argument extends to all previous periods until the first, implying that firms choose a high appropriation level during all periods; a big failure in our quest to use repeated games as a tool to promote cooperation in the commons! 64

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Quantal Response Equilibrium

  A Stochastic Theory of Games

  • Jacob K. Goeree, Charles A. Holt, Thomas R. Palfrey, Charles Holt(Authors)
  • 2016(Publication Date)
  • Princeton University Press

    (Publisher)

  5.1 QRE IN INFinitely Repeated Games Repeated games are applied widely in the social sciences, often as a workhorse model of the possibility of enduring relationships to support cooperative behavior that would not be possible in a one-shot game. Finitely Repeated Games are a special case of extensive-form games for which the AQRE model was fully developed earlier in this book. InFinitely Repeated Games are another story, and 114 CHAPTER 5 Table 5.1. A prisoner’s dilemma game. D C D 4 , 4 10 , 2 C 2 , 10 8 , 8 the purpose of this section is to show how QRE can be extended to analyze such “supergames.” Before proceeding with the formal development of QRE for supergames, we offer the following rationale for why QRE may offer new insights into the structure of equilibria, and the stability of equilibria for these games. Example 5.1 (Repeated prisoner’s dilemma game) : Consider the prisoner’s dilemma stage game in table 5.1. In this game, the unique Nash equilibrium is ( D , D ). Also, it is well known that in any finitely repeated game with T repetitions, playing ( D , D ) in every history is the only subgame-perfect equilibrium of the game. However, if the game is infinitely repeated and if players are sufficiently patient, then there exist many subgame-perfect Nash equilibria whose equilibrium paths involve players choosing ( C , C ) in every period. Such equilibria are supported by strategies that ensure lower long-run payoffs off the equilibrium path. There are at least two conceptual problems with this. First, if there is any noise in the play (as there would be in an experiment or in most other applications), then play will certainly fail to be on the equilibrium path at some point. One then must face the question about whether the specified strategies off the path are plausible. There are many reasons why they might not be. In particular, there is an extensive literature on renegotiation-proofness requirements for off-path strategies.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Game Theory

  An Introduction

  • E. N. Barron(Author)
  • 2024(Publication Date)
  • Wiley

    (Publisher)

  285 5 Repeated Games The same thing happened today that happened yesterday, only to different people –Walter Winchell Change begets change as much as repetition reinforces repetition. –Bill Drayton The more often a stupidity is repeated, the more it gets the appearance of wisdom. –Friedrich Nietzsche Repetition is the mother of learning, but variation is the spice of life. –George Bernard Shaw What happens when a game is played more than once? Many real games are played over and over again, such as setting prices or production levels for each of two or more firms. Battles in a war can be considered as two game opponents fighting essentially the same battle again and again. Companies set prices on their products every day to maximize sales. There are many games played over and over again. Think of a prisoner’s dilemma game played more than once. Recall that in the prisoner’s dilemma, the course of action predicted by Nash would be to defect, i.e., to rat out the other guy. But both players would do better if they cooperated and clammed up. But what if a prisoner knew that she was going to play again; would it affect the best course of action? Is it possible that knowing a game will be played again, possibly with no end, would lead to cooperation? Would knowledge of the players of how the opponents chose to play make any difference in a prisoner’s dilemma game played more than once? To answer that, let’s consider the two-stage extensive form of the prisoner’s dilemma given in Figure 5.1. The information sets are designed so that each player knows her own moves but not that of the opponent. The one-stage game matrix is C D C (2, 2) (0, 3) D (3, 0) (1, 1) (PD) Game Theory: An Introduction, Third Edition. E. N. Barron. © 2024 John Wiley & Sons, Inc. Published 2024 by John Wiley & Sons, Inc.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Introduction to Game Theory in Business and Economics

  • Thomas J. Webster(Author)
  • 2018(Publication Date)
  • Routledge

    (Publisher)

  There are two classes of Finitely Repeated Games. In the first class, the players know that the game will come to an end, but are uncertain as to when that will occur. In the second class, the final stage is known with certainty. We will begin our discus-sion by examining finitely repeated, static games with a certain end. Finitely repeated static game A finitely repeated game is played a limited number of times. Finitely repeated static games may have certain or uncertain ends. The one-time static game depicted in Figure 5.1 involves two players with three pure strategies. If larger payoffs are preferred, the reader should verify that this game has two Nash equilibria strategy profiles: { A2, B2 } and { A3, B3 }. The payoffs for these strategy profiles are highlighted in boldface. It should be obvious, however, that both players would be better off by agreeing to adopt the strategy profile { A1, B1 }. This game is an example of a prisoner’s dilemma since both FINITELY REPEATED, STATIC GAMES 113 players have an incentive to violate such an agreement. Player A has an incentive to switch to A2 and player B has an incentive to switch to B2 . As in all such games, individual incentives trump the incentive of the cooperative. As a result, both players earn a payoff of 8, instead of a payoff of 15 by cooperating. We saw in the previous chapter that it may be possible to escape the prisoner’s dilemma if a static game is infinitely repeated. For this to be the case, the present value of the stream of expected future payoffs from violating the agreement must be less than the present value of the stream of expected future payoffs from the agreement. The present value of the stream of future payoffs depends on the discount rate. From Inequality (4.14), the reader should verify that for the game depicted in Figure 5.1, it will be in the players’ best interest to violate the agreement for any discount rate that is greater than 140 percent.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Game Theory

  Analysis of Conflict

  • Roger B. Myerson, Roger B. Myerson(Authors)
  • 2013(Publication Date)
  • Harvard University Press

    (Publisher)

  7

  Repeated Games

  7.1 The Repeated Prisoners’ Dilemma

  People may behave quite differently toward those with whom they expect to have a long-term relationship than toward those with whom they expect no future interaction. To understand how rational and intelligent behavior may be affected by the structure of a long-term relationship, we study repeated games.

  In a repeated game, there is an infinite sequence of rounds , or points in time, at which players may get information and choose moves. That is, a repeated game has an infinite time horizon , unlike the finite game trees that were considered in Chapter 2 . In a repeated game, because no move is necessarily the last, a player must always consider the effect that his current move might have on the moves and information of other players in the future. Such considerations may lead players to be more cooperative, or more belligerent, in a repeated game than they would be in a finite game in which they know when their relationship will end.

  To introduce the study of repeated games, let us begin with a well-known example, the repeated Prisoners’ Dilemma (Table 7.1 ). Here

  gi

  is i ’s generous move, and

  fi

  is i ’s selfish move. As we saw in Chapter 3 , (f 1 ,f 2 ) is the only equilibrium of this game. Now let us consider what happens if players 1 and 2 expect to repeatedly play this game with each other every day, for a long time.

  Table 7.1    Prisoners’ Dilemma game

  For example, suppose that the number of times that the game will be played is a random variable, unknown to the players until the game stops, and that this random stopping time is a geometric distribution with expected value 100. That is, the probability of play continuing for exactly k rounds is (.99

  k −1

  ) × .01. Thus, after each round of play, the probability that players 1 and 2 will meet and play again is .99; and at any time when they are still playing, the expected number of further rounds of play is 100. In this repeated game, generous behavior can be supported in equilibrium. Consider, for example, the strategy of playing

  gi

  every day until someone plays f 1 or f 2 , and thereafter playing

  fi

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Game Theory and Applications

  • Tatsuro Ichiishi, Abraham Neyman, Yair Tauman, Karl Shell(Authors)
  • 2014(Publication Date)
  • Academic Press

    (Publisher)

  It also turns out that the complexity of a strategy is the minimal size of the information system needed by a player using the strategy. Within the context of inFinitely Repeated Games the following question arises. What payoffs of the game can be obtained by equilibria using strategies of finite complexity. Kalai and Stanford (1988) showed that for the case of repeated 134 KALAI games with discounting this is not a serious issue because every equilibrium payoff can be approximated by an equilibrium using finite complexity strategies. This approximation of equilibrium payoffs by ones using finite complexity strategies was extended by Ben-Porath and Peleg (1987) to two limit cases. The case of inFinitely Repeated Games with the average payoff criterion, and the case of low discounting. In these cases the characterizations of all equilibrium payoffs is given by the well known Folk Theorems (see Aumann and Shapley, 1976; Rubinstein, 1977; Fudenberg and Maskin, 1986). Ben-Porath and Peleg showed that all the equilibrium payoffs described by the Folk theorems can be approxi-mated by equilibrium using finite complexity strategies. For robust equilibria of generic inFinitely Repeated Games with discounting, interplayer complexity bounds exist. Kalai and Stanford (1988) showed that at such equilibria the complexity of the strategy used by any one player never ex-ceeds the product of the complexities of the strategies used by his opponents. In particular, two players playing a game must use equal-complexity strategies. 2. DESCRIPTION OF STRATEGIC GAMES A strategic game G is described by a triple G — (N, S, u) with the following structure and interpretations. N = {1, 2, . . . , n} is the set of players. Every player i E N has a set of strategies 5/. The set of strategy combinations is S = x iŒN Si. The utility function u = (u x ,u 2 , . . . , u n ) with each w,: S—» U. w, is called the utility (sometimes payoff) function of player /.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Game Theory and Exercises

  • Gisèle Umbhauer(Author)
  • 2016(Publication Date)
  • Taylor & Francis

    (Publisher)

  1 at z. I think that this game should be tested experimentally to see if players play in accordance with my expected behaviour, which isn’t the only behaviour compatible with backward induction.

  See the exercises in order to see the other SPNE paths and the detailed SPNE, according to the different possible behaviours in case of indifference.13

  ■ Figure 4.9b

  4 Finitely Repeated Games

  We now apply subgame perfection/backward induction to repeated games. A repeated game is a game with a special structure: at each period of play, the players play a same stage game which may be in normal or extensive form.

  Repetition is a usual phenomenon in economics and social sciences in general. Transactions are repetitive, working activities are repetitive, and more generally most human relations and actions are repetitive. Repetition has many consequences, among them the building of reputation, the possibility of learning, and also the broadening of the strategies’ sets and the broadening of the strategic outcomes , a point we will focus on.

  4.1 Subgame Perfection in finitely repeated normal form games

  4.1.1 New behaviour in finitely repeated normal form games

  Consider the normal form game in Matrix 4.1:

  This game, called stage game , has three Nash equilibria, (A1 ,B2 ), (C1 ,C2 ) and a mixed Nash equilibrium, where player 1 plays A1 and C1 with the probabilities 2 /3 and 1 /3 and player 2 plays B2 and C2 with probability ½ each (in this equilibrium, player 1 and player 2’s payoffs are 2 and 5/3).

  Definition 3: Finitely Repeated Games

  We focus on repeated games with an observation of past actions before a new round. In this context, at each period the players play the stage game and get, at the end of the period, the payoffs assigned to the strategies played in the stage game. They observe all the played actions; then a new period begins: the players play again the stage game and so on, until the last period, after which the game stops.

  Sign up to read

  Learn more about book