Perpetual Fully Online Horizon-Free Approximate Fairness
Pith reviewed 2026-05-20 01:32 UTC · model grok-4.3
The pith
A deficit-based rule maintains approximate fairness with slack growing only as the square root of time after any round, without knowing the total duration.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that a fully online selection rule operating on deficits relative to time-varying benchmarks guarantees that every fairness requirement is satisfied up to O(sqrt(t) log t) slack after every prefix of rounds. The rule requires no knowledge of the horizon or future values and applies perpetually to indivisible-goods allocation and public decision-making. The authors also prove that some Omega(sqrt(t)) growth is unavoidable for any online method.
What carries the argument
The deficit profile that records each fairness requirement's shortfall relative to its current time-varying benchmark, together with the greedy rule that selects the action improving the next-round deficit profile the most.
If this is right
- Approximate proportionality and envy-freeness hold online for indivisible goods without prior knowledge of item values or total rounds.
- Approximate fairness holds at every step for sequences of public decisions such as prioritizing proposals or cases.
- All guarantees apply after every individual round rather than only asymptotically.
- The sqrt(t) growth rate cannot be improved by any online rule in the worst case.
Where Pith is reading between the lines
- The deficit approach could be tested on real allocation traces to see whether observed slack stays close to the theoretical bound.
- Similar tracking might produce horizon-free guarantees in related online problems such as dynamic resource scheduling.
- The perpetual anytime property suggests a new way to compare online fairness methods independent of assumed total length.
Load-bearing premise
Fairness requirements can be expressed as deficits against time-varying benchmarks so that an action can always be chosen to improve the deficit profile.
What would settle it
An adversarial sequence of arrivals or decisions in which the maximum deficit under the rule exceeds c sqrt(t) for a constant c larger than the paper's bound after some large t.
read the original abstract
Many decision processes run for a long and unknown duration: in each round new requests arrive, an irrevocable choice must be made immediately, and the system is judged by ongoing fairness requirements. Examples include food banks allocating donated items as they arrive, computing systems repeatedly scheduling scarce resources across users, and institutions making repeated public decisions (e.g., which proposals or cases to prioritize) while remaining fair over time. A key challenge in such settings is that fairness requirements are often naturally \emph{scale-dependent}. For example, in fair item allocation, it is common to require that the unfairness is bounded by the highest values of items seen so far. Thus, the scale of fairness changes over time. We propose a general approach to online fairness based on \emph{deficits}, which measure each requirement's current shortfall relative to a time-varying benchmark. Within this framework, we analyze a simple fully online rule that, in each round, chooses the action that best improves the next-round deficit profile. We prove anytime (prefix-wise) guarantees: after every round, all tracked requirements remain satisfied up to a slack that grows only on the order of $\sqrt{t}$ (up to logarithmic factors), and we show this growth is unavoidable in general. We instantiate the framework for online allocation of indivisible goods (yielding natural relaxations of proportionality and envy-freeness) and for online public decision-making. In contrast to previous works on online fair allocation, our rule does not need to know the horizon (the total number of rounds), nor any other information on the future (e.g. the maximum item value). Moreover, our guarantees hold perpetually, at each individual time step.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims to introduce a deficit-based framework for perpetual online fairness without knowing the horizon. It analyzes a simple selection rule that chooses the action best improving the deficit profile each round, proving that fairness requirements are satisfied up to O(√t) slack (with log factors) after every round, with this bound being tight in general. The framework is applied to online allocation of indivisible goods for relaxations of proportionality and envy-freeness, and to online public decision-making.
Significance. Should the proofs hold, this result is significant as it provides horizon-free and anytime fairness guarantees for scale-dependent requirements in long-running decision processes. This is useful for applications like food banks, resource scheduling, and public decisions where the total number of rounds is unknown. The tightness of the bound and the fully online nature distinguish it from prior work.
major comments (1)
- [Abstract] The abstract asserts the existence of proofs for the anytime guarantees and their tightness, but the provided manuscript text contains no lemmas, potential analysis, or lower-bound constructions. This prevents assessment of whether the O(√t) slack bound is correctly derived and load-bearing for the central claim.
Simulated Author's Rebuttal
We thank the referee for their summary and for identifying this limitation in the provided excerpt. We address the major comment below.
read point-by-point responses
-
Referee: [Abstract] The abstract asserts the existence of proofs for the anytime guarantees and their tightness, but the provided manuscript text contains no lemmas, potential analysis, or lower-bound constructions. This prevents assessment of whether the O(√t) slack bound is correctly derived and load-bearing for the central claim.
Authors: We agree that the excerpt made available consists solely of the abstract and therefore contains no lemmas, analysis, or lower-bound constructions. The complete manuscript includes dedicated sections with the formal proofs establishing the O(√t) (log-factor) slack bound for the deficit-based rule after every round, along with matching lower-bound constructions showing tightness in general. These elements support the central claims. To resolve the assessment issue, we will revise the submission to make the proof sections more prominent and add a short high-level proof sketch to the introduction. revision: yes
- Direct verification of the specific lemmas and lower-bound constructions, since only the abstract is available in the current query and the full technical details cannot be reproduced here.
Circularity Check
No circularity: derivation self-contained via standard online analysis
full rationale
The abstract defines deficits as shortfalls relative to time-varying benchmarks and analyzes a greedy rule selecting the action that best improves the deficit profile. It claims prefix-wise O(sqrt(t)) (log factors) slack guarantees and an unavoidability lower bound. No equations, fitted parameters, or self-citations are presented that would reduce the claimed result to its inputs by construction. The approach relies on standard techniques for horizon-free online algorithms and is instantiated on concrete domains without evident self-referential loops or renaming of known results as new derivations.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Decision processes run for long unknown durations with irrevocable choices each round and ongoing fairness requirements.
invented entities (1)
-
deficits
no independent evidence
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.