The complexity of equilibria: Hardness results for economies via a correspondence with games

DOI10.1016/j.tcs.2008.08.007zbMath1162.91015OpenAlexW2071472458MaRDI QIDQ959811

Yinyu Ye, Bruno Codenotti, Amin Saberi, Kasturi R. Varadarajan

Publication date: 12 December 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.08.007

zbMATH Keywords

linear complementarityNash equilibriumNP-hardnessexchange economybimatrix gamesquasi-equilibriumLeontief economyNP-completness

Mathematics Subject Classification ID

Special types of economic equilibria (91B52) 2-person games (91A05) Applications of game theory (91A80) Auctions, bargaining, bidding and selling, and other market models (91B26) Special types of economic markets (including Cournot, Bertrand) (91B54)

Related Items (6)

Atomic Leontievian Cournotian traders are always Walrasian ⋮ Unnamed Item ⋮ Equilibria, fixed points, and complexity classes ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

Cites Work

• Unnamed Item
• Unnamed Item
• Nash and correlated equilibria: Some complexity considerations
• A finite algorithm for the linear exchange model
• The linear exchange model
• On the complexity of the parity argument and other inefficient proofs of existence
• Simple complexity from imitation games
• A path to the Arrow-Debreu competitive market equilibrium
• Non-cooperative games
• The complexity of computing a Nash equilibrium
• Auction algorithms for market equilibrium
• Market equilibrium via the excess demand function
• Finite solution of pure trade markets with Cobb-Douglas utilities
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A Survey of Eigenvector Methods for Web Information Retrieval
• Automata, Languages and Programming
• Existence of an Equilibrium for a Competitive Economy
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: The complexity of equilibria: Hardness results for economies via a correspondence with games