英文标题：
《Fair and Efficient Allocations under Lexicographic Preferences》
---
作者：
Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, Lirong Xia
---
最新提交年份：
2020
---
英文摘要：
  Envy-freeness up to any good (EFX) provides a strong and intuitive guarantee of fairness in the allocation of indivisible goods. But whether such allocations always exist or whether they can be efficiently computed remains an important open question. We study the existence and computation of EFX in conjunction with various other economic properties under lexicographic preferences--a well-studied preference model in artificial intelligence and economics. In sharp contrast to the known results for additive valuations, we not only prove the existence of EFX and Pareto optimal allocations, but in fact provide an algorithmic characterization of these two properties. We also characterize the mechanisms that are, in addition, strategyproof, non-bossy, and neutral. When the efficiency notion is strengthened to rank-maximality, we obtain non-existence and computational hardness results, and show that tractability can be restored when EFX is relaxed to another well-studied fairness notion called maximin share guarantee (MMS).
---
中文摘要：
无嫉妒直至任何商品（EFX）为不可分割商品的分配提供了强大而直观的公平保障。但这种分配是否总是存在，或者是否可以有效计算，仍然是一个重要的开放问题。我们研究了词典偏好下EFX的存在性和计算以及其他各种经济属性，这是人工智能和经济学中研究得很好的偏好模型。与加性估值的已知结果形成鲜明对比的是，我们不仅证明了EFX和帕累托最优配置的存在，而且事实上提供了这两个属性的算法特征。此外，我们还描述了这些机制的特点，即无策略性、非专横性和中立性。当效率概念被强化为秩极大值时，我们得到了不存在和计算困难的结果，并表明当EFX放松到另一个被广泛研究的公平概念，即最大共享保证（MMS）时，可处理性可以恢复。
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Economics        经济学
二级分类：Theoretical Economics        理论经济学
分类描述：Includes theoretical contributions to Contract Theory, Decision Theory, Game Theory, General Equilibrium, Growth, Learning and Evolution, Macroeconomics, Market and Mechanism Design, and Social Choice.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--

---
PDF下载：
-->