Research map / Learning theory and algorithms / Submodular and game algorithms

Online Fair Division Meets Reordering Buffers

NeurIPS 2026 · Learning theory and algorithms › Submodular and game algorithms · approach: Fair division of indivisible goods · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies online fair division of mixed manna with reordering buffers, showing buffers of size (n-1)k give temporal EF1 and EF-at-most-steps allocations for personalized k-value instances, with matching lower bounds and extensions to general additive valuations.

Problem

Online fair division of indivisible mixed manna with additive valuations: without buffers, temporal EF/EF1 is impossible even for few value levels, so the question is how small a reordering buffer suffices to guarantee temporal fairness.

Approach

Store-and-Match algorithm: keep a buffer of items, and when it is full, repeatedly find a left-perfect matching in a top-choice graph over live items (via Hall's theorem, hiding contested items), allocating matched items to keep the allocation envy-free; buffer size (n-1)k suffices for personalized k-value instances.

Key results

• Store-and-Match with buffer size (n-1)k yields temporal EF1 allocations for personalized k-value instances in both SAS and DAB models, and EF every n steps (SAS) or temporal EF/EF1 (DAB).
• Buffer size (n-1)k-1 is insufficient in the DAB model: algorithm fails EF in at least half of update steps for k-value instances.
• In the SAS model, a buffer of size floor(sqrt((k-3)/6)) cannot maintain beta-temporal-EF1 beyond 5k/6 time steps for two agents.

Surprising findings

• Lookahead of nearly k items is not enough and even with lookahead of m-4 items, temporal EF1 for 3-value instances is impossible without buffers.

Limitations

• Buffer size grows linearly with number of agents and k; not independent of n.
• General additive valuations require a multiplicative loss of rho^{-1/(k-1)} dependent on max ratio.
• SAS model lower bound shows sublinear buffers in k are insufficient for constant-factor guarantees.

Experimental setup

Metrics: temporal EF1 envy-freeness at time steps buffer size lower bounds

Baselines: Double Round-Robin

Builds on: Double Round-Robin temporal fairness reordering buffers in online scheduling efx for mixed manna

Closest papers by meaning

• Online Fair Division with Additional Information (ICML 2026 · similarity 0.93)
• The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.91)
• Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.91)
• The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.90)
• Temporal Fair Division (AAAI 2025 · similarity 0.90)
• Fairness and Efficiency in Online Class Matching (NeurIPS 2024 · similarity 0.90)