April  2015, 2(2): 117-140. doi: 10.3934/jdg.2015.2.117

Learning in monotone bayesian games

1. 

Wadham College, University of Oxford, Oxford, OX1 3PN, United Kingdom

Received  December 2014 Revised  October 2015 Published  December 2015

This paper studies learning in monotone Bayesian games with one-dimensional types and finitely many actions. Players switch between actions at a set of thresholds. A learning algorithm under which players adjust their strategies in the direction of better ones using payoffs received at similar signals to their current thresholds is examined. Convergence to equilibrium is shown in the case of supermodular games and potential games.
Citation: Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics & Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117
References:
[1]

S. Athey, Characterizing Properties of Stochastic Objective Functions, mimeo, MIT, 1996. Google Scholar

[2]

S. Athey, Single crossing properties and the existence of pure strategy equilibria in games of incomplete information, Econometrica, 69 (2001), 861-889. doi: 10.1111/1468-0262.00223.  Google Scholar

[3]

A. Beggs, Learning in bayesian games with binary actions, The B.E. Journal of Theoretical Economics: Advances in Theoretical Economics, 9 (2009), Article 33, 30pp. doi: 10.2202/1935-1704.1452.  Google Scholar

[4]

A. Beggs, Regularity and Stability in Monotone Bayesian Games, Discussion paper, University of Oxford, 2011. Google Scholar

[5]

A. Beggs, Regularity and robustness in monotone bayesian games, Journal of Mathematical Economics, 60 (2015), 145-158. doi: 10.1016/j.jmateco.2015.07.002.  Google Scholar

[6]

M. Benaïm, Dynamics of stochastic approximation algorithms, in Seminaire de Probabilités, XXXIII, vol. 1709 of Lecture Notes in Mathematics, Springer Verlag, Berlin, 1999, 1-68. doi: 10.1007/BFb0096509.  Google Scholar

[7]

M. Benaïm, Convergence with probability one of stochastic approximation algorithms whose averageis cooperative, Nonlinearity, 13 (2000), 601-616. doi: 10.1088/0951-7715/13/3/305.  Google Scholar

[8]

M. Benaïm and M. Faure, Stochastic approximation, cooperative dynamics and supermodular games, Annals of Applied Probability, 22 (2012), 2133-2164. doi: 10.1214/11-AAP816.  Google Scholar

[9]

M. Benaïm and M. Hirsch, Mixed equilibria and dynamical systems arising from fictitious play in perturbed games, Games and Economic Behavior, 29 (1999), 36-72. doi: 10.1006/game.1999.0717.  Google Scholar

[10]

U. Berger, Learning in game with strategic complementarities revisited, Journal of Economic Theory, 143 (2008), 292-301. doi: 10.1016/j.jet.2008.01.007.  Google Scholar

[11]

P. Bianchi and J. Jakubowicz, Convergence of a multi-agent projected stochastic gradient algorithm for non-convex optimization, IEEE Transactions on Automatic Control, 58 (2013), 391-405. doi: 10.1109/TAC.2012.2209984.  Google Scholar

[12]

J. Borwein and A. Lewis, Convex Analysis and Nonlinear Optimization, 2nd edition, Springer Verlag, New York, 2006. doi: 10.1007/978-0-387-31256-9.  Google Scholar

[13]

S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004. doi: 10.1017/CBO9780511804441.  Google Scholar

[14]

Y. Chow and H. Teicher, Probablity Theory: Independence, Exchangeability and Martingales, 3rd edition, Springer Verlag, New York, 1998. Google Scholar

[15]

P. Dupuis and A. Nagurney, Dynamical systems and variational inequalties, Annals of Operations Research, 44 (1993), 9-42. doi: 10.1007/BF02073589.  Google Scholar

[16]

F. Facchinei and J.-S. Pang, Finite Dimensional Variational Inequalities and Complementarity Problems, Two Volumes, Springer Verlag, New York, 2003. Google Scholar

[17]

D. Fudenberg and D. Kreps, Learning mixed equilibria, Games and Economic Behavior, 5 (1993), 320-367. doi: 10.1006/game.1993.1021.  Google Scholar

[18]

I. Gilboa and D. Schmeidler, Inductive inference: An axiomatic approach, Econometrica, 71 (2003), 1-26. doi: 10.1111/1468-0262.00388.  Google Scholar

[19]

P. Hall and C. Heyde, Martingale Limit Theory and its Applications, Academic Press, New York, 1980.  Google Scholar

[20]

W. Härdle and R. Nixdorf, Nonparametric sequential estimation of zeroes and extrema of regression functions, IEEE Transactions in Information Theory, 33 (1987), 367-372. Google Scholar

[21]

C. Henry, An existence theorem for a class of differential equations with multivalued right-hand sides, Journal of Mathematical Analysis and Applications, 41 (1973), 179-186. doi: 10.1016/0022-247X(73)90192-3.  Google Scholar

[22]

J. Jiang, Attractors in strongly monotone flows, Journal of Mathematical Analysis and Applications, 162 (1991), 210-222. doi: 10.1016/0022-247X(91)90188-6.  Google Scholar

[23]

V. Krishna, Learning in Games with Strategic Complementarities, Technical report, Harvard University, 1992. Google Scholar

[24]

H. Kushner and G. Yin, Stochastic Approximation Algorithms and Applications, Springer Verlag, New York, 1997. doi: 10.1007/978-1-4899-2696-8.  Google Scholar

[25]

P. Milgrom and C. Shannon, Monotone comparative statics, Econometrica, 62 (1994), 157-180. doi: 10.2307/2951479.  Google Scholar

[26]

P. Milgrom and R. Weber, A theory of auctions and competitive bidding, Econometrica, 50 (1982), 1089-1122. doi: 10.2307/1911865.  Google Scholar

[27]

S. Morris and H. Shin, Global games: Theory and applications, in Advances in Economics and Econometrics: Theory and Applications, Proceedings of the Eighth World Congress of the Econometric Society (eds. M. Dewatripont, L. Hansen and S. Turnovsky), Cambridge University Press, Cambridge, 2003, 56-114. Google Scholar

[28]

A. Müller and D. Stoyan, Comparison Methods for Stochastic Models and Risks, Wiley, Chichester, 2002.  Google Scholar

[29]

R. Nelsen, An Introduction to Copulas, 2nd edition, Springer, New York, 2006.  Google Scholar

[30]

R. Pemantle, Nonconvergence to unstable points in urn models and stochastic approximations, The Annals of Probability, 18 (1990), 698-712. doi: 10.1214/aop/1176990853.  Google Scholar

[31]

R. T. Rockafellar and R. Wets, Variational Analysis, Springer Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.  Google Scholar

[32]

A. Rusczyński, Nonlinear Optimization, Princeton University Press, Princeton, NJ, 2006.  Google Scholar

[33]

E. Schuster, Joint asymptotic distribution of the estimated regression function at a finite number of distinct points, Annals of Mathematical Statistics, 43 (1972), 84-88. doi: 10.1214/aoms/1177692703.  Google Scholar

[34]

R. Selten and J. Buchta, Experimental sealed bid first price auction with directly observed bid functions, in Games and Human Behavior, Essays in Honor of Amnon Rapoport (eds. I. Budescu, I. Erev and R. Zwick), Lawrence Erlbaum Associates, Mahwah, NJ, 1998, 79-102. Google Scholar

[35]

J. Steiner and C. Stewart, Learning by Similarity in Coordination Games, Technical report, CERGE, 2007. Google Scholar

[36]

J. Steiner and C. Stewart, Contagion through learning, Theoretical Economics, 3 (2008), 431-458. Google Scholar

show all references

References:
[1]

S. Athey, Characterizing Properties of Stochastic Objective Functions, mimeo, MIT, 1996. Google Scholar

[2]

S. Athey, Single crossing properties and the existence of pure strategy equilibria in games of incomplete information, Econometrica, 69 (2001), 861-889. doi: 10.1111/1468-0262.00223.  Google Scholar

[3]

A. Beggs, Learning in bayesian games with binary actions, The B.E. Journal of Theoretical Economics: Advances in Theoretical Economics, 9 (2009), Article 33, 30pp. doi: 10.2202/1935-1704.1452.  Google Scholar

[4]

A. Beggs, Regularity and Stability in Monotone Bayesian Games, Discussion paper, University of Oxford, 2011. Google Scholar

[5]

A. Beggs, Regularity and robustness in monotone bayesian games, Journal of Mathematical Economics, 60 (2015), 145-158. doi: 10.1016/j.jmateco.2015.07.002.  Google Scholar

[6]

M. Benaïm, Dynamics of stochastic approximation algorithms, in Seminaire de Probabilités, XXXIII, vol. 1709 of Lecture Notes in Mathematics, Springer Verlag, Berlin, 1999, 1-68. doi: 10.1007/BFb0096509.  Google Scholar

[7]

M. Benaïm, Convergence with probability one of stochastic approximation algorithms whose averageis cooperative, Nonlinearity, 13 (2000), 601-616. doi: 10.1088/0951-7715/13/3/305.  Google Scholar

[8]

M. Benaïm and M. Faure, Stochastic approximation, cooperative dynamics and supermodular games, Annals of Applied Probability, 22 (2012), 2133-2164. doi: 10.1214/11-AAP816.  Google Scholar

[9]

M. Benaïm and M. Hirsch, Mixed equilibria and dynamical systems arising from fictitious play in perturbed games, Games and Economic Behavior, 29 (1999), 36-72. doi: 10.1006/game.1999.0717.  Google Scholar

[10]

U. Berger, Learning in game with strategic complementarities revisited, Journal of Economic Theory, 143 (2008), 292-301. doi: 10.1016/j.jet.2008.01.007.  Google Scholar

[11]

P. Bianchi and J. Jakubowicz, Convergence of a multi-agent projected stochastic gradient algorithm for non-convex optimization, IEEE Transactions on Automatic Control, 58 (2013), 391-405. doi: 10.1109/TAC.2012.2209984.  Google Scholar

[12]

J. Borwein and A. Lewis, Convex Analysis and Nonlinear Optimization, 2nd edition, Springer Verlag, New York, 2006. doi: 10.1007/978-0-387-31256-9.  Google Scholar

[13]

S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004. doi: 10.1017/CBO9780511804441.  Google Scholar

[14]

Y. Chow and H. Teicher, Probablity Theory: Independence, Exchangeability and Martingales, 3rd edition, Springer Verlag, New York, 1998. Google Scholar

[15]

P. Dupuis and A. Nagurney, Dynamical systems and variational inequalties, Annals of Operations Research, 44 (1993), 9-42. doi: 10.1007/BF02073589.  Google Scholar

[16]

F. Facchinei and J.-S. Pang, Finite Dimensional Variational Inequalities and Complementarity Problems, Two Volumes, Springer Verlag, New York, 2003. Google Scholar

[17]

D. Fudenberg and D. Kreps, Learning mixed equilibria, Games and Economic Behavior, 5 (1993), 320-367. doi: 10.1006/game.1993.1021.  Google Scholar

[18]

I. Gilboa and D. Schmeidler, Inductive inference: An axiomatic approach, Econometrica, 71 (2003), 1-26. doi: 10.1111/1468-0262.00388.  Google Scholar

[19]

P. Hall and C. Heyde, Martingale Limit Theory and its Applications, Academic Press, New York, 1980.  Google Scholar

[20]

W. Härdle and R. Nixdorf, Nonparametric sequential estimation of zeroes and extrema of regression functions, IEEE Transactions in Information Theory, 33 (1987), 367-372. Google Scholar

[21]

C. Henry, An existence theorem for a class of differential equations with multivalued right-hand sides, Journal of Mathematical Analysis and Applications, 41 (1973), 179-186. doi: 10.1016/0022-247X(73)90192-3.  Google Scholar

[22]

J. Jiang, Attractors in strongly monotone flows, Journal of Mathematical Analysis and Applications, 162 (1991), 210-222. doi: 10.1016/0022-247X(91)90188-6.  Google Scholar

[23]

V. Krishna, Learning in Games with Strategic Complementarities, Technical report, Harvard University, 1992. Google Scholar

[24]

H. Kushner and G. Yin, Stochastic Approximation Algorithms and Applications, Springer Verlag, New York, 1997. doi: 10.1007/978-1-4899-2696-8.  Google Scholar

[25]

P. Milgrom and C. Shannon, Monotone comparative statics, Econometrica, 62 (1994), 157-180. doi: 10.2307/2951479.  Google Scholar

[26]

P. Milgrom and R. Weber, A theory of auctions and competitive bidding, Econometrica, 50 (1982), 1089-1122. doi: 10.2307/1911865.  Google Scholar

[27]

S. Morris and H. Shin, Global games: Theory and applications, in Advances in Economics and Econometrics: Theory and Applications, Proceedings of the Eighth World Congress of the Econometric Society (eds. M. Dewatripont, L. Hansen and S. Turnovsky), Cambridge University Press, Cambridge, 2003, 56-114. Google Scholar

[28]

A. Müller and D. Stoyan, Comparison Methods for Stochastic Models and Risks, Wiley, Chichester, 2002.  Google Scholar

[29]

R. Nelsen, An Introduction to Copulas, 2nd edition, Springer, New York, 2006.  Google Scholar

[30]

R. Pemantle, Nonconvergence to unstable points in urn models and stochastic approximations, The Annals of Probability, 18 (1990), 698-712. doi: 10.1214/aop/1176990853.  Google Scholar

[31]

R. T. Rockafellar and R. Wets, Variational Analysis, Springer Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.  Google Scholar

[32]

A. Rusczyński, Nonlinear Optimization, Princeton University Press, Princeton, NJ, 2006.  Google Scholar

[33]

E. Schuster, Joint asymptotic distribution of the estimated regression function at a finite number of distinct points, Annals of Mathematical Statistics, 43 (1972), 84-88. doi: 10.1214/aoms/1177692703.  Google Scholar

[34]

R. Selten and J. Buchta, Experimental sealed bid first price auction with directly observed bid functions, in Games and Human Behavior, Essays in Honor of Amnon Rapoport (eds. I. Budescu, I. Erev and R. Zwick), Lawrence Erlbaum Associates, Mahwah, NJ, 1998, 79-102. Google Scholar

[35]

J. Steiner and C. Stewart, Learning by Similarity in Coordination Games, Technical report, CERGE, 2007. Google Scholar

[36]

J. Steiner and C. Stewart, Contagion through learning, Theoretical Economics, 3 (2008), 431-458. Google Scholar

[1]

Kashi Behrstock, Michel Benaïm, Morris W. Hirsch. Smale strategies for network prisoner's dilemma games. Journal of Dynamics & Games, 2015, 2 (2) : 141-155. doi: 10.3934/jdg.2015.2.141

[2]

Miguel A. Dumett, Roberto Cominetti. On the stability of an adaptive learning dynamics in traffic games. Journal of Dynamics & Games, 2018, 5 (4) : 265-282. doi: 10.3934/jdg.2018017

[3]

Yves Achdou, Victor Perez. Iterative strategies for solving linearized discrete mean field games systems. Networks & Heterogeneous Media, 2012, 7 (2) : 197-217. doi: 10.3934/nhm.2012.7.197

[4]

Weihua Ruan. Markovian strategies for piecewise deterministic differential games with continuous and impulse controls. Journal of Dynamics & Games, 2019, 6 (4) : 337-366. doi: 10.3934/jdg.2019022

[5]

Miquel Oliu-Barton. Asymptotically optimal strategies in repeated games with incomplete information and vanishing weights. Journal of Dynamics & Games, 2019, 6 (4) : 259-275. doi: 10.3934/jdg.2019018

[6]

Xiangxiang Huang, Xianping Guo, Jianping Peng. A probability criterion for zero-sum stochastic games. Journal of Dynamics & Games, 2017, 4 (4) : 369-383. doi: 10.3934/jdg.2017020

[7]

Jingzhen Liu, Ka-Fai Cedric Yiu. Optimal stochastic differential games with VaR constraints. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1889-1907. doi: 10.3934/dcdsb.2013.18.1889

[8]

Alain Bensoussan, Jens Frehse, Christine Grün. Stochastic differential games with a varying number of players. Communications on Pure & Applied Analysis, 2014, 13 (5) : 1719-1736. doi: 10.3934/cpaa.2014.13.1719

[9]

Mathias Staudigl, Srinivas Arigapudi, William H. Sandholm. Large deviations and Stochastic stability in Population Games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021021

[10]

Samuel Drapeau, Peng Luo, Alexander Schied, Dewen Xiong. An FBSDE approach to market impact games with stochastic parameters. Probability, Uncertainty and Quantitative Risk, 2021, 6 (3) : 237-260. doi: 10.3934/puqr.2021012

[11]

Lin Xu, Rongming Wang, Dingjun Yao. Optimal stochastic investment games under Markov regime switching market. Journal of Industrial & Management Optimization, 2014, 10 (3) : 795-815. doi: 10.3934/jimo.2014.10.795

[12]

Sylvain Sorin, Guillaume Vigeral. Reversibility and oscillations in zero-sum discounted stochastic games. Journal of Dynamics & Games, 2015, 2 (1) : 103-115. doi: 10.3934/jdg.2015.2.103

[13]

Antoine Hochart. An accretive operator approach to ergodic zero-sum stochastic games. Journal of Dynamics & Games, 2019, 6 (1) : 27-51. doi: 10.3934/jdg.2019003

[14]

Matt Barker. From mean field games to the best reply strategy in a stochastic framework. Journal of Dynamics & Games, 2019, 6 (4) : 291-314. doi: 10.3934/jdg.2019020

[15]

Beatris Adriana Escobedo-Trujillo, José Daniel López-Barrientos. Nonzero-sum stochastic differential games with additive structure and average payoffs. Journal of Dynamics & Games, 2014, 1 (4) : 555-578. doi: 10.3934/jdg.2014.1.555

[16]

Beatris Adriana Escobedo-Trujillo, Alejandro Alaffita-Hernández, Raquiel López-Martínez. Constrained stochastic differential games with additive structure: Average and discount payoffs. Journal of Dynamics & Games, 2018, 5 (2) : 109-141. doi: 10.3934/jdg.2018008

[17]

Alain Bensoussan, Jens Frehse, Jens Vogelgesang. Systems of Bellman equations to stochastic differential games with non-compact coupling. Discrete & Continuous Dynamical Systems, 2010, 27 (4) : 1375-1389. doi: 10.3934/dcds.2010.27.1375

[18]

Qingmeng Wei, Zhiyong Yu. Time-inconsistent recursive zero-sum stochastic differential games. Mathematical Control & Related Fields, 2018, 8 (3&4) : 1051-1079. doi: 10.3934/mcrf.2018045

[19]

Beatris A. Escobedo-Trujillo. Discount-sensitive equilibria in zero-sum stochastic differential games. Journal of Dynamics & Games, 2016, 3 (1) : 25-50. doi: 10.3934/jdg.2016002

[20]

Ryoji Sawa. Stochastic stability in the large population and small mutation limits for coordination games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021015

 Impact Factor: 

Metrics

  • PDF downloads (40)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]