| paper | Non-Obvious Manipulability in Additively Separable and Fractional Hedonic Games |
| authors | Diodato Ferraioli, Giovanna Varricchio |
| 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 4
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), and rational directed scores \(w_{t,t'}\), let \(\operatorname{OPT}_\infty(\mu,W)\) be the limit of the maximum per-capita FHG welfare over finite clone populations with \(q\mu_t\) agents of each type, as \(q\to\infty\) through valid denominators. Compute a feasible pair-mass vector \(p\), with \(p_{t,t'}\ge 0\) and \(2p_{t,t}+\sum_{t'\ne t}p_{\min(t,t'),\max(t,t')}\le\mu_t\), maximizing \(V(p)=\sum_{t<t'}(w_{t,t'}+w_{t',t})p_{t,t'}+\sum_t2w_{t,t}p_{t,t}\), such that the resulting pair-and-singleton partition has welfare \(V(p)/2\ge\operatorname{OPT}_\infty(\mu,W)/2\).
A high-multiplicity FHG with finitely many complete affinity types, mass vector \(\mu\), and type-level scores \(w_{t,t'}\). The decision variables are pair masses \(p_{t,t'}\); the objective is maximum flattened-edge weight, and unmatched mass becomes singleton coalitions. The benchmark is the limiting optimum over arbitrary finite clone-population coalition structures.
The proposed formulation must explicitly use a finite-clone limit and define microscopic pair coalitions, since a population measure alone does not determine FHG coalition cardinalities.
fatal: False
The mirror covers the FHG welfare and \(2\)-approximation clause of Theorem 4, including its flattened maximum-matching construction. It leaves aside the NOM guarantee, the ASHG \(n\)-approximation, and the paper's other mechanism and discrete-value results.
The paper has one anchor I would use, and I would stop there rather than pad the case: Theorem 4, proved in this paper. Its FHG clause states that the mechanism \(M_1\) is NOM and achieves a \(2\)-approximation to maximum utilitarian welfare. I would mirror the computational approximation part of that theorem; the NOM part needs a separate caveat below.
The relevant regime is a large population of agents drawn from a small number of affinity or role classes. For example, a large organization may repeatedly form project teams from many agents of a few skill and working-style types. A type \(t\) specifies the complete cardinal profile \(w_{t,t'}\): how an agent of type \(t\) values a member of every type \(t'\). All agents of the same type are interchangeable for the problem. The input is a finite type set \(T\), with \(|T|=\tau\), rational masses \(\mu_t\) summing to \(1\), and rational scores \(w_{t,t'}\). The intended regime is \(N\gg\tau\): many agents, relatively few complete affinity profiles.
My lead mirror is:
*Continuous FHG-\(2\)-Approximation by Mass Matching.* Given \((T,\mu,W)\), let \(\operatorname{OPT}_\infty(\mu,W)\) be the supremum of per-capita FHG welfare over all coalition structures of the corresponding atomless population. Equivalently, for rational \(\mu\), it is the high-multiplicity limit of the optimum over \(N\mu_t\) clones of each type, with
\[ \operatorname{SW}_N(\pi) = \frac{1}{N} \sum_i \frac{\sum_{j\in \pi(i)\setminus\{i\}}w_{t(i),t(j)}}{|\pi(i)|}. \]
The task is to output a mass pairing and singleton assignment whose welfare is at least \(\operatorname{OPT}_\infty(\mu,W)/2\).
For \(t\neq t'\), define the flattened pair value
\[ \widehat w_{t,t'}=w_{t,t'}+w_{t',t}, \]
and let \(\widehat w_{t,t}=2w_{t,t}\), where \(w_{t,t}\) means the value toward a distinct member of the same type. Let \(p_{t,t'}\ge 0\) be the mass of pairs consisting of types \(t,t'\). The feasible mass matchings satisfy
\[ 2p_{t,t}+\sum_{t'\neq t}p_{\min(t,t'),\max(t,t')} \le \mu_t \qquad\text{for every }t. \]
The mechanism computes a maximum-weight feasible \(p\), with objective
\[ V(p) = \sum_{t<t'}\widehat w_{t,t'}p_{t,t'} + \sum_t 2w_{t,t}p_{t,t}. \]
It then partitions the corresponding masses into pair coalitions and leaves the unmatched mass singleton. Its welfare is \(V(p)/2\). A solution is therefore the rational optimal vector \(p\), together with any mass-preserving realization of those pairings.
This is not a fractional-outcome reinterpretation of the game. Each agent still belongs to exactly one coalition; \(p\) merely aggregates a continuum of ordinary pair coalitions. If the masses and \(p\) have denominators dividing \(N\), clearing denominators realizes the solution as a finite population of clones. Conversely, every block-constant finite FHG instance maps to such a mass instance. The original benchmark remains the best arbitrary coalition partition, not merely the best matching.
The expected classification is Class A for this stated question. The LP has \(O(\tau^2)\) variables and constraints and is solvable in polynomial time in \(\tau\) and the encoding length. The proof of Theorem 4 transfers: within any coalition, its welfare is bounded by the value of a maximum matching on that coalition; summing over coalitions gives \(\operatorname{OPT}_\infty\le V(p^\star)\), while the pair partition returned by the maximum matching has welfare \(V(p^\star)/2\).
This is a plausible mirror of the authors’ problem because it preserves the distinctive FHG ingredients: cardinal pair scores, average utility within a coalition, utilitarian welfare, arbitrary coalition structures as the benchmark, and the same flattened-graph/matching construction used in \(M_1\). Continuity changes multiplicities into masses, not coalitions into divisible goods. It also exposes the high-multiplicity content of the algorithm: the computation depends on \(\tau\), not on the number \(N\) of repeated agents.
The weakest point is the NOM claim. In an atomless population, one individual has zero mass, so a unilateral report normally cannot change the aggregate matching. Individual NOM therefore becomes vacuous, while replacing it by a positive-mass “cohort manipulation” notion would be a substantive extension of the paper’s model. I would not claim that Theorem 4’s NOM clause survives directly. The honest scope is its FHG welfare and approximation theorem, plus its scale-independent matching structure.
That limitation does not erase the mirror: the paper contains a genuine computational result, and its central welfare mechanism has a clean high-multiplicity formulation. It does mean that this is a modest Class-A mirror rather than a full continuization of the paper’s strategic contribution.
The natural follow-up questions are whether the exact continuous FHG optimum admits a finite configuration LP, whether the factor \(2\) is tight in the mass model, how precisely finite-\(N\) rounding behaves, and whether a non-vacuous cohort-NOM notion can recover any part of Theorem 4’s incentive guarantee. I would not use Proposition 2 as an additional anchor because it is explicitly a restatement of cited prior work, and I would not anchor Theorems 1, 3, or 5 without first solving the atomless-individual strategic problem.
The proponent’s anchor is difficult to defeat honestly. The strongest objection is that the displayed LP is not, by itself, an atomless FHG model. FHG utility uses the cardinality \( |C| \) of an agent’s coalition. A population measure \(\mu\) does not say whether a mass of one type is partitioned into pairs, triples, or one macroscopic coalition. If \( |C| \) is replaced by coalition mass, the model changes: a pair of agents has measure zero, so the proposed \(p\)-matching is no longer an outcome of that model. If cardinality is retained, one must add a micro-coalition structure or define a limit over finite clone populations. The claimed “equivalence” therefore requires a substantive two-scale definition, not merely replacing counts by masses.
That repair is available, but it weakens the negative case. Define \(\operatorname{OPT}_\infty\) explicitly as the limit of finite FHG instances obtained by cloning each type, and interpret \(p\) as a measurable partition into ordinary finite pairs. Then the matching proof does transfer: denominator clearing realizes rational masses, parity errors vanish asymptotically, and the returned welfare is at least half of the limiting optimum. The resulting question is a legitimate high-multiplicity FHG problem.
I would still argue that this is a very modest mirror. After the repair, the proposed algorithm is simply Theorem 4’s finite maximum-matching mechanism run on a blown-up graph and compressed to type capacities. It contributes no atomless strategic semantics, no new coalition-level structure, and no new approximation argument. But that is not a decisive objection under ChoCo’s rules: high-multiplicity compression is itself allowed, even when the resulting Class-A problem is technically simple.
The NOM component does fail more fundamentally. An individual has zero mass and cannot alter the aggregate instance, so unilateral manipulation becomes vacuous. Replacing the individual by a positive-mass cohort would introduce a new strategic actor and a new notion of deviation, not continuize NOM. Yet the proponent expressly anchors only the welfare approximation clause, so this cannot defeat the anchor.
Thus the best negative case is that the proposed LP is underspecified as an atomless FHG and, once repaired, is merely a compressed high-multiplicity version of an existing matching algorithm. That is enough to reject calling it a full mirror of Theorem 4. It is not enough to sustain the requested universal conclusion: the role-type scenario is sensible, the welfare objective forgets no relevant identity, and the \(2\)-approximation has a faithful clone-limit formulation. The honest verdict is that the negative case is weak and this anchor probably survives.
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.