| paper | Non-obvious Manipulability in Hedonic Games with Friends Appreciation Preferences |
| authors | — |
| venue | AAMAS 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 set \(T\) of complete FA affinity types, a rational mass vector \(\mu \in \mathbb{Q}_{\geq 0}^T\) with \(\sum_t \mu_t = 1\), a directed friend relation \(F(t) \subseteq T\), a rational clone-scale parameter \(\eta > 0\), and a rational threshold \(B\), does there exist a finite typed coalition structure \(\lambda = \{(q_j,z_j)\}_j\) with \(q_j \in \mathbb{N}\), \(z_j \in \mathbb{Q}_{\geq 0}^T\), \(\sum_j q_j z_j = \mu\), and \(W_\eta(\lambda)=\sum_j q_j \sum_t z_j(t)\left(\sum_{r\in F(t)} z_j(r)-\eta \sum_{r\notin F(t)} z_j(r)\right)\ge B\), or what is the maximum \(W_\eta\)?
A typed high-multiplicity coalition-formation model with T complete affinity types, society mass μ, directed type-level friendship F, coalition-profile masses zj, multiplicities qj, and explicit welfare parameter η.
With finitely many positive-mass types, the paper's η=1/N enemy term vanishes against dense friendship terms, while preserving the sparse reduction requires identity-level types, leaving unclear whether the retained-η version is a genuine continuum limit or a new weighted clustering problem.
fatal: False
The mirror covers Theorem 2's FA optimum-computation hardness; it leaves Theorem 1's NOM existence, Theorem 3's NOM (4+o(1)) approximation, Theorem 4's EA impossibility, and the structural lemmas alone.
There is a credible mirror, but it is narrow: the paper’s FA welfare problem admits a natural high-multiplicity population model. My lead anchor is Theorem 2; Theorem 3 gives a second, more ambitious mechanism-design mirror.
Take a finite set \(T\) of complete affinity types. A type \(t\) specifies whether an agent regards every member of each type \(r\) as a friend or an enemy; thus \(F(t)\subseteq T\) is the friend set of \(t\). The society is a rational mass vector \(\mu\in\mathbb{Q}_{\ge0}^{T}\) with \(\sum_t\mu_t=1\). Mass is the fraction of a large population of otherwise indistinguishable agents. This is appropriate for large team-formation systems, university cohorts, online communities, or labour-market pools with perhaps \(10^5\) agents but only tens or hundreds of role-and-affinity types.
For a coalition containing type-masses \(z=(z_t)_{t\in T}\), define \(f_t(z)=\sum_{r\in F(t)}z_r\) and \(e_t(z)=\sum_{r\notin F(t)}z_r\). With \(\eta=1/N\), \(u_{t,\eta}(z)=f_t(z)-\eta e_t(z)\) is the normalized version of the paper’s FA utility for an \(N\)-agent clone expansion. A typed coalition structure is a finite list \(\lambda=\{(q_j,z^j)\}_{j=1}^k\), where \(q_j\) is the number of coalitions with profile \(z^j\), \(z^j\le\mu\), and \(\sum_jq_jz^j=\mu\). Its normalized utilitarian welfare is \(W_\eta(\lambda)=\sum_jq_j\sum_tz_t^j u_{t,\eta}(z^j)\). This is a partition of population mass, not a lottery over outcomes.
The resulting problem is:
FA-Welfare\(_\infty\). Given \(T,\mu,F,\eta\), and a rational threshold \(B\), decide whether there is a typed coalition structure \(\lambda\) with \(W_\eta(\lambda)\ge B\), or compute an optimal \(\lambda\).
This is a direct mirror of the paper’s Theorem 2: “For FA preferences, computing the optimum is NP-hard.” The theorem is proved in this paper, by a reduction from strongly NP-hard 3-Partition.
The high-multiplicity bridge is exact on the rational grid. If \(N\mu_t\) is integral, replace type \(t\) by \(N\mu_t\) named clones. If every \(z_t^j\) is also an integer multiple of \(1/N\), the typed coalition structure is precisely a partition of those clones, after the usual correction excluding an agent from her own coalition count. Conversely, any finite FA instance with repeated affinity signatures compresses to \((T,\mu,F)\). Thus the mirror does not replace the paper’s welfare objective by an average or probabilistic objective; it removes irrelevant names while retaining coalition membership, directed friendship, enemy penalties, and utilitarian welfare.
I would expect unrestricted FA-Welfare\(_\infty\) to be Class B: hardness should be driven by the number and compatibility structure of types, not by the fact that there are many named copies. The paper’s reduction already organizes agents into large cliques and asks whether element blocks can be balanced among coalition slots. Those blocks have an obvious high-multiplicity interpretation. The likely continuous formulation is a configuration problem over coalition profiles, with the combinatorics living in \(T\) and the number of coalition templates rather than in the population scale \(N\).
That transfer is not automatic. The paper’s reduction uses sparse, identity-specific cross-clique edges, and divisible type mass might split an element block across several coalitions, potentially destroying the 3-Partition argument. A block-symmetric reduction, or a lemma showing that the complete-friend structure makes optimal mass allocations integral at the type-block level, is still needed. I would therefore claim the continuous problem confidently, and predict Class B, but not claim that Theorem 2’s proof already establishes the prediction.
The second anchor is Theorem 3, proved here: “For FA instances, Mechanism M2 is NOM and guarantees a \((4+o(1))\)-approximation of the optimum in polynomial time.” Its continuous problem is:
NOM-FA-Approx\(_\infty\). Given a typed FA society \((T,\mu,F,\eta)\), construct a deterministic direct mechanism \(M\) that returns a typed coalition structure in time polynomial in \(\tau=|T|\), the encoding length of \(\mu,F,\eta\), and \(\log N\), such that \(W_\eta(M)\) is within \(4+O(1/N)\) of the typed optimum and the mechanism is non-obviously manipulable.
The direct typed analogue of M2 first creates two population-mass bins of size approximately \(1/2\), greedily using weak friendship degree. It then exchanges or moves equal masses between bins whenever this increases welfare, and finally outputs the weakly connected components inside the two bins as coalitions. All these operations are defined on types and mass rather than named agents.
For the strategic condition, literal individual NOM is vacuous in an atomless model: one agent’s report has zero effect on \(\mu\). The meaningful continuation is positive-mass cohort NOM. If type \(t\) reports \(r_t\), let \(\mathcal U_t(r_t)\) be the set of utilities \(u_t(z)\) attainable by positive mass of type \(t\), over all declarations of the other type cohorts. Require, for every false report \(r'_t\), that \(\sup\mathcal U_t(r_t)\ge\sup\mathcal U_t(r'_t)\) and \(\inf\mathcal U_t(r_t)\ge\inf\mathcal U_t(r'_t)\). Alternatively, one can require the stronger condition that every rational clone expansion satisfies the paper’s original individual-level NOM definition.
I expect NOM-FA-Approx\(_\infty\) to be Class A. The proof of Theorem 3 is largely an edge-counting argument: friendship counts become weighted sums such as \(\sum_{t,r}z_tz_r\), greedy degrees become type-weighted degrees, and swaps become mass transfers. The parity effects responsible for the \(o(1)\) term disappear in the continuum limit. The main algorithmic question is whether the improvement phase has a polynomial compressed implementation with exact tie handling; that is a genuine continuous-optimization question rather than a mere restatement.
These mirrors cover the FA welfare results, especially Theorems 2 and 3. I would not claim to cover Theorem 4 on EA preferences: its impossibility proof relies on an individual agent improving her worst case by changing her report, precisely the phenomenon that becomes null or requires a new cohort-level interpretation in an atomless society. Nor do I claim a mirror for every structural lemma or for the paper’s full arbitrary-identity graph model.
The weakest point is the strategic one: cohort NOM is an explicit population-level extension, not literally the paper’s notion for a single atomless individual. For the lead Theorem 2 mirror, the weaker point is the unproved hardness transfer under divisible, block-symmetric types. Those are real obligations, but neither undermines the central positive claim: FA coalition formation with repeated complete affinity types is a sensible continuous population problem, and the paper supplies both an exact welfare anchor and a plausible polynomial approximation/mechanism anchor for studying it.
The strongest case against the proposed mirrors is that the proponent has confused a typed fractional variant with a genuine continuum limit. That objection seriously damages Theorem 3, but it does not honestly defeat Theorem 2 universally.
For FA welfare, the scaling is problematic. Let \(a_{tr}=1\) when type \(t\) regards type \(r\) as a friend. In an \(N\)-clone expansion, a coalition profile \(z\) contributes, after normalization by \(N^2\),
\[ \sum_{t,r}a_{tr}z_tz_r -\frac{1}{N}\sum_{t,r}(1-a_{tr})z_tz_r +O\!\left(\frac1N\right). \]
With finitely many types of positive mass, every friendship between two types produces \(\Theta(N^2)\) friend pairs, whereas the paper’s enemy penalty is only \(\Theta(N)\). Consequently, as \(N\) grows, cutting any positive-mass friendship block is overwhelmingly worse than the enemy saving. The limiting objective simply puts each friendship-connected component together; the interesting balancing trade-off disappears.
This is exactly why the paper’s hard instances use sparse, identity-level edges. In the star example, the useful friendships are only \(O(N)\), so they can be balanced against the \(O(N)\) enemy penalty. A type-level star with a positive-mass centre has dense centre–leaf friendships, hence \(O(N^2)\) positive edges, and behaves completely differently. Theorem 2’s reduction has the same problem: its one-to-one cross-clique wiring cannot be represented by a finite type relation \(F(t)\subseteq T\). Making those edges type-symmetric densifies them; preserving them requires either \(\Theta(N)\) types or vanishing-mass types, which abandons the intended high-multiplicity regime.
The proponent can retain a fixed \(\eta>0\), or replace the paper’s \(-1/N\) by a fixed enemy weight. But then the problem is no longer the continuum limit of the paper’s FA welfare: it is a new signed, weighted clustering problem. That may be worthwhile, but it cannot be offered as an established mirror of Theorem 2. Likewise, treating \(\eta=1/N\) as an additional input means that the same distribution \(\mu\) has different welfare problems depending on the arbitrary clone scale.
Theorem 3 has a more fundamental difficulty. Individual NOM disappears in an atomless population. One agent’s report has measure zero, so a mechanism based only on \(\mu\) cannot observe the deviation; the truthful and false-report outcome sets coincide and NOM becomes vacuous. The proposed “cohort NOM” changes the strategic unit from an individual to an entire positive-mass type. That is a new incentive notion, not a continuation of the paper’s definition. It also lacks a canonical utility: a type’s mass may be split between coalitions, so should NOM compare a representative member’s utility, average utility, worst-member utility, or something else?
The algorithmic part of M2 does not transfer by replacing counts with masses either. Its polynomial termination relies on unit swaps and an integer friendship potential bounded by \(n(n-1)\). With divisible mass, improving transfers can be arbitrarily small, and the potential is real-valued; a continuous local-improvement process has no corresponding finite termination bound. Forbidding type splitting makes types weighted indivisible players, while allowing it requires a new optimization and termination argument. The NOM proof’s witnesses—subsets of individual friends and enemies, and a particular agent swapped with another—also have no direct cohort analogue.
So the negative case can reject the proposed Theorem 3 mirror and show that the stated transfer of Theorem 2’s reduction is unsupported. But it cannot honestly establish the requested universal claim. A fixed-\(\eta\), block-symmetric FA welfare problem is still a sensible high-multiplicity computational object, even if it is a new variant and even if its hardness status is unknown. Theorem 2 therefore remains a credible surviving anchor; claiming that no worthwhile continuous mirror exists would overreach the evidence.
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.