Existence and Approximation of Continuous Bayesian Nash Equilibria in Games with Continuous Type and Action Spaces
Authors: 
Shaoyan Guo, Huifu Xu, Liwei ZhangAuthors Info & Claims
Abstract
Meirowitz [Econom. Lett., 78 (2003), pp. 213--218] showed existence of the continuous Bayesian Nash equilibrium for Bayesian games with continuous type and action spaces under the condition that the best response strategies are equicontinuous. In this paper, we take a step forward by presenting some verifiable conditions for the required equicontinuity, namely, some growth conditions of the expected utility function of each player. Moreover, under some monotonicity conditions, we demonstrate uniqueness of a continuous Bayesian Nash equilibrium. We then move on to develop some computational approaches for finding an approximate continuous Bayesian Nash equilibrium. First, we restrict the response strategies to polynomial functions of certain degree over the type spaces, and consequently finding a polynomial Bayesian Nash equilibrium is reduced to solving a finite dimensional stochastic Nash equilibrium problem. Second, we apply the optimal quantization method to discretize the finite dimensional stochastic Nash equilibrium problem so that the discretized problem becomes an ordinary finite dimensional deterministic Nash equilibrium problem which can be readily solved by existing numerical methods in the literature. In the case when the discretization approach is carried out by sample average approximation, we show exponential rate of convergence with respect to sample size. Finally, we carry out numerical tests on the combined approaches through an illustration with rent-seeking games.
References
[1]
V. Andrievskii and H.-P. Blatt, On approximation of continuous functions by trigonometric polynomials, J. Approx. Theory, 163 (2011), pp. 249--266.
[2]
S. Athey, Single crossing properties and the existence of pure strategy equilibria in games of incomplete information, Econometrica, 69 (2001), pp. 861--889.
[3]
R. J. Aumann, Integrals of set-valued functions, J. Math. Anal. Appl., 12 (1965), pp. 1--12.
[4]
D. Bampou and D. Kuhn, Polynomial approximations for continuous linear programs, SIAM J. Optim., 22 (2012), pp. 628--648.
[5]
B. Bank, J. Guddat, D. Klatte, B. Kummer, and K. Tammer, Nonlinear Parametric Optimization, Akademie-Verlag, Berlin, 1982.
[6]
A. Ben-Tal, A. Goryashko, E. Guslitzer, and A. Nemirovski, Adjustable robust solutions of uncertain linear programs, Math. Program., 99 (2004), pp. 351--376.
[7]
J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer, New York, 2000.
[8]
A. Brook, D. Kendrick, and A. Meeraus, GAMS: A User's Guide, The Scientific Press, South San Francisco, CA, 1988.
[9]
A. Calvó-Armengol, J. de Martí, and A. Prat, Communication and influence, Theor. Econ., 10 (2015), pp. 649--690.
[10]
R. M. Dudley, The speed of mean Glivenko-Cantelli convergence, Ann. Math. Statist., 40 (1969), pp. 40--50.
[11]
C. Ewerhart, Unique equilibrium in rent-seeking contests with a continuum of types, Econom. Lett., 125 (2014), pp. 115--118.
[12]
C. Ewerhart and F. Quartieri, Unique equilibrium in contests with incomplete information, Econom. Theory, 70 (2020), pp. 243--271.
[13]
F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003.
[14]
M. Fey, Rent-seeking contests with incomplete information, Public Choice, 135 (2008), pp. 225--236.
[15]
N. Fournier and A. Guilline, On the rate of convergence in Wasserstein distance of the empirical measure, Probab. Theory Related Fields, 162 (2015), pp. 707--738.
[16]
S. Guo and H. Xu, Statistical robustness in utility preference robust optimization models, Math. Program., 190 (2021), pp. 679--720.
[17]
S. Guo, H. Xu, and L. Zhang, Continuous Behavioural Function Equilibria and Approximation Schemes in Bayesian Games with Non-Finite Type and Action Spaces, preprint, arXiv:1710.04968, 2017.
[18]
N. Hadjisavvas, S. Komlósi and S. Schaible, Handbook of Generalized Convexity and Generalized Monotonicity, Springer, Boston, 2005.
[19]
J. Harsanyi, Games with incomplete information played by “Bayesian” players, I--III, in Papers in Game Theory, Theory Decis. Libr., vol 28, Springer, Dordrecht, the Netherlands, 1982, pp. 115--170.
[20]
Y. Kim and M. C. Ferris, Solving equilibrium problems using extended mathematical programming, Math. Program. Comput., 11 (2019), pp. 457--501.
[21]
A. Meirowitz, On the existence of equilibria to Bayesian games with non-finite type and action spaces, Econom. Lett., 78 (2003), pp. 213--218.
[22]
G. C. Pflug and A. Pichler, Multistage Stochastic Optimization, Springer International Publishing, Basel, Switzerland, 2014.
[23]
G. M. Phillips, Interpolation and Approximation by Polynomials, Springer, New York, 2003.
[24]
U. Ravat and U. V. Shanbhag, On the characterization of solution sets of smooth and nonsmooth convex stochastic Nash games, SIAM J. Optim., 21 (2011), pp. 1168--1199.
[25]
U. Ravat and U. V. Shanbhag, On the existence of solutions to stochastic quasi-variational inequality and complementarity problems, Math. Program., 165 (2017), pp. 291--330.
[26]
S. F. Richard and W. R. Zame, Proper preferences and quasi-concave utility functions, J. Math. Econom., 15 (1986), pp. 231--247.
[27]
S. M. Robinson, An application of error bounds for convex programming in a linear space, SIAM J. Control Optim., 13 (1975), pp. 271--273.
[28]
R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1997.
[29]
J. B. Rosen, Existence and uniqueness of equilibrium points for concave n-person games Econometrica, 33 (1965), pp. 520--534.
[30]
A. Shapiro, D. Dentcheva, and A. Ruszczyński, Lectures on Stochastic Programming: Modeling and Theory, SIAM, Philadelphia, 2009.
[31]
A. Shapiro and H. Xu, Stochastic mathematical programs with equilibrium constraints, modeling and sample average approximation, Optimization, 57 (2008), pp. 395--418.
[32]
G. Tullock, Efficient rent seeking, in Toward a Theory of the Rent-Seeking Society, J. Buchanan, R. Tollison, and G. Tullock, eds., Texas A&M University Press, College Station, TX, 1980, pp. 97--112.
[33]
G. Tullock, The welfare costs of tariffs, monopolies, and theft, West. Econ. J., 5 (1967), pp. 224--232.
[34]
A. Tversky and D. Kahneman, Advances in prospect theory: Cumulative representation of uncertainty, J. Risk Uncertain., 5 (1992), pp. 297--323.
[35]
T. Ui, Bayesian Nash equilibrium and variational inequalities, J. Math. Econom., 63 (2016), pp. 139--146.
[36]
K. Weierstrass, Über die analytische Darstellbarkeit sogenannter willkürlicher Functionen einer reellen Veränderlichen, Sitzungsber. Akad. Berlin, 1885, pp. 633--639.
[37]
H. Xu and D. Zhang, Stochastic Nash equilibrium problems: Sample average approximation and applications, Comput. Optim. Appl., 55 (2013), pp. 597--645.
[38]
E. Zeidler, Nonlinear Functional Analysis and Its Applications I: Fixed-Point Theorems, Springer-Verlag, New York, 1985.
Recommendations
Approximations of Nash equilibria
Inspired by previous works on approximations of optimization problems and recent papers on the approximation of Walrasian and Nash equilibria and on stochastic variational inequalities, the present paper investigates the approximation of Nash equilibria ...
On cheating in sealed-bid auctions
Special issue: The fourth ACM conference on electronic commerceMotivated by the rise of online auctions and their relative lack of security, this paper analyzes two forms of cheating in sealed-bid auctions. The first type of cheating we consider occurs when the seller examines the bids of a second-price auction ...
Pure Nash equilibria in restricted budget games
In budget games, players compete over resources with finite budgets. For every resource, a player has a specific demand and as a strategy, he chooses a subset of resources. If the total demand on a resource does not exceed its budget, the utility of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
DOI:10.1137/sjope8.31.4
Issue’s Table of Contents© 2021, Society for Industrial and Applied Mathematics.
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 01 January 2021
Author Tags
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Jan 2025