arXiv preprint ·
Single-or-Sample: Online Fair Allocation for Combinatorial Agents
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study the problem of fairly allocating $m$ indivisible goods among $n$ agents who arrive online, under the notion of maximin share (MMS) fairness. Fair allocation with online arrivals is notoriously challenging: prior work achieves constant-factor MMS guarantees only when agents' preferences belong to a set of valuation functions known in advance, while no guarantees were known without such prior information. We develop a new randomized online algorithm for additive and submodular valuations, that we call Single-or-Sample, and that achieves a constant-factor approximation to MMS simultaneously for all agents, with constant probability. The algorithm requires no prior knowledge about the agents' valuations, and works against adversarial (oblivious) inputs. We further establish a fundamental tradeoff between approximation and success probability. Specifically, for any $c \ge 1$, no online algorithm can guarantee a $1/c$-approximation to MMS with probability exceeding $1 - 1/c^2$, even for binary additive valuations. This rules out constant MMS with probability asymptotically closer to $1$ than a constant. For XOS, the lower bound is much stronger: no algorithm can achieve even $1/\log\log n$-MMS to all agents with a constant probability. We complement this lower bound with an algorithm for the regime $c\in Ω(\log n)$, namely $1/c$-MMS to all agents with probability $(1-O(1/c))$, and show that this tradeoff is tight for XOS. Our constant-factor algorithm introduces several new ideas, combining greedy submodular maximization with randomized allocation and single-item reduction. A key technical ingredient is a new approach for analyzing iterative sampling without replacement. We develop concentration bounds that apply to a broad class of adaptive processes with complex dependencies across elements and rounds, which may be of independent interest.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Evolution of Market Microstructure in the Age of AI
Learnable Randomization as Commitment Against Adaptive Optimizers
Modular Discovery of General Game-Playing Algorithms with Large Language Models
PACT: Pairwise-Anchored Calibrated Tuning for Single-Token Typed Decisions
When Privacy Moves ML-Mediated Decisions On Device: Information and Incentive Misalignment in Auctions
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.