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
- 10.1162/1532443041827880
- A case study competition among methods for analyzing large spatial data
- A Comparison of Three Methods for Selecting Values of Input Variables in the Analysis of Output from a Computer Code
- 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
- 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?)
- 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 a Generalization of the Lemke–Howson Algorithm to Noncooperative N-Person Games
- On relaxation algorithms in computation of noncooperative equilibria
- On Structure and Computation of Generalized Nash 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 differential games
- Stochastic Games
Cited in
(14)- Ex post Nash equilibrium in linear Bayesian games for decision making in multi-environments
- Bayesian Nash equilibrium and variational inequalities
- A heuristic optimization of Bayesian incentive-compatible cake-cutting
- GPGame
- Bayesian Nash equilibrium in “linear” Cournot models with private information about costs
- A game theory-based multi-agent system for expensive optimisation problems
- The Kalai-Smorodinsky solution for many-objective Bayesian optimization
- Zeroth-order single-loop algorithms for nonconvex-linear minimax problems
- Zeroth-order algorithms for nonconvex-strongly-concave minimax problems with improved complexities
- Derivative-free alternating projection algorithms for general nonconvex-concave minimax problems
- A game theoretic perspective on Bayesian many-objective optimization
- Multiobjective optimization using the R2 utility
- Empirical game theoretic analysis: a survey
- Nash game based efficient global optimization for large-scale design 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)
