| paper | d4-conf-atal-2015-0036 |
| 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{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
THEOREM 6
Given a finite support \(T_\mu\) of complete agent profiles with positive rational masses \(\mu_t\) summing to \(1\), finite signal and outcome sets \(S\) and \(O\), rational valuations \(v(t,o)\), arbitrary signaling costs \(c(t,s)\in\mathbb{Q}_{\ge 0}\cup\{\infty\}\), and an injective target rule \(F:T_\mu\to O\), does there exist a deterministic mechanism \(A:S\to O\) such that for every \(t\in T_\mu\), some utility-maximizing signal yields the required outcome: \(\exists s_t\in\arg\max_{s\in S}\bigl(v(t,A(s))-c(t,s)\bigr)\) with \(A(s_t)=F(t)\)?
A cohort is represented by a distribution \(\mu\) over complete profiles; members sharing a profile have the same valuations, signaling costs, and required outcome. Each member independently chooses a signal under the same mechanism \(A\), with no transfers or cross-agent effects. Feasibility requires the paper's individual incentive condition for every supported type; the masses record cohort composition but do not change those constraints.
The theorem quantifies over possible types of one agent; applying its common mechanism to a cohort of independent users is a plausible deployment lift, but the paper contains no cross-agent or aggregate population requirement.
fatal: False
The mirror covers the NP-completeness result in THEOREM 6 for \(\mathrm{FU/NT/U/FI}\), using arbitrary type-to-signal costs as in that theorem; it leaves the other cases and the remaining numbered results untouched.
I would anchor the positive case on Theorem 6, and only on that result. It proves here that deciding implementability in the FU/NT/U/FI setting is NP-complete: utilities are free rather than prescribed, transfers are forbidden, signaling costs are unrestricted, and the social choice function is injective, so each type has a distinct required outcome. The proof reduces from SAT. Its hard instances use type reports as signals, truthful reports at zero cost, and costs including finite values and infinity. Thus the hardness is not confined to an artificial signal space.
A plausible high-multiplicity setting is a large platform or insurer that applies the same screening rule to a very large cohort. A type is a complete policy-relevant profile: the agent’s values for outcomes, their costs of sending each signal, and the attributes determining their required outcome under the policy. Agents with the same profile are interchangeable. The cohort might have millions of users but only \(\tau\) distinct profiles, each with mass \(\mu_t\); for example, it could have equal mass on the profiles and many copies of each. This fits the paper’s own examples of screening and e-commerce, while retaining its central question: can one common mechanism induce the required decision for every type?
Here is the lead mirror, Continuous Costly-Signaling Implementation. An instance consists of a finite support \(T_\mu\) of types with positive rational masses \(\mu_t\) summing to \(1\); finite signal and outcome sets \(S\) and \(O\); rational valuations \(v(t,o)\); signaling costs \(c(t,s)\), including possibly infinite costs, with \(c(t,t)=0\) when signals are type reports; and an injective target rule \(F:T_\mu\to O\). The question is whether there is a deterministic mechanism \(A:S\to O\) such that, for every \(t\in T_\mu\), some utility-maximizing signal produces the required outcome:
\[
\exists s_t\in\arg\max_{s\in S}\bigl(v(t,A(s))-c(t,s)\bigr)
\quad\text{with}\quad A(s_t)=F(t).
\]
A solution is the mechanism \(A\) (with the corresponding best-response witnesses); the objective is feasibility, just as in the paper. The continuous analogue asks for implementation across the cohort’s type distribution, rather than for a named finite electorate.
The expected answer is hardness transfers (Class B). Given a hard instance from Theorem 6, assign each of its types positive rational mass—for instance, \(\mu_t=1/|T_\mu|\)—and preserve its valuations, costs, signals, and target rule. The continuous instance is implementable exactly when the original instance is. Its mass denominator can be scaled to represent arbitrarily many agents per type, while the number of distinct types remains \(\tau\). The mirror is therefore NP-hard; the same polynomial certificate of a mechanism and best-response witnesses gives NP membership. Further questions include whether the problem is fixed-parameter tractable in \(\tau\), and which restrictions on the cost structure make implementation tractable. This covers Theorem 6’s hardness result, not the paper’s full table of cases.
The weak point is that the masses do not affect feasibility: implementation is a pointwise incentive condition, so any positive mass makes a type relevant, however small. Continuization supplies a convincing large-cohort deployment story, but it does not relax the mechanism search or make the population weights part of the computation. I think authors working on scalable screening could recognize this as their problem deployed across a high-multiplicity population; a referee who requires the mass values themselves to change the question may judge it a thin mirror.
Theorem 6 is a clear computational result, but its types are possible states of one agent, not members of a population. The paper asks whether a single mechanism can implement \(F\) for every possible type. A distribution \(\mu\) over those types would naturally be a prior over that agent’s state, not a description of a society.
You can give the theorem a cohort story: many independent agents face the same screening mechanism, and agents with the same complete type profile behave identically. But exact implementation of the cohort still requires the incentive condition for every type present. With finite support and \(\mu_t>0\) for each supported type, implementation almost surely is equivalent to implementation type by type. Replicating the types or changing their rational masses leaves the feasible mechanisms unchanged. The population weights are extra input that the decision problem never uses.
A mass-sensitive variant—say, implementing \(F\) for at least \(1-\varepsilon\) of the population—could be worth studying. But it relaxes the paper’s guarantee: some positive-mass types may receive the wrong outcome. Likewise, extending the type domain to a continuum could create new incentive constraints, but it requires a new representation of that domain and its valuation and cost functions. Neither variant is supplied by Theorem 6’s finite, single-agent model.
So the strongest case against this anchor is that its proposed continuous mirror adds a population distribution without making the population part of the computation. The theorem already applies unchanged to any number of independent copies. I can’t rule out a worthwhile project on approximate or continuously parameterized types, but that would be a related mechanism-design question, not a continuization of this result.
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.