Subsidised Proportionality in Fair Allocation

We study resource allocation problems in which multiple self-interested players and a central decision maker need to decide on a fair allocation. Because strict fairness is hard to guarantee in the discrete setting, we introduce compensation to eliminate potential unfairness. The central decision maker seeks a solution that is fair after subsidising the players while minimising the total compensation. We focus on one of the most well-studied fairness criteria, proportionality. We provide a tight characterisation of the required compensation to achieve proportionality when players share the same entitlements (obligations) for the resources (tasks). For asymmetric agents, we derive upper and lower bounds on the required compensation to guarantee proportionality.

Funding: X. Wu is funded by the Science and Technology Development Fund (FDCT), Macau SAR (File 0147/2024/RIA2 and 001/2024/SKL) and the University of Macau (File MYRG-GRG2025-00033-IOTSC).