A Bayesian optimization approach to find Nash equilibria
From MaRDI portal
Abstract: Game theory finds nowadays a broad range of applications in engineering and machine learning. However, in a derivative-free, expensive black-box context, very few algorithmic solutions are available to find game equilibria. Here, we propose a novel Gaussian-process based approach for solving games in this context. We follow a classical Bayesian optimization framework, with sequential sampling decisions based on acquisition functions. Two strategies are proposed, based either on the probability of achieving equilibrium or on the Stepwise Uncertainty Reduction paradigm. Practical and numerical aspects are discussed in order to enhance the scalability and reduce computation time. Our approach is evaluated on several synthetic game problems with varying number of players and decision space dimensions. We show that equilibria can be found reliably for a fraction of the cost (in terms of black-box evaluations) compared to classical, derivative-based algorithms. The method is available in the R package GPGame available on CRAN at https://cran.r-project.org/package=GPGame.
Recommendations
- Bayesian Nash equilibrium and variational inequalities
- An optimization approach for approximate Nash equilibria
- scientific article; zbMATH DE number 1210333
- An experiment to evaluate Bayesian learning of Nash equilibrium play
- Bayesian learning, smooth approximate optimal behavior, and convergence to \({\varepsilon}\)-Nash equilibrium
- Approximate equilibria for Bayesian games
- On the existence of Nash equilibrium in Bayesian games
- Bayesian learning and convergence to Nash equilibria without common priors
- Bayesian Nash equilibrium existence in (almost continuous) contests
Cites work
- scientific article; zbMATH DE number 43985 (Why is no real title available?)
- scientific article; zbMATH DE number 2013849 (Why is no real title available?)
- scientific article; zbMATH DE number 6869269 (Why is no real title available?)
- scientific article; zbMATH DE number 2208228 (Why is no real title available?)
- scientific article; zbMATH DE number 3204219 (Why is no real title available?)
- scientific article; zbMATH DE number 6276166 (Why is no real title available?)
- 10.1162/1532443041827880
- A Comparison of Three Methods for Selecting Values of Input Variables in the Analysis of Output from a Computer Code
- A case study competition among methods for analyzing large spatial data
- A general framework for constrained Bayesian optimization using information-based search
- A supermartingale approach to Gaussian process based sequential design of experiments
- An informational approach to the global optimization of expensive-to-evaluate functions
- Augmented Lagrangian methods for the solution of generalized Nash equilibrium problems
- Computation of multivariate normal and \(t\) probabilities
- Distributed algorithms for the computation of noncooperative equilibria
- Efficient global optimization of expensive black-box functions
- Fast prediction of deterministic functions using sparse grid experimental designs
- Fast update of conditional simulation ensembles
- Games with randomly disturbed payoffs: a new rationale for mixed-strategy equilibrium points
- Gaussian processes for machine learning.
- Generalized Nash equilibrium problems
- Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting
- Kernels for vector-valued functions: a review
- Lenient learning in independent-learner stochastic cooperative games
- Multidisciplinary topology optimization solved as a Nash game
- Nested kriging predictions for datasets with a large number of observations
- Neumann-Dirichlet Nash strategies for the solution of elliptic Cauchy problems
- On Structure and Computation of Generalized Nash Equilibria
- On a Generalization of the Lemke–Howson Algorithm to Noncooperative N-Person Games
- On relaxation algorithms in computation of noncooperative equilibria
- Relaxation techniques and asynchronous algorithms for on-line computation of non-cooperative equilibria
- Robust Nash equilibria in \(4\)-person non-cooperative games: uniqueness and reformulation
- Sequential design for optimal stopping problems
- Sequential design of computer experiments for the estimation of a probability of failure
- Stationary features and cat detection
- Stochastic Games
- Stochastic differential games
Cited in
(11)- A heuristic optimization of Bayesian incentive-compatible cake-cutting
- Bayesian Nash equilibrium in “linear” Cournot models with private information about costs
- Zeroth-order single-loop algorithms for nonconvex-linear minimax problems
- Derivative-free alternating projection algorithms for general nonconvex-concave minimax problems
- scientific article; zbMATH DE number 7306856 (Why is no real title available?)
- Bayesian Nash equilibrium and variational inequalities
- Zeroth-order algorithms for nonconvex-strongly-concave minimax problems with improved complexities
- GPGame
- Nash game based efficient global optimization for large-scale design problems
- Ex post Nash equilibrium in linear Bayesian games for decision making in multi-environments
- A game theory-based multi-agent system for expensive optimisation problems
Describes a project that uses
Uses Software
This page was built for publication: A Bayesian optimization approach to find Nash equilibria
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q116040)
