2005 | OriginalPaper | Chapter
Walrasian Equilibrium: Hardness, Approximations and Tractable Instances
Authors : Ning Chen, Atri Rudra
Published in: Internet and Network Economics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the complexity issues for Walrasian equilibrium in a special case of combinatorial auction, called single-minded auction, in which every participant is interested in only one subset of commodities. Chen et al. [5] showed that it is NP-hard to decide the existence of a Walrasian equilibrium for a single-minded auction and proposed a notion of approximate Walrasian equilibrium called relaxed Walrasian equilibrium. We show that every single-minded auction has a
$\frac{2}{3}$
-relaxed Walrasian equilibrium proving a conjecture posed in [5]. Motivated by practical considerations, we introduce another concept of approximate Walrasian equilibrium called weak Walrasian equilibrium. We show it is strongly NP-complete to determine the existence of
δ
-weak Walrasian equilibrium, for any 0<
δ
≤ 1.
In search of positive results, we restrict our attention to the tollbooth problem [15], where every participant is interested in a single path in some underlying graph. We give a polynomial time algorithm to determine the existence of a Walrasian equilibrium and compute one (if it exists), when the graph is a tree. However, the problem is still hard for general graphs.