Non-Obvious Manipulability in Additively Separable and Fractional Hedonic Games

Diodato Ferraioli; Maria Fomenko; Giovanna Varricchio

cs.GTMay 19, 2025

Non-Obvious Manipulability in Additively Separable and Fractional Hedonic Games

Authors: Diodato Ferraioli, Maria Fomenko, Giovanna Varricchio

Organizations: University of Salerno, Italy · University of Calabria, Italy

Abstract

Hedonic Games are a well-established model for describing the formation of coalitions. In this work, we considered the design of Non-Obviously Manipulable (NOM) mechanisms, that are mechanisms that bounded rational agents may fail to recognize as manipulable, for two relevant classes of succinctly representable Hedonic Games, namely Additively Separable and Fractional Hedonic Games. In these classes, agents have cardinal scores towards other agents, and their preferences towards different coalitions are determined by aggregating these scores. Moreover, the quality of an outcome can also be easily evaluated through these scores by means of the utilitarian social welfare. We first prove that, when scores can be arbitrary, every welfare-maximizing mechanism is NOM, and, when scores are limited in a continuous interval, then there exist tie-breaking rules making welfare-maximizing mechanisms NOM. Next, we focus on efficient NOM mechanisms, since there is no known polynomial-time algorithm to compute welfare-maximizing outcomes in the considered classes of hedonic games. To this aim, we first prove a characterization of NOM mechanisms that simplifies the class of mechanisms of interest. Then, we design a NOM mechanism returning approximations that essentially match the best-known approximation achievable in polynomial time. Finally, we turn our attention to discrete scores, and specifically, the case that scores are $\{-x, 0, 1\}$ for $x > 0$ . We prove that the ability to design welfare-maximizing NOM mechanisms depends on the magnitude of the scores. In particular, for $x > 1$ , we prove that a welfare-maximizing NOM mechanism exists only when $x$ is very large. For $x \leq 1$ , instead, we observe that a welfare-maximizing NOM mechanism always exists except when $x$ lies in the interval $[a, b]$ where $a \approx 2/n^2$ and $b \approx 1/n$ .

Figures & tables

Panel of Figure 1 — Figure 1 : Example of two game instances having the same flattened graph.

Panel of Figure 2 — Figure 2 : We display, in increasing order, the utilities attainable by an agent $i$ from the outcomes of mechanism $\mathcal{M}$ when she declares $d_{i}$ , as $\mathbf{d}_{-i}$ varies. In Figure 2(a) , we show what happens if a mechanism $\mathcal{M}$ is NOM. In Figure 2(b) , we show that even though on a declaration $d_{i}$ both Conditions 1 and 2 are satisfied, the mechanism $\mathcal{M}$ can still be manipulable for some $\overline{\mathbf{d}}_{-i}$ , and $d_{i}$ is a manipulation.

Panel of Figure 3 — Figure 3 : No BAPX is RAT. Dashed lines represent the only BAPX partitions for instances when $\varepsilon<b_{1}(2)<1$ : in these instances, agent 2 has an advantage in deviating, while in all remaining instances the BAPX partitions are the same in the two instances, making the deviation also risk-averse.

Panel of Figure 4 — Figure 4 : Octopus graph having center $i$ . Undirected edges represent mutually equal weights. Solid edges represent positive weights. Dashed edges represent weights equal to zero. Absence of an edge implies negative weight.

Explore similar work

May 18, 2026cs.GT

Nash Welfare in Additively Separable Hedonic Games

Additively separable hedonic games (ASHGs) are a prominent model of coalition formation where agents' preferences are derived from their individual valuations of peers. While social welfare maximization in ASHGs has traditionally focused mostly on utilitarian welfare, Nash welfare -- a well-established metric in economics which balances fairness with efficiency and offers scale invariance -- has been entirely overlooked. In this paper, we initiate the study of Nash welfare in ASHGs. We point out desirable properties fulfilled by partitions with high Nash welfare. This includes guaranteed contractual Nash stability in symmetric games, even for any approximation of Nash welfare. This is particularly appealing since, as for other welfare notions, Nash welfare turns out to be NP-hard to maximize, even for the ASHG subclass of symmetric aversion to enemies games (AEGs). A main focus of our study is on approximation algorithms for the Nash welfare objective. We present packing-based algorithms with approximation ratios for well-established subclasses of ASHGs:

n-1

for AEGs and

2n

for appreciation of friends games. This is complemented by a strict inapproximability result showing it is NP-hard to approximate Nash welfare within a factor of

1.0000759

in general ASHGs. Further, we investigate the restricted settings with an upper bound on the coalition size or number of coalitions, and draw the boundary between the cases admitting efficient algorithms and those yielding NP-hardness: bounding the allowed size or number of coalitions by

2

admits polynomial-time solvability, whereas bounds of

3

or more yield NP-hardness or unbounded inapproximability.

Marta Pagano, Alexander Schlenga

Sapienza University of Rome, Italy · Technical University of Munich, Germany

Nash Equilibrium Game Theory Coalition Formation Imperfect-Information Games Np-Hard

Ask PDF

Jun 27, 2026cs.GT

Pure Nash Equilibria under the Affine Mechanism: A Potential Game of Exaggeration

The mean mechanism is known to be non-incentive-compatible, namely, rational players are incentivized to misreport their values. Despite this game-theoretic issue, the mean mechanism is prevalent in practice due to its other desirable properties. We give a full characterization of pure Nash equilibria--how the players will misreport--for the affine mechanism, of which the mean is a special case. Furthermore, we characterize both complete-information and Bayesian games under the affine mechanism. Our results highlight the inevitability of extreme exaggeration in such games.

Jason Jisen Li, Young Wu, Yancheng Zhu +2

University of Wisconsin - Madison

Nash Equilibrium Rationality Affine

Ask PDF

Jun 18, 2026cs.GT

Equilibrium with Internal Transfers

Nash equilibrium (NE) arises from selfish utility maximization, yet its social welfare can be arbitrarily far from optimal. Moreover, computing an NE is intractable in general. We study augmented game models in which players use budget-balanced internal transfers to improve incentives before play. We first introduce \emph{Self-Enforcing Transfer Equilibrium} (SETE), where players commit to nonnegative peer-to-peer transfers that are paid only if the recipient does not deviate from a prescribed strategy. For polymatrix games, we show that every stationary point of the social welfare function, in particular any socially optimal strategy profile, can be sustained as a SETE. This induces a Nash equilibrium in the agent normal form of the corresponding augmented game. We further propose a polynomial-time algorithm and a decentralized learning dynamic to compute such product-form equilibria. We then introduce \emph{Mediated Self-Enforcing Transfer Equilibrium} (M-SETE), where a mediator makes both the payment schedule and the prescribed strategies binding offers. This additional enforcement resolves the agent-normal-form limitation: an M-SETE is a Nash equilibrium of the augmented game itself, not merely of its agent normal form, and any socially optimal strategy profile can be supported as an M-SETE in any finite game while preserving budget balance. Thus, internal transfers improve welfare and computation while preserving independent play on the equilibrium path. When full sequential-game stability is required, binding mediation provides the corresponding implementation.

Mingyang Liu, Gabriele Farina, Asuman Ozdaglar

LIDS, EECS, Massachusetts Institute of Technology

Nash Equilibrium Equilibrium Peer-To-Peer

Ask PDF