| paper | Distance Preservation Games |
| authors | Haris Aziz, Hau Chan, Patrick Lederer, Shivika Narang, Toby Walsh |
| venue | IJCAI 2025 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 6(ii)
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), an undirected graph \(E\subseteq\binom{T}{2}\), and rational \(q\), each type \(t\) is an atomless mass \(\mu_t\); every member of type \(t\) has ideal distance \(1\) to every member of type \(u\) iff \(\{t,u\}\in E\), and is neutral otherwise. Choose a probability measure \(\lambda_t\) on \([0,1]\) for each type's locations and decide whether there exist \((\lambda_t)_{t\in T}\) with normalized welfare \(\operatorname{SW}(\lambda)=2\sum_{\{t,u\}\in E}\mu_t\mu_u\int_{[0,1]^2}|x-y|\,d\lambda_t(x)\,d\lambda_u(y)\ge q\).
A finite-type nonatomic DPG in which \(\mu\) records masses of homogeneous relationship-profile types, \(\lambda_t\) records each type's location distribution, and the objective is mass-weighted pairwise enemy distance. Purification reduces optimal solutions to endpoint choices \(z_t\in\{0,1\}\), yielding weighted \(\mathrm{MAXCUT}\).
The mirror's optimal distributions always purify to endpoint assignments, so the continuous population contributes coefficients rather than a new fractional optimization phenomenon.
fatal: False
The mirror covers Theorem 6(ii)'s exact welfare-decision hardness and naturally extends Theorem 8(2)'s \(0.879\)-approximation; it leaves jump-stability results and other DPG subclasses untreated.
The strongest positive case is a high-multiplicity enemies-and-neutrals mirror of Theorem 6(ii). The paper already has a continuous action space, namely \([0,1]\); that alone is not continuization in the ChoCo sense. The genuine mirror is to replace a large population of individually named agents by rational masses of agents with identical relationship profiles.
Call the problem Continuous Enemies-and-Neutrals Welfare. An instance consists of a finite type set \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), an undirected type graph \(E\subseteq \binom{T}{2}\), and a rational threshold \(q\). Type \(t\) represents an atomless mass \(\mu_t\) of agents. Every agent of type \(t\) regards every agent of type \(u\) as an enemy exactly when \(\{t,u\}\in E\), with ideal distance \(1\); all other agents are neutral. Thus the type description includes the complete relationship pattern, as required by the high-multiplicity interpretation.
An outcome gives each type \(t\) a probability distribution \(\lambda_t\) over locations in \([0,1]\). This permits members of one type to occupy different locations, so the model does not artificially force identical agents to move as a block. Since \(d=1\), the paper’s utility becomes \(1-\bigl||x-y|-1\bigr|=|x-y|\). The normalized utilitarian welfare is therefore \(\operatorname{SW}(\lambda)=2\sum_{\{t,u\}\in E}\mu_t\mu_u\int_{[0,1]^2}|x-y|\,d\lambda_t(x)\,d\lambda_u(y)\). The decision question is whether there exists a profile \((\lambda_t)_{t\in T}\) with \(\operatorname{SW}(\lambda)\ge q\); the optimization version asks for a welfare-maximizing profile.
This is a natural office-assignment regime. Imagine a large university or company with many researchers in each of \(\tau\) repeated cohorts or roles. Researchers in the same cohort have the same ideal distance to every other cohort, for example because the relationship is determined by department, institutional faction, or role. The total population may be \(N=r\tau\), with \(r\gg \tau\); the input records the masses \(\mu_t\), not all \(N\) individuals. Clearing denominators in \(\mu\) recovers the corresponding finite blow-up with many rational clones of every type.
My lead anchor is Theorem 6(ii), proved in this paper. It states that deciding whether a DPG has a location profile with social welfare at least \(q\) is NP-complete even for enemies-and-neutrals DPGs. The paper proves this by reducing from MAXCUT and showing that, for this restriction, one may assume every location is in \(\{0,1\}\).
Exactly the same structural fact holds in the continuous mirror. Given all location distributions except \(\lambda_t\), welfare is linear in \(\lambda_t\), so replacing \(\lambda_t\) by a point mass cannot decrease welfare. After all types have been made point masses, welfare is convex in each location, so every type can be moved to one of the endpoints \(0\) or \(1\) without decreasing welfare. Consequently, an optimal solution can be represented by \(z\in\{0,1\}^{T}\), with value \(\operatorname{SW}(z)=2\sum_{\{t,u\}\in E}\mu_t\mu_u\mathbf{1}[z_t\ne z_u]\).
For uniform masses, \(\mu_t=1/|T|\), this is exactly \(2\,\operatorname{MAXCUT}(E)/|T|^2\). Given a MAXCUT instance \((G,K)\), use its vertices as types, set all masses to \(1/|V(G)|\), and choose \(q=2K/|V(G)|^2\). The continuous instance is positive exactly when \(G\) has a cut of size at least \(K\). Membership in NP follows from the binary type-location certificate \(z\). Thus the continuous problem is NP-complete.
I would classify this as Class B: hardness transfers, rather than continuum-specific hardness. The combinatorics live in the type graph \(E\), which can remain arbitrary even when every type contains an enormous population. The continuum compresses multiplicity but does not erase the agenda-level MAXCUT structure. This is precisely the kind of result the programme wants to identify: a high-multiplicity relaxation that is mathematically meaningful and computationally nontrivial, but whose hardness is inherited rather than caused by the continuum.
The same mirror also preserves the approximation side of the paper. Although I would not count it as a separate anchor, Theorem 8(2), proved here using the Goemans–Williamson MAXCUT algorithm, extends directly to the weighted type graph with edge weights \(2\mu_t\mu_u\). A polynomial-time \(0.879\)-approximation for weighted MAXCUT gives a \(0.879\)-approximation for Continuous Enemies-and-Neutrals Welfare.
This mirror is an extension rather than a literal representation of every DPG. The original paper permits arbitrary named-agent graphs; the mirror restricts attention to graphs obtained by blowing up vertices into homogeneous cohorts. That is the weakest point. If the application genuinely depends on idiosyncratic relationships, then \(\tau\) approaches \(N\), and continuization offers little. I would also avoid claiming that Theorem 4’s PLS-complete jump-stability result transfers automatically: atomless unilateral deviations require a separate mean-field formulation.
The remaining case is nevertheless strong. Enemies-and-neutrals DPGs are an explicit class in the paper, their welfare objective is unchanged, their endpoint structure survives exactly, and the MAXCUT reduction remains visible on the quotient type graph. The mirror covers Theorem 6(ii), with Theorem 8(2) as a natural approximation companion. It generates further questions about parameterization by \(|T|\) or type-graph treewidth, restricted type graphs, and whether analogous rational-clone reductions exist for the paper’s general symmetric DPGs with interior ideal distances.
The strongest objection is that the proposed mirror’s continuum is mathematically vacuous. In the enemies-and-neutrals model,
\[ \operatorname{SW}(\lambda) = 2\sum_{\{t,u\}\in E}\mu_t\mu_u \mathbb{E}_{X\sim\lambda_t,Y\sim\lambda_u}[|X-Y|]. \]
For fixed distributions of all other types, this is linear in \(\lambda_t\), so an optimum always exists with every \(\lambda_t\) a point mass. Since \(|x-y|\) is convex in each coordinate, each point mass can then be moved to \(0\) or \(1\) without decreasing welfare. Thus the proposed atomless population never splits, transfers mass, or generates a genuinely continuous optimization problem. It reduces exactly to
\[ 2\sum_{\{t,u\}\in E}\mu_t\mu_u\mathbf 1[z_t\ne z_u], \qquad z_t\in\{0,1\}. \]
This is weighted MAXCUT on the type graph. The objection is not that the answer remains hard; inherited hardness is explicitly valuable to ChoCo. The objection is that the population continuum has disappeared from the computational object. The masses merely supply vertex weights, while the decision remains one binary location per type.
The same defeats the proposed extension of Theorem 8(2): its \(0.879\)-approximation is simply the weighted Goemans–Williamson algorithm applied to that quotient graph. It is a legitimate weighted reformulation of the theorem, but it produces no new population-level approximation question, no separation problem, and no phenomenon caused by high multiplicity.
The proponent’s office-cohort story is plausible, so this is not an objection based on the agents being inherently individuated. Nor is it an objection to type-dependent relationships. The issue is narrower: once the relationship structure is homogeneous within types and welfare is the paper’s pairwise additive objective, purification removes all within-type randomization. The continuous action space in the paper was already present; continuizing the population adds only coefficients.
A stronger proposed mirror could allow members of one type to interact with one another, rather than declaring them neutral. Then a type’s mass might genuinely split between \(0\) and \(1\), producing terms such as \(2p_t(1-p_t)\). But this introduces looped, within-cohort relationship data absent from the paper’s MAXCUT reduction and changes the quotient problem from the stated theorem. It may be a worthwhile new nonatomic distance game, but it is no longer a clean mirror of Theorem 6(ii). Likewise, allowing continuously varying relationship traits or a graphon abandons the paper’s finite-type high-multiplicity regime; adding congestion, capacity, or egalitarian objectives creates a new model rather than continuizing its welfare problem.
That said, the negative case is ultimately weak. The finite-type cohort interpretation is sensible, and ChoCo expressly permits Class B mirrors whose hardness survives in the type structure. Under the programme’s stated standard, the weighted-MAXCUT quotient probably is enough to count as a valid, if unambitious, continuous mirror. I therefore cannot honestly sustain the universal claim that no worthwhile mirror exists; the defensible criticism is only that the particular mirror offered is computationally degenerate and should not be advertised as a genuinely continuous welfare problem.
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.