Traditional fair division frameworks operate under a convenient fiction: all resources are piled on a table, all participants are seated around it, and a centralized allocator divides the goods in a single, omniscient step. As Toby Walsh points out in Challenges in Resource and Cost Allocation, these static snapshots fail to capture the messy, repeated nature of real-world logistics. In applications ranging from cloud computing and food bank distribution to kidney exchanges, resources and participants arrive and depart asynchronously over time.
When we move from static to dynamic fair division, the core mathematical guarantees—such as envy-freeness (no agent prefers another's bundle) and Pareto efficiency—must be fundamentally re-imagined. In an online setting, an algorithm must make immediate, sequential allocation decisions without knowing what resources or participants will appear in the future.
The Friction of Reallocation and Disruptions
If a system's state changes continuously, why not simply re-run a classic static fair division algorithm every time an agent arrives or leaves? The answer lies in the logistical overhead of change.
Imagine a cloud computing cluster or a physical warehouse. If every new request triggers a complete redistribution of existing assets to maintain perfect fairness, the system will suffer from massive context-switching costs. As explored by Sungjin Im et al. in Dynamic Weighted Fairness with Minimal Disruptions, maintaining absolute fairness at every instant requires constant, unsustainable disruptions to active jobs.
To make dynamic allocation practical, algorithms must trade off a small amount of instantaneous fairness to guarantee system stability. For instance, Bo Li et al. demonstrate in Dynamic Fair Division Problem with General Valuations that we can bound envy and proportionality violations by restricting reallocations to a minimal number of previous participants upon a new arrival. Similarly, in Fairly Allocating (Contiguous) Dynamic Indivisible Items with Few Adjustments, the authors focus on minimizing this "cost of change" when items arrive sequentially, proving that near-optimal fairness can be achieved with surprisingly few adjustments to existing allocations.
The Information Gap and Temporal Fairness
The second major hurdle in online fair division is the lack of future information. If an algorithm allocates a high-value resource to an early applicant, it risks running out of resources for a later, potentially more deserving applicant. Conversely, holding onto resources in anticipation of future demand can lead to waste and inefficiency.
This creates a fundamental tension between immediate fairness and long-term fairness. In Temporal Fair Division, Benjamin Cookson et al. formalize this by analyzing how to balance daily equity with overall long-term fairness when resources like work shifts or food donations arrive sequentially over multiple days.
When the future is completely unpredictable, achieving both fairness and efficiency simultaneously becomes a theoretical minefield. Alexandros Psomas et al. show in Fairness-Efficiency Tradeoffs in Dynamic Fair Division that while a known probability distribution of item values allows for balanced outcomes, operating against an adversarial or highly unpredictable environment makes it impossible for any online algorithm to outperform simple random allocation in terms of efficiency.
Leveraging Time to Bypass Impossibility
While the temporal dimension introduces severe constraints, it also offers a unique advantage: the ability to use history and memory to enforce fairness over time. In a single-shot static exchange, certain combinations of strategy-proofness, efficiency, and individual rationality are mathematically impossible to achieve simultaneously. However, repeating the interaction allows mechanisms to balance the scales across multiple periods.
A prime example of this is found in matching markets. In Strategy-Proof and Efficient Kidney Exchange Using a Credit Mechanism, Chen Hajaj et al. introduce a dynamic credit system for multi-center kidney exchanges. By tracking the contributions and withdrawals of different hospitals over time, the mechanism incentivizes truthful reporting and achieves long-term efficiency, effectively bypassing the impossibility results that cripple static exchange models.
For fluid, nonstationary environments where resource values fluctuate unpredictably, online learning frameworks can dynamically adjust allocation boundaries. As shown by Luofeng Liao et al. in Nonstationary Dual Averaging and Online Fair Allocation, parameter-free dual averaging algorithms can maintain robust fairness and low envy even when the underlying data stream is messy and correlated, adapting in real-time without requiring prior knowledge of the total supply or future demand.
Key Foundational Work
Fair On-Line Scheduling of a Dynamic Set of Tasks on a Single Resource (1997) — contributed 2 concept elements to this direction.
Dynamic Incentive Mechanisms (2010) — contributed 1 concept elements to this direction.