Research map / Bandits and online learning / Multi-armed bandits
Honor Among Bandits: No-Regret Learning for Online Fair Division
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.
Casts online fair division of indivisible goods with unknown player value means as a bandit problem and gives an explore-then-commit algorithm with Õ(T^{2/3}) regret that keeps envy-freeness or proportionality in expectation, plus a matching lower bound.
Problem
Online allocation of indivisible goods of finite types to players whose value means are unknown must maximize social welfare while satisfying envy-freeness or proportionality in expectation at every step.
Approach
Reduces fair online allocation with unknown values to a constrained bandit with one arm per (player, item type); shows fairness constraints satisfy structural properties (equal-treatment satisfaction, slack-or-equal-treatment via a combinatorial construction, Lipschitz and fixed support) that allow explore-then-commit with an LP over a confidence region to achieve T^{2/3} regret.
Key results
- Explore-then-commit algorithm achieves Õ(T^{2/3}) regret while maintaining envy-freeness in expectation or proportionality in expectation with probability 1-1/T.
- Lower bound of Ω̃(T^{2/3}) regret shows the upper bound is tight up to log factors for both fairness notions.
- Any algorithm satisfying envy-freeness in expectation has realized envy at most √T log T w.h.p., while no algorithm can guarantee realized envy below √T with constant probability when values are unknown.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Fair Explore-Then-Commit with a UAR warm-up and robust LP commitment | Online fair division · Envy-freeness in expectation | regret: \tilde{O}(T^{2/3}) | Helped |
| Use Fair Explore-Then-Commit with a UAR warm-up and robust LP commitment | Online fair division · Proportionality in expectation | regret: \tilde{O}(T^{2/3}) | Helped |
Surprising findings
- Envy-freeness in expectation at every time step incurs no social welfare loss compared with requiring it only at the end of T rounds.
- Under unknown values, the uniform-at-random allocation is the only fair allocation for some instances, so zero-regret-type fairness cannot be obtained with o(T) regret if means can approach zero.
Limitations
- Envy-freeness regret bound has a constant that is exponential in the number of players n.
- The LP has infinitely many constraints (semi-infinite program), so the algorithm is computationally non-trivial in practice.
- Does not achieve Õ(√T) regret; UCB-style methods fail because fairness constraints are tight at the optimum.
Experimental setup
Metrics: regret social welfare realized envy
Baselines: uniform at random allocation optimal fair allocation with known means
Builds on: explore-then-commit stochastic multi-armed bandits linear bandits with safety constraints
Closest papers by meaning
- Improved Regret Bounds for Online Fair Division with Bandit Learning (AAAI 2025 · similarity 0.95)
- Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies (ICML 2026 · similarity 0.92)
- My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits (ICML 2020 · similarity 0.92)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.89)
- Greedy-Based Online Fair Allocation with Adversarial Input: Enabling Best-of-Many-Worlds Guarantees (AAAI 2024 · similarity 0.89)
- No-Regret Learning for Fair Multi-Agent Social Welfare Optimization (NeurIPS 2024 · similarity 0.88)
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.