nash equilibrium

The fixed-point bundle method over product-of-simplex domains arising from game equilibria

Categories Complementarity and Variational Inequalities, Game Theory Tags , , , ,

Developing general-purpose algorithms with global asymptotic convergence guarantees for Nash equilibria of general-sum games remains a longstanding challenge. This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from simplex domains to product-of-simplex domains, enabling its direct application to Nash equilibrium computation. The resulting fixed-point bundle exhibits a composite fiber bundle structure. The … Read more

Efficient Warm-Start Strategies for Nash-based Linear Complementarity Problems via Bilinear Approximation

Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Global Optimization Applications Tags , , ,

We present an effective warm-starting scheme for solving large linear complementarity problems (LCPs) arising from Nash equilibrium problems. The approach generates high-quality starting points that, when passed to the PATH solver, yield substantial reductions in computational time and variance. Our warm-start routine reformulates each agent’s LP using strong duality, leading to a master problem with … Read more

A Jacobi-type Newton method for Nash equilibrium problems with descent guarantees

Categories Game Theory, Nonlinear Optimization, Other Topics Tags , , , ,

A common strategy for solving an unconstrained two-player Nash equilibrium problem with continuous variables is applying Newton’s method to the system obtained by the corresponding first-order necessary optimality conditions. However, when taking into account the game dynamics, it is not clear what is the goal of each player when considering they are taking their current … Read more

A Jacobi-type Newton method for Nash equilibrium problems with descent guarantees

Categories Game Theory, Other Topics Tags , , , , ,

A common strategy for solving an unconstrained two-player Nash equilibrium problem with continuous variables is applying Newton’s method to the system of nonlinear equations obtained by the corresponding first-order necessary optimality conditions. However, when taking into account the game dynamics, it is not clear what is the goal of each player when considering that they … Read more

Multilinear formulations for computing Nash equilibrium of multi-player matrix games

Categories (Mixed) Integer Nonlinear Programming, Game Theory, Global Optimization Applications Tags , , , ,

We present multilinear and mixed-integer multilinear programs to find a Nash equilibrium in multi-player strategic-form games. We compare the formulations to common algorithms in Gambit, and conclude that a multilinear feasibility program finds a Nash equilibrium faster than any of the methods we compare it to, including the quantal response equilibrium method, which is recommended … Read more

An equivalent mathematical program for games with random constraints

Categories Game Theory, Stochastic Programming Tags , , ,

This paper shows that there exists a Nash equilibrium of an n-player chance-constrained game for elliptically symmetric distributions. For a certain class of payoff functions, we suitably construct an equivalent mathematical program whose global maximizer is a Nash equilibrium. ArticleDownload View PDF

Games with joint chance constraints under mixture distributions

Categories Game Theory, Stochastic Programming Tags , ,

We consider an n-player non-cooperative game where each player has expected value payoff function and her strategy set is defined by a joint chance constraint. The random constraint vectors are independent. We propose a subset of probability distributions from elliptical family of distributions. We consider the case when the probability distribution of each random constraint … Read more

Games with distributionally robust joint chance constraints

Categories Game Theory, Stochastic Programming Tags , , ,

This paper studies an n-player non-cooperative game with strategy sets defined by stochastic linear constraints. The stochastic constraints of each player are jointly satisfied with a probability exceeding a given threshold. We consider the case where the row vectors defining the constraints are independent random vectors whose probability distributions are not completely known and belong … Read more

Assessment of Climate Agreements over the Long Term with Strategic Carbon Dioxyde Removal Activity

Categories Applications - OR and Management Sciences, Game Theory Tags , , , ,

In this paper we extend a game theoretic meta-model used to assess the future of Paris agreement to the time horizon 2100 and we include in the strategic decisions of the negotiating coalitions the use of Carbon Dioxyde Removal (CDR) technologies. The meta-game model is calibrated through statistical emulation of GEMINI-E3, a world computable general … Read more

A characterization of Nash equilibrium for the games with random payoffs

Categories Game Theory, Stochastic Programming Tags , , , , ,

We consider a two player bimatrix game where the entries of the payoff matrices are random variables. We formulate this problem as a chance-constrained game by considering that the payoff of each player is defined using a chance constraint. We consider the case where the entries of the payoff matrices are independent normal/Cauchy random variables. … Read more