Research map / Learning theory and algorithms / Submodular and game algorithms
Greedy-Based Online Fair Allocation with Adversarial Input: Enabling Best-of-Many-Worlds Guarantees
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.
Shows PACE equals integral greedy under equal budgets and proves horizon-independent envy and Nash welfare competitive-ratio bounds for both under adversarial input with bounded nonzero value ratios, completing a best-of-many-worlds guarantee.
Problem
Online fair allocation of indivisible items to agents with adversarially chosen values, where the goal is to bound multiplicative envy and Nash welfare competitive ratio independent of horizon T.
Approach
Shows that PACE (a pacing algorithm designed for stochastic inputs) reduces to the integral greedy allocation under equal budgets without projection, and proves that with a bounded ratio of nonzero values and infinite/linear monopolistic utility assumptions, both algorithms achieve asymptotic envy bound 1+2log(1/ε) and NW competitive bounds, yielding a best-of-many-worlds guarantee.
Key results
- Integral greedy and PACE have asymptotic multiplicative envy bounded by 1+2log(1/ε), shown tight by a matching lower bound.
- Integral greedy achieves a Nash welfare competitive ratio of λ·(n!)^{1/n+α} for any α>0, and any deterministic online algorithm suffers at least (n!)^{1/n}.
- PACE achieves a Nash welfare competitive ratio of (1+2log(1/ε))/c under assumptions on the monopolistic utility.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| restrict each agent's nonzero values to {0}∪[ε, 1] and require infinite monopolistic utility | Integral Greedy · Adversarial inputs, T→∞ | multiplicative envy: unrestricted: Ω(T) -> 1 + 2\log\frac{1}{\varepsilon} | Helped |
| restrict each agent's nonzero values to {0}∪[ε, 1] and require infinite monopolistic utility | Integral Greedy · Adversarial inputs, T→∞ | competitive ratio w.r.t. Nash welfare: unrestricted: Ω(T) -> \lambda\cdot(n!)^{\frac{1+\alpha}{n}} | Helped |
| restrict input and use projection bounds ℓ < ε²/(ε+1+(n-1)(1+log(1/ε))), r=1 | PACE · Adversarial inputs, T→∞ | multiplicative envy: 1+2\log\frac{1}{\varepsilon} | Helped |
| require each agent's monopolistic utility V_i ≥ cT, bound nonzero values, and use ℓ < cε²/(1+ε+(n-1)(1+log(1/ε))), r=1 | PACE · Adversarial inputs, T→∞ | competitive ratio w.r.t. Nash welfare: \left(1+2\log \frac{1}{\varepsilon}\right) \cdot \frac{1}{c} | Helped |
| remove the bounded nonzero-valuation-ratio restriction | Integral Greedy · Adversarial inputs with arbitrary values in [0,1] | worst-case multiplicative envy: \Omega(T) | Hurt |
| remove the bounded nonzero-valuation-ratio restriction | Any online allocation algorithm · Adversarial inputs with arbitrary values in [0,1] | competitive ratio w.r.t. Nash welfare: \Omega(T) | Hurt |
| add a seed utility δ to each agent's initial utility | Integral Greedy · Adversarial inputs with arbitrary values in [0,1] | seeded utility ratio Rδ: 3 + \frac{4}{\delta} + 2\log\Big(1+\frac{1}{\delta}\Big) + 2 \log T | Helped |
| use ε=1, so every nonzero valuation is equal | Integral Greedy · Adversarial inputs, T→∞ | competitive ratio w.r.t. Nash welfare: \lambda = 1, \alpha = 0 | Helped |
| remove projection from PACE with equal agent weights | PACE · Online allocation, equal weights | equivalence to integral greedy | No clear effect |
Surprising findings
- Both integral greedy and PACE have infinite envy and Omega(T) competitive ratio under completely arbitrary inputs, so extra assumptions are necessary.
- Under the stated restrictions, the best-of-many-worlds guarantee for PACE is established, while the conservative adversarial algorithm of prior work can be far from optimal under stochastic inputs.
Limitations
- Results depend on assumptions bounding the ratio of minimum nonzero to maximum value and linear monopolistic utility; unbounded ratios yield infinite envy.
- Equivalence to integral greedy and the analysis hold for equal budgets; unequal weights are only partially covered.
- The constant in the competitive ratio bound may not be tight.
Experimental setup
Metrics: multiplicative envy competitive ratio w.r.t. Nash welfare
Baselines: PACE conservative half-equal allocation algorithm
Builds on: PACE Eisenberg-Gale program Fisher market
Closest papers by meaning
- Fair and Efficient Online Allocations with Normalized Valuations (AAAI 2021 · similarity 0.91)
- Honor Among Bandits: No-Regret Learning for Online Fair Division (NeurIPS 2024 · similarity 0.89)
- Improved Regret Bounds for Online Fair Division with Bandit Learning (AAAI 2025 · similarity 0.89)
- Online Fair Division Meets Reordering Buffers (NeurIPS 2026 · similarity 0.87)
- Online Matching with Stochastic Rewards: Provable Better Bound via Adversarial Reinforcement Learning (ICML 2024 · similarity 0.86)
- Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.