Non-obvious Manipulability in Hedonic Games with Friends Appreciation Preferences

Giovanna Varricchio; Maria Fomenko; Michele Flammini

REVIEW 2 major objections 4 minor 35 references

Non-obvious Manipulability in Hedonic Games with Friends Appreciation Preferences

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read In hedonic games with friends-appreciation preferences, the paper shows that an optimal mechanism can be non-obviously manipulable, yet computing the optimum is NP-hard, and gives a polynomial-time NOM mechanism with a…

desk verdict A genuine new direction for NOM in hedonic games, with a likely-correct optimality/NP-hardness pair and a plausible deterministic 4-approximation; the M2 NOM proof has a real but likely patchable gap, and the prior-art claims need fixing. read the letter →

arxiv 2501.00976 v1 pith:U3ATX6DX submitted 2025-01-01 cs.GT

Michele Flammini , Maria Fomenko , Giovanna Varricchio This is my paper · ORCID

classification cs.GT MSC 91A1268W25

keywords non-obviousmanipulabilityhedonicgamesfriendsappreciationpreferencesstrategyproofnesssocialwelfareapproximationcoalitionformationmechanismdesignNP-hardness

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks what a coalition-formation mechanism can guarantee when agents may lie about whom they consider friends, but only in ways that are not 'obvious'—meaning a liar cannot improve either her best-case or her worst-case outcome from the outside. For hedonic games with friends-appreciation preferences, where agents prefer coalitions with more friends and, in ties, fewer enemies, the authors prove that an optimal mechanism can still be non-obviously manipulable, although finding the optimum is NP-hard. The central positive result is a polynomial-time mechanism, called M2, that is non-obviously manipulable and approximates the maximum social welfare within a factor of (4+o(1)); before this, strategyproof mechanisms for this setting were only known to achieve a linear approximation. The paper also shows that the enemy-aversion counterpart behaves differently: there, no mechanism that always returns an optimal outcome can be non-obviously manipulable.

What carries the argument

The machinery has three parts. The friendship graph represents each instance as a directed graph with an edge i→j when j is a friend of i, and weak connectivity in this graph determines which agents can end up in the same coalition. Generalized octopus graphs—a head clique connected to a center, with tentacles that can only connect through the center—are the worst-case structures used to force an agent into her best or worst possible coalition, making the NOM proof tractable. M2's engine is a balanced greedy 2-partition followed by ImproveSW, a local-search routine that repeatedly swaps agents across the two sides, or moves one agent, whenever the swap raises social welfare; the key lemma lower-bounds the number of friendships that survive inside coalitions by f·(1/2−o(1)), which yields the (4+o(1)) approximation ratio.

What would settle it

Construct the instance used in the proof of Condition 2 for e_i < ceil(n/2)-1: let A = N \ (E_i ∪ X ∪ {i}) be a bidirectional clique, let all agents in E_i declare i as a friend, and give no declared edges from X to i; run the greedy 2-partition and ImproveSW. If the resulting P2 = E_i ∪ X ∪ {i} is not weakly connected, then i may not be placed with all her enemies, and the asserted worst-case utility profile would not occur; checking this instance, and the analogous one for every possible declaration of i, settles whether the proof's forcing step holds.

Watch

Extended reading notes

Core claim

The paper's central claim is that replacing strategyproofness with non-obvious manipulability unlocks constant-factor welfare guarantees for friends-appreciation preferences. It first exhibits an optimal NOM mechanism, M1, which returns an optimum partition with the fewest coalitions, and proves M1 is NOM by characterizing, for each agent, the best and worst coalitions she can land in when telling the truth. Since computing the optimum is NP-hard, the paper then designs M2: it builds a greedy 2-partition of the agents, seeded by the most connected agents and grown along weak connectivity, improves the two sides by local swaps and moves that strictly raise social welfare, and finally outputs weakly connected components. The authors prove M2 is NOM and that the output retains enough friendships to give a (4+o(1))-approximation, with a matching instance showing the ratio stays close to 4. For enemies-aversion preferences, the paper proves that no mechanism that always computes the optimum can be NOM.

Load-bearing premise

In proving the worst-case half of NOM, the paper relies on a constructed instance in which the set E_i ∪ X ∪ {i} is weakly connected from the declared edges, but the construction as written only gives edges from enemies E_i to i; whether agents in X are connected to the rest depends on i's own declaration, so the forced placement of i in that coalition is the load-bearing premise that needs the declared edges to make it hold.

Editorial extensions

If this is right

If M2 is correct, it is the first deterministic constant-factor approximation for friends-appreciation preferences under a manipulation-resistance condition, improving on the best-known strategyproof mechanism's linear approximation.
Optimality and NOM are compatible for friends-appreciation preferences through M1, but because the optimum is NP-hard, the practical route is approximation; the enemies-aversion result shows this compatibility does not carry over to the counterpart preference class.
The mechanism's welfare guarantee depends only on the number of friendships that survive inside coalitions, so the same balancing and local-search analysis can be applied to other settings encoded by a friendship graph with comparable weak-connectivity structure.
For a designer who only needs to deter obvious manipulations, the paper shows that friends-appreciation instances admit a polynomial-time mechanism with a constant welfare ratio, which strategyproofness alone had ruled out.
The NP-hardness reduction from 3-Partition means the optimal NOM mechanism M1 is a purely existential result, and any implementation of optimal welfare for friends-appreciation preferences would need additional assumptions or exponential time.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The greedy-seeding plus local-swap template in M2 is a natural candidate for other hedonic classes, such as friends-and-neutrals preferences or the group activity selection problem, where strategyproof impossibility drives the search for weaker manipulation-resistance notions.
The enemies-aversion impossibility for optimal NOM mechanisms suggests a more general boundary: NOM is not automatically compatible with optimality, and the asymmetry between friends-appreciation and enemies-aversion may stem from the fact that in the first class the worst outcome can still be controlled by a forced coalition, while in the second a singleton is always available.
A testable extension within the paper's own framework is to run M2 on random small friends-appreciation instances and compare its social welfare to the true optimum and to the randomized 4-approximation baseline, to see whether the deterministic ratio is empirically closer to 4−o(1) or to a smaller constant.
The proof that an agent with few enemies cannot improve her worst case depends on a constructed declaration profile that forces her into a specific coalition; a reader who wants to verify the argument can re-run the construction with the declared edges and check whether that coalition is indeed weakly connected for every possible declaration of the agent.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: this paper is worth engaging seriously. It brings non-obvious manipulability into hedonic games for the first time, shows an optimal NOM mechanism exists even though optimality is not strategyproof, proves computing the optimum is NP-hard, and gives a deterministic (4+o(1))-approximation NOM mechanism for FA preferences. Those are real contributions, not a routine transposition of NOM from voting or assignment.

The optimal-mechanism section is the cleanest part. The octopus-graph lemmas give a sharp worst-case characterization, and the argument that M1 is NOM is clear once you accept Lemma 6. The NP-hardness reduction from 3-Partition looks standard and the auxiliary lemmas in the appendix support the claimed structure of the optimum. The approximation mechanism M2 is also well conceived: greedy 2-partition, local swaps to increase friendships, then weakly connected components. Lemma 7, giving f_pi >= (n-2)/(2n-1) f, is the right engine, and the lower-bound construction in Appendix B shows the 4 is not an artifact.

Now the soft spots. The proof of Theorem 3, Condition 2, in the case ei < ceil(n/2)-1 has a genuine gap. The constructed d_-i makes A a bidirectional clique and makes agents in Ei point to i, but it says nothing about X or A pointing to i, and nothing connects X to the rest of P2. For a false d_i that does not list X as friends, P2 = Ei ∪ X ∪ {i} need not be weakly connected, so i may not end up in that coalition at all. The claim δ(i)=n-1 also does not follow for arbitrary d_i under the stated construction. This is likely repairable by strengthening d_-i (e.g., make every agent point to i and make the X part connected to the rest), but as written the proof does not establish the worst-case bound uniformly over all false declarations.

There is also a smaller but real misstatement: the abstract and introduction say the best strategyproof approximation is linear, ignoring the randomized constant-factor SP mechanism from [18]. Section 5 itself cites RandMech, so the paper contradicts itself. Easy fix, but it should be corrected.

Overall, the central theorems are probably correct, the direction is novel, and the approximation result improves the state of the art. The flaws are patchable without changing the architecture. This deserves a serious referee; I'd send it to review and ask for a revised proof of Theorem 3's Condition 2 plus a corrected prior-art statement.

Referee Report

2 major / 4 minor

Summary. The paper studies non-obvious manipulability (NOM) in hedonic games with Friends Appreciation (FA) preferences. It proves that an optimal mechanism returning a welfare-maximizing partition with fewest coalitions is NOM, that computing an optimal partition is NP-hard, and that for FA a deterministic polynomial-time mechanism M2 that is NOM achieves a (4+o(1))-approximation of the optimal social welfare. It also shows that for Enemies Aversion preferences no mechanism that always outputs a social optimum can be NOM. The main algorithmic idea is a greedy balanced two-partition refined by local swaps and moves, followed by splitting each side into weakly connected components.

Significance. If the proofs are repaired as indicated, the paper would establish the first deterministic constant-factor approximation for FA under a manipulation-resistance requirement, improving on the linear deterministic strategyproof guarantee while remaining polynomial-time. The NOM notion is relatively new in this setting, and the paper gives a clean demonstration of its power in hedonic games. The explicit lower-bound instance showing that M2 does not beat 4-o(1) is valuable, and the NP-hardness reduction is technically involved. The mechanisms are stated precisely enough to be checked, and the Appendix contains the detailed approximation analysis.

major comments (2)

[Section 5, proof of Theorem 3, Condition 2, case e_i < ceil(n/2)-1] The construction of d_-i does not imply the asserted behavior for an arbitrary misreport d_i. The proof claims delta(i)=n-1, but delta(i) counts outgoing edges chosen by i as well as incoming edges fixed by d_-i; the stated d_-i only adds incoming edges from E_i (and, if added, X), so a false d_i with no outgoing edges can make delta(i) as small as e_i, and the greedy initialization will not necessarily select i first. Moreover, P2=E_i union X union {i} is not weakly connected unless all agents in X (and possibly some in A) consider i a friend, so the statement that i is put in exactly this coalition 'regardless of the declaration of i' is not established; the swap argument also assumes simultaneously that A does not consider i a friend and that i has maximal degree. The gap appears repairable, for instance by making all agents in E_i union X consider i a friend and redoing the swap analysis, or by observing that any subcoalition of P2 containing i gives utility no larger than the truthful worst case, but as written the proof of the key NOM property is incomplete.
[Section 3, proof of Lemma 6, item 2] The text states that for T=N\(C union {i}) one has |T intersect F_i| = ceil(n/2)-e_i-f'. Since |F_i|=n-1-e_i, the correct value is |T intersect F_i| = n-1-e_i-f'. With the printed expression the subsequent inequality cannot yield the claimed contradiction; replacing the expression by n-1-e_i-f' gives the intended bound and a valid contradiction. Because Theorem 1 relies on Lemma 6, this must be fixed, even though it appears to be a typographical error.

minor comments (4)

[Abstract and Introduction] The phrase 'best-known approximation to the optimum subject to strategyproofness is linear' should be qualified as 'deterministic strategyproof', since [18] already contains a randomized mechanism that is strategyproof in expectation with a constant approximation ratio; as written the sentence is misleading.
[Appendix A.4, Algorithm 1, Move phase] The assignments 'Y <- X\{i}; X <- Y union {i}' are inverted; the intended update is X <- X\{i} and Y <- Y union {i}. In the printed form the move does not move i and discards the old Y.
[Section 2.1, Definition 3 and elsewhere] The word 'weekly' should be 'weakly' throughout, for example in 'weekly connected neighborhood' and related phrases.
[Section 3, proof of Lemma 6] The parenthetical remark 'We notice that, Lemma 4 the last inequality should be ≥; however...' is an informal editorial note; the strictness argument should be integrated into the proof or stated as a formal lemma preceding it.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation found: the NOM and approximation proofs are self-contained; self-citations to [18] are contextual and not load-bearing.

full rationale

The paper's central claims are not circular. The NOM proofs for M1 and M2 are built from explicit constructions of other agents' declarations d_-i and directly compare the truthful and misreported best/worst utility outcomes; no fitted parameter is renamed as a prediction and no equation reduces to its own input by construction. M2's approximation guarantee rests on Lemma 7, which derives a lower bound on the number of intra-coalition friendships from the termination conditions of ImproveSW, and on the case analysis in the appendix; the RandMech citation from [18] is used as inspiration and as a comparison baseline, but the deterministic M2 analysis is carried out in the paper itself. Self-citations to [17,18] for valuation encodings and previous strategyproofness results are contextual rather than load-bearing. A separate correctness concern, noted clearly but not a circularity, is that in the proof of Condition 2 of Theorem 3 for e_i < ceil(n/2)-1 the construction specifies A as a bidirectional clique and states that agents in E_i consider i a friend, yet it does not explicitly add X-to-i edges before asserting that P2 = E_i ∪ X ∪ {i} is weakly connected. This is an under-specified case that appears repairable, but even if this gap were fatal it would be a soundness issue, not a circularity, because the claimed outcome is not equivalent to the construction's inputs. Overall, the derivation chain is self-contained; hence the low circularity score.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper's contributions are algorithmic and complexity-theoretic; no ad hoc numbers are fitted to data. The only postulates are standard definitions and the FA encoding from earlier work.

assumptions (4)

domain assumption FA preferences can be encoded in ASHGs with values 1 and -1/n (from prior work, Section 2)
This encoding makes the utility comparisons match the lexicographic friends-first, then fewer-enemies rule; it is used in Lemma 1 and throughout.
domain assumption Non-obvious manipulability definition from Troyan and Morrill (2020) is the operative incentive criterion
All mechanisms are evaluated against this definition; the results are relative to it.
standard math 3-Partition is strongly NP-hard (standard result)
Used in the hardness reduction of Theorem 2.
standard math The social welfare formula from Lemma 1 is correct
It is derived from the ASHG encoding and used for all SW calculations.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Non-obvious Manipulability in Hedonic Games with Friends Appreciation Preferences." pith.science (2026). https://pith.science/paper/U3ATX6DX

@misc{pith2026250100976,
  author       = {Pith},
  title        = {Pith review of: Non-obvious Manipulability in Hedonic Games with Friends Appreciation Preferences},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U3ATX6DX}},
  note         = {Machine review of arXiv:2501.00976}
}

abstract

In this paper, we study non-obvious manipulability (NOM), a relaxed form of strategyproofness, in the context of Hedonic Games (HGs) with Friends Appreciation (FA) preferences. In HGs, the aim is to partition agents into coalitions according to their preferences which solely depend on the coalition they are assigned to. Under FA preferences, agents consider any other agent either a friend or an enemy, preferring coalitions with more friends and, in case of ties, the ones with fewer enemies. Our goal is to design mechanisms that prevent manipulations while optimizing social welfare. Prior research established that computing a welfare maximizing (optimum) partition for FA preferences is not strategyproof, and the best-known approximation to the optimum subject to strategyproofness is linear in the number of agents. In this work, we explore NOM to improve approximation results. We first prove the existence of a NOM mechanism that always outputs the optimum; however, we also demonstrate that the computation of an optimal partition is NP-hard. To address this complexity, we focus on approximation mechanisms and propose a NOM mechanism guaranteeing a $(4+o(1))$-approximation in polynomial time. Finally, we briefly discuss NOM in the case of Enemies Aversion (EA) preferences, the counterpart of FA, where agents give priority to coalitions with fewer enemies and show that no mechanism computing the optimum can be NOM.

Figures

Figures reproduced from arXiv: 2501.00976 by the authors.

**Figure 1.** A FA instance and the corresponding Gf . Solid (resp. dashed) edges represent friend (resp. enemy) relations. Example 1. Let us describe a simple instance with friends appreciation preferences: Let N = {1, 2, 3} be the set of agents, and let F1 = {2}, F2 = {3}, F3 = {2} and E1 = {3}, E2 = {1}, E3 = {1} be the agents’ sets of friends and enemies, respectively. This instance is depicted in Figure 1a, where a directed … view at source ↗

**Figure 2.** Octopus graph structures having center i. Undirected edges represent bidirectional edges in Gf . • for each j ∈ H, {j, i} ∈ F; • for each j ∈ N \ i and k ∈ N \ ({i} ∪ H), none of {j, k}, {k, j}, {k, i} belongs to F while {i, j} may belong to F. A picture of an i-centered octopus graph is given in Figure 2a. Lemma 3. Let Gf be an i-centered octopus graph with head H. If |H| ≥ n 2 , there exists a unique optimum c… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 34 canonical work pages

[18]

Strategyproof mechanisms for friends and enemies games

Michele Flammini, Bojana Kodric, and Giovanna Varricc hio. Strategyproof mechanisms for friends and enemies games. Artif. Intell. , 302:103610, 2022

work page 2022
[1]

Truthful allocation mechanisms without payments: Charact erization and implications on fair- ness

Georgios Amanatidis, Georgios Birmpas, George Christo doulou, and Evangelos Markakis. Truthful allocation mechanisms without payments: Charact erization and implications on fair- ness. In Proceedings of the 2017 ACM Conference on Economics and Computa tion, pages 545–562, 2017

work page 2017
[2]

Pareto o ptimality in coalition formation

Haris Aziz, Felix Brandt, and Paul Harrenstein. Pareto o ptimality in coalition formation. Games and Economic Behavior , 82:562–581, 2013

work page 2013
[3]

Computi ng desirable partitions in additively separable hedonic games

Haris Aziz, Felix Brandt, and Hans Georg Seedig. Computi ng desirable partitions in additively separable hedonic games. Artiﬁcial Intelligence , 195:316–334, 2013

work page 2013
[4]

Obvious manipulability of voting rules

Haris Aziz and Alexander Lam. Obvious manipulability of voting rules. In Dimitris Fotakis and David R ´ ıos Insua, editors, Algorithmic Decision Theory - 7th International Conference, ADT 2021, Toulouse, France, November 3-5, 2021, Proceeding s, volume 13023 of Lecture Notes in Computer Science , pages 179–193. Springer, 2021

work page 2021
[5]

Core in a simple coalition forma- tion game

Suryapratim Banerjee, Hideo Konishi, and Tayfun S¨ onme z. Core in a simple coalition forma- tion game. Social Choice and Welfare , 18(1):135–153, 2001

work page 2001
[6]

Unknown agents in friends oriented hedonic games: Stability and complexity

Nathana¨ el Barrot, Kazunori Ota, Yuko Sakurai, and Makoto Yokoo. Unknown agents in friends oriented hedonic games: Stability and complexity. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence , volume 33, pages 1756–1763, 2019

work page 2019
[7]

Noncooperative formation of coalitions in hedonic games

Francis Bloch and Eﬀrosyni Diamantoudi. Noncooperative formation of coalitions in hedonic games. International Journal of Game Theory , 40(2):263–280, 2011

work page 2011

Show all 35 references

[8]

Anna Bogomolnaia and Matthew O. Jackson. The stability o f hedonic coalition structures. Games and Economic Behavior , 38(2):201–230, 2002

2002
[9]

Proving the incompatibility of eﬃciency and strategyproofness via smt solving

Florian Brandl, Felix Brandt, Manuel Eberl, and Christi an Geist. Proving the incompatibility of eﬃciency and strategyproofness via smt solving. Journal of the ACM (JACM) , 65(2):1–28, 2018

2018
[10]

Hedonic games with friends, enemies, and neutrals: Resolving open questions and ﬁne-gr ained complexity

Jiehua Chen, Gergely Cs´ aji, Sanjukta Roy, and Soﬁa Sim ola. Hedonic games with friends, enemies, and neutrals: Resolving open questions and ﬁne-gr ained complexity. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023, L...

2023
[11]

Simple priorities and core stability in hedonic games

Dinko Dimitrov, Peter Borm, Ruud Hendrickx, and Shao Ch in Sung. Simple priorities and core stability in hedonic games. Social Choice and Welfare , 26:421–433, 2006

2006
[12]

Enemies and friends i n hedonic games: Individual deviations, stability and manipulation

Dinko Dimitrov and Shao Chin Sung. Enemies and friends i n hedonic games: Individual deviations, stability and manipulation. SSRN Electronic Journal , 02 2004

2004
[13]

Hedonic coalitio ns: Optimality and stability

Jacques H Dreze and Joseph Greenberg. Hedonic coalitio ns: Optimality and stability. Econo- metrica: Journal of the Econometric Society , pages 987–1003, 1980

1980
[14]

Pr ice of pareto optimality in hedonic games

Edith Elkind, Angelo Fanelli, and Michele Flammini. Pr ice of pareto optimality in hedonic games. Artiﬁcial Intelligence , 288:103357, 2020. 17

2020
[15]

Hedonic coaliti on nets

Edith Elkind and Michael J Wooldridge. Hedonic coaliti on nets. In AAMAS (1), pages 417–424. Citeseer, 2009

2009
[16]

Hedonic clustering games

Moran Feldman, Liane Lewin-Eytan, and Joseph (Seﬃ) Nao r. Hedonic clustering games. ACM Trans. Parallel Comput. , 2(1):4:1–4:48, may 2015

2015
[17]

Strategyproof mech- anisms for additively separable and fractional hedonic gam es

Michele Flammini, Bojana Kodric, Gianpiero Monaco, an d Qiang Zhang. Strategyproof mech- anisms for additively separable and fractional hedonic gam es. Journal of Artiﬁcial Intelligence Research, 70:1253–1279, 2021

2021
[19]

Approximat e strategyproof mechanisms for the additively separable group activity selection problem

Michele Flammini and Giovanna Varricchio. Approximat e strategyproof mechanisms for the additively separable group activity selection problem. In Proceedings of the Thirty-First Inter- national Joint Conference on Artiﬁcial Intelligence, IJCAI 202 2, Vienna, Austria, 23-29 Jul...

2022
[20]

Computing stable outc omes in hedonic games

Martin Gairing and Rahul Savani. Computing stable outc omes in hedonic games. In Interna- tional Symposium on Algorithmic Game Theory , pages 174–185. Springer, 2010

2010
[21]

Computers and intractability , volume 174

Michael R Garey and David S Johnson. Computers and intractability , volume 174. freeman San Francisco, 1979

1979
[22]

On coalition formation games

Jana Hajdukov´ a. On coalition formation games. IM Preprints series A , (5), 2004

2004
[23]

Hedonic games with gra ph-restricted communication

Ayumi Igarashi and Edith Elkind. Hedonic games with gra ph-restricted communication. In Proceedings of the 2016 International Conference on Autonomo us Agents & Multiagent Sys- tems, pages 242–250. International Foundation for Autonomous A gents and Multiagent Sys- tems, 2016

2016
[24]

Altruistic hedonic games

Anna Maria Kerkmann, Nhan-Tam Nguyen, Anja Rey, Lisa Re y, J¨ org Rothe, Lena Schend, and Alessandra Wiechers. Altruistic hedonic games. Journal of Artiﬁcial Intelligence Research , 75:129–169, 2022

2022
[25]

Core stability and strategy-proofness in hedonic coalition formation problems with friend-orien ted preferences

Bettina-Elisabeth Klaus, Flip Klijn, and Se¸ ckin ¨Ozbilen. Core stability and strategy-proofness in hedonic coalition formation problems with friend-orien ted preferences. Available at SSRN 4677609
[26]

A general impossibility result on strategy-proof social choice hyperfunctions

Sel¸ cuk ¨Ozyurt and M Remzi Sanver. A general impossibility result on strategy-proof social choice hyperfunctions. Games and economic behavior , 66(2):880–892, 2009

2009
[27]

Fair and eﬃcient allocations without obvious manip- ulations

Alexandros Psomas and Paritosh Verma. Fair and eﬃcient allocations without obvious manip- ulations. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annua l Conference on Neural Inform...

2022
[28]

Strategy-proof coalition formation

Carmelo Rodr ´ ıguez-´Alvarez. Strategy-proof coalition formation. International Journal of Game Theory, 38:431–452, 2009. 18

2009
[29]

Borda- induced hedonic games with friends, enemies, and neutral players

J¨ org Rothe, Hilmar Schadrack, and Lena Schend. Borda- induced hedonic games with friends, enemies, and neutral players. Mathematical Social Sciences , 96:21–36, 2018

2018
[30]

(non-) obvious manipulability of rank-m inimizing mechanisms

Peter Troyan. (non-) obvious manipulability of rank-m inimizing mechanisms. Journal of Mathematical Economics, page 103015, 2024

2024
[31]

Obvious manipulation s

Peter Troyan and Thayer Morrill. Obvious manipulation s. Journal of Economic Theory , 185:104970, 2020

2020
[32]

On approximate strategyproof me chanisms for hedonic games and the group activity selection problem

Giovanna Varricchio. On approximate strategyproof me chanisms for hedonic games and the group activity selection problem. In Proceedings of IPS , volume 3585 of CEUR Workshop Proceedings. CEUR-WS.org, 2023. A Appendix A.1 Further Deﬁnitions In the viewpoint of graph representa...

2023
[33]

Therefore, c2 + 2h≤ n must hold true

If π1⁄= π3, then, c2≥ 1. Therefore, c2 + 2h≤ n must hold true. Being, h≥ ⌈ n 2 ⌉ ≥ n 2 , we can conclude c2 + 2h≥ n + 1 leading again to a contradiction. To sum up, if h≥ ⌈ n 2 ⌉ , there exists a unique social optimum consisting of the coal ition{i}∪ H and all remaining agents...
[34]

fπ = ⌈ n 2 ⌉ : n· (2n− 1) (n− 2) ( n + 1− ⌈ n 2 ⌉ − 3 + 2 ⌈ n 2 ⌉ − 2(⌈ n 2⌉−1) 2 ⌈ n 2⌉ ) = n· (2n− 1) (n− 2) ( n + 2− ⌈ n 2 ⌉ − 2 ⌈ n 2⌉ ) ≤ n· (2n− 1) (n− 2) ( n + 2− n−1 2 − 4 n−1 ) = 2n· (2n− 1)(n− 1) (n− 2)(n2 + 4n− 13) = 4− o(1)
[35]

B Lower bound for M2 In this section, we provide a FA instance where the approximation of M2 is at least 4 − o(1)

fπ = n− 2: n· (2n− 1) (n− 2) ( n + 1− n + 2− 3 + 2 ⌈ n 2 ⌉ − 2(⌈ n 2⌉−1) 2 n−2 ) = n· (2n− 1)(n− 2) (n− 2) ( 2 ⌈ n 2 ⌉ (n− 2)− 2 (⌈n 2 ⌉ − 1 ) 2) = n· (2n− 1) 2n ⌈ n 2 ⌉ − 4 ⌈ n 2 ⌉ − 2 (⌈n 2 ⌉) 2 + 4 ⌈ n 2 ⌉ − 2 = n· (2n− 1) 2 ⌈ n 2 ⌉ · ( n− ⌈ n 2 ⌉) − 2≤ n· (2n− 1) n2−1 2 − ...

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [18]

Strategyproof mechanisms for friends and enemies games

Michele Flammini, Bojana Kodric, and Giovanna Varricc hio. Strategyproof mechanisms for friends and enemies games. Artif. Intell. , 302:103610, 2022

work page 2022

[2] [1]

Truthful allocation mechanisms without payments: Charact erization and implications on fair- ness

Georgios Amanatidis, Georgios Birmpas, George Christo doulou, and Evangelos Markakis. Truthful allocation mechanisms without payments: Charact erization and implications on fair- ness. In Proceedings of the 2017 ACM Conference on Economics and Computa tion, pages 545–562, 2017

work page 2017

[3] [2]

Pareto o ptimality in coalition formation

Haris Aziz, Felix Brandt, and Paul Harrenstein. Pareto o ptimality in coalition formation. Games and Economic Behavior , 82:562–581, 2013

work page 2013

[4] [3]

Computi ng desirable partitions in additively separable hedonic games

Haris Aziz, Felix Brandt, and Hans Georg Seedig. Computi ng desirable partitions in additively separable hedonic games. Artiﬁcial Intelligence , 195:316–334, 2013

work page 2013

[5] [4]

Obvious manipulability of voting rules

Haris Aziz and Alexander Lam. Obvious manipulability of voting rules. In Dimitris Fotakis and David R ´ ıos Insua, editors, Algorithmic Decision Theory - 7th International Conference, ADT 2021, Toulouse, France, November 3-5, 2021, Proceeding s, volume 13023 of Lecture Notes in Computer Science , pages 179–193. Springer, 2021

work page 2021

[6] [5]

Core in a simple coalition forma- tion game

Suryapratim Banerjee, Hideo Konishi, and Tayfun S¨ onme z. Core in a simple coalition forma- tion game. Social Choice and Welfare , 18(1):135–153, 2001

work page 2001

[7] [6]

Unknown agents in friends oriented hedonic games: Stability and complexity

Nathana¨ el Barrot, Kazunori Ota, Yuko Sakurai, and Makoto Yokoo. Unknown agents in friends oriented hedonic games: Stability and complexity. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence , volume 33, pages 1756–1763, 2019

work page 2019

[8] [7]

Noncooperative formation of coalitions in hedonic games

Francis Bloch and Eﬀrosyni Diamantoudi. Noncooperative formation of coalitions in hedonic games. International Journal of Game Theory , 40(2):263–280, 2011

work page 2011