Maximizing the Egalitarian Welfare in Friends and Enemies Games Conference: ;
Edith Elkind, Michele Flammini, Giovanna Varricchio* · 2025
Read Maximizing the Egalitarian Welfare in Friends and Enemies Games Conference: ; by Edith Elkind, Michele Flammini, Giovanna Varricchio* (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-20261.txt.
Introduction
Edith Elkind, Michele Flammini, and Giovanna Varricchio study coalition formation when every agent labels the others as friends or enemies. These hedonic games ask for a partition of agents into groups. Egalitarian welfare judges a partition by its worst-off member, so fairness is built into the goal from the start.
Two preference styles are analyzed. Under enemies aversion, avoiding enemies matters most; under friends appreciation, gathering friends matters most. The authors prove hardness results for both and design polynomial-time approximation methods with stated guarantees. Randomization and symmetric friendship recover stronger guarantees for the friends-first case. They also find special cases where the best partition can be computed exactly and quickly.
Catalog record
| CREATOR | Edith Elkind, Michele Flammini, Giovanna Varricchio* |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-20261
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Maximizing the Egalitarian Welfare in Friends and Enemies Games Conference: ; Edith Elkind, Michele Flammini, Giovanna Varricchio* Abstract . We consider the complexity of maximizing egalitarian welfare in Friends and Enemies Games —a subclass of hedonic games in which every agent partitions other agents into friends and enemies . We investigate two classic scenarios proposed in the literature, namely, Friends Appreciation ( \FA \FA ) and Enemies Aversion ( \EA \EA ): in the former, each agent primarily cares about the number of friends in her coalition, breaking ties based on the number of enemies, while in the latter, the opposite is true. For \EA \EA , we show that our objective is hard to approximate within O ( n 1 − ϵ ) O(n^{1-\epsilon}) , for any fixed ϵ > 0 \epsilon>0 , and provide a polynomial-time ( n − 1 ) (n-1) -approximation. For \FA \FA , we obtain an NP-hardness result and a polynomial-time approximation algorithm. Our algorithm achieves a ratio of 2 − Θ ( 1 n ) 2-\Theta(\frac{1}{n}) when every agent has at least two friends; however, if some agent has at most one friend, its approximation ratio deteriorates to n / 2 n/2 . We recover the 2 − Θ ( 1 n ) 2-\Theta(\frac{1}{n}) approximation ratio for two important variants: when randomization is allowed and when the friendship relationship is symmetric. Additionally, for both \EA \EA and \FA \FA we identify special cases where the optimal egalitarian partition can be computed in polynomial time. 1. Introduction Hedonic Games (HGs) ( 16 ) provide a game-theoretic framework for analyzing coalition formation among selfish agents and have been extensively studied in the literature (see, e.g., ( 2 ; 3 ; 6 ; 8 ; 18 ; 17 ; 21 ) ). In these games, the objective is to partition a set of agents into disjoint coalitions, with each agent’s satisfaction determined solely by the members of her coalition. Different preference models give rise to different subclasses of HGs. For instance, in additively separable HGs (ASHGs) ( 8 ) , agents assign values to each other and evaluate coalitions by summing the values they assign to every other member. A particularly natural scenario is when agents classify others as either friends or enemies . Two canonical preference models have been studied in this setting ( 14 ) : under Friends Appreciation ( \FA ) preferences, agents prioritize coalitions with more friends and, in case of ties, prefer those with fewer enemies; conversely, under Enemies Aversion ( \EA ) preferences, agents prefer coalitions with the lowest number of enemies and, if the number of enemies is the same, favor those with more friends. While most of the existing literature on HGs has focused on stability, i.e., the resilience of an outcome to individual or group deviations, another important concept in coalition formation is the social welfare , which captures the quality of a partition. Specifically, the utilitarian welfare, which is given by the sum of the agents’ utilities, measures the overall happiness of the agents in a given partition. However, maximizing utilitarian welfare may come at a cost of treating some agents badly if doing so increases the total sum. In contrast, the egalitarian welfare is determined by the minimum utility among all agents. Thus, a partition that maximizes the egalitarian welfare is fairer, in the sense that the lowest utility is as high as possible. Despite its appeal, egalitarian welfare has received limited attention in the context of hedonic games. 1.1. Our Contribution We study the computation of the maximum egalitarian welfare in Friends and Enemies Games. For \EA games, we prove that the problem is hard to approximate within O(n^{1-\epsilon}) for any fixed \epsilon>0 , where n is the number of agents, and complement this hardness result with a polynomial-time algorithm achieving an (n-1) -approximation. For \FA games, we show that maximizing egalitarian welfare is computationally hard. We then provide a polynomial-time approximation algorithm whose performance depends on the structure of the instance: it achieves an approximation of 2-\Theta(\frac{1}{n}) , when every agent has at least two friends, and an n/2 -approximation in the worst case. We further improve this result in two important settings, namely, (1) when randomization is allowed, and (2) when the preferences are symmetric, that is, the friendship relations are mutual. For both cases, we design algorithms attaining an approximation ratio of 2-\Theta(\tfrac{1}{n}) . Finally, we complement these results by identifying special cases of both \EA games and \FA games where the optimal egalitarian partition can be computed exactly in polynomial time. 1.2. Related Work There is a substantial body of literature on hedonic games; we refer the interested reader to ( 5 ) for a comprehensive overview. In what follows, we focus on work that is directly related to ours. Aziz et al. ( 3 ) consider ASHGs, and show that computing an optimal egalitarian partition is strongly NP -hard; moreover, verifying whether a given partition maximizes the egalitarian welfare is co NP -complete. The complexity of this problem is further investigated by Hanaka et al. ( 24 ) , who identify several tractable cases. Peters ( 30 ) obtained a related result, showing that an optimal egalitarian partition is polynomial-time computable in graphical HGs as long as the underlying graph has bounded treewidth. In addition, egalitarian welfare has been studied in online ASHGs ( 11 ) and in ASHGs where at most k coalitions can be formed ( 32 ) . For simple fractional hedonic games (sFHGs) with symmetric preferences, Aziz et al. ( 4 ) show that maximizing the egalitarian welfare is NP -hard, and provide a polynomial-time 3 -approximation algorithm. Aziz et al. also state that in instances where the underlying graph is a tree, an optimal egalitarian partition can be computed in polynomial time via dynamic programming. This idea was later formalized by Hanaka et al. ( 23 ) , who present an efficient algorithm for bounded treewidth graphs. The egalitarian welfare has also been employed as a quality measure for evaluating stable outcomes in modified fractional HGs ( 28 ) . A closely related problem is the existence of a wonderful (a.k.a. perfect) partition in HGs where agents have dichotomous preferences , that is, each agent values each coalition as either 0 or 1 . A wonderful partition is one where each agent assigns value 1 to her coalition. Clearly, a wonderful partition exists if an only if there exists a partition whose egalitarian welfare is 1 . Establishing whether such a partition exists is, in general, NP -hard ( 29 ; 2 ) , though some tractable cases have been identified ( 29 ; 12 ) . Notably, the positive result of Constantinescu et al. ( 12 ) implies that the problem of maximizing the egalitarian welfare in anonymous HGs with single-peaked preferences is polynomial-time solvable. Friends and Enemies Games constitute a widely studied subclass of hedonic games and have been further extended to capture more complex social contexts ( 14 ; 31 ; 26 ; 7 ; 13 ; 10 ) . In this line of research, most of the focus has been on finding desirable outcomes according to various