论文标题
在需求小的市场中，沃尔拉斯平衡
Walrasian Equilibria in Markets with Small Demands
论文作者
论文摘要
我们研究了在代理商具有$ k $的估值的市场中找到沃尔拉斯平衡的复杂性。这些估值是单位需求估值的扩展，其中捆绑包的值是其$ k $ -subsets值的最大值。对于保证沃尔拉斯平衡存在的单位需求代理，我们表明问题是在准NC中。对于$ k = 2 $，我们表明，即使估值在分分为小节（XOS）的情况下，决定是否存在Walrasian均衡，而对于$ k = 3 $，硬度将其硬度延续到预算添加的估值。此外，我们为具有二心估值或单位点数估值的市场提供多项式时间算法。
We study the complexity of finding a Walrasian equilibrium in markets where the agents have $k$-demand valuations. These valuations are an extension of unit-demand valuations where a bundle's value is the maximum of its $k$-subsets' values. For unit-demand agents, where the existence of a Walrasian equilibrium is guaranteed, we show that the problem is in quasi-NC. For $k=2$, we show that it is NP-hard to decide if a Walrasian equilibrium exists even if the valuations are fractionally subadditive (XOS), while for $k=3$ the hardness carries over to budget-additive valuations. In addition, we give a polynomial-time algorithm for markets with 2-demand single-minded valuations, or unit-demand valuations.
