Researchers resolve a gap in online fair division theory by proving that proportionality up to one good (PROP1) cannot be approximated by standard greedy algorithms against adaptive adversaries, but can be achieved through randomized allocation or learning-augmented approaches with predictions.
This theoretical computer science paper addresses a fundamental problem in algorithmic game theory: how to fairly allocate indivisible goods that arrive sequentially without the ability to revise past decisions. The research fills an important gap by demonstrating that proportionality guarantees—ensuring each agent receives at least their proportional share—cannot be approximated using traditional allocation rules when facing strategic, adaptive adversaries. The authors establish tight impossibility results for three common greedy baselines, proving these heuristics fail completely in worst-case scenarios. However, the paper offers constructive solutions through two distinct approaches. Random allocation achieves meaningful approximation guarantees with high probability against non-adaptive adversaries, with near-perfect proportionality when item values are small. More promisingly, incorporating maximum item value predictions enables robust algorithms that gracefully degrade under one-sided prediction errors, suggesting practical applicability. The contrast between impossibility results for greedy methods and feasibility with randomization or augmented information reveals fundamental trade-offs in online allocation problems. This work contributes to understanding which fairness notions remain achievable under severe computational constraints, distinguishing PROP1 from stronger but unattainable concepts like envy-freeness and maximin share. The learning-augmented approach aligns with modern algorithmic trends incorporating machine learning predictions to improve worst-case guarantees, suggesting the methodology could extend to other resource allocation domains.
- →Standard greedy allocation rules cannot guarantee any multiplicative approximation to PROP1 against adaptive adversaries.
- →Uniform random allocation achieves meaningful PROP1 approximation with high probability under non-adaptive adversaries.
- →Incorporating maximum item value predictions enables robust online algorithms with graceful degradation under prediction errors.
- →PROP1 remains more approximable than stronger fairness notions like EF1 and MMS even with perfect predictions.
- →Item value magnitude critically affects achievable approximation guarantees in sequential fair division settings.