Tropical Complementarity Problems and Nash Equilibria

DOI10.1137/21M1446861MaRDI QIDQ6171260zbMATH OpenFDO

Authors Xavier Allamigeon, Stéphane Gaubert, Frédéric Meunier

Publication date 11 August 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.05314

zbMATH Keywords

bimatrix gamesLemke-Howson algorithmlinear complementarity problemsNash equilibriatropical geometry

Mathematics Subject Classification ID

Tropical optimization (e.g., max-plus optimization) (90C24) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Abstract: Linear complementarity programming is a generalization of linear programming which encompasses the computation of Nash equilibria for bimatrix games. While the latter problem is PPAD-complete, we show that the tropical analogue of the complementarity problem associated with Nash equilibria can be solved in polynomial time. Moreover, we prove that the Lemke--Howson algorithm carries over the tropical setting and performs a linear number of pivots in the worst case. A consequence of this result is a new class of (classical) bimatrix games for which Nash equilibria computation can be done in polynomial time.

Recommendations

• Hard-to-Solve Bimatrix Games
• Settling the complexity of computing two-player Nash equilibria
• Finding Gale strings
• How do you like your equilibrium selection problems? Hard, or very hard?
• The complexity of computing a Nash equilibrium

Cites work

• A generalized complementary pivoting algorithm
• A nullstellensatz for amoebas
• A theorem on the number of Nash equilibria in a bimatrix game
• Abstract tropical linear programming
• Colorful linear programming, Nash equilibrium, and pivots
• Equilibrium computation for two-player games in strategic and extensive form
• Equilibrium Points of Bimatrix Games
• Hard-to-Solve Bimatrix Games
• scientific article; zbMATH DE number 7650372 (Why is no real title available?)
• Ky-Fan inequality, Nash equilibria in some idempotent and harmonic convex structure
• Linear and combinatorial optimization in ordered algebraic structures
• Minimax algebra
• New maximal numbers of equilibria in bimatrix games
• NP-completeness of the linear complementarity problem
• On the integer max-linear programming problem
• Settling the complexity of computing two-player Nash equilibria
• The equivalence of linear programs and zero-sum games
• The Linear Complementarity Problem
• Tropical Carathéodory with matroids
• Tropical Cramer determinants revisited
• Tropical linear-fractional programming and parametric mean payoff games
• Tropical polyhedra are equivalent to mean payoff games
• Tropical spectrahedra
• Tropicalizing the positive semidefinite cone
• Tropicalizing the simplex algorithm
• Tropically convex constraint satisfaction

Cited in

(2)

• Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria
• Semidefinite games

This page was built for publication: Tropical Complementarity Problems and Nash Equilibria

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6171260)