Combinatorial walrasian equilibrium
Combinatorial walrasian equilibrium
复制标题
组合瓦尔拉斯平衡
DOI：
10.1145/2488608.2488617
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Brendan Lucier
中科院分区：
文献类型：
--
作者：
M. Feldman;N. Gravin;Brendan Lucier
我们研究了一个组合市场设计问题，其中一组不可分割的物品在均衡约束下被定价并出售给潜在的买家。这类问题的经典解概念是瓦尔拉斯均衡(WE)，它提供了一个简单而透明的定价结构，实现了最优的社会福利。WE概念的主要弱点是，它只存在于非常有限的情况下。为了克服这一局限，我们引入了组合瓦尔拉斯平衡(CWE)的概念，它是WE的自然松弛。CWE和(非组合)我们之间的区别在于，卖家可以在销售前将物品打包成不可分割的捆绑，而市场不一定是透明的。我们证明了每个估值曲线都允许CWE获得至少一半的最优(无约束)社会福利。此外，我们设计了一个多时间算法，在给定任意分配X的情况下，计算至少达到X福利的一半的CWE。因此，寻找具有高社会福利的CWE的经济问题归结为社会福利近似的算法问题。此外，我们还证明了每个估值曲线都允许CWE提取最优福利的对数分数作为收入。最后，当卖家被限制只能使用物品价格时，这些结果得到了强大的下限的补充，这促使了捆绑的使用。我们结果的强势部分来自于它们的普遍性-我们的结果适用于任意的估值，可能显示出替代和补充的复杂组合。
We study a combinatorial market design problem, where a collection of indivisible objects is to be priced and sold to potential buyers subject to equilibrium constraints. The classic solution concept for such problems is Walrasian Equilibrium (WE), which provides a simple and transparent pricing structure that achieves optimal social welfare. The main weakness of the WE notion is that it exists only in very restrictive cases. To overcome this limitation, we introduce the notion of a Combinatorial Walrasian equilibium (CWE), a natural relaxation of WE. The difference between a CWE and a (non-combinatorial) WE is that the seller can package the items into indivisible bundles prior to sale, and the market does not necessarily clear. We show that every valuation profile admits a CWE that obtains at least half of the optimal (unconstrained) social welfare. Moreover, we devise a poly-time algorithm that, given an arbitrary allocation X, computes a CWE that achieves at least half of the welfare of X. Thus, the economic problem of finding a CWE with high social welfare reduces to the algorithmic problem of social-welfare approximation. In addition, we show that every valuation profile admits a CWE that extracts a logarithmic fraction of the optimal welfare as revenue. Finally, these results are complemented by strong lower bounds when the seller is restricted to using item prices only, which motivates the use of bundles. The strength of our results derives partly from their generality --- our results hold for arbitrary valuations that may exhibit complex combinations of substitutes and complements.