A new randomized online algorithm for additive and submodular valuations, called Single-or-Sample, is developed, that achieves a constant-factor approximation to MMS simultaneously for all agents, with constant probability, and establishes a fundamental tradeoff between approximation and success probability.
Abstract
We study the fair allocation of $m$ indivisible goods among $n$ heterogeneous agents arriving online, under maximin share (MMS) fairness. The key challenge lies in making allocation decisions in an adversarial setting without knowing future agents'valuations. No guarantees were known prior to our work in adversarial settings. Our main positive result is an online allocation algorithm for submodular agents that with probability at least $0.4$ guarantees a $1/24$-approximation to MMS to all agents simultaneously. Our algorithm intersperses a greedy-style adaptive sampling-without-replacement protocol with single-good reduction rounds. For XOS valuations, we adapt this single-or-sample approach to guarantee a $c$-MMS for all agents simultaneously with probability $1-O(c)$ for any parameter $c\in O(1/\log n)$. A key technical contribution of our work is in establishing Chernoff-style tail bounds on item allocation events for this adaptive sampling process despite strong positive correlations among the items, a result that may be of independent interest. The approximation versus success probability tradeoffs achieved by our algorithms are asymptotically tight. We show that even for binary additive valuations, no randomized algorithm can ensure $c$-MMS to all agents with probability exceeding $(1-c^2/5)$, for any $c\in (0,1]$. For XOS valuations, stronger lower bounds hold: no randomized algorithm can ensure $c$-MMS to all agents with probability exceeding $(1-c/3)$, for any $c\in (0,1]$. Furthermore, no algorithm can achieve $\omega(1/\log \log n)$-MMS with any constant probability. All our lower bounds hold even for simple binary instances whose MMS values and MMS partitions can be computed in linear time.
Online fair division captures allocation problems in which indivisible resources arrive over time and must be assigned before future resources are known. Understanding what fairness remains achievable when allocation decisions are immediate and irrevocable is a fundamental question in this setting. We study determinist...
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 ac...
We study the fair allocation of $m$ indivisible chores among $n$ agents in the agent-arrival model against an oblivious adversary. The chore set and the number of agents are known in advance. When agent $i$ arrives, her nonnegative additive cost function $c_i$ is revealed, and the algorithm must immediately and irrevoc...
We study online fair division, where indivisible goods arrive one at a time and must be allocated immediately and irrevocably among $n\ge2$ agents. Against an oblivious adversary that fixes the input in advance, we ask what fairness guarantees randomized online algorithms can achieve. We present the Deficit Allocation...
Saar Cohen, Nicholas J. Teh, Michael Wooldridge· 3 citations
We study online allocation problems where $n$ requests over $m$ resources arrive in an adversarial order and must be served immediately and irrevocably. This framework captures both Online Resource Allocation, where the goal is to maximize value subject to resource budgets, and Online Load Balancing, where the goal is...
Matthew Faw, Sahil Singla, Yi-Fan Wang· 0 citations
This work determines the tight high-probability PROP1 guarantee of the classical Like rule, which assigns each good uniformly among the agents who value it positively, and improves when fewer agents value the same good, unlike uniform random allocation.
Tzeh Yuan Neoh, Nicholas J. Teh· 9 citations· ⚡2
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.