Walrasian Equilibrium: Hardness, Approximations and Tractable Instances
Walrasian Equilibrium: Hardness, Approximations and Tractable Instances
复制标题
瓦尔拉斯均衡：硬度、近似值和易处理的实例
DOI：
10.1007/s00453-007-9103-9
复制
发表时间：
2005
期刊：
影响因子：
1.1
通讯作者：
A. Rudra
中科院分区：
文献类型：
--
作者：
Ning Chen;A. Rudra
摘要
我们研究了一种特殊的组合拍卖情形下的瓦尔拉斯均衡的复杂性问题，这种情形被称为专一拍卖，在这种拍卖中，每个参与者只对一个商品子集感兴趣。Chen等人（J. Comput.系统科学第六十九条第四款：675 - 687，2004）表明，这是NP-困难的决定存在的瓦尔拉斯均衡的一个单一的头脑拍卖，并提出了一个概念，近似瓦尔拉斯均衡称为放松瓦尔拉斯均衡。我们发现，每一个一心一意的拍卖有一个放松的瓦尔拉斯均衡，满足至少三分之二的参与者，证明了陈等人提出的猜想。系统科学69（4）：675 - 687，2004）。出于实际的考虑，我们引入了另一个近似瓦尔拉斯均衡的概念，称为弱瓦尔拉斯均衡。我们证明了弱瓦尔拉斯平衡点近似结果的NP-完全性和困难性。
为了寻找积极的结果，我们将注意力限制在收费站问题上（Guruswami等人，《离散算法研讨会论文集》（SODA），第1164 - 1173页，2005年），其中每个参与者都对某个底层图中的单个路径感兴趣。我们给出了一个多项式时间算法，以确定存在的瓦尔拉斯平衡和计算一个（如果它存在），当图是一棵树。然而，这个问题对于一般的图仍然是NP-困难的。
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.