Walrasian equilibrium: Hardness, approximations and tractable instances

DOI10.1007/s00453-007-9103-9zbMath1142.91472OpenAlexW1500978555WikidataQ106376685 ScholiaQ106376685MaRDI QIDQ943867

Ning Chen, Atri Rudra

Publication date: 12 September 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9103-9

zbMATH Keywords

NP-hardApproximationWalrasian equilibriumCombinatorial auctionSingle-minded auction

Mathematics Subject Classification ID

Special types of economic equilibria (91B52) Microeconomic theory (price theory and economic markets) (91B24) Auctions, bargaining, bidding and selling, and other market models (91B26) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare ⋮ Unnamed Item ⋮ Nash stability in additively separable hedonic games and community structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation of Walrasian equilibrium in single-minded auctions
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Decomposition by clique separators
• Walrasian equilibrium with gross substitutes
• Competitive equilibrium in an exchange economy with indivisibilities
• On complexity of single-minded auction
• Combinatorial Auctions: A Survey
• The complexity of computing a Nash equilibrium
• On the complexity of equilibria
• An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
• Job Matching, Coalition Formation, and Gross Substitutes
• Existence of an Equilibrium for a Competitive Economy
• Computing correlated equilibria in multi-player games

This page was built for publication: Walrasian equilibrium: Hardness, approximations and tractable instances