| paper | Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games |
| authors | Martin Bullinger, Matan Gilboa |
| venue | IJCAI 2025 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu\in\Delta(T)\), rational nonnegative valuations \(v_{t,r}\), and fixed \(B\), let \(\mathcal A_B=\{a\in\mathbb Z_{\ge0}^{T}:1\le |a|\le B\}\) and \(u_t(a)=\frac{\sum_r(a_r-\mathbf 1[r=t])v_{t,r}}{|a|}\). Decide whether there exists \(z\ge0\) with \(\sum_a a_tz_a=\mu_t\) for every \(t\), such that for every feasible challenger \(z'\ge0\) and every transport \(w_{t,a,b}\ge0\) satisfying \(\sum_b w_{t,a,b}=a_tz_a\) and \(\sum_a w_{t,a,b}=b_tz'_b\), the margin \(\sum_{t,a,b}w_{t,a,b}(\mathbf 1[u_t(b)>u_t(a)]-\mathbf 1[u_t(a)>u_t(b)])\) is at most zero.
A bounded-team high-multiplicity FHG in which role types \(t\) carry masses \(\mu_t\), \(z_a\) is the density of teams with template \(a\), and \(w\) realizes an identity-preserving reassignment between two team structures; popularity is a strict majority condition on moved agent mass.
The claimed LP collapse is not established: optimizing the challenger for fixed \(z\) is linear, but dualizing while \(z\) is variable can introduce bilinear terms such as \(y^{\mathsf T}Dz\).
fatal: False
The mirror covers the existence problems in Theorems 2 and 1, with bounded-team FHGs as the lead case and signed ASHGs as a companion. It leaves verification, arbitrary coalition sizes without \(B\), strong popularity, mixed popularity, and other hedonic classes untouched.
My strongest case is a high-multiplicity mirror of the paper’s existence problem for popular partitions, with Theorem 2 as the lead anchor.
The natural regime is a large workforce repeatedly forming small project teams. A type \(t\) is a complete role: skills, and the vector of values \(v_{t,t'}\) that the role assigns to every other role. There are \(N\) agents but only \(\tau\) role types, with type \(t\) occupying fraction \(\mu_t\) of the population. Thus \(N\) can grow while \(\tau\) stays fixed or grows much more slowly. This is a genuine high-multiplicity scenario: agents of one type are interchangeable for the purposes of coalition formation.
I would use finite coalition templates rather than macroscopic coalitions. A template is a vector \(a\in\mathbb Z_{\ge 0}^{\tau}\), where \(a_t\) is the number of type-\(t\) agents in one team. Fix a natural team-size bound \(B\), and let \(\mathcal A_B=\{a:1\leq |a|\leq B\}\). A continuous coalition structure is a vector \(z=(z_a)_{a\in\mathcal A_B}\), where \(z_a\) is the density of teams of template \(a\). Feasibility means
\[ \sum_{a\in\mathcal A_B} a_t z_a=\mu_t \]
for every type \(t\). Thus \(a_tz_a\) is the mass of type-\(t\) agents assigned to template \(a\).
This is exactly the high-multiplicity limit of the discrete problem. If \(n_t/N=\mu_t\) and \(k_a/N=z_a\), then \(k_a\) is the number of teams of template \(a\), and the feasibility equations become \(\sum_a a_tk_a=n_t\). The continuous model simply permits fractional densities of repeated teams.
For an ASHG, a type-\(t\) member of template \(a\) receives utility
\[ u^{A}_t(a)=\sum_{r\in T}\bigl(a_r-\mathbf 1[r=t]\bigr)v_{t,r}. \]
For an FHG, the utility is
\[ u^{F}_t(a)= \frac{\sum_{r\in T}\bigl(a_r-\mathbf 1[r=t]\bigr)v_{t,r}}{|a|}. \]
The subtraction removes the agent herself, exactly as in the paper. In the FHG mirror, all \(v_{t,r}\) are nonnegative, preserving the restriction in Theorem 2.
Popularity must compare the same agents under two structures. If \(z\) is the status quo and \(z'\) is a challenger, let \(w_{t,a,b}\) be the mass of type-\(t\) agents currently in template \(a\) who move to template \(b\). The transport must satisfy
\[ \sum_b w_{t,a,b}=a_tz_a \]
and
\[ \sum_a w_{t,a,b}=b_tz'_b. \]
The challenger’s popularity margin is
\[ M(z',w;z)= \sum_{t,a,b}w_{t,a,b} \left( \mathbf 1[u_t(b)>u_t(a)] - \mathbf 1[u_t(a)>u_t(b)] \right). \]
The status quo \(z\) is mass-popular if every feasible challenger and transport satisfy \(M(z',w;z)\leq 0\). A positive value means that more population mass strictly prefers the challenger than prefers the status quo.
The lead problem is therefore:
\[ \text{\mathrm{FHG}^{(B)}_\infty-EXISTS-MASS-POPULAR} \]
Input: a finite type set \(T\), rational type masses \(\mu\), rational nonnegative valuation matrix \(v\), and the fixed team-size bound \(B\).
Question: does there exist a feasible vector \(z\) such that no feasible \(z'\) and transport \(w\) have \(M(z',w;z)>0\)?
A solution is the mass coalition structure \(z\), not a lottery over partitions. This is recognisably the authors’ problem: the outcome is still a partition into coalitions, agents still evaluate only their own coalition, and popularity is still a head-to-head majority condition. Only individual multiplicity has been replaced by mass.
This mirrors Theorem 2, printed as “FHG-EXISTS-POPULAR is \(\Sigma^p_2\)-complete, even if valuations are nonnegative.” The theorem is proved in this paper, not cited from elsewhere. It is my strongest anchor because the nonnegativity restriction gives an especially credible repeated-role interpretation: compatibility or benefit scores between skill classes are naturally nonnegative, while fractional averaging makes coalition size consequential.
For fixed \(B\), I expect this continuous problem to be tractable, in Class A. The reason is structural rather than merely hopeful. Once \(B\) is fixed, \(\mathcal A_B\) is finite, and all comparisons \(u_t(b)>u_t(a)\) are fixed rational predicates on pairs of templates. For a fixed candidate \(z\), the largest possible challenger margin is a linear program over \(z'\) and \(w\). Linear-programming duality converts the statement “every challenger has margin at most zero” into the existence of a dual certificate. Consequently, existence of a popular \(z\) together with its no-challenger certificate can itself be expressed as one linear program.
This is precisely the kind of collapse that continuization is meant to expose: the discrete problem has an existential partition followed by a universal family of competing partitions, while the mass version turns the adversary into a flow/configuration LP. The remaining computational question is whether the exponentially many coalition templates can be priced without enumerating them. With fixed \(B\), \(|\mathcal A_B|=\binom{\tau+B}{B}\) is polynomial in \(\tau\), so the result is polynomial in the natural high-multiplicity parameters.
The companion anchor is Theorem 1, also proved in this paper: “ASHG-EXISTS-POPULAR is \(\Sigma^p_2\)-complete.” Its continuous problem is the same mass-popularity problem with the ASHG utility \(u^A_t(a)\), allowing signed valuations. I would call it
\[ \text{\mathrm{ASHG}^{(B)}_\infty-EXISTS-MASS-POPULAR}. \]
The input and question are identical except that valuations may be negative. The expected classification is again Class A for fixed \(B\), by the same LP-duality argument. Signed valuations are important here: restricting ASHGs to nonnegative valuations would make the grand coalition optimal for everyone, exactly as the paper observes, and would destroy the intended problem.
The two anchors should be argued separately. The FHG result is stronger for the positive case because nonnegative role compatibility is easy to motivate and the averaging operation has a direct team-quality interpretation. The ASHG result shows that the mirror is not dependent on fractional averaging: even additive coalition utility admits the same high-multiplicity formulation.
The scope is deliberately limited. These mirrors cover the paper’s two main existence problems for popularity. They do not claim to cover strong popularity, mixed popularity, arbitrary hedonic preferences, or the cited verification results. Nor do they treat continuity of the outcome space or randomized partitions. The society alone is continuous.
The main weakness is the bounded-team assumption. The paper permits coalitions of arbitrary size, whereas this mirror takes a natural repeated-team regime in which \(B\) is fixed. An opponent can fairly say that fixing \(B\) may remove some of the combinatorics responsible for the \(\Sigma^p_2\)-hardness. There is also a genuine modelling issue: if coalitions were required to have population-scale mass, ordinary finite teams would disappear in the atomless limit. Using densities of repeated finite coalition templates is meant to avoid that defect, but it means the mirror is a high-multiplicity team-formation model, not a universal continuum limit of every hedonic game.
That weakness does not invalidate the case. The programme asks whether the problem admits a sensible high-multiplicity scenario, not whether every arbitrary instance has one. Large populations repeatedly forming bounded-size teams are a credible regime, and the mirror preserves the paper’s central object and solution concept exactly. The important follow-up is to remove the fixed \(B\): can the implicit pricing problem over all coalition templates still be solved efficiently, does hardness transfer when the number of role types grows, or does the unrestricted continuous problem become a genuinely continuum-specific hard case?
The strongest case against the proposal is that neither mirror is currently a direct continuization of the paper’s problem. The paper does provide genuine computational anchors—Theorems 1 and 2—so the “no named result” objection is unavailable. The difficulty is instead that the proposed model changes the outcome space before taking a population limit.
For Theorem 2, the bounded-team assumption is doing the essential work. Replacing \(n_t\) by \(\mu_t\) is a high-multiplicity transformation; restricting every coalition to size at most \(B\) is a new substantive restriction. The paper allows arbitrary partitions, whereas the proposed problem allows only configurations from \(\mathcal A_B\). If \(B\) is fixed, this is a bounded-size fractional team-formation problem. If \(B\) is part of the input or grows with the population, the configuration family is no longer polynomially enumerable, and the claimed tractability disappears. If coalitions instead become population-scale, finite coalitions have measure zero and the FHG denominator produces a different atomless model. Thus the attractive bounded version is not the canonical limit of the paper’s FHG problem; it is a re-modeling motivated by an external workforce story.
The claimed LP collapse is also not established. For a fixed status quo \(z\), the best challenger can indeed be found by an LP over transport variables. But existence of a popular \(z\) requires optimizing over \(z\) while requiring that this challenger LP have value at most zero. Dualizing the challenger introduces a certificate \(y\) whose feasibility condition contains a term of the form \(y^{\mathsf T}Dz\). Since both \(y\) and \(z\) are unknown, this is bilinear, not one LP. Equivalently, the challenger value is generally a piecewise-linear value function of \(z\), and its nonpositive sublevel set need not have the claimed simple formulation. This does not prove the continuous problem uninteresting—it could itself be a worthwhile hard problem—but it removes the proponent’s main reason for regarding the mirror as a ChoCo-style continuous-optimization win.
The high-multiplicity fidelity is also fragile in the actual \( \Sigma^p_2 \) construction. Clause agents and literal agents have formula-specific valuation patterns: their identities encode which literals occur in which clauses. They are not repeated instances of a small fixed collection of roles. Keeping those incidence patterns requires essentially one type per relevant formula signature, so \(\tau\) grows with the original instance and the supposed type compression gives little population multiplicity. Replicating the roles produces a legitimate new game, but not a faithful high-multiplicity version of the reduction’s combinatorial object.
The same objection defeats the ASHG mirror for Theorem 1. Signed valuations are not the problem; negative compatibility can be natural. The problem is that the reduction’s decisive agents and coalitions are indexed gadgets. In a genuine population limit, the single agents \(b_1\), \(b_2\), and the formula-specific clause and literal roles either have vanishing mass or must be replicated and reweighted. Replication changes the popularity margins and the gadget’s role in the reduction. The resulting mass game may be sensible, but it is no longer simply the paper’s ASHG existence problem with multiplicities replaced by rational masses.
The transport formulation itself is not obviously wrong: after clearing denominators, feasible transports can generally be realized by sufficiently many clones. That concession matters. It means the proposal is a plausible extension, especially for a deliberately bounded-team application. But it also means the negative case cannot honestly establish the universal claim that no worthwhile mirror exists. What it can defeat is the stronger presentation that these are direct mirrors of Theorems 1 and 2 and that fixed-team mass popularity automatically becomes an LP.
My honest verdict is therefore that the universal negative case is weak. The paper probably does admit a worthwhile high-multiplicity extension if bounded teams are explicitly treated as a new regime and the resulting popularity problem is studied without assuming tractability. The defensible negative conclusion is narrower: the proponent has not yet shown a faithful direct mirror, and their Class-A argument is invalid.
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.