Discrete versions of the KKM lemma and their PPAD-completeness

DOI10.1007/978-3-031-09574-0_11OpenAlexW4285270903MaRDI QIDQ2097223

Alexander Grishutin, Daniil Musatov

Publication date: 11 November 2022

Full work available at URL: https://doi.org/10.1007/978-3-031-09574-0_11

zbMATH Keywords

fixed pointsSperner's lemmadiscrete topologyKKM lemmaPPAD-completeness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equilibrium in a discrete exchange economy with money
• On total functions, existence theorems and computational complexity
• On the complexity of 2D discrete fixed point problem
• On equilibria in finite games
• The relative complexity of NP search problems
• On the complexity of the parity argument and other inefficient proofs of existence
• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• The Hairy Ball problem is PPAD-complete
• Non-cooperative games
• Rental Harmony: Sperner's Lemma in Fair Division
• Market equilibrium under separable, piecewise-linear, concave utilities
• On the Complexity of Nash Equilibria and Other Fixed Points
• Settling the complexity of computing two-player Nash equilibria
• Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria
• Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
• The Complexity of Computing a Nash Equilibrium
• Reducibility among Fractional Stability Problems
• Algorithmic Game Theory
• The Core of an N Person Game
• Equilibrium points in n -person games
• Existence of an Equilibrium for a Competitive Economy
• Settling the complexity of Nash equilibrium in congestion games