允许有限共享可恢复难以实现的公平分配，让资源分配更合理。
Maximin Share Guarantees via Limited Cost-Sensitive Sharing
- 通过控制性共享，确保至少半数人可获得精确公平分配。
- 设计算法在共享成本可控时，达到接近最优的公平保障。
- 提出新公平标准SMMS，适用于两人或相同偏好场景。
研究在允许有限共享情形下的不可分资源公平分配问题，即每件物品最多可分配给至多k名参与者，但需承担共享成本。经典最大最小份额（MMS）分配在许多情况下不存在，而我们证明：当物品可被成本敏感地分配给至少一半参与者且人数为偶数时，精确MMS分配始终存在；奇数人数时略弱。进一步提出共享袋填充算法，可保证(1−C)(k−1)近似MMS，其中C为最大共享成本；当(1−C)(k−1)≥1时，即恢复精确分配。我们引入共享最大最小份额（SMMS）作为MMS在k-共享设置下的自然扩展。在相同效用下及两人情形中，SMMS分配恒存在；但构造反例证明其普遍存在性不成立。最后建立SMMS与受限最大最小份额（CMMS）的联系，借助已有CMMS结果提供对SMMS的近似保证。这些成果为多智能体环境下有限资源共享的公平分配提供了深刻的理论洞察。
原文摘要 · Abstract (English)
We study the problem of fairly allocating indivisible goods when limited sharing is allowed, that is, each good may be allocated to up to $k$ agents, while incurring a cost for sharing. While classic maximin share (MMS) allocations may not exist in many instances, we demonstrate that allowing controlled sharing can restore fairness guarantees that are otherwise unattainable in certain scenarios. (1) Our first contribution shows that exact maximin share (MMS) allocations are guaranteed to exist whenever goods are allowed to be cost-sensitively shared among at least half of the agents and the number of agents is even; for odd numbers of agents, we obtain a slightly weaker MMS guarantee. (2) We further design a Shared Bag-Filling Algorithm that guarantees a $(1 - C)(k - 1)$-approximate MMS allocation, where $C$ is the maximum cost of sharing a good. Notably, when $(1 - C)(k - 1) \geq 1$, our algorithm recovers an exact MMS allocation. (3) We additionally introduce the Sharing Maximin Share (SMMS) fairness notion, a natural extension of MMS to the $k$-sharing setting. (4) We show that SMMS allocations always exist under identical utilities and for instances with two agents. (5) We construct a counterexample to show the impossibility of the universal existence of an SMMS allocation. (6) Finally, we establish a connection between SMMS and constrained MMS (CMMS), yielding approximation guarantees for SMMS via existing CMMS results. These contributions provide deep theoretical insights for the problem of fair resource allocation when a limited sharing of resources are allowed in multi-agent environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。