| paper | Topological Distance Games |
| authors | — |
| venue | AAAI 2023 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4.2
statement extracted from the paper’s text layer
Given rational masses over complete utility types, capacitated topology locations with a specified aggregate distance kernel, and a nonnegative acyclic utility matrix, decide whether there exists a feasible mass assignment \(x\) such that every type occupying a location weakly prefers it to every location with residual capacity.
A capacitated nonatomic TDG with complete utility types \(p\) of masses \(\mu_p\), location capacities \(\kappa_v\), mass variables \(x_{p,v}\), linear type-location utilities induced by the topology kernel, and feasibility as the objective: find a jump-stable assignment.
The mirror needs an explicit seat-bundle topology or aggregate kernel, especially for interactions among agents assigned to the same capacitated location, because the paper's injective unit-node model does not define this case.
fatal: False
The secure mirror covers Theorem 4.2's polynomial-time existence and construction result; Theorem 4.7 remains speculative, while Theorem 3.2 and the dynamic results in Theorems 5.1-5.4 are left uncovered.
There is a credible continuous mirror here, but it should be narrow. My lead is the paper’s structured positive result, Theorem 4.2; Theorem 4.7 supplies a second, more ambitious mirror whose complexity is genuinely open after continuization.
The right high-multiplicity setting is a large organization, hotel, or conference venue with many agents occupying a topology of offices or seats. Agents fall into a moderate number of complete utility types: two agents of type \(p\) assign exactly the same inherent utility to every type \(q\), including the same positive and negative relationships. A type has mass \(\mu_p\), representing its fraction of the population. The number of people may be \(N=M|T|\), with \(M\) large and \(|T|\) moderate. Locations have capacities, representing many interchangeable seats or offices in a location class.
Formally, let \(T\) be the type set, \(G=(V,E)\) the topology graph, and \(\kappa_v\) the capacity of location \(v\). A continuous assignment is
\[ x_{p,v}\ge 0,\qquad \sum_v x_{p,v}=\mu_p,\qquad \sum_p x_{p,v}\le \kappa_v. \]
If \(a_{pq}\) is the inherent utility of type \(p\) for type \(q\), then the utility of type \(p\) at \(v\) is
\[ U_p(v;x)=\sum_{q\in T}\sum_{w\in V} f(d_G(v,w))\,a_{pq}\,x_{q,w}, \]
with disconnected locations contributing zero. The nonatomic jump-stability condition is:
\[ x_{p,v}>0,\quad \sum_q x_{q,w}<\kappa_w \quad\Longrightarrow\quad U_p(v;x)\ge U_p(w;x). \]
Thus an infinitesimal member of a type cannot improve by moving to a location with spare capacity. This preserves the paper’s topology, directed inherent utilities, distance discounting, additive utility, and jump-stability semantics. Only the population has been continuized.
The strongest anchor is Theorem 4.2, proved in this paper rather than cited from elsewhere. It states that for every distance factor function, if utilities are nonnegative and the friendship graph is acyclic, a jump-stable assignment exists and can be computed in polynomial time.
The corresponding problem is:
Acyclic Typed Continuous TDG Stability. Given rational type masses \(\mu\), rational location capacities \(\kappa\), a topology graph \(G\), a rational distance factor, and a nonnegative type-utility matrix whose positive-support graph is acyclic, output a jump-stable mass assignment \(x\), or decide whether one exists.
This is a faithful continuous version of Theorem 4.2, and it should remain in Class A. Take a topological ordering of the type graph. When processing type \(p\), all types that \(p\) values positively have already been assigned. Therefore \(U_p(v;x)\) is already fixed for every location \(v\), and later types cannot change it. Allocate the mass of \(p\) greedily to currently available locations in nonincreasing order of \(U_p(v;x)\), splitting mass only at a tie or capacity boundary. Any location still having capacity at the end was available when \(p\) was placed, so it cannot offer \(p\) a better deviation. This is exactly Algorithm 1 with identical agents handled by mass rather than one at a time. Sorting locations for every type gives a polynomial algorithm in \(|T|+|V|\) and the input bit length.
The scenario is also plausible rather than artificial: junior and senior researchers, employees in recurring departments, or guests with recurring friendship and avoidance profiles can form a large population with an acyclic hierarchy of influence. The continuous statement—“what fraction of each role should occupy each part of the building?”—is a natural high-multiplicity version of the authors’ assignment problem.
The second anchor is Theorem 4.7, also established by the authors, although the conference paper prints only a proof sketch. It states that for reciprocal distance \(f(k)=1/k\), deciding whether a jump-stable assignment exists is NP-complete, even with a constant number of connected components and \(|V|=\Theta(n)\). The reduction is from EXACT 3-COVER; Karp’s result is cited only for the source problem.
Its continuous counterpart is:
Continuous Reciprocal-TDG Stability. Given rational type masses, capacities, arbitrary rational inherent utilities, a topology graph with a constant number of connected components, and \(f(k)=1/k\), decide whether there exists a mass assignment \(x\) satisfying the capacity constraints and the nonatomic jump-stability inequalities above.
This remains recognisably the same question: can the population be placed on the topology so that no agent wants to flee to spare capacity? The high-multiplicity scenario uses many copies of each complete utility type—element-role agents, set-role agents, and the disturber role in the reduction, with the instance-specific utility profiles included in the type definition. Thus the logical instance may have many types, but it can still have \(N=M|T|\) agents with \(M\gg |T|\). No individual is targetable; only type mass is.
I would expect this problem to be Class C unless the reduction can be strengthened to Class B. The printed NP-hardness proof does not automatically transfer, because fractional mass may realize fractional versions of the exact-cover gadget. The continuous problem is instead a complementarity problem: utilities are linear in \(x\), but stability says that every positively occupied location must maximize the relevant linear utility among all locations with spare capacity. Cyclic asymmetric relationships can make this intrinsically difficult even when the discrete exact-cover integrality disappears. A successful block-integrality or strict-gap argument would upgrade the result to hardness transfer; without one, continuum-specific hardness is the more honest expectation.
This second problem generates useful questions: do stable mass assignments always have rational witnesses; is existence in NP, \(\exists\mathbb R\), or another class; which topology restrictions restore tractability; and can the discrete and continuous versions be related by rounding when every type has large multiplicity?
I would not anchor on the dynamic results in Section 5. Population continuization does not naturally preserve the paper’s sequential identity-specific jump histories, and time continuity is outside ChoCo’s scope. Likewise, Theorem 3.2’s PLS-completeness is interesting but less clean: atomless local deviations turn the discrete local-search problem into a different equilibrium problem.
The weakest point is that capacities and nonatomic deviations are not literally the paper’s injective assignment to unit-capacity nodes. A hostile referee could call this a capacitated Wardrop extension rather than a mirror. The answer is that capacity is precisely the natural high-multiplicity encoding of interchangeable seats, and the deviation condition is the limit of an individual jump when one agent has vanishing population mass. Still, I would present Theorem 4.2 as the secure result and Theorem 4.7 as a carefully posed research question, not as an already-established hardness transfer.
The strongest negative case is against Theorem 4.7, not Theorem 4.2.
The proposed continuous version of Theorem 4.7 is not yet a genuine high-multiplicity mirror. The EXACT-3-COVER reduction distinguishes element agents, set agents, and the special disturber through instance-specific roles and incidence information. Calling these “three types” confuses broad roles with complete types in the programme’s sense. If two agents have different feasible placement roles or different incidence relations, they are not interchangeable types.
Replicating every such agent \(M\) times does not solve this. It merely pads an instance whose combinatorial information still lives in \(O(n)\) distinguished types. Conversely, if those agents are genuinely identified as common types, the exact-cover incidence structure has to disappear or be moved into the topology. Fractional mass can then be split among gadget positions, and the discrete cover argument is no longer preserved. Forcing whole masses or integral gadget occupation simply reinstates the original discrete problem. Thus Theorem 4.7 gives no established Class-C mirror: the proposed problem is either a fractional assignment game with a different combinatorics, or a padded discrete reduction whose hard information is not population multiplicity.
There is also a modelling problem with the proponent’s formulation. The paper assigns agents injectively to distinct graph nodes. Giving a node capacity \(\kappa_v>1\) permits co-location, but \(f(d(v,v))\) is not defined in the paper and co-location changes the meaning of distance-based influence. Replacing a capacitated node by many physical seats does not repair this automatically: one must specify the distances among those seats, and the aggregate variable \(x_{p,v}\) generally loses that information. The proposed object is therefore a capacitated nonatomic spatial game, not merely the paper’s population continuized.
Theorem 4.2 is harder to defeat. In a specially chosen regime—many interchangeable agents in a genuine hierarchy, with a topology whose location classes have well-defined aggregate distances—the greedy proof does lift to masses. Processing types in topological order and filling locations in descending utility order is a valid block version of Algorithm 1. A hotel or organization with repeated hierarchical roles is a plausible story, too.
The only serious negative point is that this requires extra structure on both sides: repeated complete utility types and sufficiently symmetric location classes. With the original injective topology, the graph must grow with the number of agents; with capacities, co-location semantics must be added; with arbitrary graph blow-ups, the aggregate state is no longer just type-by-location mass. But this is a modelling objection, not a decisive impossibility. Symmetric topology families can make the construction natural.
So the requested universal negative case does not honestly succeed. Theorem 4.7 can be rejected as an inadequately justified high-multiplicity anchor, but Theorem 4.2 survives as a narrow, legitimate Class-A mirror. The negative verdict should therefore be “the ambitious hardness mirror is unsupported; the tractable hierarchical mirror is real but specialized,” not “there is no worthwhile continuous mirror in any scenario.”
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.