兼顾主观评价与市场价值的公平分配新模型
Fair Division with Market Values
- 引入主观估值与市场价值双重标准的分配框架
- 可保证主观估值下EF1，市场价值下SD-EF1
- 适用于资源分配、拍卖等场景，适合研究公平算法者
我们提出一种包含市场价值的公平分配模型，其中不可分物品需在具有（可加性）主观估值的参与者间分配，每个物品还附带一个对所有参与者一致的市场价值。目标是同时满足主观估值和市场价值下的公平性。我们证明：在两种估值下均满足随机占优意义下的免嫉妒至多一物（SD-EF1）的分配不一定存在；但可保证主观估值下为EF1，市场价值下为SD-EF1。此外，我们研究了帕累托最优、EFX、MMS等其他公平性保障，并探讨非可加性估值及蛋糕分割情形。过程中揭示多个待解开放问题。
原文摘要 · Abstract (English)
We introduce a model of fair division with market values, where indivisible goods must be partitioned among agents with (additive) subjective valuations, and each good additionally has a market value. The market valuation can be viewed as a separate additive valuation that holds identically across all the agents. We seek allocations that are simultaneously fair with respect to the subjective valuations and with respect to the market valuation. We show that an allocation that satisfies stochastically-dominant envy-freeness up to one good (SD-EF1) with respect to both the subjective valuations and the market valuation does not always exist, but the weaker guarantee of EF1 with respect to the subjective valuations along with SD-EF1 with respect to the market valuation can be guaranteed. We also study a number of other guarantees such as Pareto optimality, EFX, and MMS. In addition, we explore non-additive valuations and extend our model to cake-cutting. Along the way, we identify several tantalizing open questions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。