| paper | d4-conf-ijcai-2017-0045 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, already for \(m=2\) · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 9
statement extracted from the paper’s text layer
Given a finite opinion set \(S\), \(\tau\) role types with positive rational masses \(\mu_r\), beliefs \(b_r\), rational role interaction matrix \(K\), costs \(f_r,g_r\), and pressure \(\rho\), decide whether there are masses \(y_{r,a}\ge 0\) with \(\sum_{a\in S}y_{r,a}=\mu_r\), positive total mass on at least two opinions, and every used opinion a best response. For each role \(r\), define \(C_r(a;y)=f_r(d(a,b_r))+\rho g_r(1)\sum_s K_{rs}\sum_{a'\ne a}y_{s,a'}\); require \(C_r(a;y)\le C_r(a';y)\) for every \(a'\in S\) whenever \(y_{r,a}>0\).
A nonatomic best-response game with \(\tau\) role types, rational masses \(\mu_r\), and cross-role interaction matrix \(K\). The decision variables are opinion masses \(y_{r,a}\); the question is feasibility of a non-consensus allocation in which every used opinion minimizes its role's cost.
The mirror covers Theorem 9's stationary-disagreement question in finite role-block networks. It leaves the arbitrary-graph partition characterization, Theorem 10's minimum-cut condition, clique convergence bounds, and logit hitting-time results unaddressed.
The strongest mirror is Continuous Stationary Disagreement: deciding whether a large, typed population on a structured social network can have a non-consensus stationary opinion profile.
My anchor is Theorem 9, proved in this paper. It says that when \(\rho^\star>f(1)/g(1)\), best-response dynamics on a graph \(G\) diverges if and only if \(G\) is well-partitioned: its vertices can be divided into at least two parts so that every vertex has at least as many neighbors in its own part as in each other part. This is a structural characterization, not a P-versus-NP classification. It does give divergence a polynomially checkable certificate—the partition—so the characterization implies membership in NP. The authors leave the exact recognition complexity open.
For the mirror, consider a large photo-sharing community whose members fall into a few recurring network roles: within each role, people have the same initial privacy belief, costs, and average exposure to every other role. A role is the complete type; its mass is the fraction of the community in it. This fits settings with large cohorts and repeated contact patterns, rather than arbitrary person-to-person networks, and gives \(\tau\) roles for a population of \(n\) people with \(\tau\ll n\).
Here is the decision problem. The input is a finite opinion set \(S\), rational role masses \(\mu_r\) summing to one, each role’s belief and costs, a rational interaction matrix \(K\), and social pressure \(\rho\). Let \(y_{r,a}\) be the mass of role \(r\) holding opinion \(a\), with \(\sum_{a\in S}y_{r,a}=\mu_r\). For the paper’s binary-disagreement cost, the cost to a member of role \(r\) of choosing \(a\) is
\[ C_r(a;y)=f_r(d(a,b_r))+ \rho\,g_r(1)\sum_s K_{rs}\sum_{\substack{a'\in S\\a'\ne a}}y_{s,a'}, \]
where \(b_r\) is the role’s belief and \(d(a,b_r)\) is zero for agreement and one for disagreement. Continuous Stationary Disagreement asks whether there is a mass allocation \(y\) with positive mass on at least two opinions such that every opinion used by a role is a best response: \(C_r(a;y)\le C_r(a';y)\) for every \(a'\in S\) whenever \(y_{r,a}>0\). A solution is such a rational allocation, or a certificate that none exists.
I expect this finite-type version to be fixed-parameter tractable in \((\tau,|S|)\). Enumerate, for each role, the nonempty set of opinions it uses. For each choice of supports, the best-response conditions are linear inequalities in \(y\); feasibility, including strict positivity for opinions in the support, can be checked by rational linear programming. There are at most \((2^{|S|}-1)^\tau\) support choices. This is a proposed result for the mirror, not a result proved in the paper. It makes the society continuous while keeping opinions discrete, and asks a computational question about the existence of a stationary outcome.
The mirror covers Theorem 9’s question about non-consensus stationary states on non-clique networks. The paper’s Theorem 10 adds a useful partial clue: a non-singleton minimum cut implies the graph is well-partitioned, giving a recognizable sufficient condition for divergence, but not a full recognition algorithm. I am not claiming that the clique convergence bounds or the logit result—the \(n^3+k^\star\) expected hitting-time bound of Theorem 5—carry over to a continuous population. Finite-population noise is central to that logit hitting-time guarantee.
The main weakness is that Theorem 9 relies on integer neighbor counts: a positive difference is at least one. In a mass model, exposure differences can be arbitrarily small, and members of one role can split across opinions at indifference. Thus the theorem’s graph-only partition criterion does not simply transfer; the mirror instead checks the actual cost-based best-response conditions. There is also a scope distinction: this is a stationary-state existence problem, and a paper focused on whether a particular trajectory from the belief profile reaches such a state might require an additional reachability question.
Theorem 9 is the only serious anchor, but it supports a narrower claim than the proposed mirror. It characterizes when a graph admits a non-consensus stationary state; the paper leaves the complexity of recognizing those graphs open. Its criterion depends on the individual vertices’ neighbor counts: every vertex in a part must have at least as many neighbors in that part as in each other part.
That makes the population compression the hard modeling step. To preserve those conditions exactly, a type must capture each agent’s relevant neighborhood. In a generic network, that can leave almost every vertex in its own type, so the high-multiplicity regime disappears. Replacing individual neighborhoods with average exposure through \(K\) gives a coherent block-structured mean-field game, but it no longer asks whether an arbitrary graph is well-partitioned. The proposed support enumeration and LP are valid for that restricted model; they do not transfer the open recognition problem.
A graphon formulation could retain more network detail, but without a finite input representation it does not define a computational problem. A finite block representation returns to the same tradeoff: retain enough neighborhood detail and the number of types may grow with the population; compress it and the question changes.
That is the strongest case against the anchor: the faithful version often lacks multiplicity, while the tractable multiplicity version is a different network model. It does not, however, defeat every plausible scenario. Large, repeated network roles with uniform cross-role interactions are a sensible high-multiplicity regime, and the authors could recognize the resulting stationary-state question as theirs. So the case against a direct mirror is substantial, but the universal claim that no worthwhile mirror exists is weak.
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.