| paper | d4-conf-atal-2016-0315 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Exact computation is polynomial-time in \(m,\tau,L\); deciding \(V\ge q\) belongs to \(\mathrm{P}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite support of complete local allocation types \(\Theta\), with binary-rational masses \(\mu_\theta\) summing to one, where each type specifies an independent two-agent instance, compute the maximum population-average expected utility \(V=\max_{(\sigma_\theta)}\sum_{\theta\in\Theta}\mu_\theta E_\theta(\sigma_\theta)\) for the A-side participants.
A distribution \(\mu\) over complete types of independent two-agent allocation units; each unit retains its own indivisible items, sincere B-side opponent, and random process, while A-side strategies are chosen per type and the objective is population-average expected utility.
The units do not share an allocation or feasibility constraints, so the population layer aggregates independent games and adds no interaction across types.
fatal: False
The mirror covers Theorem 4 for random sequences and Theorem 5 for random tie-breaking; it does not claim a population analogue for Theorems 1–3 or the paper’s other discussions.
The most credible positive mirror is a large population of independent two-agent allocation units. Imagine a platform running the same local picking protocol across many sites, each with its own copy of \(2m\) indivisible items and two participants. The many A-side participants are the population; each is paired with a sincere B-side opponent. A type \(\theta\) records the complete local instance: B’s strict ranking, A’s additive utility, and any varying protocol state. If \(N\) is large while the number \(\tau\) of distinct types is small, \(\mu_\theta\) is the fraction of A-side participants of type \(\theta\). Mass is across local units; every unit still allocates whole items.
My lead anchor is Theorem 4, proved in the paper. It says that, for two agents and \(2m\) items, given B’s strict ranking, A’s additive utility, and the current partial sequence, the maximum expected utility A can achieve against B’s sincere picking strategy—optimizing over adaptive strategies as the fair random sequence unfolds—can be computed in polynomial time in \(m\). The paper proves this through its strategy based on admissible secure plans.
The corresponding problem is Population Max-Expected-Utility for Random Sequences. Its instance is a finite support \(\Theta\) of types with binary-rational masses \(\mu_\theta\) summing to one. Each type has its own independent local copy of the paper’s allocation problem. The question is to find the maximum population-average expected utility, and a type-specific optimal strategy for each supported type if strategies are requested. The objective is \(V=\max_{(\sigma_\theta)}\sum_{\theta\in\Theta}\mu_\theta E_\theta(\sigma_\theta)\). Since units do not interact, this is the weighted sum of their typewise optima. Theorem 4 gives a Class A expectation: polynomial time in \(m\), \(\tau\), and the binary input length \(L\), with the support handled by solving each type’s instance.
A second, separate anchor is Theorem 5, also stated as proved in the paper, though its formal proof is omitted. It says that, for two agents and additive utility, the maximum expected utility in the paper’s sequential allocation model with random tie-breaking can be calculated in polynomial time in \(m\). The protocol lets the agents bid on remaining items and resolves a conflict by a fair coin; B picks sincerely and A optimizes.
Its mirror is Population Max-Expected-Utility for Random Tie-Breaking: use the same type distribution over independent local units, run the random tie-breaking protocol in each unit, and compute the maximum mass-weighted expected utility of the A-side population. The answer is the exact optimum value; a typewise policy can accompany it. Theorem 5 supplies the same Class A prediction, with the extra factor for the finite support. These are two different protocol questions, not two versions of one blended anchor.
The mirror’s plausibility rests on preserving the paper’s local problem intact: the same two roles, indivisible items, sincere opponent, random process, and adaptive manipulation. The paper’s coin flips describe uncertainty *within* each unit; \(\mu\) describes the population *across* units. So the continuous object is not the lottery over outcomes. Nor does it fractionalize anyone’s bundle. It extends the problem to a setting with many repeated deployments and relatively few complete local types.
The weakest point is that the population consists of repeated allocation units, rather than many agents interacting in a single shared allocation. The authors could reasonably accept this as a high-multiplicity batch version of their problem, but they might regard the population layer as an aggregation: the algorithms simply run once per type. Consequently, this is a narrow, honest Class A mirror, not a strong example of discrete hardness dissolving in the continuum. The paper offers no named hardness result to anchor that question. The mirror covers Theorems 4 and 5; it makes no claim about the other results, larger groups, welfare, or fairness. Natural follow-up questions would add shared constraints across units—such as a common budget or aggregate quota—and ask whether the resulting coupled problem remains tractable. Those would be new questions beyond the anchors here.
Theorem 4 and Theorem 5 are genuine computational results, so “no named result to mirror” is not available here. The stronger objection is that both fix the number of agents at two. The parameter \(m\) grows the number of rounds and items; it never creates a large population within one allocation. The results offer no regime in which many agents of a few types jointly affect one outcome.
The best version of the proposed mirror is a platform running many independent two-agent allocations. Grant that each unit can be given a complete type—including both agents’ preferences, the local item set, and the protocol—and let \(\mu_\theta\) be the fraction of units of each type. This is a plausible batch setting. But the continuous object is then a distribution over allocation instances, not a society whose members share an allocation. Each A-side agent optimizes in a separate game with its own items and B-side opponent. The population mass does not couple their choices or change feasibility in any unit. The proposed objective, \(\sum_\theta \mu_\theta E_\theta^*\), aggregates the outputs of separate instances; it does not formulate a population-level manipulation problem of the kind ChoCo studies.
That distinction defeats both anchors. For Theorem 4, the typewise optimum is already computed by the paper’s algorithm. For Theorem 5, the same holds for each random tie-breaking instance. Adding support of size \(\tau\) means running the corresponding computation for each supported type and taking a weighted average. This could be useful as a batch-performance statistic, but its computational content comes from the original two-agent problems, not from continuizing the population. The paper’s random sequences and expected utility concern uncertainty within each instance; they do not supply the missing interaction across a society.
A stronger coupling—such as a shared item pool or a common budget across units—could make mass affect the allocation. But shared items turn the units into a many-agent process, while a centrally enforced budget changes the agents’ independent utility-maximization problem into a collective allocation problem. Either may be a worthwhile new model, but Theorems 4 and 5 do not anchor it. A continuum of opponents with a distinguished manipulator is another possible construction; preserving the manipulator’s discrete choices and meaningful access to items would require additional modeling choices, and would again change the two-agent setting.
So the negative case is strongest against these particular anchors: their most natural continuous construction is a population of separate instances, not a continuous society in one shared computational problem. It is not airtight. A platform’s distribution of repeated allocation units is plausible, and the authors might value its aggregate utility question. Whether that clears ChoCo’s gate depends on whether a workload of independent games counts as a society; under the programme’s stated population focus, I would not count it as a worthwhile continuous mirror.
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.