Graph constraints settled for fair resource sharing on networks
Settling PROPm and PROPavg in Graphical Resource Allocation
Computer Science and Game Theory
Summary
This paper looks at how to fairly share resources that connect people, represented as a network where people are points and resources are links. The authors study different fairness levels, focusing on two in between extremes whose existence was unknown. They prove that one intermediate fairness condition, called PROPm, can always be achieved and found efficiently, even when some resources are good or bad. However, the other condition, PROPavg, cannot always be met and is hard to check. They also measure the cost of insisting on PROPm fairness in terms of overall happiness.
What this means in practice
- •For network schedulers: Design network link assignments ensuring fair distribution among connected agents following the PROPm fairness guarantee.
- •For supply chain planners: Verify whether resource assignments meeting both intermediate fairness and efficiency are possible in logistics modeled as graphs.
A theory result. No direct application yet.
Authors
Bo Li, Ankang Sun, Ruijie Wang
Abstract
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.