On the complexity of market equilibria with maximum social welfare

DOI10.1016/J.IPL.2005.09.004MaRDI QIDQ1044745zbMATH OpenOpenAlexFDO

Authors Xiaotie Deng, Li-Sha Huang

Publication date 18 December 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2005.09.004

zbMATH Keywords

computational complexitymarket equilibriumNP-hardnessLeontief economy

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Special types of economic equilibria (91B52) Special types of economic markets (including Cournot, Bertrand) (91B54) Welfare economics (91B15)

Recommendations

• The complexity of equilibria: Hardness results for economies via a correspondence with games
• Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria
• On the complexity of price equilibria
• The complexity of economic equilibria for house allocation markets
• Exchange market equilibria with Leontief's utility: freedom of pricing leads to rationality

Cites work

• scientific article; zbMATH DE number 3894789 (Why is no real title available?)
• A path to the Arrow-Debreu competitive market equilibrium
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Automata, Languages and Programming
• Existence of an Equilibrium for a Competitive Economy
• Finite solution of pure trade markets with Cobb-Douglas utilities
• Leontief economies encode nonzero sum two-player games
• Market equilibrium via the excess demand function
• Nash and correlated equilibria: Some complexity considerations
• New complexity results about Nash equilibria
• On the complexity of price equilibria
• On the polynomial time computation of equilibria for certain exchange economies
• The complexity of economic equilibria for house allocation markets
• The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results

Cited in

(10)

• Market equilibria with hybrid linear-Leontief utilities
• Core pricing in combinatorial exchanges with financially constrained buyers: computational hardness and algorithmic solutions
• The Complexity of Non-Monotone Markets
• The complexity of economic equilibria for house allocation markets
• On the computational complexity of the maximum trade problem
• Recent development in computational complexity characterization of Nash equilibrium
• scientific article; zbMATH DE number 5697111 (Why is no real title available?)
• The complexity of equilibria: Hardness results for economies via a correspondence with games
• On the complexity of price equilibria
• Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets

This page was built for publication: On the complexity of market equilibria with maximum social welfare

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