在可预见未来物品的情况下，实现每轮分配的公平性突破。
Temporal Fair Division of Indivisible Items
- 基于未来物品全知，设计时序公平分配机制
- 特定场景下存在可计算的近似公平分配方案
- 揭示公平与效率不可兼得，适合资源调度研究者
我们研究一种不可分物品按序到达且必须即时、不可撤销分配的公平分配模型。已有研究显示，在此类约束下难以实现近似无嫉妒分配。本文考虑一个知情设定：算法掌握未来所有物品信息，目标是确保每轮累计分配满足近似无嫉妒性——定义为时序无嫉妒至多一项（TEF1）。研究聚焦物品均为纯利益或纯负担的情形。对于利益，尽管TEF1分配未必总存在，但我们在两参与者、两类物品、广义二元估值、单峰偏好等特殊情况下证明其存在，并给出多项式时间算法；同时证明判断是否存在TEF1分配是NP难问题。对于负担，类似结果成立，但可判定性稍弱。此外，我们还证明了TEF1与帕累托最优不兼容，即即使对两人，也难以找到最大化任意p-均福利的TEF1分配。
原文摘要 · Abstract (English)
We study a fair division model where indivisible items arrive sequentially, and must be allocated immediately and irrevocably. Previous work on online fair division has shown impossibility results in achieving approximate envy-freeness under these constraints. In contrast, we consider an informed setting where the algorithm has complete knowledge of future items, and aim to ensure that the cumulative allocation at each round satisfies approximate envy-freeness -- which we define as temporal envy-freeness up to one item (TEF1). We focus on settings where items can be exclusively goods or exclusively chores. For goods, while TEF1 allocations may not always exist, we identify several special cases where they do -- two agents, two item types, generalized binary valuations, unimodal preferences -- and provide polynomial-time algorithms for these cases. We also prove that determining the existence of a TEF1 allocation is NP-hard. For chores, we establish analogous results for the special cases, but present a slightly weaker intractability result. We also establish the incompatibility between TEF1 and Pareto-optimality, with the implication that it is intractable to find a TEF1 allocation that maximizes any $p$-mean welfare, even for two agents.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。