Envy-Free Allocations for Random Non-Additive Valuations

概要

Benade et al. (EC 2024) introduced a semi-random model for non-additive fair division in which each agent starts with an arbitrary base valuation over bundles of items and independently permutes the item names uniformly at random. While they proved that envy-free allocations exist with high probability as the number of items grows for $n = 2$ agents, they left open whether the same holds for $n > 2$ agents. We resolve this open question in the affirmative: for any fixed number of agents $n$ and any number of items $m$ divisible by $n$, an envy-free allocation exists with probability $1 - o(1)$ as $m \to \infty$. Our proof combines the second moment method with a connection to the (small-set) expansion of generalized Johnson graphs, which may be of independent interest.

参考リンク

• Paper ↗

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

実装を始めるプロンプト

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

# 論文・記事
Envy-Free Allocations for Random Non-Additive Valuations

# 概要
Benade et al. (EC 2024) introduced a semi-random model for non-additive fair division in which each agent starts with an arbitrary base valuation over bundles of items and independently permutes the…

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

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