Colorful linear programming, Nash equilibrium, and pivots
From MaRDI portal
Publication:1707915
DOI10.1016/j.dam.2016.10.006zbMath1395.90179arXiv1409.3436OpenAlexW2962953286MaRDI QIDQ1707915
Pauline Sarrabezolles, Frédéric Meunier
Publication date: 4 April 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1409.3436
complexitySperner's lemmabimatrix gamescolorful Carathéodory theorempivoting algorithmscolorful linear programming
Noncooperative games (91A10) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)
Related Items (6)
Computing colourful simplicial depth and Median in \(\mathbb{R}_2\) ⋮ Tropical Carathéodory with matroids ⋮ Tropical Complementarity Problems and Nash Equilibria ⋮ The intersection of a matroid and an oriented matroid ⋮ Computational aspects of the colorful Carathéodory theorem ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma
- The colourful feasibility problem
- Points surrounding the origin
- Polyhedral proof methods in combinatorial optimization
- How easy is local search?
- A generalization of Caratheodory's theorem
- Complementary bases of a matroid
- On the complexity of the parity argument and other inefficient proofs of existence
- On the \(\epsilon\)-perturbation method for avoiding degeneracy
- Oriented Euler complexes and signed perfect matchings
- Very colorful theorems
- Colourful simplicial depth
- AN UPPER BOUND FOR THE NUMBER OF DIFFERENT SOLUTIONS GENERATED BY THE PRIMAL SIMPLEX METHOD WITH ANY SELECTION RULE OF ENTERING VARIABLES
- A Further Generalization of the Colourful Carathéodory Theorem
- Settling the complexity of computing two-player Nash equilibria
- On the Complexity of 2D Discrete Fixed Point Problem
- On the complexity of four polyhedral set containment problems
- Orientation in Complementary Pivot Algorithms
- Matroid intersection algorithms
- Colourful Linear Programming and its Relatives
- Equilibrium Points of Bimatrix Games
- Computing and proving with pivots
- Reducibility among Fractional Stability Problems
- Quadratically Many Colorful Simplices
- The Approximation of Fixed Points of a Continuous Mapping
- A THEOREM ON INDEPENDENCE RELATIONS
This page was built for publication: Colorful linear programming, Nash equilibrium, and pivots
