| paper | d4-conf-sigecom-2003-0005 |
| 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}\)-hard, even for \(\tau=2\) and \(k=0\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite two-player game \(G=(A_1,A_2,u_1,u_2)\) with rational payoffs, a target set \(D\subseteq A_1\times A_2\), and \(k\ge 0\), consider a unit mass of independent encounters, each retaining the original atomic two-player game. The population has role types \(1\) and \(2\), each of mass \(1/2\). Does there exist a pair of nonnegative bonus tables \(v_i:A_1\times A_2\to\mathbb{R}_{\ge 0}\) such that \(\varnothing\ne ND_1(v)\times ND_2(v)\subseteq D\) and every rational outcome distribution \(\rho\) supported on \(ND_1(v)\times ND_2(v)\) has \(\int (v_1+v_2)\,d\rho\le k\)?
A unit mass of independent, paired encounters with role types \(1\) and \(2\), each of mass \(1/2\); each encounter retains the paper’s finite two-player incentives. The operator chooses nonnegative bonus tables \(v_i(a_1,a_2)\), uniformly applied across encounters, and the decision question is whether they implement only profiles in \(D\) while keeping total per-encounter payment at most \(k\).
The mirror covers Theorem 4’s NP-hardness for set \(k\)-implementation, including the two-player, fixed-budget reduction. It leaves the singleton characterization, exact implementation, VCG results, and mixed- and correlated-strategy results outside its scope.
The strongest mirror is the paper’s set implementation problem, lifted to a continuum of identical pairwise encounters. This fits a plausible high-multiplicity regime: a platform runs a very large cohort of standardized two-party interactions. Each encounter has the same rules and payoffs, and a reliable operator can promise bonuses based on the actions observed in that encounter, but cannot change the rules or compel behavior. Think of users choosing routes or service options in a repeated protocol. The users form two complete types, one for each role, with mass \(1/2\) each; the number of participants is unbounded while the number of types stays at two.
The anchor is Theorem 4, proved in this paper. It says that, given a game \(G(U)\), a desired set \(O\) of strategy profiles, and an integer \(k\ge 0\), deciding whether \(O\) has a \(k\)-implementation is NP-hard. A solution is a vector of nonnegative payments \(V\) such that the non-dominated strategy profiles form a nonempty subset of \(O\), and the total payment at every such profile is at most \(k\). The paper proves hardness by reducing SAT, already for two-player games and the fixed budget \(k=2\).
Here is the continuous question I would hand to a prover: Continuum Pairwise \(k\)-Implementation. An instance consists of a finite two-player game \(G=(A_1,A_2,u_1,u_2)\) with rational payoffs, a target set \(D\subseteq A_1\times A_2\), and an integer \(k\ge0\). The society is a unit mass of identical encounters, each containing one participant of each role; the participants in each role share their strategy set, payoff function, and interaction structure. A society-wide outcome is a distribution \(\rho\) over local action profiles, giving the fraction of encounters in which each profile occurs. The operator chooses nonnegative bonus tables \(v_i:A_1\times A_2\to\mathbb R_{\ge0}\), applied in every encounter. In the resulting local game, let \(ND_i(v)\) be the role-\(i\) actions not dominated in the paper’s sense. The question is whether there are tables \(v_1,v_2\) such that
\[
\varnothing\ne ND_1(v)\times ND_2(v)\subseteq D
\]
and, for every rational society outcome supported on those profiles,
\[
\int_{A_1\times A_2} \bigl(v_1(a,b)+v_2(a,b)\bigr)\,d\rho(a,b)\le k.
\]
A solution is the pair of bonus tables satisfying these conditions. Since any profile in \(ND_1(v)\times ND_2(v)\) can occur in every encounter, the population-wide budget condition is equivalent to the paper’s worst-case per-encounter payment bound. This makes the mirror precise and keeps the intervention, objective, and minimal-rationality assumption the authors’ own.
I expect hardness to transfer (Class B). The continuous question is equivalent to Theorem 4’s decision problem: a homogeneous continuum of encounters makes the outcome distribution continuous, but does not remove the game’s action-profile combinatorics. That is consistent with the programme’s heuristic that hardness living in the alternatives or agenda tends to survive continuization. The scope here is specifically Theorem 4’s hardness for implementing a set of profiles; I would not claim this mirror covers the paper’s singleton formula, exact implementation, VCG results, or mixed-strategy results.
The main weakness is that the continuum is a cohort of independent copies of a finite game. Aggregate masses describe how often local profiles occur, but they do not change any participant’s incentives, so the hardness result carries over unchanged. This is a credible mirror for a high-volume deployment of repeated interactions, but it offers little of the new continuous-optimization structure that makes some ChoCo mirrors especially valuable. A harder follow-up would let encounters interact through aggregate congestion or let the operator condition payments on society-wide frequencies; then one would need to determine whether the resulting mass-based implementation problem is still recognizable to the authors and whether its complexity changes.
The strongest objection is that the proposed continuum sits mostly in \(\rho\), the distribution of local outcomes, while the society itself is fixed at two role types with masses \(1/2\). Moreover, its population cost constraint adds no new condition. Since a rational society outcome may put all its mass on any one surviving profile, requiring
\[ \int \bigl(v_1+v_2\bigr)\,d\rho \le k \]
for every such \(\rho\) is equivalent to requiring \(v_1(a,b)+v_2(a,b)\le k\) at every profile in \(ND_1(v)\times ND_2(v)\). The mass distribution disappears from the decision problem, leaving Theorem 4’s finite-game question intact. This is a real weakness in the proposed formulation: its continuous notation adds no population-level computational structure.
A more substantive mirror would make the target or incentives depend on the population’s aggregate action frequencies. But then the paper’s finite set \(O\) of strategy profiles and its non-dominated-action condition need a new population-level definition. Theorem 4’s SAT reduction does not automatically establish hardness for that model. In an atomless population, one agent’s action does not change aggregate frequencies; aggregate-contingent payments therefore need careful design to affect individual incentives. That leaves an interesting modeling and complexity task, but it is no longer the direct mirror the proponent claimed.
This objection still does not defeat the stronger scenario. A platform could run a very large cohort of standardized, independent two-party interactions, with participants interchangeable within each role and bonuses applied uniformly to each encounter. The society then really is a high-multiplicity population of two complete types. Per-capita implementation cost is a natural normalization, and the finite game’s input can remain the local interaction. Theorem 4’s reduction applies to each encounter, so this version is a sensible, if narrow, continuous-population question.
The paper’s mixed- and correlated-strategy results do not already answer that set-implementation complexity question, and hardness surviving the limit is not an objection under the programme’s criteria. My best case against is therefore that this mirror is computationally a replication of the finite problem, with a trivial mass constraint. That may make it less valuable for developing continuous-optimization methods, but it does not establish that the population regime is unsound or the question unworthy. I cannot honestly defeat Theorem 4 as an anchor; the negative case is weak against the programme’s stated standard.
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.