Competitive Allocation of a Mixed Manna
Competitive Allocation of a Mixed Manna
复制标题
混合甘露的竞争性分配
DOI：
10.1137/1.9781611976465.85
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Bhaskar Ray Chaudhury, Jugal Garg
中科院分区：
文献类型：
--
作者：
Bhaskar Ray Chaudhury, Jugal Garg
研究了可加可分分段线性凹（SPLC）效用下混合甘露分配的公平划分问题。混合吗哪包含了每个人都喜欢和每个人都不喜欢的东西，以及一些人喜欢和其他人不喜欢的东西。Bogomolnaia等人的开创性工作论述了为什么分配混合甘露比分配好甘露或坏甘露更复杂，以及为什么竞争均衡是最好的机制。他们还提供了均衡的存在性，并建立了它的特殊性质（例如，即使在线性效用下，平衡点的非凸和断开集），但没有解决计算均衡的问题。我们的主要成果是一个基于Lemke方案的类简单算法，用于在SPLC公用事业下计算混合甘露的竞争分配，这是线性的严格推广。在随机生成实例上的实验结果表明，该算法在实际应用中具有较快的速度。对于好吗哪来说，这个问题是ppad -困难的，对于坏吗哪，我们也显示了类似的结果。考虑到这些ppad -硬度结果，设计这样一个算法是唯一已知的非枚举选项。我们的算法也产生了一些新的结构性质作为简单的推论。我们得到了一个更一般的设置的存在性的（建设性的）证明，问题在PPAD中的隶属性，有理值解和奇数解的性质。最后一个性质也肯定地解决了[14]的猜想。
We study the fair division problem of allocating a mixed manna under additively separable piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone likes and bads that everyone dislikes, as well as items that some like and others dislike. The seminal work of Bogomolnaia et al. [14] argue why allocating a mixed manna is genuinely more complicated than a good or a bad manna, and why competitive equilibrium is the best mechanism. They also provide the existence of equilibrium and establish its peculiar properties (e.g., non-convex and disconnected set of equilibria even under linear utilities), but leave the problem of computing an equilibrium open.Our main result is a simplex-like algorithm based on Lemke's scheme for computing a competitive allocation of a mixed manna under SPLC utilities, a strict generalization of linear. Experimental results on randomly generated instances suggest that our algorithm will be fast in practice. The problem is known to be PPAD-hard for the case ofgoodmanna [24], and we also show a similar result for the case ofbadmanna. Given these PPAD-hardness results, designing such an algorithm is the only non-enumerative option known.Our algorithm also yields several new structural properties as simple corollaries. We obtain a (constructive) proof of existence for a far more general setting, membership of the problem in PPAD, rational-valued solution, and odd number of solutions property. The last property also settles the conjecture of [14] in the affirmative.
登录
查看更多内容
DOI：
10.2139/ssrn.2914241
发表时间：
2017-02
期刊：
National Research University Higher School of Economics Research Paper Series
影响因子：
--
作者：
Anna Bogomolnaia;H. Moulin;Fedor Sandomirskiy;E. Yanovskaya
通讯作者：
Anna Bogomolnaia;H. Moulin;Fedor Sandomirskiy;E. Yanovskaya
DOI：
10.1287/moor.2023.1361
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
Simina Brânzei;Fedor Sandomirskiy
通讯作者：
Fedor Sandomirskiy
DOI：
--
发表时间：
2019
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
Xin Huang;P. Lu
通讯作者：
P. Lu
使用混合甘露计算竞争均衡
DOI：
--
发表时间：
2020
期刊：
AAMAS Conference proceedings
影响因子：
--
作者：
Garg, Jugal;McGlaughlin, Peter
通讯作者：
McGlaughlin, Peter
可分离分段线性凹效用下不可分项的纳什社会福利
DOI：
--
发表时间：
2016
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Nima Anari;Tung Mai;S. Gharan;V. Vazirani
通讯作者：
V. Vazirani