| paper | Online Fair Allocations with Binary Valuations and Beyond |
| authors | Yuanyuan Wang, Tianze Wei |
| venue | AAAI 2026 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 9
Given a finite set \(\Theta\) of complete worker cost types, a rational mass vector \(\mu\in\Delta(\Theta)\), finite category-labelled chore templates, and horizon \(H\), with \(c_\theta(B)=|B|-r_\theta(B)\) for a partition-matroid rank \(r_\theta\), an adversary reveals a per-capita stream of chore copies online. Each copy is assigned immediately and wholly to one agent, with no batch coordination; the fluid state is the mass \(z_{\theta,B}\) of type-\(\theta\) agents holding integral bundle \(B\). Decide whether a nonanticipating deterministic policy can be complete and \(\alpha\)-EF1 for \(\mu\)-almost every ordered pair at every prefix, or minimize \(\alpha\ge1\).
A high-multiplicity online chore model with population mass \(\mu\) over finitely many complete partition-matroid cost types, integral bundle-state transitions represented by \(z_{\theta,B}\), immediate complete assignment of each incoming copy, and objective to minimize the worst-prefix \(\alpha\)-EF1 factor against an adversarial arrival stream.
The proponent does not fully specify whether a packet is processed as an atomic batch or generated through sequential irrevocable copies, so mass splitting might grant coordination unavailable in the finite theorem.
fatal: False
The mirrors cover the central immediate-allocation, no-future-information frontiers represented by Theorems 9 and 3, while leaving the personalized bi-valued results, general tri-valued bounds, deadline setting, and partial-information appendix untreated.
The strongest positive case is a high-multiplicity online allocation mirror, with Theorem 9 as the lead anchor. The paper contains no NP-hardness or parameterized-complexity theorem; its strongest computational results are online impossibility and approximation-bound theorems proved in the paper. Those are still excellent anchors because their key question is whether the obstruction comes from online irrevocability or merely from having only two named agents.
The common continuous model is this. Let \(\Theta\) be a finite set of complete agent types, with masses \(\mu_\theta\) summing to \(1\). A type contains the whole valuation or cost function, so two agents of one type are indistinguishable for the problem. The intended regime has \(N\gg |\Theta|\): for example, \(N\) workers but only two cost types.
Items arrive online in a per-capita stream. A packet of item \(e\) with mass \(q\) represents \(Nq\) distinct indivisible copies in an \(N\)-agent approximation. Every copy is still assigned whole and irrevocably to one agent. The mass notation only records the empirical distribution of those assignments; it does not allow an item to be divided between agents.
Formally, at a prefix \(s\), let \(z_{\theta,B}(s)\) be the mass of type-\(\theta\) agents currently holding the integral bundle \(B\). When an item packet \(e\) arrives, the policy chooses nonnegative flows \(x_{\theta,B,e}\) from current bundle states to \(B\cup\{e\}\), with total assigned mass equal to the incoming mass. The choice may depend on the observed history and current packet, but not future arrivals. For chores every item mass must be assigned. For goods, non-wastefulness requires positive marginal value for every assigned copy and zero marginal value for every discarded copy.
Fairness is imposed on almost every ordered pair of agents. For goods, \(\rho\)-EF1 means
\[ v_a(B_a)\ge \rho\,v_a(B_{a'}\setminus\{e\}) \]
for some \(e\in B_{a'}\). For chores, \(\alpha\)-EF1 means
\[ c_a(B_a\setminus\{e\})\le \alpha\,c_a(B_{a'}) \]
for some \(e\in B_a\). MMS and welfare are defined by the corresponding per-capita continuum limits: MMS is the best common guarantee obtainable by a measurable complete assignment of the arrived item mass, while USW and USC are the integrals of individual utilities and costs.
This is a genuine population continuization. For rational masses, the model has an exact finite interpretation with \(N\mu_\theta\) agents and \(Nq\) item copies. Conversely, finite instances with many repeated agents converge to the mass-flow model. The item bundles remain integral. The per-capita item supply is necessary: with only finitely many atomic arrivals, almost every atomless agent would remain empty and the fairness problem would degenerate.
My lead anchor is Theorem 9, proved in this paper. It states that, for supermodular binary cost functions and any \(\alpha\ge 1\), no deterministic online algorithm can achieve:
The proof uses the paper’s Lemma 7, cited from Barman, Narayan, and Verma, which characterizes supermodular binary costs by \(c(S)=|S|-r(S)\) for a matroid rank function \(r\).
The continuous problem I would hand to a prover is Continuous Complete-Chore EF1\(_\infty\):
Given finitely many supermodular-binary cost types \((\Theta,\mu,c)\), including the two partition-matroid cost types used in the proof of Theorem 9, and an adversarial stream of per-capita chore packets revealed online, determine the smallest \(\alpha\) for which there exists a deterministic online mass-flow policy that is complete and \(\alpha\)-EF1 at every prefix.
The natural regime is a large rota or service workforce. There are, say, two positive-mass cohorts of interchangeable workers, each cohort having the same category-dependent cost function. Daily compulsory tasks arrive in \(\Theta(N)\) individual copies, in an order unknown in advance, and each task must immediately be assigned to one worker. A worker incurs zero marginal cost for the first task in a category but unit marginal cost for duplicate tasks, exactly the partition-matroid construction used in the theorem. This is a plausible high-multiplicity setting: \(N\) is large while the number of cost types is two.
I expect the finite impossibility to dissolve in this mirror, at least for the partition-matroid templates: the answer should be Class A, with an online balancing or flow algorithm achieving EF1, and likely finite MMS guarantees as well. The two-agent proof repeatedly forces the algorithm down one branch by allocating a single item to one of two individuals. With two positive-mass cohorts, each incoming task can be spread across many current bundle states, so those branches need not be forced. The min-USC version is a separate, harder variant; it may retain a genuinely online obstruction even after EF1 becomes tractable.
The second anchor is Theorem 3, also proved in this paper. It states that, for submodular binary valuations and every \(\varepsilon>0\), no deterministic online algorithm can achieve:
The paper’s positive Theorem 2 supplies the matching \(\frac12\) guarantees via Marginal-Greedy, so Theorem 3 is a sharp boundary result rather than a loose impossibility statement.
The corresponding problem is Continuous Non-Wasteful Goods Frontier\(_\infty\):
Given finitely many submodular-binary valuation types \((\Theta,\mu,v)\), a per-capita online stream of indivisible goods, and a target \(\rho>\frac12\), determine whether there is a deterministic online mass-flow policy that is non-wasteful at every prefix and simultaneously guarantees \(\rho\)-EF1, \(\rho\)-MMS, and \(\rho\)-max-USW.
A plausible scenario is a large food-bank or institutional donation system. Many recipient households share one of a small number of eligibility or need profiles, represented by matroid-rank valuations. Donations arrive in \(\Theta(N)\) individual copies, and each copy must be assigned immediately. Again, the paper’s goods remain indivisible at the micro-level; only the population distribution over integral bundle states is continuous.
I expect a nontrivial improvement over \(\frac12\) in fixed finite-type, finite-template regimes, probably Class A through matroid exchange plus mass-flow optimization. I would not promise \(\rho=1\) for max-USW under completely adversarial arrivals: the welfare component may have its own online frontier. If a \(\frac12\)-barrier survives despite positive-mass cohorts, that would be a genuinely continuum-specific online obstruction, not hardness transferred from the number of agents.
These mirrors cover the paper’s central no-future, immediate-allocation model, not its deadline or partial-information appendices, and not every personalized bi-valued theorem. They are also not novelty collisions: the paper has finite named agents and indivisible item arrivals, but no distribution over agent types, no mass-flow state, and no high-multiplicity analysis. Existing online fair-division work cited by the authors is therefore supporting prior art, not a reason to reject the mirror.
The weakest point is that the fluid model must scale item supply with population size. If one insists on exactly one atomic item at a time while replacing only the agents by an atomless population, fairness becomes largely vacuous because only countably many agents ever receive items. Conversely, if one allows an item itself to be fractionally divided, the model leaves the paper’s problem and becomes an outcome-space relaxation. The proposed mirror survives only because it occupies the narrow middle: many indivisible item copies, many repeated agent types, integral bundles for every microscopic agent, and fractional quantities only as type-level population flows.
The strongest negative case is that neither anchor induces a canonical continuous-population problem. The paper’s results are about an adaptive sequence of distinct item identities, while the proposed mirrors need a second limit—replicating or batching items—to prevent the fixed finite adversarial sequence from affecting only measure zero of the population.
For Theorem 9, preserving one-item-at-a-time arrivals means that a six-item counterexample touches only finitely many workers as \(N\to\infty\); almost every worker remains empty, and pairwise EF1 becomes vacuous almost everywhere. Scaling the items with \(N\) creates a different problem. If the copies arrive as packets and the policy sends fractions of the packet to different bundle states, the policy has acquired batch coordination unavailable in the theorem’s model. If copies arrive sequentially, the state is a distribution over bundle histories \(B\), not merely a distribution over the two cost types; its support can grow exponentially with the arrival history. The result is an infinite-dimensional online control problem, not the fixed-type continuous society contemplated by the programme.
The workforce example is plausible, but it therefore does not merely continuize Theorem 9. It specifies a new model of recurring task categories, packet sizes, arrival granularity, and worker-state evolution. The theorem supplies no reason to regard that particular lift as the intended one. The finite lower bound neither survives nor has a uniquely defined continuous counterpart; determining the right lift is itself most of the modelling work.
Theorem 3 has an additional obstruction. A submodular-binary valuation is a matroid rank function on a ground set of distinct items. Replicating an item is not semantically determined: copies may be parallel elements, independent clones, or new category elements. These choices produce different marginal values, non-wastefulness constraints, MMS values, and welfare frontiers. The food-bank scenario can choose one extension, but then it is studying a newly specified repeated-category allocation model rather than a continuous version forced by the paper.
Thus the best case against both anchors is that the paper contains online guarantee and impossibility theorems, not a complexity landscape whose high-multiplicity relaxation is naturally defined. Any meaningful mirror requires substantial extra assumptions about item replication, packet timing, valuation extension, horizon, and the evolving bundle-state distribution. That makes the proposed questions underdetermined and adjacent to the programme rather than clear continuizations of this paper.
But this negative case is ultimately weak. The two-type workforce and food-bank scenarios are credible high-multiplicity regimes, and their mass-flow versions retain integral bundles for individual agents. The fact that the \(\tfrac12\) or EF1 barriers may disappear is not an objection; it is exactly the sort of useful result the programme seeks. I cannot honestly defeat both anchors universally: a careful reader should regard the proposed mirrors as legitimate new continuous online-allocation problems, albeit ones requiring a more explicit model than the proponent supplied.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.