| paper | d4-conf-sagt-2018-0007 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\), already for uniform positive rational masses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 3
Given a finite graph \(H=(T,F)\) and positive binary rational masses \(\mu_t\) summing to \(1\), compute the exact value and an optimal rate vector for \(\bar\alpha(H,\mu)=\min\{\max_{I\in\mathcal I(H)}\sum_{t\in I}\mu_t q_t:q_t\ge0,\ q_t+q_u\ge1\ \forall tu\in F\}\). Each type represents interchangeable players; a cross-type pair is a minimal winning coalition exactly when its types form an edge, and no within-type pair wins.
A society is a distribution \(\mu\) over role types \(T\), with pairwise winning interactions given by \(H=(T,F)\). Choose a nonnegative per-capita payoff \(q_t\) for each type, require \(q_t+q_u\ge1\) on each winning pair, and minimize the largest total payoff \(\sum_{t\in I}\mu_t q_t\) over independent type sets \(I\). For rational masses, this is exactly the original graphic-game threshold divided by the population size in the corresponding blow-up.
The mirror covers Proposition 3, the NP-hardness result for computing the threshold in arbitrary graphic simple games. It leaves the paper’s structural bounds and its algorithmic results for bipartite graphs and fixed threshold values untouched.
My lead is the Mass-Normalized Graphic Critical-Threshold Problem. It mirrors the paper’s Proposition 3 in Section 5, proved there: computing \(\alpha_G\) for an arbitrary graphic simple game \(G\) is NP-hard. The paper proves this by reducing from maximum independent set. Given a graph \(G\) with \(n\) vertices and maximum independent set size \(k\), it forms \(G^\ast\) from two copies of \(G\), joining \(i'\) to \(j''\) exactly when \(i=j\) or \(ij\in E(G)\). The paper shows that \(\alpha_{G^\ast}=k/2\), so computing \(\alpha\) recovers \(k\). The proposition is established in the paper; the NP-hardness of maximum independent set is the cited starting point.
For the mirror, let \(H=(T,F)\) be a finite graph of role types, and let \(\mu_t>0\) be the fraction of the population with type \(t\), with \(\sum_{t\in T}\mu_t=1\). Agents of type \(t\) are interchangeable: a pair from types \(t,u\) is a minimal winning coalition exactly when \(tu\in F\). There are no within-type winning pairs. A coalition is a mass vector \(x\), with \(0\le x_t\le\mu_t\); it is losing exactly when its positive-mass types form an independent set of \(H\).
Assign each agent of type \(t\) a nonnegative payoff rate \(q_t\). The edge constraints \(q_t+q_u\ge1\) preserve the paper’s requirement that every minimal winning pair receive total payoff at least one. The continuous problem is
\[ \bar\alpha(H,\mu)= \min_{\substack{q_t\ge0\\q_t+q_u\ge1\ \forall\,tu\in F}} \ \max_{I\in\mathcal I(H)}\sum_{t\in I}\mu_tq_t, \]
where \(\mathcal I(H)\) is the set of independent type sets. A solution is an optimal \(q\) and the exact value \(\bar\alpha(H,\mu)\). The inner maximum is the largest total payoff of a losing coalition: with nonnegative rates, it takes all the mass of each type in some independent set.
This is the normalized high-multiplicity version of the paper’s problem, not just a similar-looking optimization. Replace each type \(t\) by \(r_t=M\mu_t\) identical players, for an integer \(M\) making all counts integral, and put all cross-type winning edges specified by \(H\). The resulting graphic simple game has
\[ \frac{\alpha}{M}=\bar\alpha(H,\mu). \]
The equality follows by averaging any feasible payoff assignment within each type: symmetry preserves feasibility and cannot increase the maximum losing-coalition payoff. Thus every rational-mass instance is exactly the normalized value for arbitrarily large populations with the same type proportions.
The hardness anchor transfers directly. For the paper’s \(G^\ast\), use \(H=G^\ast\) and uniform masses \(\mu_t=1/(2n)\). Then \(\bar\alpha=\alpha_{G^\ast}/(2n)=k/(4n)\), so an exact algorithm for the continuous problem would recover the maximum independent set size \(k\). The corresponding population can have \(M\) agents and only \(2n\) types, with \(M\) arbitrarily large. The expected classification is hardness transfers: the difficult combinatorics live in the type-interaction graph, not in the population multiplicity.
This is a credible extension of the paper’s graphic simple games. The paper itself discusses a game with large classes of players of types A and B, so grouping interchangeable players is already natural in its setting. The mirror covers the arbitrary-graph NP-hardness result, not all the paper’s structural bounds or other algorithmic results. It also suggests follow-up questions: which restrictions on \(H\) make exact computation tractable, and can parameters such as support size or graph structure yield efficient exact or approximation algorithms?
The weakest point is that the continuous problem preserves the minimal pair rule as a local constraint \(q_t+q_u\ge1\), rather than imposing the original payoff ratio directly on integrals over winning mass. That is deliberate: the exact blow-up identity shows this local rule is what the paper’s \(\alpha\) problem becomes after normalizing by population size. A second limitation is that the hardness family needs the number of types to grow; it establishes hardness when each type has high multiplicity, not when the total type universe is fixed once and for all.
The paper has one genuine computational anchor: the Section 5 proposition that computing \(\alpha_G\) for graphic simple games is NP-hard. I can’t dismiss it on the ground that the paper lacks a computational result.
The strongest objection is that the proposed mirror keeps the hard instance intact. Its type graph \(H\) is the original graph structure; making \(M\) copies of each type changes the headcount but not the normalized optimization. The hard part still grows with the support size \(\tau\), and the added population multiplicity is inert. For fixed \(\tau\), the independent sets can be enumerated and the resulting optimization solved as a finite LP. So the mirror does not show hardness arising from a large population that can be compressed to a small type description.
There is also a modeling tension. The proposed constraint \(q_t+q_u\ge 1\) retains a two-person winning coalition, while a continuous coalition can contain arbitrarily small positive masses of the two types. If payoffs are integrated over mass, such a coalition can have arbitrarily small total payoff. A continuous version therefore needs a normalization tied to finite minimal winning coalitions. The proposed normalization supplies one, but it makes the problem exactly the normalized blow-up optimization. That leaves a choice between an atomless coalition interpretation with a degenerate winning threshold and a per-capita convention that reproduces the finite high-multiplicity problem.
These objections make the mirror look less like a new computational landscape and more like an exact high-multiplicity formulation of an existing graph problem. But they do not defeat it under the programme’s stated test. The role-type scenario is plausible for a voting body with repeated constituencies, the exact blow-up identity is itself a useful bridge, and hardness that transfers is an accepted outcome. I know of no continuous computational treatment that already answers this question, and the paper’s existing high-multiplicity examples support its plausibility.
So the honest negative case is weak: it raises a real question about the continuum’s coalition semantics and the mirror’s added value, but it does not establish that no worthwhile scenario exists. The anchor likely survives.
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.