| paper | Individual Rationality in Topological Distance Games Is Surprisingly Hard |
| authors | Argyrios Deligkas, Eduard Eiben, Dušan Knop, Šimon Schierreich |
| venue | IJCAI 2024 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given \(B\) rooms of normalized capacity \(1/B\), type masses \(\mu_i=s_i/(Bc)\), within-type coefficients \(a_i=(c-s_i)/(s_i-1)\), and cross-type utilities \(-1\), does there exist \(x_{i,r}\ge0\) with \(\sum_r x_{i,r}=\mu_i\), \(\sum_i x_{i,r}\le1/B\), and \(U_{i,r}=f(1)(a_i x_{i,r}-\sum_{j\ne i}x_{j,r})\ge0\) whenever \(x_{i,r}>0\)?
An atomless high-multiplicity blow-up of the paper’s disjoint-clique topology: finitely many complete utility types carry masses, rooms have capacities, \(x_{i,r}\) assigns type mass, and individual rationality is required almost everywhere on positive support.
The room model is a capacitated nonatomic replacement of finite cliques, and the coefficients \(a_i\) are calibrated to \(s_i\) and \(c\), so the fixed-type high-multiplicity interpretation remains narrower than the paper’s general model.
fatal: False
It mirrors Theorem 1’s unrestricted-agent NP-completeness under symmetric two-value utilities. It does not cover Theorems 2–11, the XP, FPT, and W[1] classifications, the ETH lower bound, or the path-topology dichotomies.
My lead case is a high-multiplicity mirror of the paper’s Theorem 1.
Theorem 1, proved in this paper, states that for every distance-factor function \(f\), IR-TDG is NP-complete even when utilities are symmetric and each agent uses at most two off-diagonal utility values. The reduction is from UNARY BIN PACKING, cited to Garey and Johnson. This is an unusually good anchor because its hard instances already contain large clone cohorts: the \(s_i\) agents representing one item have identical utility behaviour.
I would name the mirror Atomless Room-IR-TDG. Its scenario is a large banquet, office, or classroom allocation. There are \(B\) rooms, each with capacity \(c\), and many agents divided into utility types. A type is a complete interpersonal profile: every member of type \(i\) has the same utility toward every member of type \(j\). The mass of type \(i\) is \(\mu_i=s_i/(Bc)\), so the total population mass is \(1\). The regime is \(Bc\) agents and only \(q\) cohorts, with \(q\ll Bc\); capacities and population scale together.
Each room is a nonatomic clique: any two distinct seats in the same room have distance \(1\), while seats in different rooms have distance \(\infty\). This is the natural continuum blow-up of the disjoint-clique topology used in Theorem 1. A solution is a matrix \(x_{i,r}\ge0\), where \(x_{i,r}\) is the mass of type \(i\) placed in room \(r\), satisfying
\[ \sum_{r=1}^{B}x_{i,r}=\mu_i \qquad\text{and}\qquad \sum_i x_{i,r}\le \frac1B. \]
Because total population and total capacity are both \(1\), every room is full. For the exact utility family from Theorem 1, define
\[ a_i=\frac{c-s_i}{s_i-1}, \]
let a type-\(i\) agent receive utility \(a_i\) from another type-\(i\) agent, and utility \(-1\) from every other type. The utility of type \(i\) in room \(r\) is therefore
\[ U_{i,r} = f(1)\left( a_i x_{i,r} - \sum_{j\ne i}x_{j,r} \right). \]
The decision problem is:
Does there exist such a mass assignment \(x\) for which \(U_{i,r}\ge0\) whenever \(x_{i,r}>0\)?
The output is the matrix \(x\), together with the inequalities certifying individual rationality on its support. This is genuinely pointwise individual rationality almost everywhere, not merely non-negative average utility for each type.
This is recognisably the authors’ problem. The topology is still doing the same work, utility is still the sum of distance-weighted interpersonal utilities, and the objective is still existence of an individually rational assignment. Only the population has been made divisible and represented by type masses. The room capacities scale with the population, so this is not a fixed-resource degeneration.
In this anchored family, I expect hardness to transfer: it is a Class B mirror. Suppose \(x_{i,r}>0\). Since room \(r\) is full,
\[ \sum_j x_{j,r}=\frac1B, \]
and individual rationality implies
\[ (a_i+1)x_{i,r}\ge \frac1B, \]
hence
\[ x_{i,r}\ge \frac{s_i-1}{B(c-1)}. \]
If type \(i\) appeared in two rooms, its total mass would be at least
\[ \frac{2(s_i-1)}{B(c-1)}. \]
For \(s_i\ge2\), this is greater than \(s_i/(Bc)=\mu_i\), so a type cannot be split between two rooms. The continuous action variable permits splitting in principle, but individual rationality forbids it. Every type cohort must occupy one room.
Consequently, a feasible mass assignment induces a bin packing: put item \(s_i\) in the unique room occupied by type \(i\). Conversely, any bin packing gives a feasible mass assignment. If item \(i\) is placed wholly in one room, then
\[ \frac{U_{i,r}}{f(1)} = \frac{c-s_i}{s_i-1}\cdot\frac{s_i}{Bc} - \frac{c-s_i}{Bc} = \frac{c-s_i}{Bc(s_i-1)} \ge0. \]
Thus the continuous problem is equivalent to the UNARY BIN PACKING instance underlying Theorem 1. The hardness is not caused by named-agent identity: it survives after replacing each clone cohort by one divisible mass variable. The combinatorics lives in assigning cohesive utility types to rooms.
This also illustrates why the mirror is interesting even though it remains hard. The continuum does not automatically turn every assignment problem into a flow problem. Support conditions—whether a type is present at a location—can force indivisibility endogenously. A natural next question is whether this cohesion phenomenon can be characterized, or whether a configuration LP and a pricing oracle can solve broader continuous IR-TDG instances.
I would not claim that this mirrors the whole paper. It covers Theorem 1’s restricted NP-completeness result, not the parameterized results or the path-topology dichotomies.
The weakest point is that the mirror replaces each finite clique by a nonatomic room and therefore scales the topology’s seat supply with the population. That is an extension of the original model, though a very close one: it is precisely the high-multiplicity version of having many interchangeable seats at each topological location. The second weakness is empirical rather than mathematical: uniform type-to-type utilities are a strong abstraction. But that is exactly what a legitimate high-multiplicity regime requires. On balance, this is a convincing mirror because the continuous model is fully specified, the original authors’ IR predicate is preserved, the clone cohorts are genuine types, and their named hardness result survives for a reason that is visible in the continuous formulation itself.
The strongest negative case is that the proposed mirror quietly continuizes the topology as well as the population. The paper assigns named agents injectively to a finite graph. An atomless population cannot be assigned to that graph without either allowing co-location or replacing each finite clique by a capacitated measure space. Thus the “rooms” are not merely a distribution over agent types; they are a new capacitated-topology model. Under a strict population-only reading of ChoCo, the mirror is outside scope.
There is also a semantic weakness in the claimed high-multiplicity interpretation. The cohort indexed by \(i\) is not just a type with many copies: its utility coefficient
\[ a_i=\frac{c-s_i}{s_i-1} \]
is tuned to its own multiplicity \(s_i\) and to the room capacity \(c\). The reduction therefore does not exhibit a stable population regime in which the utility matrix is fixed while multiplicities vary. It builds a separate “private affinity clan” for every bin-packing item and calibrates that clan’s preferences to its prescribed size. If one insists that high multiplicity means fixed type parameters with variable masses, the construction is a bespoke encoding of bin packing, not a genuine continuous social model.
That criticism does not defeat the best version of the mirror, however. Private clans with strong within-clan affinity are a legitimate high-multiplicity scenario, and the room capacities can be viewed as ordinary capacities in a mass-assignment problem rather than as a second continuity operation. The finite self-exclusion issue can also be removed by choosing, for example, \(a_i=(c-s_i)/s_i\); then individual rationality still forces \(x_{i,r}\ge \mu_i\), so each type remains unsplittable. Restricted instances with every \(s_i\ge2\), or scaled 3-Partition instances, provide genuinely large cohorts.
Consequently, I cannot honestly defeat this anchor. Its construction is narrow and gadget-driven, but it is a recognizable continuous mass-assignment problem, and its equivalence to bin packing is mathematically sound. The negative case can show that the example does not establish a broad theory of continuous topological distance games; it cannot support the universal claim that no worthwhile continuous mirror exists.
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.