Settling PROPm and PROPavg in Graphical Resource Allocation

概要

We study proportional fairness in graphical resource allocation, where agents are vertices, indivisible items are edges, and each item must be allocated to one of its two endpoints. It has been proved that PROP1 orientations always exist and PROPx orientations may not, but it has remained open whether the intermediate relaxations PROPm and PROPavg (both can be satisfied without graphical constraints) can always be satisfied. In this paper, we resolve this gap. We prove that PROPm orientations always exist for goods on multigraphs and can be computed efficiently. The guarantee extends to chores and a mixture of goods and chores. In sharp contrast, we show that PROPavg orientations need not exist, even for simple graphs with binary valuations, and that deciding their existence is NP-complete. We further quantify the efficiency loss of PROPm: for goods, the price of PROPm is exactly $2$, which is one of the few settings where a constant bound on the price of fairness can be obtained. We complement these results with hardness results for welfare optimization under PROPm and for the existence of orientations that are simultaneously PROPm and Pareto optimal.

参考リンク

• Paper ↗

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

実装を始めるプロンプト

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

# 論文・記事
Settling PROPm and PROPavg in Graphical Resource Allocation

# 概要
We study proportional fairness in graphical resource allocation, where agents are vertices, indivisible items are edges, and each item must be allocated to one of its two endpoints. It has been…

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

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