| paper | d4-conf-aaai-2017-0676 |
| 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→P discrete result → its continuous mirror
Answer: \(\text{polynomial-time solvable}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite connected undirected role graph \(H=(T,F)\) of maximum degree six, positive rational masses \(\mu_t\) summing to one, and rational \(\varepsilon>0\), consider an atomless population with mass \(\mu_t\) of each role \(t\). Agents are adjacent exactly when their roles are adjacent in \(H\). For a measurable coalition \(j\), let \(x_{t,j}\) be its mass of role \(t\) and \(S_j=\{t:x_{t,j}>0\}\). Distinct roles in \(S_j\) have their shortest-path distances in \(H[S_j]\); distinct agents of the same role have distance two if that role has a neighbor in \(S_j\), and infinite distance otherwise. Their utility is the average inverse distance to coalition members, and total welfare is the integral of utility over the population. Find a finite rational mass table defining a partition with welfare within \(\varepsilon\) of the supremum over measurable partitions.
An atomless population distributed over finitely many roles, with role masses \(\mu_t\), adjacency inherited from a bounded-degree role graph, and measurable coalition partitions. Optimize total average-inverse-distance welfare, represented by role masses \(x_{t,j}\) in each coalition.
The mirror covers Theorem 1’s welfare-maximization problem; it leaves aside Theorem 2’s approximation guarantee and the PPO bounds in Theorems 3–8.
I would lead with Theorem 1 alone. It states that finding a welfare-maximizing partition in an unweighted undirected Social Distance Game is NP-hard even when the social graph has maximum degree \(6\). The paper presents this as its own result, although it omits the proof; it extends the earlier NP-hardness result for unrestricted graphs cited from Brânzei and Larson (2011). The underlying task is to partition the graph’s agents into coalitions to maximize the sum of their utilities, where an agent’s utility is the sum of inverse distances to the other coalition members, divided by coalition size. A welfare-maximizing partition is Pareto optimal, so this is also the paper’s hard case of finding the best stable outcome.
A continuous version I find credible is Continuous Role-SDG Welfare Optimization. Its input is a finite, weakly connected, undirected role graph \(H=(T,F)\) with maximum degree \(6\), and rational masses \(\mu_t>0\) for its roles, summing to \(1\). The population is atomless: role \(t\) contains mass \(\mu_t\). Two agents are directly connected exactly when their roles are adjacent in \(H\); thus every member of one role has the same connections to every neighboring role. This makes a role a complete description of an agent for the model.
An outcome is a measurable partition of the population into positive-mass coalitions. Let \(x_{t,j}\) be the mass of role \(t\) in coalition \(j\), and \(M_j=\sum_t x_{t,j}\). Write \(S_j=\{t:x_{t,j}>0\}\). For distinct roles \(t,s\in S_j\), let \(d_j(t,s)\) be their shortest-path distance in \(H[S_j]\). Two distinct agents of the same role have distance \(2\) if that role has a neighbor in \(S_j\), and infinite otherwise. Then a role-\(t\) agent in coalition \(j\) has utility
\[ u_{t,j}=\frac{1}{M_j}\sum_{s\in S_j}\frac{x_{s,j}}{d_j(t,s)}, \]
with \(1/\infty=0\). The welfare is
\[ \operatorname{SW}(x)=\sum_j\sum_{t\in S_j}x_{t,j}u_{t,j}. \]
The task is to maximize this welfare over partitions, returning, for rational \(\varepsilon>0\), a finite rational mass table \(x_{t,j}\) whose welfare is within \(\varepsilon\) of the supremum. Any attained global maximum is Pareto optimal: a measurable deviation that weakly improves almost everyone and strictly improves a positive mass would increase total welfare.
The regime is a large online or organizational social network whose participants fall into a small or moderate number \(\tau=|T|\) of standardized roles. For example, members of neighboring departments may all be reachable by one another, while members of the same role share the same network profile. In finite approximations there may be \(N\) agents, with about \(N\mu_t\) in each role, while the input and decision variables are expressed through \(\tau\) and the rational masses. This is a population continuization: mass can be split among coalitions, while harmonic distance, coalition formation, and the welfare objective remain.
I expect this problem to be continuum-specifically hard (Class C), though that is a conjecture, not a consequence of Theorem 1. The role graph still carries arbitrary shortest-path structure, and allowing role mass to split does not erase that structure. Theorem 1 gives a strong anchor for asking whether the hard combinatorics survive, dissolve, or change form.
The soft spot is substantial: Theorem 1 bounds the degree of each individual’s graph, while this role blow-up gives an agent connections to whole role populations, so individual degree grows with population size. The theorem’s hardness therefore does not transfer directly. The proposed problem is a high-multiplicity SDG variant with a changed graph regime, not a proof that the paper’s bounded-degree instances have a continuous limit of the same complexity.
This mirror covers Theorem 1, not the paper’s approximation guarantee or its PPO bounds. It leaves useful questions: is the optimum attained, can an optimal or near-optimal partition be represented with a bounded number of coalitions, and is welfare optimization polynomial in \(\tau\), the mass bit length, and \(1/\varepsilon\)—or does hardness persist even with only six neighboring roles per type?
Theorem 1 is a genuine computational anchor: it proves NP-hardness for welfare maximization in Social Distance Games, even on graphs of maximum degree \(6\). The strongest objection is that the proposed mirror does not preserve the graph regime that makes this result distinctive. In a bounded-degree instance, an agent’s position among particular neighbors can determine its distances to everyone else. A type description that retains those relationships may need to distinguish many vertices, leaving little repeated population to continuize.
The proposed role graph takes the other route: every member of one role is connected to every member of each neighboring role. In a finite realization, a role-\(t\) agent then has degree proportional to the population size, so the graph is a dense blow-up rather than a high-multiplicity version of the theorem’s bounded-degree instances. Its distances and welfare can differ substantially from those in the original graph. Preserving sparse local structure in a continuum would require carrying additional relational information—such as a graphing or a detailed edge structure—alongside the role masses. That could define an interesting problem, but it is no longer a mass table over a fixed finite type set, and its computational input would still contain the graph geometry responsible for the original hardness.
This objection does not establish that the role-level model is unworthy. A dense network of standardized roles is plausible, and the resulting welfare problem is a coherent continuization of Social Distance Games. The authors could reasonably recognize it as their problem. The objection instead weakens the claimed connection to Theorem 1: that theorem gives no reason to expect its bounded-degree complexity landscape to survive in the proposed model. Still, under the brief’s universal burden, I cannot honestly rule out a worthwhile mirror in every scenario. The negative case is weak precisely where the proposed dense-role scenario is strongest.
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.