Walrasian equilibrium: Hardness, approximations and tractable instances

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 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 δ5-weak Walrasian equilibrium, for any 0 < 6 ≤ 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.