Toward Constant-Factor Maximin Share Guarantees for Subadditive Valuations

概要

For $n$ agents and $m$ indivisible goods, an agent's maximin share (MMS) is the largest minimum bundle value she can obtain by partitioning the goods into $n$ bundles. Constant MMS approximations are known for additive, submodular, or XOS valuations, but whether such a guarantee exists for general subadditive valuations remains open. We advance this question in two directions. For general subadditive valuations, we exponentially improve the guarantee from $Ω(1/\log\log n)$ to $Ω(1/\log^* n)$, where $\log^* n$ is the iterated logarithm. We then seek constant MMS guarantees under additional structure on subadditive valuations by studying $q$-partitioning valuations: every partition of a bundle into at most $q$ groups admits nonnegative group prices that sum to the bundle's value and whose sum on any collection of groups is at most the value of their union. This hierarchy ranges from subadditivity at $q=2$ to XOS for $q\ge m$. We give the first study of MMS in the intermediate classes and prove constant guarantees whenever $q/n$ has a fixed positive lower bound, including $1/6$ for $q\ge n$ and $1/4$ for $q\ge2n$. For XOS valuations, we further improve the universal guarantee from $4/17\approx 0.2353$ to $5/16=0.3125$. For subadditive valuations, we prove a bidding amplification theorem that gives an exponential bound on each agent's probability of receiving less than half her MMS, while satisfying her budget in every outcome. For $q$-partitioning valuations, we give a scalar criterion that converts bounds on the value lost from disjoint deletions within a bundle into bounds on potential losses, even when an agent contributes zero below the target bundle value. For XOS valuations, we prove a reservation theorem that selects goods for integral assignment together with auxiliary additive valuations and accounts for the loss in rounding.

参考リンク

• Paper ↗

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

実装を始めるプロンプト

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

# 論文・記事
Toward Constant-Factor Maximin Share Guarantees for Subadditive Valuations

# 概要
For $n$ agents and $m$ indivisible goods, an agent's maximin share (MMS) is the largest minimum bundle value she can obtain by partitioning the goods into $n$ bundles. Constant MMS approximations are…

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

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