Revisiting the Fairness of Pure Nash Equilibria of Round-Robin

概要

We prove that for additive valuations, not every pure Nash equilibrium of the Round-Robin mechanism induces an allocation that is envy-free up to one good (EF1) with respect to the agents' true valuations. This corrects an earlier claim of Amanatidis et al. (WINE 2021; Math. Oper. Res. 2024). On the positive side, every pure Nash equilibrium of every fixed recursively balanced picking sequence mechanism induces an allocation that is $1/2$-EF1 and proportional up to one good (PROP1). We prove the approximate EF1 guarantee through a potential function comparing two executions, and the proportionality guarantee via a deviation that preserves the agent's most valuable goods. We also give a family of Round Robin equilibria showing that it is not possible to have a strictly better guarantee than $2/3$-EF1 for all equilibria.

参考リンク

• Paper ↗

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

実装を始めるプロンプト

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

# 論文・記事
Revisiting the Fairness of Pure Nash Equilibria of Round-Robin

# 概要
We prove that for additive valuations, not every pure Nash equilibrium of the Round-Robin mechanism induces an allocation that is envy-free up to one good (EF1) with respect to the agents' true…

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

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