摘要翻译:
我们研究了在一组$N$Agents中,一组$M$Inclusive商品的公平分割问题。虽然在不可分商品的环境中通常不存在无嫉妒分配,但如果引入一定数量的可分商品(金钱),则可以实现无嫉妒分配。具体地说,Halpern和Shah(Sagt2019,pp.374-389)表明,在给定附加估值函数的情况下,每个项目的边际价值为每个代理最多1美元,总是存在一个无嫉妒分配,需要最多$(n-1)\cdot m美元的补贴。作者还推测,补贴N-1美元足以进行附加估值。我们证明了这个猜想。事实上,每个代理最多一美元的补贴就足以保证无嫉妒分配的存在。进一步,我们证明了对于一般的单调估值函数,一个无嫉妒的分配总是存在的,每个代理人的补贴至多为2(n-1)$。特别是,单调估值所需的补贴总额与项目数量无关。
---
英文标题:
《One Dollar Each Eliminates Envy》
---
作者:
Johannes Brustle and Jack Dippel and Vishnu V. Narayan and Mashbat
Suzuki and Adrian Vetta
---
最新提交年份:
2019
---
分类信息:
一级分类: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.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--
---
英文摘要:
We study the fair division of a collection of $m$ indivisible goods amongst a set of $n$ agents. Whilst envy-free allocations typically do not exist in the indivisible goods setting, envy-freeness can be achieved if some amount of a divisible good (money) is introduced. Specifically, Halpern and Shah (SAGT 2019, pp.374-389) showed that, given additive valuation functions where the marginal value of each item is at most one dollar for each agent, there always exists an envy-free allocation requiring a subsidy of at most $(n-1)\cdot m$ dollars. The authors also conjectured that a subsidy of $n-1$ dollars is sufficient for additive valuations. We prove this conjecture. In fact, a subsidy of at most one dollar per agent is sufficient to guarantee the existence of an envy-free allocation. Further, we prove that for general monotonic valuation functions an envy-free allocation always exists with a subsidy of at most $2(n-1)$ dollars per agent. In particular, the total subsidy required for monotonic valuations is independent of the number of items.
---
PDF链接:
https://arxiv.org/pdf/1912.02797