论文标题
双值实用程序下的随机分配：分析Hylland-Zeckhauser，Nash-Bargaining和其他规则
Random Assignment Under Bi-Valued Utilities: Analyzing Hylland-Zeckhauser, Nash-Bargaining, and other Rules
论文作者
论文摘要
Hylland-Zeckhauser（HZ）规则是随机分配项目的众所周知的规则。该规则的复杂性最近与Vazirani和Yannakakis（2020）提出了对双重评估实用程序下规则的强烈多项式算法，并提供了一些一般见解。我们研究了具有双价值公用事业的代理商的规则。我们指出了HZ规则的几个特征，与文献中的几个著名规则相关。结果，我们指出了Hz溶液的替代性多项式时间算法。我们还从计算HZ解决方案到基于词汇或NASH社会福利的众所周知的解决方案的减少。一个有趣的对比是，HZ规则是群体进行的，而与收入相等的不受限制的竞争平衡甚至都不是策略性的。我们阐明从1-0实用程序转移到更通用的双价值实用程序时，哪些结果会发生变化。最后，我们证明，紧密相关的NASH讨价还价解决方案即使在1-0的公用事业下也违反了嫉妒和防止战略性。
The Hylland-Zeckhauser (HZ) rule is a well-known rule for random assignment of items. The complexity of the rule has received renewed interest recently with Vazirani and Yannakakis (2020) proposing a strongly polynomial-time algorithm for the rule under bi-valued utilities, and making several general insights. We study the rule under the case of agents having bi-valued utilities. We point out several characterizations of the HZ rule, drawing clearer relations with several well-known rules in the literature. As a consequence, we point out alternative strongly polynomial-time algorithms for the HZ solution. We also give reductions from computing the HZ solution to computing well-known solutions based on leximin or Nash social welfare. An interesting contrast is that the HZ rule is group-strategyproof whereas the unconstrained competitive equilibrium with equal incomes rule is not even strategyproof. We clarify which results change when moving from 1-0 utilities to the more general bi-valued utilities. Finally, we prove that the closely related Nash bargaining solution violates envy-freeness and strategyproofness even under 1-0 utilities.
