| paper | Online Fair Division for Personalized 2-Value Instances |
| authors | Georgios Amanatidis, Alexandros Lolos, E. Markakis, Victor Turmel |
| venue | SAGT 2025 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Existence is polynomial-time solvable: every valid input admits a deterministic policy with \(\rho=1\). The maximum achievable value is always \(1\); decision and value computation take \(O(L)\) time including input reading. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 5.4
statement extracted from the paper’s text layer
Given finite types \(\Theta\) with rational masses \(\mu_\theta\), personalized \(2\)-value data, and complete valuation patterns on a finite-horizon scenario tree, goods arrive sequentially in per-capita blocks and a policy sees only revealed history plus the next block. Assign each individual an integral bundle through mass transports \(y_{\theta,B,q}\) from type/bundle states, irrevocably and nonanticipatorily, while enforcing pairwise \(\rho\)-\(\mathrm{EF2}\) at every prefix and \(\rho\)-\(\mathrm{EF1}\) at block boundaries. Compute the maximum achievable \(\rho\), in particular deciding whether \(\rho=1\) is achievable for every allowed arrival path.
A high-multiplicity online fair-division model in which \(\mu\) is mass over complete valuation types, \(z_{\theta,B}\) is mass in integral bundle state \(B\), and \(y_{\theta,B,q}\) transports that mass to \(B\cup\{q\}\). Optimize \(\rho\) subject to supply, nonanticipation, irrevocability, and pairwise fairness constraints, using transportation or configuration formulations.
The proponent has not supplied a polynomially bounded encoding or complexity measure for the state-rich nonanticipatory policy over bundle histories and scenario trees.
fatal: False
The mirror covers Theorem 5.4 and Algorithm 3's temporal \(\mathrm{EF2}\), block-boundary \(\mathrm{EF1}\), \(1/n\)-MMS, and persistence guarantees; it leaves the impossibility theorems, Deferred-Priority results, two-agent foresight result, and interval-reduction results unaddressed.
I would defend a qualified positive case centred on the paper’s general matching result, Theorem 5.4. The paper contains no named NP-hardness or complexity-classification theorem, so this is an algorithmic anchor rather than a hardness-dissolution claim.
The high-multiplicity regime is a large distribution or aid-allocation system with millions of recipients but only finitely many valuation profiles. A type \(\theta\) specifies the personalized values \((\alpha_\theta,\beta_\theta)\), together with the complete high/low pattern describing how that type values every possible arriving good. The population is a rational distribution \(\mu\) over a finite type set \(\Theta\), with \(|\Theta|=\tau\ll N\), where \(N\) is the eventual number of individual recipients. For example, a food bank may serve many repeated recipient classes, while incoming goods arrive sequentially and are valued highly or weakly according to dietary, medical, or household needs.
The goods must scale with the population. A normalized round contains one good per capita: at finite scale \(N\), it consists of \(N\) individually indivisible goods, and the continuum notation records their limiting mass. Goods remain indivisible for every individual recipient; only the aggregate allocation is represented by mass. Thus a type cohort may be split into subcohorts receiving different integral bundles, but no recipient receives a fractional good.
The paper’s anchor is:
Theorem 5.4, proved in this paper. For any personalized 2-value instance with foresight of length \(n-1\), Algorithm 3 constructs an allocation that is temporal-EF2, is EF1—and therefore \(1/n\)-MMS—at every time \(t=kn\), and has the additional property that if the allocation fails to be \(1/2\)-EF1 at some time \(t_0\), then it is \(1/2\)-EF1 at the end of every time \(t\ge \lceil t_0/n\rceil n\). Algorithm 3 obtains this by looking one round ahead, constructing the current envy graph, topologically ordering it, defining auxiliary two-value valuations, finding a maximum-weight matching between the \(n\) agents and the next \(n\) goods, and irrevocably committing to that matching.
My continuous problem is Continuum One-Round-Foresight Fair Allocation.
An instance consists of a finite type set \(\Theta\), rational masses \(\mu_\theta\) summing to \(1\), personalized 2-value valuation data, a finite horizon, and a finite scenario tree describing the possible sequences of arriving good-patterns. A good-pattern specifies, for every \(\theta\), whether that type values the good at \(\alpha_\theta\) or \(\beta_\theta\). Goods arrive in per-capita blocks of total mass \(1\); inside a block, goods are still revealed sequentially. At the beginning of a block, the policy sees the current block and the next block, exactly as \(n-1\) individual goods amount to one normalized future block in a finite population of size \(n\).
The decision variable is an online, nonanticipatory mass allocation. If \(x_{\theta,B}\) is the mass of type-\(\theta\) agents currently holding integral bundle \(B\), then \(y_{\theta,B,q}\) is the mass of those agents receiving an arriving good of pattern \(q\). It must satisfy the supply constraints \(\sum_{\theta,B}y_{\theta,B,q}=\lambda_q\), the capacity constraints \(\sum_q y_{\theta,B,q}\le x_{\theta,B}\), and the update rule that receiving \(q\) changes \(B\) to \(B\cup\{q\}\). At a scenario-tree node, the decision may depend only on the revealed history and the permitted one-block preview.
The fairness requirement is imposed on the integral bundles of almost every individual, not merely on type averages. At every prefix, for almost every pair of agents \(a,b\), the allocation must satisfy
\[ v_a(A_a)\ge \rho\min_{\substack{S\subseteq A_b\\ |S|\le 2}}v_a(A_b\setminus S), \]
and at every block boundary it must satisfy
\[ v_a(A_a)\ge \rho\min_{\substack{S\subseteq A_b\\ |S|\le 1}}v_a(A_b\setminus S). \]
The optimization objective is to maximize \(\rho\); the exact analogue of Theorem 5.4 asks whether \(\rho=1\) is achievable. A solution is the complete nonanticipatory family of mass transports \(y\), together with a decomposition into individual integral bundles.
This is recognizably the authors’ problem. It preserves the online arrival process, irrevocability, personalized 2-value valuations, EF1 and EF2, and limited foresight. The only co-modification is forced by population continuization: \(n-1\) future individual goods become one future per-capita block, and \(n\) named recipients become unit population mass. For rational \(\mu\), clearing denominators recovers a finite instance with repeated clones; conversely, normalized finite allocations converge to the mass-transport representation.
I would provisionally classify this mirror as Class A for finite type support and finite horizon. Algorithm 3’s matching step becomes a maximum-weight transportation problem over population mass. The type-level variables are genuinely active: the policy decides which mass receives which arriving goods and which integral bundle configurations are populated. This is not merely replacing counts by coefficients in an unchanged committee problem. The likely technical tools are transportation LPs, configuration formulations, and possibly column generation over bundle states.
The main follow-up questions are whether the exact EF1 guarantee survives for arbitrary rational type masses, whether a polynomial-size representation exists without enumerating exponentially many bundle configurations, and whether one-block foresight is minimal. The no-foresight version would also test whether the paper’s impossibility results persist after population multiplicity is made divisible.
The weakest point is the normalization of foresight. The paper’s \(n-1\) lookahead is tied to a finite number of agents, while the continuum has no finite \(n\). If the proposed model were allowed to give fractional goods to individuals or to require only type-average EF1, it would become a different, much easier fractional fair-division problem. The case therefore depends on retaining individual integral bundles and interpreting the continuum as the mass limit of \(N\) indivisible recipients and \(N\)-scaled goods. If that decomposition or the exact almost-everywhere pairwise fairness requirement cannot be established, I would withdraw the positive claim rather than call a type-average relaxation the same problem.
The proponent has found a coherent scaling story, but not a worthwhile ChoCo mirror of Theorem 5.4.
The first weakness is the anchor itself. Theorem 5.4 is not a complexity result about an input society; it is a finite-agent guarantee for one online algorithm. The proposed problem, “maximize \(\rho\) over nonanticipatory mass policies,” is therefore not the high-multiplicity version of a computational problem formulated in the paper. It is a new policy-synthesis problem. That could still be interesting, but it cannot inherit its motivation merely by citing Theorem 5.4.
More seriously, the population cannot be represented by the proposed valuation types alone. EF1 and EF2 are pairwise bundle comparisons:
\[ v_a(A_a)\geq \min_{\lvert S\rvert\leq 1}v_a(A_b\setminus S). \]
Two agents with the same valuation type can receive different goods, acquire different bundles, and occupy different positions in the envy graph. Their future treatment consequently differs. The relevant state is not \(\theta\), but something like \((\theta,B)\), together with the agent’s entire allocation history. A mass over valuation types does not determine either fairness or the next decision.
The proponent’s \(x_{\theta,B}\) variables acknowledge this, but that concession removes the claimed compression. After \(h\) arrivals, a type may be split over exponentially many bundle configurations. Exact pairwise EF1 requires constraints between every positively populated pair of configurations, not merely a constraint on type averages. Replacing those constraints by average utility or type-level EF1 would be a fractional-outcome relaxation, not the paper’s indivisible-agent problem. Retaining them produces a measure over individual histories rather than a continuous society described by a fixed finite type space.
The same obstruction appears in the proof of Theorem 5.4. Algorithm 3 constructs an envy graph on named agents, topologically sorts that graph, and uses the resulting individual rank in the matching weights
\[ 2\left(1+\frac{1}{2n}\right)^{n-i} \quad\text{and}\quad \left(1+\frac{1}{2n}\right)^{n-i}. \]
There is no envy graph on valuation types: one type can occupy many different bundle states and have many different envy relations. A mass transportation problem between types and goods is therefore not the continuous version of the algorithm. The faithful version needs a measurable ordering of bundle-history atoms and a matching over those atoms. That is a new measure-valued matching theorem, not a consequence of the paper.
The proposed scenario-tree formulation also has an unavoidable fork. If the realized good sequence is given explicitly, the future is already known and the online/nonanticipatory content disappears. If all possible sequences are supplied in a scenario tree, the problem is finite-horizon policy synthesis whose input size is the tree, not the population distribution. If the adversary is left implicit, no finite computational encoding or complexity measure has been specified. Scaling \(n-1\) goods to one per-capita future block is a defensible modelling choice, but it does not repair this missing computational object.
For rational masses, clearing denominators simply creates a finite population of clones. Theorem 5.4 can then be run on those clones. Thus the proposed model is either a repackaging of the finite algorithm, with no new continuous computation, or it requires a genuinely new state-rich policy-synthesis theory. For irrational masses, passing to a limit and proving that exact almost-everywhere EF1 survives is an additional analytic result absent from the paper.
The strongest charitable scenario—a large food-bank system with repeated recipient profiles, per-capita supplies, integral bundles, and block foresight—is socially plausible. I therefore cannot honestly claim that no meaningful continuous online fair-division model could ever be written. The negative case is instead that this paper supplies no qualifying population-level computational anchor, and its central theorem does not close under fixed-type continuization: quotienting by types loses the theorem’s identity-sensitive state, while preserving that state turns the proposal into either clone bookkeeping or a new research problem.
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.