{"id":"3e27c5ba-c60b-4eb8-81d5-a6be918330d0","arxiv_id":"2501.00976","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For friends-appreciation hedonic games, there exists a non-obviously manipulable mechanism that computes an optimal partition, and a polynomial-time one achieving a (4+o(1))-approximation.","lead":"The paper studies whether a relaxed form of manipulation resistance, non-obvious manipulability, can make hedonic game mechanisms both honest and efficient. It shows an optimal mechanism can be non-obviously manipulable for friends-appreciation preferences, but the optimum is NP-hard, so it builds a polynomial-time mechanism with a (4+o(1))-approximation.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"M2 NOM worst-case construction omits X-to-i edges, so P2 can be disconnected for false declarations and the claimed outcome is not established.","rationale":"The paper's headline result is Theorem 3, and the NOM proof is the part that most directly supports it. The reader's weakest assumption correctly locates the fragile step: the constructed worst-case instance must force i into the coalition P2 = E_i ∪ X ∪ {i} for every possible declaration d_i, but the specified d_-i does not connect X to i unless d_i happens to include edges i->x. I verified the surrounding argument: if one adds X ⊆ F^{-1}_i, the swap gain remains positive for all d_i (the 2(|A|-1) term dominates), and i indeed ends up in P2; without that edge set, the proof as written fails to derive its claimed conclusion. This is not a fatal flaw in the theorem itself, but it is a genuine gap in the proof, exactly matching the reader's conditional verdict. The approximation side was also checked: Lemma 7 ignores the possibility that ImproveSW's move step changes the set sizes for odd n, but this appears fixable with essentially the same constant; it is secondary to the NOM gap. I therefore keep the reader's CONDITIONAL verdict unchanged and recommend the concrete small-instance verification plus the explicit edge-set repair as the settling check.","tokens_in":24568,"tokens_out":47107,"duration_ms":437089,"concrete_test":"First, repair the construction by setting all agents in E_i ∪ X to consider i a friend (i.e., E_i ∪ X ⊆ F^{-1}_i in d_-i) and re-verify the greedy and ImproveSW steps: the swap i <-> j should then strictly increase the number of positive edges for every d_i, and the final coalition of i should be exactly P2. Second, run a brute-force verification of Theorem 3 on all FA instances with n ≤ 6: enumerate all truthful types t_i, all false declarations d_i, all d_-i, and execute M2 with a fixed deterministic tie-breaking, checking both NOM conditions. If a violation appears, the theorem is false; if none appears, the identified gap is a presentation issue rather than a substantive error.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The pivotal step is the proof of Condition 2 in Theorem 3 for the case e_i < ceil(n/2)-1. The proof fixes X ⊂ F_i with |X| = floor(n/2)-1-e_i, sets A = N \\ (E_i ∪ X ∪ {i}), and chooses d_-i so that A is a bidirectional clique and 'all agents in E_i consider i a friend'. It then asserts that P2 = E_i ∪ X ∪ {i} is weakly connected and that, after the greedy initialization and ImproveSW, i is placed in exactly this coalition 'regardless of the declaration of i'. The construction gives no edges between X and i: agents in X are not said to consider i a friend, and i's declaration d_i may or may not include edges i->x for x ∈ X. For a false d_i that does not list X as friends, P2 has no edge connecting X to E_i ∪ {i}, so P2 is not weakly connected. The mechanism's final partition would then put i in a proper sub-coalition (containing E_i and at most a subset of X), not in the full P2 claimed in the proof. Hence the proof does not establish the asserted worst-case utility profile uniformly over all d_i. The gap is likely repairable by also requiring X ⊆ F^{-1}_i in d_-i, or by observing that any sub-coalition of P2 gives i no higher utility, but as written the argument is incomplete.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24811,"tokens_out":23406,"duration_ms":224211,"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":[{"comment":"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":"Section 5, proof of Theorem 3, Condition 2, case e_i < ceil(n/2)-1"},{"comment":"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.","section":"Section 3, proof of Lemma 6, item 2"}],"minor_comments":[{"comment":"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.","section":"Abstract and Introduction"},{"comment":"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":"Appendix A.4, Algorithm 1, Move phase"},{"comment":"The word 'weekly' should be 'weakly' throughout, for example in 'weekly connected neighborhood' and related phrases.","section":"Section 2.1, Definition 3 and elsewhere"},{"comment":"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.","section":"Section 3, proof of Lemma 6"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for a conference or journal in algorithmic game theory, and the results are likely correct. The main risk is the repair of the NOM proof for M2 in Theorem 3; the construction and swap analysis need to be made consistent for arbitrary misreports. The self-citation of [18] is legitimate given the direct dependency. The abstract's omission of the randomized prior result should be corrected in revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nNow 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.\n\nThere 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.\n\nOverall, 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.","headline":"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.","tokens_in":25333,"tokens_out":4031,"would_cite":true,"duration_ms":39368,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A12","68W25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["non-obvious manipulability","hedonic games","friends appreciation preferences","strategyproofness","social welfare approximation","coalition formation","mechanism design","NP-hardness"],"falsifier":"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.","tokens_in":24354,"feed_emoji":"🧩","tokens_out":7181,"duration_ms":71959,"temperature":0.7,"pith_summary":"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.","feed_headline":"Manipulation-resistant mechanism hits a 4-approximation in friend games","feed_subtitle":"Optimal outcomes are NP-hard, yet a poly-time mechanism defuses obvious lies and stays within a constant of the optimum.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines friends-and-enemies preferences and studies stability and manipulation, supplying the preference model used throughout the paper.","marker":"[12]"},{"why":"Shows that strategyproof mechanisms for additively separable hedonic games cannot have bounded approximation, motivating the NOM relaxation.","marker":"[17]"},{"why":"Provides the best-known strategyproof linear-approximation mechanism and the randomized 4-approximation whose analysis M2 adapts and makes deterministic.","marker":"[18]"},{"why":"Supplies strong NP-hardness of 3-Partition, which the reduction for computing the optimum is built on.","marker":"[21]"},{"why":"Introduces non-obvious manipulability and its best-case and worst-case conditions, which the paper adopts as its manipulation-resistance notion.","marker":"[31]"}],"fun_headline_variants":["Friendship games: 4-approx that resists obvious manipulation","NP-hard optimum, but a poly-time NOM gives 4-approx","Non-obvious manipulability yields constant-factor welfare","4-approx mechanism for friend preferences, immune to lies","Friend games: a manipulation-resistant 4-approx exists"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Friendship games: 4-approx that resists obvious manipulation","NP-hard optimum, but a poly-time NOM gives 4-approx","Non-obvious manipulability yields constant-factor welfare","4-approx mechanism for friend preferences, immune to lies","Friend games: a manipulation-resistant 4-approx exists"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000265,"raw_usage":{"total_tokens":1641,"prompt_tokens":1015,"completion_tokens":626,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":631,"completion_tokens_details":{"reasoning_tokens":541}},"tokens_in":631,"tokens_out":626,"duration_ms":6917,"temperature":1.0,"reasoning_tokens":541,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:38:57.539738+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Enemies and friends i n hedonic games: Individual deviations, stability and manipulation","cited_arxiv_id":null,"evidence_quote":"Defines friends-and-enemies preferences and studies stability and manipulation, supplying the preference model used throughout the paper."},{"cited_title":"Strategyproof mech- anisms for additively separable and fractional hedonic gam es","cited_arxiv_id":null,"evidence_quote":"Shows that strategyproof mechanisms for additively separable hedonic games cannot have bounded approximation, motivating the NOM relaxation."},{"cited_title":"Strategyproof mechanisms for friends and enemies games","cited_arxiv_id":null,"evidence_quote":"Provides the best-known strategyproof linear-approximation mechanism and the randomized 4-approximation whose analysis M2 adapts and makes deterministic."},{"cited_title":"Obvious manipulation s","cited_arxiv_id":null,"evidence_quote":"Introduces non-obvious manipulability and its best-case and worst-case conditions, which the paper adopts as its manipulation-resistance notion."}],"review_version":1}