| paper | Strategyproof Mechanisms for Additively Separable and Fractional Hedonic Games |
| authors | M. Flammini, Bojana Kodric, G. Monaco, Qiang Zhang |
| venue | JAIR 2021 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; the guarantee \(W_{\mathrm{pair}}(x)\ge\tfrac12\mathrm{OPT}_\infty(\mu,V)\) is achievable and sharp among pair allocations. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu\) with \(\sum_t\mu_t=1\), and a rational symmetric valuation matrix \(V\), define \(\mathrm{OPT}_\infty(\mu,V)=\limsup_{N\to\infty,\;N\mu\in\mathbb{Z}^T}\mathrm{OPT}(N\mu,V)/N\), where \(\mathrm{OPT}(N\mu,V)\) is maximum FHG welfare for the corresponding clone population. Compute pair masses \(x_{\{s,t\}}\) and \(x_{tt}\), with singleton remainder, satisfying \(2x_{tt}+\sum_{s\ne t}x_{\{s,t\}}\le\mu_t\) and \(W_{\mathrm{pair}}(x)=\sum_{s<t}v_{st}x_{\{s,t\}}+\sum_t v_{tt}x_{tt}\ge\frac12\mathrm{OPT}_\infty(\mu,V)\).
A high-multiplicity symmetric FHG in which type \(t\) carries mass \(\mu_t\) and assigns symmetric value \(v_{ts}\) to type \(s\). The decision variables are masses of same-type and cross-type pairs; the objective is their normalized welfare, while the benchmark allows arbitrary finite or macroscopic coalitions through the clone-limit definition.
The finite-template description does not fully define measurable or macroscopic coalition structures or establish existence of the normalized limit \(\mathrm{OPT}_\infty\), so the clone-limit benchmark needs formal completion.
fatal: False
The mirror covers Theorem 1 and its symmetric-FHG welfare approximation, but not Theorems \(2\)–\(12\), whose individual strategyproofness arguments become vacuous or change under an atomless population.
My strongest mirror is built around Theorem 1, and I would use no second anchor. The paper does not prove a numbered NP-hardness theorem for its underlying welfare problem; it only states, citing Aziz et al. (2015), that maximum-welfare symmetric FHGs are NP-hard. Theorem 1 is therefore the paper’s clearest named computational anchor.
Theorem 1, proved in this paper, says:
For symmetric fractional hedonic games, the coalitions induced by Mechanism M1 give a \(2\)-approximation to maximum social welfare.
Mechanism M1 represents the symmetric FHG as an undirected weighted graph, adds zero-weight edges to make it complete, computes a maximum-weight matching with a fixed lexicographic tie-break, and turns every matched edge into a two-agent coalition while leaving unmatched agents singletons. The theorem asserts that the resulting welfare is at least half the welfare of the best unrestricted coalition structure. The polynomial-time matching computation is standard and cited by the authors to Dughmi and Ghosh (2010); the \(2\)-approximation proof is theirs.
The continuous mirror would be the following.
Call it Continuous Symmetric-FHG Welfare Approximation. An instance consists of:
The type is complete: two agents of type \(t\) have identical valuations toward every type. The society contains a mass \(\mu_t\) of type \(t\).
A coalition structure still consists of integral coalitions of agents. Only the population is continuous. For a finite coalition template \(a\in\mathbb Z_{\ge 0}^{\tau}\setminus\{0\}\), let \(a_t\) be the number of type-\(t\) agents in the coalition and \(q(a)=\sum_ta_t\). A type-\(t\) member receives
\[ u_t(a)= \frac{\sum_{s\ne t}a_s v_{ts}+(a_t-1)v_{tt}}{q(a)}. \]
If \(y_a\) is the mass of coalitions having template \(a\), feasibility requires
\[ \sum_a a_t y_a=\mu_t \qquad\text{for every }t. \]
The welfare of such a structure is \(\sum_a y_a\sum_ta_tu_t(a)\). Coalitions whose size grows with the population are interpreted by the corresponding limiting type-mass averages. Equivalently, the benchmark is the high-multiplicity limit of finite clone instances: replace each type \(t\) by \(N\mu_t\) identical agents, maximize finite FHG welfare, divide by \(N\), and let \(N\) grow.
The continuous problem is:
Given \((T,\mu,V)\), output a population of pair coalitions and singleton coalitions whose normalized welfare is at least half the optimum welfare over all continuous coalition structures.
The output can be represented by pair masses \(x_{st}\ge0\). Here \(x_{st}\) is the mass of type-\(s\)/type-\(t\) pairs for \(s\ne t\), and \(x_{tt}\) is the mass of pairs containing two type-\(t\) agents. The pair population is feasible precisely when
\[ 2x_{tt} +\sum_{s<t}x_{st} +\sum_{s>t}x_{ts} \le \mu_t \qquad\text{for every }t. \]
Its welfare is
\[ W_{\mathrm{pair}}(x) = \sum_{s<t}v_{st}x_{st} + \sum_t v_{tt}x_{tt}. \]
Thus the proposed algorithm solves the finite LP
\[ \max_x\; \sum_{s<t}v_{st}x_{st} + \sum_t v_{tt}x_{tt} \]
subject to those capacity constraints, and puts all unused mass into singleton coalitions.
This is genuinely the same underlying problem as Theorem 1. The benchmark still permits arbitrary coalitions; we have not replaced the welfare problem by matching. Matching is merely the restricted solution returned by the theorem’s mechanism. The continuum changes only the population representation: a large number of indistinguishable agents becomes type mass, while every unit of mass still belongs to an integral coalition template.
The natural regime is a large recurring population with few complete affinity profiles. For example, a very large social or political platform may contain millions of participants but only \(\tau=8\) or \(\tau=20\) recurring symmetric compatibility profiles. A type records the person’s valuation toward every profile, and \(\mu_t\) records the fraction of the population of that profile. This is not a claim that every friendship network has low multiplicity. It is a sensible instance regime for the same weighted-graph model: the finite graph is a blow-up of a small weighted type graph.
The expected classification is Class A for this approximation problem. The type-level matching LP has \(O(\tau^2)\) variables and constraints and is solvable in time polynomial in \(\tau\) and the input bit length. For rational \(\mu\), multiply the masses by a sufficiently large \(N\) and create \(N\mu_t\) clones of type \(t\). A feasible type-level matching becomes an ordinary matching among clones, and its normalized weight is exactly \(W_{\mathrm{pair}}(x)\). Applying Theorem 1 to every such blow-up gives
\[ W_{\mathrm{pair}}(x) \ge \frac12\,\mathrm{OPT}_N. \]
Taking the high-multiplicity limit yields
\[ W_{\mathrm{pair}}(x) \ge \frac12\,\mathrm{OPT}_\infty(\mu,V). \]
So the paper’s finite \(2\)-approximation has a natural continuous counterpart whose computation is polynomial in the number of types rather than in the number of agents.
This also gives the mirror a meaningful boundary. If every agent has a distinct valuation row, then \(\tau\) is essentially \(N\), and the construction is no longer a high-multiplicity regime; the cited NP-hardness of unrestricted symmetric FHG welfare may reappear. The interesting question is whether that hardness is driven by the number of distinct types and coalition identities, and whether it dissolves when \(N\gg\tau\). The matching approximation survives cleanly, while exact computation of \(\mathrm{OPT}_\infty\) remains a separate question.
The mirror generates several follow-ups: whether the exact continuous optimum is computable in polynomial time for fixed \(\tau\); whether the factor \(2\) can be improved in the high-multiplicity regime; whether optimal continuous structures need only bounded-size coalition templates plus a small number of macroscopic coalitions; and whether the cited discrete NP-hardness transfers when \(\tau\) grows but remains much smaller than \(N\).
The weakest point is that Theorem 1 is explicitly described by the authors as somewhat orthogonal to their main strategyproofness programme. The paper’s central results concern individual incentives, whereas an infinitesimal agent cannot change an aggregate type distribution, so ordinary individual strategyproofness becomes largely vacuous in the continuum. I would not claim that this mirror captures Theorems 2–12. It covers one named result emphatically: the paper’s welfare-maximization problem for symmetric FHGs, with the same unrestricted coalition objective and a nontrivial continuous optimization question.
I cannot honestly defeat the proponent’s only anchor. The strongest negative case is against the paper’s central strategyproofness programme, not against Theorem 1.
In an atomless society, one agent has measure zero. Changing that agent’s report cannot change an aggregate outcome determined by the type distribution, so individual strategyproofness becomes vacuous. The paper’s lower bounds all depend on a named agent’s report changing the relevant edge and forcing a comparison between instances \(I_1\) and \(I_2\). Replacing that deviation by a positive-mass misreport creates a different, collective incentive problem, not a continuous version of strategyproofness. Thus Theorems 2–12 do not have faithful mirrors without changing their subject.
Theorem 1 is different, however, and the proposed mirror survives the obvious objections. There are formal weaknesses in the presentation: a distribution \(y_a\) over finite coalition templates is not by itself a complete measurable partition of an atomless population, and the stated template system omits coalitions whose size grows with the population. The phrase “corresponding limiting type-mass averages” needs an actual definition.
Those are repairable, though. Define the continuous benchmark as the normalized limit of \(N\)-clone instances, or add the appropriate matching and macroscopic-coalition measures. For rational \(\mu\), the type-level pair variables \(x_{st}\) are exactly realizable by an ordinary matching among sufficiently many clones. Hence the finite theorem gives
\[ W_{\mathrm{match},N}\ge \frac{1}{2}\mathrm{OPT}_N \]
for every clone size \(N\), and taking the high-multiplicity limit yields the same inequality for the continuous benchmark. The objective remains unrestricted coalition welfare; matching is still only the algorithm returned by the theorem.
Nor is the proposed population regime incoherent. A large population with a small number of complete, repeated affinity profiles is precisely a blow-up of the symmetric weighted graph used in Theorem 1. The objective does not depend on individual identity once those profiles are fixed, so aggregation loses no information relevant to welfare.
Thus the honest negative verdict is limited: the paper’s main strategic-mechanism results largely evaporate under continuization, and the proponent’s first formulation needs repair. But after that repair, Theorem 1 supplies a genuine high-multiplicity computational mirror, with a type-level matching LP and nontrivial questions about the exact continuous optimum and the factor \(2\). Since one sound named mirror is enough, the universal claim that no worthwhile continuous mirror exists cannot be sustained.
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.