d4-conf-aaai-2017-0169

The exact network-role restriction is narrow, but the proponent gives a coherent cloned-role regime, so that objection alone does not defeat the mirror. The proposed stability condition lets an infinitesimal agent deviate without changing community masses, unlike the finite-agent moves in Theorem 2. It therefore asks about welfare-best nonatomic equilibria, a different solution concept; under the specified \(b\)-changes rule, the anchor does not survive.

The objection that survived

The opponent's requested clarification about a deviating agent's role leaves a separate issue: an infinitesimal mover leaves community masses fixed, unlike a finite agent in Theorem 2.

What the mirror covers

The proposed model covers Theorem 2 only; it leaves Theorem 1 and Theorems 3–6 without mirrors.

Open questions for a prover

The case FOR (proponent)

My lead, and the paper’s strongest computational anchor for this case, is Theorem 2: “Computing a best Nash equilibrium for SDGs is NP-hard.” The theorem is proved in this paper, by a polynomial reduction from Restricted Exact Cover by 3-Sets. Here “best” means a Nash-stable clustering with maximum social welfare. The paper’s other named theorems concern convergence or welfare ratios, so I would not use them as additional complexity anchors.

A plausible high-multiplicity setting is a large organization or online community whose members occupy a small number of repeated communication roles. Members of each role have the same links to every other role, and the same within-role pattern: either every pair is linked or none is. People choose which community to belong to, and prefer communities where other members are close in the communication network. The population \(N\) may be very large while the number \(\tau\) of distinct network roles stays modest. A type here includes the full network role, so its members are genuinely indistinguishable for this game.

I would define the Continuum Best Nash-Stable Clustering problem as follows. Its instance is a finite role graph \(H\), including each role’s within-role pattern, rational masses \(\mu_t\geq 0\) for \(t\in T\) with \(\sum_{t\in T}\mu_t=1\), and a rational welfare threshold \(B\). A candidate outcome is a finite allocation \(q_{tj}\geq0\): the mass of type \(t\) assigned to community \(j\), with \(\sum_j q_{tj}=\mu_t\). Distances between members of a community are the shortest-path distances in the graph obtained by expanding its positive-mass roles according to \(H\). For an agent of type \(t\) in community \(j\), define utility as the average inverse distance to its members:
\[ u_t(j)=\frac{\sum_{s\in T}q_{sj}/d_j(t,s)}{\sum_{s\in T}q_{sj}}, \]
where \(1/\infty=0\). In the same-role term, distance is between two distinct members of that role; the agent’s own mass is zero in the continuum.

Stability means that no infinitesimal agent can gain by moving to any existing community. A move into an empty community yields singleton utility \(0\), as in the finite game. The decision question is: does there exist a finite, Nash-stable mass allocation with social welfare
\[ \sum_j\sum_t q_{tj}u_t(j)\geq B? \]
Such an allocation is a witness. The corresponding optimization problem maximizes welfare over these allocations. The threshold form makes the question precise without assuming in advance that a maximum is attained.

This keeps the game’s central objects: graph distance, harmonic-centrality utility, unilateral community changes, Nash stability, and total welfare. Mass replaces headcount, and infinitesimal deviations are the natural limit of individual deviations in a large population. I think the authors would recognize it as their problem in a nonatomic, repeated-role regime. This mirror covers Theorem 2 only; it makes no claim about the paper’s convergence or price-of-anarchy and price-of-stability results.

For this mirror I expect Class A, tractable parameterized by \(\tau\), not hardness transfer. There is a concrete reason to investigate that direction. At equilibrium, every type \(t\) receives the same utility \(\lambda_t\) wherever its mass is placed. Two communities with the same role support can therefore be merged: their distance patterns are identical, and pooling their masses preserves each type’s utility and total welfare. Thus it suffices to consider at most one community for each support, giving at most \(2^\tau\) communities. After enumerating which supports are present, the mass constraints and stability conditions can be written as rational polynomial constraints of degree at most two: utilities are ratios of linear forms in masses, and multiplying by community mass gives quadratic constraints. Welfare is \(\sum_t\mu_t\lambda_t\). That suggests an exact real-algebraic approach with a number of variables depending only on \(\tau\), and a target running time \(f(\tau)\operatorname{poly}(L)\), where \(L\) includes the input bit length. This is an algorithmic conjecture to investigate, not a result established by the paper.

The main weakness is that this regime demands repeated network roles, not merely repeated preferences. Many social networks have lots of members but few preference types while still giving nearly everyone a distinct neighborhood. The paper’s RXC3 reduction uses graph structure to encode the hard instance, and Theorem 2 gives no reason to think that structure survives when \(\tau\) is small. That is also why I would not claim the hardness transfers: the mirror asks whether the combinatorics disappear in a credible high-multiplicity regime. The key next questions are whether the welfare threshold problem is indeed fixed-parameter tractable in \(\tau\), whether an optimal stable allocation is always attained, and how far the result extends beyond role graphs with uniform links between types.

The case AGAINST (opponent, writing after the proponent)

The strongest objection is that “type” in an SDG must preserve a node’s entire network role. Sharing a department, degree, or distribution of contacts is not enough: differences in edges can change shortest paths and therefore utility. A low-\(\tau\) population requires many exact network twins. The proposed role graph assumes every pair of roles is joined either completely or not at all. That is a severe restriction on large social networks; replacing those links with random ties or expected distances changes the game.

But that objection does not defeat Theorem 2’s mirror. A large population cloned from a small graph of repeated network roles is a coherent weighted SDG: coalition masses determine the harmonic-centrality averages, and agents’ objectives remain their own utilities and total welfare. Such graphs are stylized, but plausible enough as an instance regime. The paper’s best-equilibrium problem is computational, and the text offers no existing continuous treatment that already answers it. Nor does a possible tractable answer make the question unworthy.

The proposed formulation needs one detail made explicit: when a type considers joining a community where it is absent, its utility must be computed with the deviating agent’s node and links included. That is a repair to the stability definition, not a fundamental obstacle. The suggested support enumeration and real-algebraic approach also make the mirror look tractable rather than vacuous.

So the honest case against is that the useful high-multiplicity regime may be much narrower than “many repeated social roles” suggests. It does not establish that the regime is implausible or that the mirror is not worth asking. I cannot honestly defeat this anchor; the universal negative case 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.