Polynomial Algorithms for Simultaneous Share-Based and Envy-Based Guarantees

概要

We study the simultaneous achievement of share-based and envy-based fairness in the allocation of indivisible goods with nonnegative additive valuations. The AnyPrice share (APS) is a strengthening of the maximin share (MMS). A polynomial-time algorithm is known to guarantee a $2n/(3n-1)$ approximation of APS, but without an accompanying envy-based guarantee. Separately, allocations simultaneously satisfying minimum EFX share (MXS) and envy-freeness up to one less-preferred good (EFL), and subsequently the stronger requirement of residual maximin share (RMMS) together with EFL, have been shown to exist. However, the known constructions do not provide pseudopolynomial-time guarantees. We develop algorithms that combine these share-based and envy-based fairness requirements. First, for every $\varepsilon \in (0,1)$, we give an algorithm that computes an allocation satisfying exact EFL, $(1-\varepsilon)$-MXS, and $2n/(3n-1)$-APS. Its running time is polynomial in the binary input length and $1/\varepsilon$. Thus, we match the previously established polynomial-time APS approximation while simultaneously guaranteeing exact EFL and an arbitrarily close approximation to MXS. Second, we provide a pseudopolynomial-time algorithm that simultaneously guarantees exact MXS, exact EFL, and $2n/(3n-1)$-APS. Third, for every fixed number of agents, we obtain a pseudopolynomial-time algorithm that simultaneously achieves exact RMMS and exact EFL. Finally, we establish that computing a numerical threshold between MXS and RMMS is weakly NP-hard, even for additive valuations. This identifies a computational barrier to extending our polynomial-time approach to exact MXS through independently computed residual-valid share thresholds.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Polynomial Algorithms for Simultaneous Share-Based and Envy-Based Guarantees

# 概要
We study the simultaneous achievement of share-based and envy-based fairness in the allocation of indivisible goods with nonnegative additive valuations. The AnyPrice share (APS) is a strengthening…

# 原典
https://arxiv.org/abs/2610.15437

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。