Non-Obvious Manipulability in Additively Separable and Fractional Hedonic Games

1 Introduction

Hedonic Games are a well-established model for describing coalition formation [Dreze and Greenberg, 1980]. In these games, agents have preferences over possible coalitions, and the goal is to compute a "good" partition of the agents, which constitutes the outcome of the game. Two approaches have been considered for the computation of these partitions: a decentralized one, in which agents autonomously choose their coalition; and a centralized one, where agents reveal their preferences to a designer who determines the outcome. While, in the first approach, it is assumed that the attained partition satisfies some form of stability against either individual or group deviation [Bloch and Diamantoudi, 2011; Feldman et al., 2015; Gairing and Savani, 2010; Bogomolnaia and Jackson, 2002; Banerjee et al., 2001; Elkind and Wooldridge, 2009; Igarashi and Elkind, 2016], in the second, it is instead necessary to design algorithms, a.k.a., mechanisms, incentivizing agents to report their real preferences [Flammini et al., 2021a; Flammini et al., 2022; Klaus et al., 2023; Dimitrov and Sung, 2004; Dimitrov et al., 2006; Rodr´ıguez- ´Alvarez, 2009; Varricchio, 2023].

In the design of these mechanisms, the goal is thus to align the scope of the designer, i.e., to compute partitions that satisfy some useful property, with the one of the agents, that is, being assigned to coalitions that they prefer. This alignment is usually achieved by requiring that the algorithm used for computing partitions satisfies a property named strategyproofness (SP). Strategyproofness ensures that an agent's best outcome, given the preferences of other agents, is obtained by truthfully reporting her own preferences. Unfortunately, strategyproofness has been proved to be often a too demanding requirement: it indeed assumes that agents are fully rational, meaning that they would be able to evaluate which report would be the best for every possible realization of the game (i.e., for every possible set of preferences expressed by other agents). In some cases, this would be computationally unaffordable due to the exponentially large set of realizations to verify. In other cases, it requires an agent to parse very complex mathematical proofs, which is not feasible for agents with a scarce mathematical background. Moreover, it has been observed that in many settings agents lack contingent reasoning [Charness and Levin, 2009; Esponda and Vespa, 2014; Ngangou´e and Weizs¨acker, 2021], i.e., they are not inclined to execute case analysis, and they make their decision by aggregating different cases.

Moreover, asking for strategyproof mechanisms against fully rational agents usually causes a very bad quality of the computed partitions. In particular, ¨Ozyurt and Sanver [2009] show that it is in general impossible to have nondictatorial strategyproof mechanisms. Similar impossibility results have also been provided in more restricted settings and specific coalitions' quality measures [Amanatidis et al., 2017; Brandl et al., 2018]. For example, Flammini et al. [2021a] proved that no strategyproof mechanism can return a bounded approximation of the optimal partition, even for games whose preferences are succinctly representable, and the partitions are evaluated with respect to the social welfare.

Hence, it would be very natural to ask whether better partitions can be achieved if one only requires that the mechanism is strategyproof against bounded rational agents or, more precisely, against agents lacking contingent reasoning skills. Recall that these agents are supposed to submit false preferences (i.e., to manipulate) only if this is convenient to them based on an aggregation of the different possible realizations. In particular, very recently, there has been a lot of attention on Non-Obvious Manipulable (NOM) mechanisms [Troyan and Morrill, 2020], that aggregate the realizations by only considering the best and worst cases. Specifically, in NOM mechanisms, an agent does not submit a false report only if: (i) the best outcome (over all possible reports of other agents) she can achieve for this report is not better than the best outcome that the agent can achieve by submitting her real preferences; and (ii) the worst outcome achievable with this report is not better than the worst outcome achievable with the true report. This choice for aggregating the possible realizations is motivated by empirical evidence from the failure of people in recognizing profitable manipulations, mainly in school choice and two-sided matching problems [Dur et al., 2018; Pathak and S¨onmez, 2008].

NOM mechanisms have been recently designed for different problems: school choice, two-sided matching, auctions, bilateral trade [Troyan and Morrill, 2020], voting [Aziz and Lam, 2021; Arribillaga and Bonifacio, 2024], fair division [Ortega and Segal-Halevi, 2022; Psomas and Verma, 2022], and single-parameter domains [Archbold et al., 2023a; Archbold et al., 2023b; Archbold et al., 2024]. For many of these, it has been shown that NOMmechanisms can produce much better outcomes than SP mechanisms. Very recently, similar results have been obtained by Flammini et al. [2025] for hedonic games with friends' appreciation preferences, a special class of additively separable hedonic games. Hence, the hope is that the same may occur also for more expressive classes of hedonic games.

Our Contribution. We focus on two well-studied subclasses of hedonic games with succinct preference representation: Fractional Hedonic Games (FHG) [Aziz et al., 2019] and Additively Separable Hedonic Games (ASHG) [Hajdukov´a, 2006]. Here, preferences over coalitions are expressed by utilities computed from the scores assigned by an agent to every other coalition member. This allows evaluating the partition's quality by using utilitarian social welfare, the sum of agents' utilities for the outcome.

We first show that, while no SP mechanism may return even a bounded approximation of the optimal social welfare [Flammini et al., 2021a], every mechanism that returns such the optimum is NOM. Unfortunately, this result does not settle the problem at all for two reasons. First, in both FHGs and ASHGs, computing the social welfare maximizing partition is a computationally hard problem [Flammini et al., 2022; Aziz et al., 2015], and hence one would be interested in evaluating the approximation of the social welfare achievable by mechanisms that are both NOM and computationally efficient. Moreover, optimal mechanisms may fail to be NOM

as soon as scores are restricted to limited intervals.

We address the first issue by proving that an efficient NOM mechanism that returns an n-approximation of the optimal social welfare in ASHGs, where n is the number of agents, and a 2-approximation in FHG exists. We stress that for ASHGs the bound is tight, as an approximation better than n cannot be computed in poly-time, unless P=NP, even if one does not care about manipulability [Flammini et al., 2022].

On the route to achieve this, we prove another result that may be of independent interest: We show that when one cares about NOM mechanisms with bounded approximation, it is without loss of generality to look at "natural" mechanisms, i.e., mechanisms that determine whether two agents must belong to the same coalition, only by considering how much they like/dislike each other (in total), regardless of the specific mutual scores. This characterization also allows us to show that, while not every optimal mechanism is NOM, there always exists an optimal mechanism that is NOM, even if scores are bounded in a continuous interval.

In turn, such a result no longer holds true as soon as we turn the attention to discrete values: for example, in [Flammini et al., 2025] it has been proven that in ASHGs, if scores are in {-n, 1}, then no optimal mechanism is NOM. In this work, we elaborate more on these settings by providing an almost full characterization of the existence of optimal NOMmechanisms for ASHGs when scores can take values in {-x, 0, 1}, with x ≥ 1. Interestingly, we show that, when x > 2n-3, every optimal mechanism is NOM, whereas no optimal mechanism is NOM for x ∈ (1, 2n-3). However, for x = 1, 2n-3, NOM is possibly compatible with optimality, delineating that there is not a clear phase transition over the values of x.

Due to space limits, we defer some proofs to the full paper.

2 Notation and Preliminaries

This section presents the notation and preliminary results.

2.1 Hedonic Games

In Hedonic Games (HGs) we are given a set of n agents, denoted by N = {1, . . . , n}, and the goal is to split them into disjoint coalitions, that is, to provide a partition π = {C1, . . . , Ck} such that ∪kh=1Ch = N. Such a partition π is also called outcome or coalition structure. We might denote by π(i) the coalition i ∈ N is assigned to in a partition π. The grand coalition refers to a partition that consists of one coalition containing all the agents; a singleton coalition refers to a coalition containing only one agent. The main characteristic of HGs is that agents have preferences over the possible outcomes that solely depend on the coalition they are assigned to and not on how the others aggregate. We denote the set of all possible coalitions of i by Ni = {C ⊆ N |i ∈ C}.

Of particular interest are HGs classes where agents express their preferences using utilities and admit succinct representation, meaning the memory used to store the necessary information to compute agents' preferences is polynomial in the instance size. In fractional (FHGs) and additively separable (ASHGs) HGs, agents report individual scores towards other agents, and the utility they derive from the coalition they are assigned to is based on the value they attribute to the other coalition members. More formally, each agent i has a weight function wi : N → R that determines the score that agent i assigns to any other participant. We always assume that wi(i) = 0 and denote wij = wi(j).

In ASHGs and FHGs, the utility that agent i derives in being in a coalition C ∈ Ni, is given by

Note that ui(C) is well-defined only if C ∈ Ni.

In general, wij can be any value in R. Nonetheless, we may also consider restrictions to specific settings. Specifically, we say that the agents' weights towards the other agents are:

• arbitrary if wij ∈ R, for all i, j ∈ N;
• non-negative if wij ∈ R≥0, for all i, j ∈ N;
• bounded if wij ∈ [-1, 1], for all i, j ∈ N;
• general duplex if wij ∈ {-x, 0, 1}, for all i, j ∈ N and x ∈ (0, ∞) (in case x = 1 we simply say duplex).

The distinction in arbitrary, non-negative, bounded, and duplex weights has been presented in [Flammini et al., 2021a]. We introduce the notion of general duplex valuations to include the well-known class of friends and enemies games [Dimitrov and Sung, 2004]. If we do not specify otherwise, we assume the values are arbitrary real numbers.

Graph Representation and Flattened Graph. ASHGs and FHGs have a very convenient representation by means of directed and weighted graphs ⃗G = (N, {wi}i∈N), where N are the vertices and a directed edge (i, j) has weight wij, denoting the value i has for agent j. We always assume the graphs to be complete: an edge exists even if its weight is 0.

Given two disjoint coalitions C1, C2 ⊆ N, we refer to the cut (C1,C2) induced in the graph ⃗G by these two coalitions, that is, Cut(C1,C2) = {(i, j), (j, i) | i ∈ C1, j ∈ C2}. The value of the cut Cut(C1,C2) is ∑i∈C1, j∈C2 (wij +wji). Moreover, we denote by δ+(i) = {j ̸= i |wij > 0} and δ-(i) = {j ̸= i |wij < 0} the set of positive and negative neighbors of i, respectively.

When focusing on the utilitarian social welfare of a partition, given a pair of agents i, j, the values wij and wji either both contribute to the social welfare or neither does. Therefore, we may consider an undirected version of ⃗G where the edge weight of an edge is given by the sum of the mutual values. More formally, we say that a weighted and undirected graph G = (N, ˆw) is the flattened graph of a directed and weighted graph ⃗G, if it has the same vertices of ⃗G and, for each pair of directed edges (i, j) and (j, i) of weights wij and wji in ⃗G, respectively, there is an undirected edge e = {i, j} of weight ˆw(e) = ˆw(i, j) = wij + wji in G. Notice that an ASHG or FHG instance is uniquely determined by the directed graph ⃗G we described above; however, different instances may have the same flattened graph G.

Proportional Graphs. Given two undirected and weighted graphs G and G′ with the same set of vertices, and having edge weights ˆw and ˆw′ , we say that G and G′ are proportional if there exists λ > 0 such that ˆw(i, j) = λ · ˆw′ (i, j)

holds true for each pair of vertices i ̸= j. Notice that proportionality is an equivalence relation over the set of weighted and undirected graphs; we write G′ ∼P G′′ to denote that the two graphs are proportional. We often slightly abuse notation, and we will simply say that two instances, namely I, I ′ , are proportional, and write I ∼P I ′ , if the flattened graphs modeling these instances are proportional. In Section 4.2, proportionality will turn out to be a useful property to characterize mechanisms resistant to obvious manipulations.

2.2 Strategyproofness andManipulability

In order to compute desirable partitions of the agents, we need to know their preferences. However, the values wij might be private information of agent i, so agents must reveal them. Let d = (d1, . . . , dn) be the vector of agents' declarations, where the declaration di contains the information revealed by agent i: by assuming direct revelation, di = {dij}j∈N\{i}, where dij represents the value that agent i declares for agent j. We denote by D the space of all possible declarations. For convenience, d-i denotes the declarations of all agents except i, and D-i is the set of all feasible d-i. Similarly, we denote by Di the space of feasible di.

We shall denote by M a mechanism and by M(d) its output upon a declaration d ∈ D of the agents. We denote by Mi(d) the coalition i is assigned to. Being our agents strategic, an agent i could possibly declare di ̸= wi, where wi contains the real values assigned by agent i, and will be henceforth also called real type. In this context, a key challenge is to design algorithms - commonly referred to as mechanisms - encouraging agents to behave truthfully, i.e., to submit a declaration di = wi where she reveals her true values towards the other agents. The most desirable and widely studied characteristic for such a kind of mechanisms is strategyproofness.

Definition 1 (Strategyproofness). AmechanismMis said to be strategyproof (SP) if for each i ∈ N, and any declaration of the other agents d-i

holds true for any possible declaration di ̸= wi of agent i.

In turn, a mechanism is said to be manipulable if there exists an agent i, a real type wi, and a declaration di ̸= wi s.t. Eq. 1 does not hold true. Such a di is called a manipulation.

Due to its demanding requirement, strategyproof mechanisms have been shown to be highly inefficient; for this reason, mechanisms satisfying milder conditions have been introduced with the scope of obtaining more efficient outcomes.

Definition 2 (Non-Obvious Manipulability). A mechanism M is said to be non-obviously manipulable (NOM) if for every i ∈ N, real type wi, and any other declaration di the following two conditions hold true:

In case there exist i, wi, and di such that one of the aforementioned conditions is violated, thenM is obviously manipulable and di is an obvious manipulation.

In other words, to determine if a mechanismM is NOM for an agent i, we need to consider the best- and the worstcase scenario for i (according to her truthful preferences) of M when i declares her true type wi and any other possible declaration di ̸= wi. In particular, neither the best nor the worst possible outcome when declaring wi can be strictly worse than the best or the worst outcome, according to her true preferences, attainable when declaring di.

Clearly, for any game class, SP ⇒ NOM. That is, SP is more demanding than NOM as it requires verifying for every declaration of the others if there exists a profitable manipulation. However, the agents might not know upfront what the others' declarations are. This is circumvented by NOM.

In order to work with non-obvious manipulability, it is necessary to understand the structure of outcomes guaranteeing such a property. We here provide a first result in this direction: a simple but still useful sufficient condition for a mechanism being NOM. A finer characterization will be given later.

To this aim, let us introduce some necessary notation. Given a mechanismM, for any di ∈ Di, let

be the set of possible outcomes if i declares di. Moreover,

is the set of possible coalitions for i if she declares di.

Proposition 1. Given a mechanism M, if for each i ∈ N and di ∈ Di, given the truthful declaration wi,

1. CoalM i (wi) = CoalM i (di) or
2. OutMi (wi) = OutMi (di),

then, M is NOM.

Proof. Suppose first that CoalM i (wi) = CoalM i (di). That is, whatever the declaration of agent i is, the set of coalitions i may end up with remains the same. Then, the best/worst outcome remains the same as well, and the conditions (1) and (2) in Definition 2 are always satisfied with the equality, and thus NOM holds true. Note that OutMi (wi) = OutMi (di) implies CoalM i (wi) = CoalM i (di), and thus the thesis follows even for the condition 2.

Proposition 1 provides two simple yet useful sufficient conditions for determining whether a mechanism is NOM.

2.3 Optimal and Approximate Solutions

Being the agents' preferences expressed by means of utilities, we can evaluate the quality of outcomes through a social welfare (SW). Specifically, let π be any outcome; the (utilitarian) SW of π is given by SW(π) = ∑i∈N ui(π(i)). We call social optimum, or simply the optimum, any outcome OPT in arg maxπ SW(π) and we denote by opt the value SW(OPT).

In the considered classes of games, computing an optimal outcome is often intractable. Therefore, we may focus on finding approximate solutions.

Let optd the value of the social optimum for the declaration d, i.e., optd = maxπ ∑i∈N ∑j∈π(i) dij for ASHG, and optd = maxπ ∑i∈N ∑j∈π(i) dij π(i) for FHG.

Figure 1: No BAPX is SP. Dashed lines represent the only BAPX partition for the given instance.

Definition 3 (Bounded approximation property (BAPX)). A mechanismM satisfies the bounded approximation property (BAPX) if

holds true for a real-valued and bounded function r(n). We denote by rM the approximation ratio of a mechanismM.

If optd = 0 the only bounded approximation mechanism is the one returning the optimum. 1

We ask our mechanisms to return solutions that guarantee a non-negative SW, since there is at least one non-negative solution (namely, each agent in a singleton), and hence also the optimum is non-negative.

A mechanism that for any input instance returns an optimum partition is called optimal.

As we already mentioned, strategyproofness turned out to be extremely inefficient in terms of approximation to the social optimum. For the sake of completeness, we include the next theorem, which is a restatement of results from [Flammini et al., 2021a].

Proposition 2. For both ASHGs and FHGs with arbitrary weights, no SP mechanism is BAPX.

Sketch. The following applies to both ASHGs and FHGs.

Assume there are two agents and the graph depicted in Figure 1a describes their truthful preferences. Any BAPX mechanism must put the agents in the same coalition. However, this outcome guarantees to agent 2 a negative utility.

In turn, if agent 2 misreports, as shown in Figure 1b, the only way to achieve BAPX in this instance is to put the agents in singletons. This guarantees to agent 2 a higher utility and shows there exists a manipulation.

Fortunately, NOM stands in contrast to this impossibility result. We will demonstrate that NOM is, in fact, compatible with optimality, and that any approximation algorithm with BAPX can be transformed into a NOM mechanism that preserves the same approximation guarantee.

3 Optimality and NOM

While strategyproofness is incompatible with any bounded approximation of the optimum (see Proposition 2), in this section, we show that non-obvious manipulability is instead compatible with optimality, at least for arbitrary weights.

Theorem 1. For both ASHGs and FHGs with arbitrary weights, any optimal mechanism is NOM.

1 In this case, we assume " 0 0 = 1".

Proof. The next arguments hold for both ASHGs and FHGs. Let us fix an agent i, and let C ∈ Ni. We next show that for any di ∈ Di there exists d-i ∈ D-i such that, in any optimal partition π of instance d = (di, d-i), it holds π(i) = C.

Since the weights range in R, for any di we can select d-i ∈ D-i in such a way that the flattened graph of the instance, G = (N, ˆw), has the weights defined as follows: ˆw(e) = 1, for all e = (j, j ′ ) with j, j ′ ∈ C, and ˆw(e) = -M, for a sufficiently large M, otherwise.

Let π be any optimal partition for such an instance, and suppose that there is j ∈ π(i) such that j ̸∈ C; then, SW(π(i) \ {j}) - SW(π(i)) < 0, for an M large enough. Being such a difference negative, it would be preferable to move j to a singleton coalition, contradicting the optimality of π. Therefore, π(i) ⊆ C.

Assume there exist two disjoint coalitions in π, C ′ ,C ′′ , both contained in C. Being π optimum, ∆ = SW(C ′ ∪C ′′ )- SW(C ′ ) - SW(C ′′ ) ≤ 0, as it must not be strictly more convenient to merge these two coalitions for the SW. However, in the case of ASHGs, ∆ measures the total weight of the cut (C ′ , C ′′ ). Being this cut made of positive edges only, we have ∆ > 0, a contradiction to the optimality of π. In FHGs, ∆ = (|C ′ ∪ C ′′ | - 1) - (|C ′ | - 1) - (|C ′′ | - 1) > 0, again a contradiction to the optimality of π.

In conclusion, for any optimal M, CoalM i (di) = Ni, for each di ∈ Di, including the truthful declaration wi of i. Therefore, the condition 1 of Proposition 1 is satisfied by any optimal mechanism, and our claim follows.

Theorem 1 poses NOM in sharp contrast with SP. Unfortunately, such a result does not hold for any class of weights as the following example shows.

Example 1. Assume weights are bounded. The following arguments apply to both ASHGs and FHGs.

Let M be an optimal mechanism that, whenever there are two agents and d12+d21 = 0, works as follows: if d12 = -1, the mechanism puts the two agents in distinct coalitions, otherwise, the two agents are put in the same coalition. Note that if d12 + d21 = 0, any partition of the two agents is optimal.

If the true type w1 of agent 1 is such that the score towards agent 2 is -x, with x < 1, then, OutM1 (w1) = {{N}, {{1}, {2}}}. In fact, whenever d21 > x (which is possible as long as x < 1) the only optimum is achieved by putting the agents in the same coalition; in turn, if d21 < x the optimum must split the agents in separate coalition.

Assume agent 1 misreports by declaring d1 where d12 = -1. In this case, OutM1 (d1) = {{{1}, {2}}}. In fact, d12+d21 ≤ 0 as d21 ≤ 1, and hence, if d12+d21 < 0 any optimal outcome will put the agents in singletons, otherwise, the mechanism will apply the tie-breaking rule described above, showing that the only possible partition is {{1}, {2}}. Therefore, this manipulation improves the worst case for 1, proving that the optimal mechanismM is not NOM.

Even though optimal mechanisms may not necessarily be NOM, in the next section, we provide a characterization of BAPX and NOMmechanisms. As a result, this will show that there always exists an optimal and NOM mechanism, both for bounded and non-negative weights.

4 BAPX and NOMMechanisms

In the previous section, we observed that while all optimal mechanisms are NOM, when weights range in R, this is not necessarily the case when weights are bounded. However, looking back to Example 1, we highlight that some strange behavior of the mechanism caused its obvious manipulability. In particular, such a mechanism may return different optimal outcomes for two proportional instances (instances having the same flattened graph).

We notice that, given any outcome π, whenever two agents i, j are in the same coalition, both wij and wji contribute to the social welfare; conversely, if they are not in the same coalition, neither wij nor wji contributes to it. For this reason, the optimality of an outcome is scale-independent, that is, if an outcome is optimum, it remains optimum for a proportional instance. Leading to the following observation.

Observation 1. In ASHGs and FHGs, proportional instances have the same optimal outcomes.

Therefore, since by Observation 1 proportional instances share the same optimal solutions, it looks reasonable that, when designing an optimal mechanism, one should care only about the flattened graph of the instance, rather than the mutual evaluations of the agents. For all these reasons, we introduce the property of scale-independence for a mechanism.

Definition 4 (Scale-Independence (SI)). AmechanismMis scale-independent (SI) if for any pair of proportional inputs, d, d′ , it returns the same outcome, that is,M(d) =M(d′ ).

SI requires the mechanism to be consistent with the flattened graph, and any graph proportional to it, meaning that the outcome should solely depend on the contribution of pairs of agents to the social welfare, rather than the individual contributions of the agents. This assumption looks quite natural, as the mutual values of a pair of agents contribute to the social welfare only if the agents are in the same coalition.

4.1 A Sufficient Condition for NOM

In Example 1, the presented optimal mechanism is not NOM and does not even satisfy SI. With the next theorem, we further emphasize the importance of considering SI mechanisms as this suffices to guarantee NOM.

Theorem 2. For both ASHGs and FHGs with arbitrary, nonnegative, or bounded weights, SI ⇒ NOM.

Sketch. The bulk of our proof is given by the following observation, the proof can be found in the full paper. If D is the space of arbitrary, bounded, or non-negative weights, then, for each i ∈ N, the following holds true:

Let M be an SI mechanism, and π = M(di, d-i) be an outcome of OutMi (di). Being M scale-independent, and given that (⋆) holds true, then, for any other d′i ∈ Di there exists d′-i ∈ D-i such that M(di, d-i) = M(d′i , d′-i ), and thus π ∈ OutMi (d′i ). This shows that for any pair of di, d′i , OutMi (di) = OutMi (d′i ). Therefore, by choosing d′i = wi, Proposition 1 proves M is NOM.

4.2 ACharacterization of BAPX and NOM

Let us now specifically focus on BAPX mechanisms. Notice that since optimal mechanisms may not be SI (see Example 1), the same holds true for BAPX mechanisms.

We next show that, for any possible approximation ratio ρ, there always exists an SI mechanism with approximation factor exactly ρ. To this end, we will exploit some interesting properties deriving from the definition of the equivalence class ∼P over game instances. In particular, we introduce a poly-time procedure which, for any pair of instances I, I ′ such that I ∼P I ′ , selects the same representative for their equivalence class. We call this procedure REPR and it works as follows: Given a game instance I, it builds the corresponding flattened graph G ∈ G n ; next, REPR transform G = (N, ˆw) into a proportional flattened graph G′ = (N, ˆw′ ) such that the maximum weight in absolute terms in G′ equals 1. This is clearly always possible by normalizing weights by a factor maxi̸=j | ˆw(i, j)|; finally, by assuming that there is a prefixed ordering of the agents, say 1, . . . , n, REPR returns an instance with agents N and weights w′′ i , for all i ∈ N, defined as follows:

We will call the instance returned by REPR(I) as the representative instance of I.

It is not hard to see that REPR(I) ∼P I, and for any pair of proportional instances I, I ′ we have REPR(I) = REPR(I ′ ). Moreover, the procedure REPR works in polynomial time.

REPR turns out to be very helpful in transforming a mechanism into an SI mechanism while maintaining the same approximation guarantee, as the following lemmas show.

Lemma 1. For any mechanism M, the mechanism M′ = M◦ REPR 2 is SI.

Lemma 2. If M is a ρ-appoximating mechanism, then, M′ = M ◦ REPR is a ρ-appoximating mechanism as well.

Lemmas 1 and 2 together with Theorem 2 show the following theorem.

Theorem 3. For any ρ ≥ 1, in ASHGs or FHGs with arbitrary, non-negative, or bounded weights, there exists a NOM and ρ-approximating mechanism if and only if there exists an SI and ρ-approximating mechanism.

Essentially, Theorem 3 allows us to focus our attention on generic ρ-approximating mechanisms. Indeed, each such algorithm can be turned into a ρ-approximating and SI mechanism, through the procedure REPR, and hence in a ρapproximating and NOM mechanism, by Theorem 2.

4.3 Approximate NOMMechanism

We recall that, in ASHGs, whenever the agents' weights are non-negative, the optimum, which consists in grouping all the agents in the same coalition, is SP. In turn, no SP mechanism has a bounded approximation ratio for arbitrary and bounded weights. Moreover, regardless of the SP or NOM

2 We denote f(g(·)) by f ◦ g(·).

requirement, no algorithm can provide an approximation in ASHG that is O(n1-ε ), for every ε > 0, even in simple cases [Flammini et al., 2022], while computing welfare maximizing partitions in FHGs is NP-hard [Aziz et al., 2015]. In what follows, we focus on determining NOM and efficient mechanisms for both arbitrary, non-negative, and bounded weights.

MechanismM1. Given an instance I, let M be a mechanism that builds the flattened graph corresponding to I, computes a maximum weighted matching on it, and creates a coalition for each matched pair of agents; unmatched agents are put in singletons. Then, we defineM1 =M◦ REPR.

Theorem 4. M1 is NOM for both ASHGs and FHGs under unbounded, non-negative, and bounded weights. Furthermore, it provides an n-approximation of opt for ASHGs and a 2-approximation for FHGs.

To show the theorem, we will make use of the following well-known fact (see e.g. Problem 16.5 of [Soifer, 2009]):

Fact 1. Let K be a clique of size k. Its edges can be partitioned into k-1, if k is even, and k, if odd, disjoint matchings.

Proof of Theorem 4. (NOM) By Lemma 1, M1 is SI; therefore, from Theorem 2, M1 is NOM for instances with arbitrary, non-negative, or bounded weights.

(Approximation) Let M be the subroutine as described in the definition of M1. We next show the approximation guarantee of M for both ASHGs and FHGs. Being M1 = M◦ REPR, by Lemma 2, this approximation guarantee is preserved inM1. Let π denote the outcome of M.

Consider an optimal partition OPT and let k be the number of its coalitions, say, C1, . . . ,Ck. Let us compute for each coalition Ch a maximum matching Mh whose edges are in the subgraph by considering only the vertices in Ch, and let vh be the value of this matching (the sum of its edges weights). Let us now consider a coalition in the optimum Ch of size |Ch| = ch. By Fact 1, the edges of Ch can be partitioned into either ch or ch - 1 disjoint matchings. Each of these matchings has a value of at most vh, due to the maximality of Mh. Therefore, ∑i,j∈Ch wij ≤ ch · vh ≤ n · vh.

Consider now the maximum matching M ∗ computed by M, and let us denote by v∗ its total value (the sum of the weights of its undirected edges).

In the case of ASHGs, SW(Ch) = ∑i,j∈Ch wij and being opt = ∑kh=1 SW(Ch) ≤ ∑kh=1 n · vh ≤ n · v∗ = n · SW(π), the approximation follows. Notice that the last inequality holds true as M = ∪kh=1Mh is a matching in G, and being M ∗ optimal, the value of M cannot be larger than v∗ .

In FHGs, SW(Ch) = ∑i,j∈Ch wij Ch ≤ vh, and hence opt = ∑kh=1 SW(Ch) ≤ ∑kh=1 vh ≤ v∗ = 2 · SW(π). Notice that if the value of a matching is v, then, the SW of the corresponding partition equals v/2.

5 NOMand Optimality in Discrete Settings

So far we have seen that when weights range in R, R≥0, or [-1, 1], optimality and NOM are compatible. However, in [Flammini et al., 2025] it has been shown that for ASHGs with weights in {-n, 1}, no optimal mechanism is NOM, while, if the weights are in {- 1n , 1} there exists a NOM and optimal mechanism. Therefore, even in simple discrete settings, the compatibility of NOM with optimality depends on the specific values the weights may take.

In what follows, we will dive into these known results to provide a more complete understanding of the compatibility of NOM with optimality in discrete settings. Since known results only focus on ASHGs, we here only consider this class, and we assume general duplex valuations, i.e., weights that may take values in {-x, 0, 1} for x ∈ [1,∞), that contains and extends the setting considered in [Flammini et al., 2025]. We are able to prove the following characterization.

Theorem 5. For general duplex valuations with x ≥ 1, the following hold true:

• For x > 2n - 3, any optimal mechanism is NOM;
• for x ∈ (1, 2n-3), no optimal mechanism is NOM;
• for x ∈ {1, 2n - 3} there exists an optimal and NOM mechanism.

Note that for x ∈ (0, 1) the compatibility of NOM with optimality remains open, besides the case x = 1n [Flammini et

al., 2025]. We believe this case is worth further investigation.

We next sketch the proof of some interesting cases of Theorem 5. Hereafter, we denote by ∆+i = δ+ i (wi) ∪ {i} and ∆-i = δi (wi) ∪ {i}, where wi is the truthful type of i.

Case x > 2n - 3: any optimal mechanism is NOM. To this end, we will make use of the following lemma.

Lemma 3. Under general duplex valuations with x > 2n - 3, for any optimal partition π, there is no negative relation within the agents in any coalition C ∈ π.

We are ready to show that any optimal mechanism is NOM. To this end, we will make sure that both the conditions of Definition 2 are satisfied.

Worst-case) If i truthfully reports wi, by Lemma 3, no optimal outcome can guarantee her a negative utility as no agent in δ-(wi) can be put in her coalition. Consider now any di, we show there exists d-i such that i ends up in a singleton coalition. Indeed, by Lemma 3, it suffices to set dj(i) = -x, for each j ̸= i. In conclusion, the worst-case scenario by truthfully reporting is to be assigned to the singleton coalition, and this cannot be avoided by misreporting the preferences. Therefore, condition 1 of Definition 2 is satisfied.

Best-case) In this case, by truthfully reporting wi, agent i will be assigned to the coalition ∆+i whenever all agents in δ+(wi) positively value only agents in∆+i and any other declaration is set to -x. Since no coalition guarantees i a higher utility, condition 2 of Definition 2 is satisfied.

Case x = 2n - 3: there exists and optimal and NOM mechanism. Let us notice that if x = 2n - 3, Lemma 3 no longer holds true. Suppose indeed that C = N and there exists a unique negative relation within the agents in C. Let j be an agent incident to the negative relation. In this case, both the outcomes π = {N} and π′ = {N \ {j}, {j}} are optimal. However, from a close inspection of the proof of Lemma 3, it turns out that it still holds as long as the optimal mechanism breaks ties in favor of π′ rather than π. Hence, we can derive the following fact: for any π output by this optimal mechanism, there is no negative relation within the agents in any coalition C ∈ π. Then, by replacing Lemma 3 with the aforementioned fact in the proof for x < 2n - 3, we achieve that this optimal mechanism is NOM for x = 2n - 3.

Although we just proved that a NOM and optimal mechanism exists, it is natural to wonder if all optimal mechanisms are NOM. Unfortunately, this is not the case.

Example 2. Let x = 2n - 3. Assume that in case of ties between the outcomes π = {N} and π′ = {N \{j}, {j}} are optimal, for some j ∈ N, an optimal mechanismM returns π rather than π′ .

Consider an instance where there are three agents, namely, 1, 2, 3, and w12 = -x while w13 = 1. If 1 truthfully reports w1, then, due to the aforementioned tie-breaking rule, the mechanism may return the grand coalition as the outcome of the game, which guarantees 1 a negative utility. Notice that this may not necessarily be the worst outcome for 1, but we can infer that, in the worst case, 1 gets a negative utility. However, if 1 reports d12 = d13 = -x, in every optimal partition, i will be put in a singleton and obtains a utility equal to 0, violating Condition 2 of Definition 2.

In conclusion, not every optimal mechanism is NOM.

6 Conclusions and FutureWork

We explored the design of mechanisms for wide classes of succinctly representable HGs that would be robust at least against manipulations of bounded rational agents and return coalition structures of good quality. We followed recent literature and considered NOM mechanisms, and we proved that these mechanisms can always guarantee nonmanipulability (by agents lacking contingent reasoning) and optimality, at least in the continuous case. We also proved that if one requires computational efficiency, we can compute non-manipulable outcomes that approach the best possible approximation achievable in polynomial time. We also consider the discrete values showing a preliminary characterization of optimal and NOM mechanisms.

From a technical viewpoint, it would be clearly interesting to address the questions left open in this work: to close the gap between the best approximation achievable by a NOM mechanism in FHGs, and to extend the optimality characterization to other discrete variants of ASHGs and FHGs.

Another intriguing future challenge is to understand to what extent the results and techniques defined herein can be extended beyond ASHG and FHG, either to other classes of hedonic games, such as B-games [Cechl´arov´a and Hajdukov´a, 2003], W-games [Cechl´arov´a and Hajdukov´a, 2004], or distance HGs [Flammini et al., 2021b], or even to generalizations of hedonic games, such as the group activity selection problem [Darmann et al., 2012]. Moreover, considering the design of mechanisms that are not manipulable by bounded rational agents beyond NOM represents an important future work. Indeed, as discussed above, NOM considers a specific way, for an agent lacking contingent reasoning, to aggregate the possible realizations of the game. Hence, it is natural to ask what may happen with other "simple" aggregation rules.

Acknowledgments

This work was supported by: the PNRR MIUR project FAIR - Future AI Research (PE00000013), Spoke 9 - Green-aware AI; "INdAM - GNCS Project", code CUP E53C24001950001.