Walrasian Equilibrium: Hardness,Approximations and Tractable Instances |
| |
Authors: | Ning Chen Atri Rudra |
| |
Affiliation: | (1) Department of Computer Science & Engineering, University of Washington, Seattle, WA 98105, USA |
| |
Abstract: | 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. (J. Comput. Syst. Sci. 69(4):
675–687, 2004) 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 relaxed Walrasian equilibrium that satisfies at least two-thirds of the participants, proving a conjecture posed in
Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004). Motivated by practical considerations, we introduce another concept of approximate Walrasian equilibrium called weak Walrasian
equilibrium. We show NP-completeness and hardness of approximation results for weak Walrasian equilibria.
In search of positive results, we restrict our attention to the tollbooth problem (Guruswami et al. in Proceedings of the
Symposium on Discrete Algorithms (SODA), pp. 1164–1173, 2005), 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 NP-hard for general graphs. |
| |
Keywords: | Walrasian equilibrium Combinatorial auction Single-minded auction NP-hard Approximation |
本文献已被 SpringerLink 等数据库收录! |
|