research-article

Equilibrium paths in discounted supergames

Authors:

Mitri KittiAuthors Info & Claims

Volume 260, Issue C

Pages 1 - 27

https://doi.org/10.1016/j.dam.2019.01.026

Published: 15 May 2019 Publication History

Abstract

This paper examines the subgame-perfect pure-strategy equilibria in discounted supergames with perfect monitoring. It is shown that all the equilibrium paths are composed of fragments called elementary subpaths. This characterization result makes it possible to compute and analyze the equilibrium paths and payoffs by using a collection of elementary subpaths. It is also shown that all the equilibrium paths can be compactly represented by a directed graph when there are finitely many elementary subpaths. In general, there may be infinitely many elementary subpaths, but it is always possible to construct finite approximations. When the subpaths are allowed to be approximatively incentive compatible, it is possible to compute in a finite number of steps a graph that represents all the equilibrium paths. The directed graphs can be used in analyzing the complexity of equilibrium outcomes. In particular, it is shown that the size and the density of the equilibrium set can be measured by the asymptotic growth rate of equilibrium paths and the Hausdorff dimension of the payoff set.

References

[1]

Abreu D., Extremal equilibria of oligopolistic supergames, J. Econom. Theory 39 (1986) 191–225.

[2]

Abreu D., On the theory of infinitely repeated games with discounting, Econometrica 56 (1988) 383–396.

[3]

D. Abreu, B. Brooks, Y. Sannikov, A “pencil-sharpening” algorithm for two player stochastic games with perfect monitoring, Working paper, 2016.

[4]

Abreu D., Pearce D., Stacchetti E., Optimal cartel equilibria with imperfect monitoring, J. Econom. Theory 39 (1986) 251–269.

[5]

Abreu D., Pearce D., Stacchetti E., Toward a theory of discounted repeated games with imperfect monitoring, Econometrica 58 (1990) 1041–1063.

[6]

Abreu D., Sannikov Y., An algorithm for two player repeated games with perfect monitoring, Theor. Econ. 9 (2014) 313–338.

[7]

G. Andersen, V. Conitzer, Fast equilibrium computation for infinitely repeated games, in: Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013, pp. 53–59.

[8]

Berg K., Elementary subpaths in discounted stochastic games, Dynam. Games Appl. 6 (2016) 304–323.

[9]

Berg K., Extremal pure strategies and monotonicity in repeated games, Comput. Econ. 49 (2017) 387–404.

[10]

Berg K., Set-valued games and mixed-strategy equilibria in discounted supergames, Discrete Appl. Math. (2018),.

Digital Library

[11]

K. Berg, M. Kärki, An algorithm for computing the minimal pure-strategy subgame-perfect equilibrium payoffs in repeated games, Working paper, 2014.

[12]

Berg K., Kitti M., Computing equilibria in discounted 2 × 2 supergames, Comput. Econ. 41 (2013) 71–78.

[13]

Berg K., Kitti M., Fractal geometry of equilibrium payoffs in discounted supergames, Fractals 22 (2014).

[14]

Berg K., Schoenmakers G., Construction of subgame-perfect mixed-strategy equilibria in repeated games, Games 8 (2017).

[15]

Bertsekas D.P., Shreve S.E., Stochastic Optimal Control: The Discrete Time Case, Athena Scientific, 1996.

[16]

Borgs C., Chayes J., Immorlica N., Kalai A.T., Mirrokni V., Papadimitriou C., The myth of the folk theorem, Games Econom. Behav. 70 (2010) 34–43.

[17]

A. Burkov, B. Chaib-draa, An approximate subgame-perfect equilibrium computation technique for repeated games, in: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010, pp. 729–736.

[18]

Chatterjee K., Sabourian H., Game theory and strategic complexity, in: Meyers R.A. (Ed.), Encyclopedia of complexity and system science, Springer, 2009.

[19]

Chen X., Deng X., Teng S.-H., Settling the complexity of computing two-player nash equilibria, J. ACM 56 (3) (2009).

[20]

Cronshaw M.B., Algorithms for finding repeated game equilibria, Comput. Econ. 10 (1997) 139–168.

[21]

Cronshaw M.B., Luenberger D.G., Strongly symmetric subgame perfect equilibria in infinitely repeated games with perfect monitoring, Games Econom. Behav. 6 (1994) 220–237.

[22]

Cvetković D., Rowlinson P., Simić, Eigenspaces of Graphs, Cambridge University Press, 1997.

[23]

Daskalakis C., On the complexity of approximating a nash equilibrium, ACM Trans. Algorithms 9 (3) (2013).

[24]

Daskalakis C., Goldberg P., Papadimitriou C.H., The complexity of computing a nash equilibrium, SIAM J. Comput. 39 (1) (2009) 195–259.

Digital Library

[25]

Demaine E.D., Playing Games with Algorithms: Algorithmic Combinatorial Game Theory, in: Mathematical Foundations of Computer Science (MFCS 2001), Springer, 2001.

[26]

Edgar G.A., Golds J., A fractal dimension estimate for a graph-directed iterated function system of non-similarities, Indiana Univ. Math. J. 48 (1999) 429–447.

[27]

Fraenkel A., Combinatorial games: selected bibliography with a succinct gourmet introduction, Dynamic Survey, Electron. J. Combin. 2 (2012).

[28]

Fudenberg D., Maskin E., The folk theorem in repeated games with discounting and incomplete information, Econometrica 54 (1986) 533–554.

[29]

Gottlob G., Greco G., Scarcello F., Pure nash equilibria: hard and easy games, J. Artificial Intelligence Res. 24 (2005) 357–406.

[30]

Judd K., Yeltekin Ş., Conklin J., Computing supergame equilibria, Econometrica 71 (2003) 1239–1254.

[31]

Kalai E., Bounded rationality and strategic complexity in repeated games, in: Ichiishi T., Neyman A., Tauman Y. (Eds.), Game Theory and Applications, Academic Press, 1990, pp. 131–157.

[32]

M. Kitti, Equilibrium payoffs for pure strategies in repeated games, Working paper, 2016.

[33]

M. Kitti, Subgame perfect equilibria in continuous-time repeated games, Working paper, 2018.

[34]

Kitti M., Conditionally stationary equilibria in discounted dynamic games, Dynam. Games Appl. 1 (2011) 514–533.

[35]

Kitti M., Conditional markov equilibria in discounted dynamic games, Math. Methods Oper. Res. 78 (2013) 77–100.

[36]

Kitti M., Subgame perfect equilibria in discounted stochastic games, J. Math. Anal. Appl. 435 (2016) 253–266.

[37]

Mailath G.J., Obara I., Sekiguchi T., The maximum efficient equilibrium payoff in the repeated prisoners’ dilemma, Games Econom. Behav. 40 (2002) 99–122.

[38]

Mauldin R.D., Williams S.C., Hausdorff dimension in graph directed constructions, Trans. Amer. Math. Soc. 309 (1988) 811–829.

[39]

Nachbar J.H., Zame W.R., Non-computable strategies and discounted repeated games, Econom. Theory 8 (1996) 103–122.

[40]

Salonen H., Vartiainen H., Valuating payoff streams under unequal discount factors, Econom. Lett. 99 (2008) 595–598.

[41]

Sorin S., On repeated games with complete information, Math. Oper. Res. 11 (1986) 147–160.

[42]

Stahl D.O., The graph of prisoners’ dilemma supergame payoffs as a function of the discount factor, Games Econom. Behav. 3 (1991) 368–384.

Cited By

Dargaj JSimonsen J(2022)Discounted Repeated Games Having Computable Strategies with No Computable Best Response under Subgame-Perfect EquilibriaACM Transactions on Economics and Computation10.1145/350558510:1(1-39)Online publication date: 8-Apr-2022
https://dl.acm.org/doi/10.1145/3505585

Index Terms

Equilibrium paths in discounted supergames

Index terms have been assigned to the content through auto-classification.

Recommendations

Computing Equilibria in Discounted 2 × 2 Supergames

This article examines the subgame perfect pure strategy equilibrium paths and payoff sets of discounted supergames with perfect monitoring. The main contribution is to provide methods for computing and tools for analyzing the equilibrium paths and ...
Dynamic Price Competition with Fixed Capacities

In this paper, we study price competition for an oligopoly in a dynamic setting, where each of the sellers has a fixed number of units available for sale over a fixed number of periods. Demand is stochastic, and depending on how it evolves, sellers may ...
Paid peering among internet service providers
GameNets '06: Proceeding from the 2006 workshop on Game theory for communications and networks

We develop models for Internet Service Provider (ISP) peering when ISPs charge each other for carrying traffic. We study linear pricing schemes in a simple ISP peering model using a two stage sequential Nash game in which self interested providers first ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Applied Mathematics

Discrete Applied Mathematics Volume 260, Issue C

May 2019

294 pages

ISSN:0166-218X

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 15 May 2019

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dargaj JSimonsen J(2022)Discounted Repeated Games Having Computable Strategies with No Computable Best Response under Subgame-Perfect EquilibriaACM Transactions on Economics and Computation10.1145/350558510:1(1-39)Online publication date: 8-Apr-2022
https://dl.acm.org/doi/10.1145/3505585

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents