Computing all solutions of Nash equilibrium problems with discrete strategy sets
From MaRDI portal
Abstract: The Nash equilibrium problem is a widely used tool to model non-cooperative games. Many solution methods have been proposed in the literature to compute solutions of Nash equilibrium problems with continuous strategy sets, but, besides some specific methods for some particular applications, there are no general algorithms to compute solutions of Nash equilibrium problems in which the strategy set of each player is assumed to be discrete. We define a branching method to compute the whole solution set of Nash equilibrium problems with discrete strategy sets. This method is equipped with a procedure that, by fixing variables, effectively prunes the branches of the search tree. Furthermore, we propose a preliminary procedure that by shrinking the feasible set improves the performances of the branching method when tackling a particular class of problems. Moreover, we prove existence of equilibria and we propose an extremely fast Jacobi-type method which leads to one equilibrium for a new class of Nash equilibrium problems with discrete strategy sets. Our numerical results show that all proposed algorithms work very well in practice.
Recommendations
- Enumeration of Nash equilibria for two-player games
- A globally convergent algorithm to compute all Nash equilibria for \(n\)-person games
- Computing all solutions of linear generalized Nash equilibrium problems
- Towards a black-box solver for finite games: computing all equlibria with gambit and PHCpack
- Finding a Nash equilibrium in noncooperativeN-person games by solving a sequence of linear stationary point problems
Cites work
- Branching and bounds tighteningtechniques for non-convex MINLP
- Competitive equilibrium in an exchange economy with indivisibilities
- Computing integral solutions of complementarity problems
- Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
- Decomposition algorithms for generalized potential games
- Equilibrium points in n -person games
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- Generalized Nash equilibrium problems
- scientific article; zbMATH DE number 53115 (Why is no real title available?)
- scientific article; zbMATH DE number 1243371 (Why is no real title available?)
- Interfaces to PATH 3.0: Design, implementation and usage
- Mixed-integer nonlinear optimization
- Non-cooperative games
- Nonsmooth optimization reformulations characterizing all solutions of jointly convex generalized Nash equilibrium problems
- Nonsmooth optimization reformulations of player convex generalized Nash equilibrium problems
- On the computation of all solutions of jointly convex generalized Nash equilibrium problems
- On the solution of the KKT conditions of generalized Nash equilibrium problems
- On the solutions of discrete nonlinear complementarity and related problems
- Parametrized variational inequality approaches to generalized Nash equilibrium problems with shared constraints
- Partial penalization for the solution of generalized Nash equilibrium problems
- Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games
- Solving discretely constrained, mixed linear complementarity problems with applications in energy
- Solving discretely-constrained Nash-Cournot games with an application to power markets
- Solving quasi-variational inequalities via their KKT conditions
- The complexity of pure Nash equilibria
Cited in
(21)- A bridge between bilevel programs and Nash games
- Algorithms for generalized potential games with mixed-integer variables
- An explicit Tikhonov algorithm for nested variational inequalities
- The Gauss-Seidel method for generalized Nash equilibrium problems of polynomials
- A decomposition method for a class of convex generalized Nash equilibrium problems
- Equilibrium selection for multi-portfolio optimization
- A parametrized variational inequality approach to track the solution set of a generalized Nash equilibrium problem
- The noncooperative fixed charge transportation problem
- On generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables
- Combining approximation and exact penalty in hierarchical programming
- The standard pessimistic bilevel problem
- A branch-and-prune algorithm for discrete Nash equilibrium problems
- A finite convergence algorithm for solving linear-quadratic network games with strategic complements and bounded strategies
- A bilevel approach to ESG multi-portfolio selection
- Equilibrium modeling and solution approaches inspired by nonconvex bilevel programming
- A globally convergent improved BFGS method for generalized Nash equilibrium problems
- A branch-and-bound algorithm for nonconvex Nash equilibrium problems
- Generalized Nash equilibrium problems with mixed-integer variables
- Computing equilibria of Cournot oligopoly models with mixed-integer quantities
- Efficient QoS processing for Internet of medical things using non-cooperative game theory: resource allocation in cloud framework
- Computing approximate Nash equilibria for integer programming games
This page was built for publication: Computing all solutions of Nash equilibrium problems with discrete strategy sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828338)
