Temporal Fair Division of Indivisible Goods with Structured Constraints
Computer Science and Game Theory
Summary
The authors study how to fairly divide items given out over multiple rounds, focusing on fairness measured over time rather than just once. They explore strong fairness criteria but note these are usually impossible to meet exactly, so they look for conditions that make fairness achievable. Their main result is a new method that perfectly ensures fairness over time for a special case where values are simple (binary). They also identify when approximations are possible and clearly show where fairness can’t be mathematically guaranteed, helping to clarify previous work in this area.
Authors
Kui-Wang Choi, Minming Li
Abstract
This paper investigates temporal fair division, a setting where items are allocated over multiple rounds and agents require cumulative fairness over time. We focus on dynamic extensions of classic fairness notions: Temporal Envy-Freeness Up to Any Good (TEFX), its $α$-TEFX approximation, and Temporal Maximin Share (TMMS). Because these strict fairness criteria are known to be generally impossible to satisfy, we analyze the model under constraints to map the boundary between what is possible and what is not. Our contribution systematically maps the structural boundaries of these temporal fairness notions. Our main technical result introduces a novel dynamic backtracking framework that achieves exact TEFX for Strong Binary Valuations. We prove, via a lexicographical potential function argument, that this bounded historical reallocation systematically resolves temporal envy cycles and terminates in finite time. Finally, we establish tight approximation ratios for $α$-TEFX under identical valuations and bi-valued goods, alongside targeted impossibility results for TEFX and TMMS, demonstrating exactly where temporal fairness is mathematically unattainable, and properly contextualizing prior algorithms that only implicitly satisfied our newly defined TMMS metric.