| paper | Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness |
| authors | Georgios Amanatidis, Georgios Birmpas, Federico Fusco, Philip Lazos, S. Leonardi, Rebecca Reiffenhauser |
| venue | WINE 2021 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The decisive problem is formal: Theorem 3.3 is a finite-game fairness theorem, while Theorem A.3 is an existence statement, so neither supplies the required named computational result. The proposed mass-flow formulation is a coherent research direction, but nonatomic deviations and periodic phases re-model the sequential game rather than continuize the anchored theorem. Therefore bit (a) fails.
fails bit a — no named computational result to mirror
In the nonatomic limit, an individual deviation changes aggregate availability by \(O(1/N)\) and vanishes, so the proposed best-response condition is Wardrop-like rather than the finite-player PNE proved about in Theorem 3.3; preserving pivotality would require extra phase or bloc-deviation assumptions.
fatal: True
The proposal concerns Theorem 3.3 and uses Theorem A.3 only as supporting evidence for finite equilibrium existence; it leaves Theorem 4.3, Theorems 4.5 and 4.7, and the cited best-response hardness results outside the mirror.
The strongest honest case is qualified. Strictly under the programme’s anchor rule, this paper has no fully compliant computational anchor: it contains no numbered theorem asserting NP-hardness, membership in \( \mathrm{P} \), FPT, or a comparable complexity classification. Remark 2.8 says that best responses for Round-Robin are NP-hard, citing [11], and that best responses for Mod-Cut&Choose are NP-hard by an easy reduction from PARTITION, but neither is a named result proved in this paper.
There is nevertheless a substantive mirror, led by Theorem 3.3.
Theorem 3.3, proved in the paper, states: for every fair-division instance \(I=(N,M,v)\) with additive valuations, every pure Nash equilibrium of Round-Robin induces an allocation that is EF1 with respect to the agents’ true valuations. The companion Theorem A.3, also proved in the paper, establishes that Round-Robin has at least one pure Nash equilibrium for every additive-valuation instance.
I would formulate the following lead problem.
Continuous Round-Robin Equilibrium–EF1. The input consists of:
The supply scaling is essential: a population of size \(N\) has \(N\kappa_g\) copies of good \(g\). Goods remain indivisible for every individual. A feasible continuous allocation is a mass distribution \(x_{t,B}\), where \(B\) is an integral bundle, satisfying \( \sum_B x_{t,B}=\mu_t \) and \( \sum_{t,B:g\in B}x_{t,B}\le\kappa_g \).
Each type chooses a reported ranking \( \pi_t \) of the good classes. The continuous Round-Robin mechanism is the periodic mass-flow version of the paper’s mechanism: each infinitesimal agent takes her highest-ranked currently available good, and \(x\) records the resulting mass of agents receiving each integral bundle. A solution is a report profile \( (\pi_t)_{t\in T} \), together with \(x\), such that:
The decision version asks whether such a mass equilibrium exists; the search version asks for the report profile, the bundle-mass table \(x\), and a certificate of the no-profitable-deviation and support-wise EF1 conditions.
This is a genuine population continuization. The many agents are employees, households, or students receiving repeated copies of a standard catalogue of indivisible goods. Their valuation types can coincide because they share a job role, contract, or household profile; their schedule phase is included in the type because serial position is behaviourally relevant. A realistic regime has millions of agents but perhaps dozens of valuation-and-phase types. The model does not replace indivisible bundles by fractional bundles and does not replace EF1 by an average-value condition. Fractions describe how much population receives each integral bundle.
The authors should recognise this as their problem: it retains additive true valuations, strategic reports, no payments, sequential picking, pure Nash equilibrium, and EF1 at equilibrium. The only necessary co-modifications are the recurring supply and the explicit periodic schedule. Without them, fixed finite goods make the large-population limit vacuous; without the schedule, a distribution of types does not determine the outcome of a sequential mechanism.
My expectation is Class A in the fixed-type regime: with fixed \( |T|=\tau \), the aggregate process should admit a capacitated-flow or configuration formulation, and the dependence on the number \(N\) of named agents should disappear. The natural technical questions are whether the equilibrium constraints admit a finite-state dynamic programme, whether the configuration pricing problem is polynomial, and whether the result is FPT in \( \tau \). If \( \tau \) and the number of good classes are unrestricted, the best-response combinatorics may survive; the paper’s own Remark 2.8 points toward a possible hardness boundary, although it cannot serve as the formal anchor.
This mirror covers Theorem 3.3 and uses Theorem A.3 as supporting evidence for the existence part. I would not use Theorem 4.3 as a second anchor: its Mod-Cut&Choose result is restricted to two strategic agents, and turning it into a large population would most naturally produce independent replicated two-agent households rather than a genuinely interacting continuum.
The weakest point is the equilibrium semantics. Round-Robin depends essentially on individual order, and an atomless population has no canonical order or individually pivotal deviation. Adding a periodic schedule and defining equilibrium through mass-flow or finite-replication limits is therefore a real modelling choice. The resulting problem could be criticised as a new batched allocation game rather than a direct limit of the paper’s game. Still, it preserves the paper’s central strategic and fairness question much more faithfully than a type-average or divisible-goods formulation.
Thus the best positive verdict is: a plausible and technically interesting continuous-population extension exists, centred on Theorem 3.3, but the paper does not contain a qualifying named computational result. Under a strict anchor requirement, that formal deficiency must be reported.
The strongest objection is formal and decisive: this paper has no qualifying named computational result to mirror. Theorem 3.3 proves a fairness property of finite-game equilibria; Theorem A.3 proves equilibrium existence. Neither states membership in \( \mathrm{P} \), hardness, approximation, FPT, or another computational classification. The paper explicitly says that computing best responses and reaching equilibria are outside its scope. Remark 2.8 mentions hardness only as background, citing other work. Thus the proposed continuous decision/search problem would be a new problem inspired by the paper, not a continuization of one of its computational results.
The proposed Round-Robin mirror also loses the strategic content of Theorem 3.3. In the finite mechanism, an agent’s report can change which goods remain available to later agents, and the paper’s proof is built around precisely this path dependence. With \(N\) replicated agents and \(O(N)\) copies of each good class, one agent’s deviation changes aggregate availability by only \(O(1/N)\), hence by zero in the nonatomic limit. Her report can change her own bundle, but not the future aggregate process. The resulting equilibrium is therefore a Wardrop-style pointwise best-response condition, not the pure Nash equilibrium studied in the paper. If true additive values are used, the strategic manipulation that motivates the theorem largely disappears.
There is a three-way obstruction here. If exact serial position is included in the type, then the type is effectively \( (v,i) \), where \(i\) is the agent’s place in the order. The number of types grows with the population, so the model has no genuine high-multiplicity compression. If exact positions are replaced by finitely many phases, the imposed periodic schedule is additional structure not determined by the population distribution; it defines a new batched allocation mechanism. If positive-mass deviations are allowed so that reports affect the aggregate process, the deviating object is a type bloc or coalition, not an individual strategic agent, and the equilibrium concept is no longer the paper’s PNE.
The suggested support-wise EF1 condition is itself a sensible mass analogue: agents may receive integral bundles while the population is split fractionally among bundles. That removes the usual mistaken objection about fractional outcomes. But it does not repair the central problem. It adds a new fairness requirement to an aggregate allocation process after the finite strategic externality has vanished. A periodic repeated-copy allocation problem might be worthwhile in its own right, but it is not what Theorem 3.3 establishes.
Theorem A.3 does not provide an independent rescue. Finite existence for every \(N\) does not specify a canonical continuum equilibrium, nor does it yield an algorithm for computing one. Its proof relies on perturbing individual valuations and on the finite sequential order. A limit of selected equilibria would require additional choices about schedules, symmetry, and convergence, all absent from the paper.
So the positive case identifies a plausible new high-multiplicity fair-division model, but not a continuous computational mirror of this paper. Under ChoCo’s anchor rule, the paper should not receive a green verdict: the sole proposed anchor is non-computational, and every way of preserving its strategic substance either keeps \(N\)-scale individual order or changes PNE into a different equilibrium notion.
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.