| paper | d4-conf-ijcai-2015-0544 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given \(N\), a set of complete types \(\Theta\) with rational masses \(\mu_\theta\) satisfying \(N\mu_\theta\in\mathbb{Z}_{\ge 0}\), and a set of houses, let \(x_{\theta,r}\) be the mass of type \(\theta\) reporting ranking \(r\), with \(Nx_{\theta,r}\in\mathbb{Z}_{\ge 0}\) and \(\sum_r x_{\theta,r}=\mu_\theta\). Run PS on the corresponding \(N x_{\theta,r}\) agents. Compute a report-mass matrix \(x\) such that no agent can improve their expected utility by moving their individual mass \(1/N\) from their current report to another ranking.
Types share a true ranking and cardinal utility vector; reports are strategic choices and may differ within a type. The society is represented by masses \(\mu_\theta\), reports by \(x_{\theta,r}\), and PS uses the paper's unit house supplies. The equilibrium condition compares each type's expected utility before and after a unilateral \(1/N\) report change.
The results establish neither hardness for small support \(\tau\) nor properties of the genuinely atomless equilibrium; the proponent identifies both limits, so they bound the mirror rather than defeat it.
fatal: False
The mirror covers Theorems 3 and 4 on PNE verification and computation. It leaves the best-response cycles, the existence result, the two-agent algorithm, and the welfare experiments aside.
My lead is a high-multiplicity, mass-compressed version of computing a pure Nash equilibrium under PS. It keeps the paper’s unilateral-deviation question intact while representing the society by type masses.
The natural regime is a large school or course allocation with many applicants but relatively few complete types: each type includes both a strict ranking and the cardinal utility vector used to evaluate expected utility. For example, students following the same standardized program could share a type. If there are \(N\) applicants and \(\tau\) such types, the input gives their rational shares \(\mu_\theta\), with \(N\mu_\theta\) integral. Different members of one type may report different rankings.
Let \(x_{\theta,r}\) be the share of type \(\theta\) reporting ranking \(r\), so \(\sum_r x_{\theta,r}=\mu_\theta\) and \(Nx_{\theta,r}\) is integral. Run PS with \(Nx_{\theta,r}\) agents reporting \(r\), each eating at unit speed and each house having the paper’s unit supply. All agents reporting \(r\) receive the same PS allocation, say \(p_r(x)\). A type-\(\theta\) agent’s payoff from that report is \(u_\theta\cdot p_r(x)\). A unilateral deviation moves mass \(1/N\) from \(x_{\theta,r}\) to \(x_{\theta,s}\); the profile is an equilibrium exactly when no such move raises that agent’s expected utility. Computing an equilibrium means returning such a mass matrix \(x\); verification asks whether a supplied one satisfies this condition.
The strongest anchor is Theorem 4, proved in this paper: given agents’ utilities, computing a preference profile that is a PNE under PS is NP-hard. The authors’ proof uses a construction that forces designated agents to report truthfully, then invokes the previously established NP-hardness of computing one agent’s expected-utility best response. In the mass formulation, this asks whether the PNE search remains hard when the population is represented by type shares and reported mass. For the unrestricted support-size problem, I expect hardness to transfer: aggregating identical agents loses no information about PS outcomes or single-agent deviations, and the original instance can be recovered by expanding the counts. This is the lead because it directly tests whether a population-mass representation removes the paper’s computational obstacle.
A second, worthwhile anchor is Theorem 3, also proved here: given agents’ utilities and a reported preference profile, checking whether it is a PNE under PS is coNP-complete. The paper proves hardness by adapting a 3SAT reduction and choosing utilities that force the other agents to report truthfully; membership follows because a profitable deviation is a polynomially checkable certificate of non-equilibrium. Its mass mirror is the verification problem just defined, with the candidate supplied as \(x\). I likewise expect coNP-completeness for unrestricted support: a profitable deviation is still witnessed by a type, a report used by that type, and one alternative ranking. The paper’s result is proved here, though its reduction builds on cited best-response hardness.
The mirror covers the paper’s computational PNE results, Theorems 3 and 4. It does not treat the cycle or welfare experiments as computational anchors, and PS’s fractional assignments are not the source of continuity here; the society is represented by a distribution over complete types.
The soft spot is that this model retains the single-person step \(1/N\). It is a high-multiplicity encoding, not a strict atomless limit. Removing that step changes the equilibrium concept, so these theorems would not establish hardness for a nonatomic PS game. Also, the paper’s reductions do not show hardness when \(\tau\) is small relative to \(N\). That restricted regime is a natural next question: does type compression make equilibrium computation tractable when many agents truly share a small set of complete types?
The strongest objection to both anchors is that their hardness is built around an atomic unilateral deviation. In the paper, one named agent changes their report, potentially changing the PS eating schedule. The report masses alone do not specify that strategic effect: the deviation has size \(1/N\), so one needs the population size and the granularity of its atoms.
For Theorem 4, the reduction singles out one manipulator and uses specially chosen utilities to force the other agents to report truthfully. It then imports the hardness of that one agent’s best response. The proof does not establish hardness in a regime with many copies of a small set of complete types. Replicating the agents may change the equilibrium incentives; keeping the manipulator as a single agent leaves a deviation of size \(1/N\). In an atomless model, that deviation has zero mass and does not change the aggregate PS process. Keeping the \(1/N\) step preserves the theorem’s problem, but it preserves a finite atomic game too. That is a high-multiplicity encoding, not by itself a limit result.
Theorem 3 has the same issue. Its coNP reduction makes the truthful profile an equilibrium exactly when the singled-out agent has no profitable manipulation. A certificate against equilibrium is still one agent’s deviation. In the atomless model, checking best responses against the aggregate schedule is a different verification problem; the paper’s reduction does not show that it is coNP-hard. In the finite-mass version, the reduction may carry over when the support includes the engineered agents as distinct types, but that does not settle the low-support regime where type compression is doing substantive work. The two theorems are therefore not independent evidence for a continuous computational landscape: both lean on the same single-agent manipulation result.
The best version of the mirror is coherent: for a large course or school allocation with a small set of complete utility types, let each type distribute its mass over reported rankings, run a continuum PS process, and require every report used by a type to maximize that type’s expected utility against the resulting aggregate schedule. That defines a computational equilibrium problem. But it is a nonatomic or Wardrop-style equilibrium: an individual’s deviation does not change the schedule. If instead a positive mass deviates together, the deviation is coordinated and no longer the paper’s PNE. The paper’s theorems do not tell us which version has the properties its authors would care about, or whether either is tractable.
That is the best case against: the paper’s central equilibrium results may not survive the move to a genuinely continuous population without changing what “deviation” means. It is a real modeling risk, but it does not support the universal claim that no worthwhile mirror exists. The high-multiplicity version remains a sensible question under ChoCo’s stated scope, and the nonatomic version is a plausible, if different, one. I would not claim the negative case defeats both anchors decisively.
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.