OpenAlex ·
Randomized Online Fair Division: High-Probability and Expected Realized Fairness
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.23577
- Original
- Read it at the publisher
- Topics
Abstract
We study randomized algorithms for the fully online allocation of indivisible goods among $n\ge2$ agents with nonnegative additive valuations. Goods arrive sequentially and must be allocated immediately and irrevocably, with only $n$ known in advance. Since exact ex-ante envy freeness and proportionality are readily achievable, while no positive ex-post approximation is possible for the fairness notions considered here, we study the intermediate notions of high-probability fairness and expected realized fairness. Against a non-adaptive adversary, we give a randomized algorithm for proportionality up to one good (PROP1) whose parameter depends only on $n$ and that preserves exact ex-ante envy-freeness and proportionality. At confidence $1-δ$, its PROP1 guarantee improves on independent uniform allocation (Rand) by a factor of $Ω(\log n)$, uniformly over $δ\in(0,1/2]$. As $n\to\infty$, its expected realized PROP1 factor is at least $\frac{3-\sqrt5}{2}-o(1)$. We also show that the expected realized PROP1 factor of Rand is $(1+o(1))/\log n$, yielding an improvement of at least $\bigl(\frac{3-\sqrt5}{2}-o(1)\bigr)\log n$ for our algorithm. For every randomized online algorithm and every positive approximation factor, the success probability can be made arbitrarily small for envy freeness up to any good (EFX) and at most $\frac{n+1}{2n}$ for envy freeness up to one good (EF1). Consequently, every randomized fully online algorithm has an expected realized EFX guarantee of zero and an expected realized EF1 guarantee of at most $\frac{n+1}{2n}$.
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 Artificial Intelligence
Firm Valuation When AI Shapes the Business Model: A Milestone-Based Real-Options Framework for the AI Valuation Uncertainty Problem
Social Influence and the Allocation of Scientific Attention in AI Populations
Quantifying Long-Range Dependence in Object-Valued Time Series
A Dual-Process Perspective on Nudge Susceptibility in LLM-Based GUI Agents
Seeing Is Not Perceiving: When Synthetic Consumers Can and Cannot Pretest Visual Marketing
Get the few papers worth your time in Artificial Intelligence 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.