Cumbersome coordination in repeated games

This paper examines the role communication between players might serve in enabling them to reach an agreement on the future play of a repeated game. The property of the communication process that we focus on is the amount of time it takes to complete. We characterize the effects of such communication processes indirectly by determining the set of agreements they may yield. A weak and a strong criterion are introduced to describe sets of agreements that are “stable” in the sense that players would follow the current agreement and not seek to reach a new agreement. We show that as players become extremely patient, strongly stable sets converge to Pareto efficient singletons. We apply the stability criteria to Prisoner’s Dilemmas and show how the unique strongly stable set reflects asymmetries in the players’ stage-game payoffs. Finally, we model the communication process as a Rubinstein alternating-offer bargaining game and demonstrate that the resulting agreements help characterize the strongly stable set for a general class of communication mechanisms. Received January 1998/final version June 1999     

Strategic absentmindedness in finitely repeated games

In this paper we consider finitely repeated games in which players can unilaterally commit to behave in an absentminded way in some stages of the repeated game. We prove that the standard conditions for folk theorems can be substantially relaxed when players are able to make this kind of compromises, both in the Nash and in the subgame perfect case. We also analyze the relation of our model with the repeated games with unilateral commitments studied, for instance, in García-Jurado et al. (Int. Game Theory Rev. 2:129–139, 2000). Authors acknowledge the financial support of Ministerio de Educaci ón y Ciencia, FEDER and Fundación Séneca de la Región de Murcia through projects SEJ2005-07637-C02-02, ECO2008-03484-C02-02, MTM2005-09184-C02-02, MTM2008-06778-C02-01 and 08716/PI/08.     

Strategic stability in repeated signaling games

This paper extends selection rules now used in the signaling literature (such as the Intuitive Criterion of Cho and Kreps (1987)) to a class of repeated signaling games, where each player can exchange the messages conditioned on his private information. STABAC (STAbility and BACkward induction) is defined as a procedure whereby forward induction arguments (Kohlberg and Mertens (1986)) are applied in combination with the backward induction process. We specify the conditions under which any strategically stable outcome of a repeated signaling game includes an equilibrium that induces a stable equilibrium outcome in every subform, whence STABAC does not eliminate any stable outcome of the repeated signaling game.     

Delayed perfect monitoring in repeated games

Delayed perfect monitoring in an infinitely repeated discounted game is studied. A player perfectly observes any other player’s action choice with a fixed and finite delay. The observational delays between different pairs of players are heterogeneous and asymmetric. The Folk theorem extends to this setup. As is shown for an example, for a range of discount factors, the set of perfect public equilibria is reduced under certain conditions and efficiency improves when the players take into account private information. This model applies to many situations in which there is a heterogeneous delay between information generation and the players’ reaction.     

ɛ-Consistent equilibrium in repeated games

We introduce the concept of ɛ-consistent equilibrium where each player plays a ɛ-best response after every history reached with positive probability. In particular, an ɛ-consistent equilibrium induces an ɛ-equilibrium in any subgame reached along the play path. The existence of ɛ-consistent equilibrium is examined in various repeated games. The main result is the existence in stochastic games with absorbing states. Received January 1995/Revised version October 1996/Final version September 1997     

Sequencing games with repeated players

Two classes of one machine sequencing situations are considered in which each job corresponds to exactly one player but a player may have more than one job to be processed, so called RP(repeated player) sequencing situations. In max-RP sequencing situations it is assumed that each player’s cost function is linear with respect to the maximum completion time of his jobs, whereas in min-RP sequencing situations the cost functions are linear with respect to the minimum completion times. For both classes, following explicit procedures to go from the initial processing order to an optimal order for the coalition of all players, equal gain splitting rules are defined. It is shown that these rules lead to core elements of the associated RP sequencing games. Moreover, it is seen that min-RP sequencing games are convex. We thank two referees for their valuable suggestions for improvement. Financial support for P. Calleja has been given by the Ministerio de Educación y Ciencia and FEDER under grant SEJ2005-02443/ECON, and by the Generalitat de Catalunya through a BE grant from AGAUR and grant 2005SGR00984.     

Simple coalitional strategy profiles in repeated games

In this paper we introduce simple coalitional strategy profiles to avoid group deviations in repeated games. In the repeated Cournot supergame we prove that it is possible to sustain the symmetric monopoly outcome by means of a variety of strategies which satisfy the requirement that no coalition (other than the grand one) will deviate in any subgame.     

Folk theorems in multicriteria repeated N-person games

In this paper we consider the question of existence of a multicriteria-Nash equilibrium in multicriteria multistage N-person games. Besides, we present several forms of multicriteria-Nash equilibrium for repeated games both with infinitely and finitely many stages. The author thanks the Spanish Ministry of Science and Technology through grant number BFM01-2378.     

Two-person repeated games with finite automata

We study two-person repeated games in which a player with a restricted set of strategies plays against an unrestricted player. An exogenously given bound on the complexity of strategies, which is measured by the size of the smallest automata that implement them, gives rise to a restriction on strategies available to a player.  We examine the asymptotic behavior of the set of equilibrium payoffs as the bound on the strategic complexity of the restricted player tends to infinity, but sufficiently slowly. Results from the study of zero sum case provide the individually rational payoff levels. Received February 1997/revised version March 2000     

Nash equilibria of finitely repeated games

Under weak conditions, any feasible and individually rational payoff vector of a one-shot game can be approximated by the average payoff in a Nash equilibrium of a finitely repeated game with a long enough horizon.     

The normal distribution and repeated games

For a reperated zero-sum two-person game with incomplete information discussed byZamir, it is proved here that \(\mathop {\lim }\limits_{n \to \infty } \sqrt n v_n (p) = \phi (p)\) whereφ (p) is the normal density function evaluated at itsp-quantile (i.e. \(\phi (p) = \frac{1}{{\sqrt {2\pi } }}e^{ - ({1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-0em} 2})x^2 } p\) where \(\frac{1}{{\sqrt {2\pi } }}\mathop {\smallint ^p }\limits_{ - \infty }^x e^{ - ({1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-0em} 2})x^2 } dx = p\) . Here for 0?p?1, (p, 1 ?p) is the a priori probability distribution on two states of nature, the actual state of nature is known to the maximizer but not to the minimizer.v _n (p) is the minimax value of the game withn stages.     

On equilibria in repeated games with absorbing states

We prove the existence of ε-(Nash) equilibria in two-person non-zerosum limiting average repeated games with absorbing states. These are stochastic games in which all states but one are absorbing. A state is absorbing if the probability of ever leaving that state is zero for all available pairs of actions.     

Optimal strategies in repeated games with incomplete information

The paper is concerned with zero-sum two-person repeated games with lack of information on one side. The main result in the construction of an optimal strategy for the uninformed player in the infinitely repeated game.     

Discounting-sensitivity in symmetric repeated games: An example

I present an example of a symmetric repeated game in which an arbitrarily small change in the discount factor can lead to a discontinuous change in the level of symmetry that can be sustained in equilibrium.     

An operator approach to zero-sum repeated games

We consider two person zero-sum stochastic games. The recursive formula for the valuesvλ (resp.v _n) of the discounted (resp. finitely repeated) version can be written in terms of a single basic operator Φ(α,f) where α is the weight on the present payoff andf the future payoff. We give sufficient conditions in terms of Φ(α,f) and its derivative at 0 for limv _n and limvλ to exist and to be equal. We apply these results to obtain such convergence properties for absorbing games with compact action spaces and incomplete information games.     

On repeated games with general information function

For a class of repeated two-person zero-sum games with incomplete information it was proved byAumann andMaschler that limν _n exists,ν _n being the value of the game withn repetitions. If the players know at each stage the moves done by both players at all previous stages,Aumann andMaschler could prove that the error termδ _n=¦ν _n — limν _n ¦ satisfiesδ _n≤c/√n for somec>0. It was then shown byZamir that this bound is the lowest possible. In this paper it is shown that if previous moves are not always announced,δ _n may be of higher order of magnitude e.g.δ _n≥c/n ^1/3 for somec>0. New upper bounds forδ _n are given for two classes of games.     

Asymptotically optimal strategies in repeated games with incomplete information

It is known that for repeated zero-sum games with incomplete information the limit of the values of theN-stage game exists asN tends to infinity. In this paper strategies are constructed that guarantee in theN-stage game the limit of values up to an error term \(\frac{K}{{\sqrt N }}.\)      

The use of public randomization in discounted repeated games

This paper presents an example where the set of subgame-perfect equilibrium payoffs of the infinitely repeated game without public randomization is not convex, no matter how large the discount factor is. Also, the set of pure-strategy equilibrium payoffs is not monotonic with respect to the discount factor in this example. These results are in sharp contrast to the fact that the equilibrium payoff set is convex and monotonic if public randomization is available.     

Ternary choices in repeated games and border collision bifurcations

Several recent contributions formalize and analyze binary choices games with externalities as those described by Schelling. Nevertheless, in the real world choices are not always binary, and players have often to decide among more than two alternatives. These kinds of interactions are examined in game theory where, starting from the well known rock-paper-scissor game, several other kinds of strategic interactions involving more than two choices are examined. In this paper we investigate how the dynamics evolve introducing one more option in binary choice games with externalities. The dynamics we obtain are always in a stable regime, that is, the structurally stable dynamics are only attracting cycles, but of any possible positive integer as period. We show that, depending on the structure of the game, the dynamics can be quite different from those existing when considering binary choices. The bifurcation structure, due to border collisions, is explained, showing the existence of so-called big-bang bifurcation points.     

A note on repeated games with non-monotonie value

We show that even when the information structure is independent of the state of nature, the value of then-stage zero-sum game with incomplete information is not necessarily monotonie with respect to the length of the game. More precisely, we give an example of such ann-stage game in whichV ₁ >V ₂ <V ₃.I am very grateful to Ehud Lehrer who introduced this question to me.