Clustering via Hedonic Games: New Concepts and Algorithms
Authors: Gergely Csáji
Alexander Gundert
Jörg Rothe
Ildikó Schlotter
Venue: NeurIPS 2025 spotlight ()
Keywords: graphical hedonic games
coalition formation
clustering
popularity
community detection
Primary area: theory
TL;DR: We study a stability notion in coalition formation games, give an efficient algorithm, and show that it is surprisingly good for general clustering tasks too.

Abstract: We study fundamental connections between coalition formation games and clustering, illustrating the cross-disciplinary relevance of these concepts.
  We focus on graphical hedonic games where agents' preferences are compactly represented by a friendship graph and an enemy graph.
  In the context of clustering, friendship relations naturally align with data point similarities, whereas enmity corresponds to dissimilarities.	
  We consider two stability notions based on single-agent deviations: local popularity and local stability. 
Exploring these concepts from an algorithmic viewpoint, we 
design efficient mechanisms for finding locally stable or locally popular partitions. 
Besides gaining theoretical insight into the computational complexity of these problems, we perform simulations that demonstrate how our algorithms can be successfully applied in clustering and community detection. 

  Our findings highlight the interplay between coalition formation games and data-driven clustering techniques, offering fresh perspectives and applications in both areas.

Clustering via Hedonic Games: New Concepts and Algorithms
Gergely Csáji
Alexander Gundert
ELTE Centre of Economic and Regional Studies Budapest, Hungary
Heinrich-Heiner Uniiee-nniviiitti Düsseldorf
Düsseldorf, Germany
csaji i gergely@krtk elte.hu
Alexander Gundert&hhu.
Jörg Rothe Searric--Heinee -niie---nivessitätt Düsseldorf Düsseldorf, Germany rothe@hhu.de
Ildikó Schlotter
ELTE Centre Economic and Regional Studies
Budapest, Hungary
schlotter. penttterriddikeee ildikokkrtk elte hu
Abstract
We study fundamental connections between coalition formation games and clus- tering, illustrating the cross-disciplinary relevance of these concepts. We focus on graphical hedonic games where agents' preferences are compactly represented by friendship graph and an enmity graph. In the context of clustering, friendship relations naturally align with data point similarities, whereas enmity corresponds to dissimilarities. We consider two stability notions based single-agent deviations: local popularity and local stability. Exploring these concepts from an algorithmic viewpoint, design efficient mechanisms for finding locally stable locally popular partitions. Besides gaining theoretical insight into the computational complexity of these problems, we perform simulations that demonstrate how algorithms can be successfully applied in clustering and community detection.
Introduction
Coalition formation and clustering two research areas that capture different aspects of grouping set of entities a meaningful or optimal way. While coalition formation studies autonomous agents who have preferences over the various ways in which they can be partitioned into groups, clustering aims to unearth hidden structure and similarities within a set of datapoints. Despite the shared theme of group formation, there is substantial interplay between these two research fields.
This study aims to investigate how different solution concepts emerging from coalition formation particular, from hedonic games-can be used in data clustering. Traditional clustering metrics measure the quality the boundaries between the clusters or the average similarities within clusters. aim for clustering where deviation
We propose criterion that is based form of stability: by a single agent (or data point) should lead to a more preferred outcome. We aim to investigate how such stability notions can be harnessed in clustering algorithms.
Similarities and dissimilarities, the baseline concepts used by clustering algorithms, can be associated with relations of compatibility and of conflict between two agents. Leveraging this idea, we focus on a model coalition formation due to Dimitrov al. [16] where agents' preferences over different coalitions are determined by their friendships and their enmities, represented as two graphs. (FEN) games [33, 37, 27]
More precisely, we adopt the model hedonic friends-enemies-nee where agents classify all other agents friend, enemy, neutral, and each agent evaluates given partition based on the number of friends and the number of enemies their coalition.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Unfortunately, finding "optimal" or, in some sense, stable partitions often turns out to be computa- tionally intractable task. Since computational efficiency is often crucial in clustering applications. we focus our attention on local stability concepts requiring only that re-assigning a single agent to a different coalition does not yield a partition deemed better for the majority of agents. Such single-agent deviations were studied in FEN games by Kerkmann and Rothe [28] and, more recently, in friends-enemies (FE) games-a a model excluding neutrality-by Brandt et al. [10] who showed that in model where two partitions are compared by taking the majority vote of the agents, such deviations converge into a locally stable partition in a polynomial number of rounds. We extend these results to FEN games and also to slightly more stringent stability concept, local popularity. As opposed to the FE games studied by Brandt et al. [10], the option of neutrality introduces a flexibility that allows focusing on relations between points that are either very similar, or very different. Further- more, neutrality yields smaller degrees in the friendship and enmity graphs which, as we show, has a huge benefit in terms of the convergence speed. Depending on the application under focus, different emphasis might be given to grouping together similar data points versus separating dissimilar data points. In the context of FEN game, agents may put significantly larger weight the objective of being grouped together with friends than being separated from enemies, or vice versa; third, more balanced approach is when agents treat these two objectives with the same importance. These options give rise to three preference fonianns-frienn--appreeiaa study may facilitate the application of our results different clustering domains.
enemy-averse, and balanced-whose
By identifying "similarity" with "friendship" and "difference" with "enmity,"" we demonstrate via simulations how our algorithms for finding locally stable or locally popular partitions be used in the context of data clustering. The stability property enforced by our algorithm is particularly useful in clustering tasks where agents have meaningful local interactions or preferences. This includes standard benchmarks such as citation networks (e.g.. Cora [36]), email communication graphs (e.g.. Enron [30], and social networks, where misclassifying a node can distort community structure. By ensuring that no agent prefers to switch to a different cluster based on local relationships. our method yields clusters that are robust against local deviations. This distinguishes our approach from traditional methods like k- k-means or DBSCAN, which may prioritize global fit over local consistency. As our simulations attest, this interdisciplinary approach can be surprisingly successful when compared to the most prevalent clustering algorithms. Thus we hope our work can spark a stronger cooperation between these fields explore the applicability of coalition formation games in clustering.
Related work. Although both hedonic games and clustering are widely studied, broad subjects, the only work connecting these two areas we are aware of is by Feldman et al. [20] who study hedonic clustering games in a noncooperative framework where clustering is obtained via decisions made by independent agents. They propose two types of hedonic games for which they characterize Nash equilibria and analyze the price of anarchy and the price of stability. Although some ideas appear both in our model and theirs-e.ge eegrs-eeg., the utilities of agents depending on their similarities with agents within their own cluster and on dissimilarities with agents in other clusters- the models proposed by Feldman al. significantly differ from ours. Most importantly. while our work is rooted in cooperative game theory. Feldman et al. take noncooperative approach. In addition, although they establish the existence of Nash equilibria for certain specific domains, their results do not seem to lead to efficient, scalable algorithms for general clustering.
Regarding the broader literature related to our study, we only point out the most important precursors of our work and few key references for more background on the relevant research areas. Coalition formation is a central topic in cooperative game theory. Starting with the seminal work of Drèeze and Greenberg [17], researchers' focus shifted to so-called hedonic games where agents' preferences depend only on the coalition they are contained in; see also [5, 8, 13] and the book chapters by Aziz and Savani [4] and Bullinger et al. [11, Section 3.6]. FE games were introduced by Dimitrov et al. [16] as a subclass of hedonic games with a concise description (namely, the agents' friendship relations). FEN games, the extension of their model that allows for neutrality, have also been studied [14, 27, 28, 33, 37, 40]. Single-agent deviations and their induced dynamics were investigated in FE games by Brandt et al. [10] who, in various settings, showed that such deviations converge to a partition that fulfills certain stability concepts. Among the stability concept they considered is what we call local stability; our work extends their results on this notion to FEN games. Our stability concepts stem from the idea of popularity as introduced by Gärdenfors [22]. Popularity has been widely studied in matching and allocation problems [1, 6, 15, 25, 26] and has also been considered in

---

the context of hedonic games by, e.g., Aziz et al. [3], Kerkmann et al. [27], Brandt and Bullinger [9], Kerkmann and Rothe [29], and Bullinger and Gilboa [12].
For a recent survey on clustering-4 fundamental problem in unsupervised learning aimed at dis- covering structure in data by grouping similar elements-see [19]. Classical clustering methods such as k-means, introduced by MacQueen [34], optimize intra-cluster similarity under geometric assumptions, while DBSCAN by Ester et al. [18] identifies dense regions in data and is robust to noise. The most relevant subfield of clustering for our purposes is community detection, which seeks to partition the nodes of a graph into densely connected groups with sparse interconnections. Here, the Louvain algorithm of Blondel et al. [7] and its improved variant Leiden by Traag et al. [41] are state-of of-the-art methods that optimize modularity to reveal community structure in networks. Our main metric to compare our algorithms with k-means, DBSCAN, Louvain, and Leiden is the Rand some true labeling for the data points- computes the fraction of pairs of points that are correctly clustered together or separately.
distance [39], which-assumine
Our contribution. We study two stability concepts in hedonic FEN games: local popularity and local stability. The former-introduced in this paper-assures that no single agent can deviate such that more agents improve than get worse, while the latter requires this only for Nash deviations (where the deviating agent improves). Our main result is a simple algorithm that always finds locally popular partition in polynomial time if friendship and enmity relationships are symmetric in all three settings (friend-apreeciative, averre,, and balanced). For asymmetric relationships, we show that locally stable partition can still be found efficiently in the balanced case, but all other settings yield NP-hardness. See Table for summary of our results.
We also conduct experimental study comparing our algorithms common clustering and commu- nity detection algorithms, in particular, to k-means, DBSCAN, Louvain, and Leiden. Our simulations provided sufficient data show that our algorithms are well suited for clustering and community detection tasks, often outperforming existing solutions.
2 Preliminaries
Let N denote the set of agents. A subset C C N is called a coalition; in particular, N is the grand coalition. In this paper, partition refers to family of pairwise disjoint nonempty subsets of N whose union is N. Given a partition म, the coalition in π that contains i N is denoted by (i)).
A hedonic game is a pair (N, )) where > = (Ex)ieN is a preference profile that contains for each agent weak preference list N5 over the possible coalitions containing i. That is, for any two coalitions C, C" with i E C C' (meaning that C' is preferred to C' by i), C' ~ C (meaning that i is indifferent between the two coulitions). In a hedonic game, the preference lists of the agents only depend on the coalitions they are in. Hence, 2; also induces weak ranking of agent i over the possible partitions.
C³, either C' >; C (meaning that C' is preferred to C' by i), or
Given an agent& E N, partition n, and a coalition E æ U (0), the deviation where i leaves its original coalition (i) and joins C' (or forms new coalition {i} in the case when C' = 0) is referred
to as the switch + C. We use T to denote the partition resulting from æ by the switch i - C. that is, Ti-C (π \ (i), C}) U {m(1) \ (i), CU {i]}. We say that has incentive to join C if CU >: (i); in this case, i - C is a Nash deviation. More generally, extending this notion to partitions, say that an agent j votes for (or, j votes against) switch + C. if j prefers T:-C to π (or, j prefers æ to T,-C, respectively). Further, we define
+1 if if) >, m(}), if + 0
vote, (T,T)
if i() ~3 7()
for partitions v and x' over N. Let A(TT, = ESEN (T, x') be the sum of the agents" votes for n' against т. We will further write A_ a²===)= EjENt (Tt for the sum of votes for against among all agents excluding agent i.
agent i, and a coalition C E π U (0), we say that the switch i i-> C locally dominates π if A(T, a.-c) > O; and the switch - C locally blocks v it is Nash deviation that locally dominates A partition is popular if for any partition n², we have that
Definition 1. Given a partition
3

---

A(T, x²) S O. Moreover, т is locally popular if there is no switch that locally dominates T, and π is locally stable if there no switch that locally blocks т.
Note that a single deviation by one agent can also change the situation-and thus the voting behavior on these two partitions- other agents, giving rise to the above notions of local popularity and local stability. Note further that local popularity implies local stability.
Preferences in FEN games. Dimitrov et al. [16] introduced preference domain for hedonic games where agents' preferences over the coalitions containing them depend only on the number of friends and enemies they have in their coalition. Thus, in a FEN game over agent set N, each agent i classifies all remaining agents into one of three disjoint categories: those that i considers either friends, enemies, neutrals; we denote these agent sets by F(i), E(i), and N (i), respectively. The friendship and enmity relations can be represented by two directed graphs, the friendship digraph
G (N, A and the enmity digraph G (N, A²), where an are (i,j) E A means that i considers j a friend, whereas an are (i,j) E A means that considers j an enemy. We denote by A the maximum number or arcs incident to any agent in G in G A FEN game is symmetric if friendship and enmity relations are both symmetric; it is asymmetric otherwise.
FEN games are subclasses of so-called additively separable hedonic games [5] where each agent i has a valuation function v, over N (i) that is defined as
a if i considers j friend, i.c.. E: F(i),
Oxe if i considers j an enemy, i.e., E Et)),
if i considers j neutral, i.e., ((i)
for some integers O, > 0 and 0g < O, and agent i's utility in a given coalition C' containing i is defined as (.(C'= Σ, jECY (;(; we refer to the pair (at, 0z) as the rype of the FEN game. Then the preferences of agent are based on i's utilities: for two coalitions C and C' both containing i, C c2 C' if and only if (C) 2 (C").. For coalition C N with i E C. we let f3 [F(i) n CI and elc [ii n CI denote the number of i's friends and enemies within C, respectively; then un (,(C) = fC a ec- ac. The utility of agent in a partition π is uz(x) = (1))).
Friend-appreeiattnng, enemy-averse, and balanced preferences. Following Dimitrov al. [16]. we introduce the following preference domains for FEN games. A FEN game with appreciation of friends (or a FEN-AF game, for short) is FEN game over agent set N whose type is (IN), That is, C Z C" holds for two coalitions C, C' with E C'C C" if and only if either fC > fcr. or ft = fo. and et S e By contrast, a FEN game with aversion to enemies (or a FEN-AE game, for short) is FEN game over agent set N whose type is (1, (N]). That is, C Z C' holds for two coalitions C, C' with E C'n C' if and only if either eg < ec., or e' = E and fo 2 fö.- Finally, a FEN game with balanced preferences (or a FEN-B game, for short) a FEN game with type (1, 11).
That is, C 2. C" holds fo two coalitions C, C' with E C C' if and only if fC ec 2 fo. écc. We will call (C) = fC- e'c the balanced utility of i in C.
Problem definitions. Let define the decision problems related to the existence of locally popular and locally stable partitions.
Given FEN game I of type (ay, (ie) defined over a set N of agents with friendship digraph GF problem asks if there exists
and an enmity digraph G the locally popular partition for T; analogously, the LO the same input- asku if there exists locally stable partition for I.
problem-give
3 Local heuristics
We present two local heuristics, one find locally popular partition, the other to find a locally stable partition. Both heuristics start from an arbitrary partition and iteratively modify it using only single-agent deviations; the conditions that determine whether or not to perform given switch is a local condition that can be checked efficiently.
LocPop:
1. Start from an arbitrary partition π.
2. While there exists a coalition C' E x U {0} and an agent & C such that A(T, Ti) > 0, replace with Ty-sc and continue.

---

Table 1: Summary of our results on the computational complexity of
EXISTENCE and partition always exists in the settings where the corresponding problem is proven to be in P. By contrast, a locally stable or locally popular partition may not exist in those settings where the corresponding problem is proven to be NP-complete (abbreviated as "NP-c")-
We remark that a locally stable or locally popular
LOCAL- CICAL-STABILLITYEXXIIEEEEE
LOCAL-POPULARITE EEPULARRTY-EXISTENCE
symmetric
asymmetric
symmetric
asymmetric
FEN-B game
P (Thm. 2)
P (Thm. 4)
P (Thm. 2)
NP-c (Thm. 9)
FEN-AF game
P (Thm. 2)
NP-c (Thm. 7)
P (Thm. 2)
NP-c (Thm. 7)
FEN-AE game
P (Thm. 2)
NP-c (Thm. 13)
P PTThm. 2)
NP-c (Thm. 13)
LocStab:
1. Start from an arbitrary partition π.
2. While there exists a coalition C E π (0} and an agent i & C such that A(T, Ti-C) > 0 and C'U {i} >; (()), replace π with Ti-C0 and continue.
LocPop and LocStab can both be modified such that the number of coalitions within the partition remains fixed: it suffices to consider switches of the form i + C where C E ι and (i) E क in Step 2.
In the rest of this section, we show that the above heuristics converge in certain FEN games, that is, they arrive at a locally popular or locally stable partition in finite number of steps. We remark that LocPop and LocStab cannot guarantee to achieve popularity; in fact, we show in Appendix A that deciding whether there exists popular partition or even just verifying popularity
cord-
Our convergence results both for symmetric and asymmetric FEN games rely on a potential functtiial that we define the total balanced utility of agents: f(T)) = EiEn uf (=(()) Eien Si(e) *(O))
3.1 Symmetric FEN games
Lemma 1. For a FEN game over agent set N, let v be partitionn, i E N agent, and C E xuf6) a coalition with A(T, TT-C) > O. Then (a) EjEN((O) uz (TT-C) -u] ()( = A_ T.cc). Moreover, if T is symmetric FEN game, then (b) (C) -ul (m(()()) ( Ti-c) and (c) f( = (T,, + 2A TT-sC).
Proof. First, consider the agents in N (i). Each such agent j may gain lose friend an enemy by the switch -> C, and thus its balanced utility increases exactly by the value of vote, (T. Ti-sc) E C. Summing up the increase in the balanced utility of all agents in N \ {i), we therefore obtain A (,, proving statement (a) of the lemma.
{-1, 0, } as result of the switch
Assume now that is symmetric. Consider the contribution of agent to [TT=-C) [(T). The change in the balanced utility of as a result of the switch - C' is exactly u² (C) u (i)) = (=1 + as friendships are symmetric, each agent who gains (or loses) a friend or enemy due to i + is in turn a friend or an enemy gained (or lost) by i; this yields statement (b).
Statement (c) then follows by summing up (a) and (b).
Theorem 2. In a symmetric FEN-AF, FEN-AE, or FEN-B game, irrespective of the initial partition, heuristic LocPop always converges in O(n steps (in O(nA) steps for FEN-B games) locally popular (and thus also locally stable) partition, and heuristic LoeStab always converges in ((n)) steps to a locally stable partition.
Proof. Consider step in heuristic LocPop or LocStab where partition x is replaced by T for some agent i N and coalition C E x U (0). Then A(T, -,-C) > 0 implies A-, m.-,c) > 0. By statement (b) of Lemma 1, this immediately yields that f(Ti-c)) 2 f(T), meaning that f is nondecreasing during the execution of the heuristic. As the total balanced utility within the range [-nA, AA), there can be at most 2nA steps when f*) strictly increases.
Let us now consider the case when ((T-C) = f(x), i.e., the potential function does not increase; our aim is to bound the number of such steps during the execution of the heuristic. By statement (b) of Lemma 1, by f(T(-C)) = fTT we must have A x 0. By statement (a) of Lemma
A So e' fa( + c 0.
(l)
5

---

We introduce (T) = [( E A (() = H and g (*) = (((,,)) E A
T(i) - -
We distinguish between the following three cases depending on the type of the FEN game.
Case 1: Balanced preferences. By Lemma 1, the switch - C' increases the balanced util- ity of i by exactly (--() = O. Since agent i has balanced preferences, this implies vote; (T,, -. = O. However, then A(T, Ti-C) = 0 follows, contradicting our assumption that the condition A(T, ==+C)= > 0 holds. This proves f(T+-c))= f(T) for balanced preferences.
Case 2: Frieedtappreciatting preferences. Since we assumed friendships to be symmetric, 2 22f)) We claim that g (T.-c) > 9 0 (TT). Indeed, the switch + C was performed by the heuristic based on the condition (M-C) > O, it follows that agent i must prefer Ti-C to π; hence, either fC > (*()) holds as promised, or ft f*()) and e' < Cx(0) however, (1) excludes the latter.
g (TT (st)
Case 3: Enemy-averse preferences. Since we assumed enmities to be symmetric, we have 9d (TI-c) 9 (T)) = (e)) - 2ec. We claim that g (T+--) > g (T)). As in Case 2, we have A(T,, T-- > 0, which implies that agent i must prefer Ti-sC to π;; hence, either eq < ((()) holds promised, or ecc (0) and fü > fa(ssj however, (1) again excludes the latter.
Total number of steps. We have shown that the number of steps when the potential function strictly increases is most 2nA. In each such step, gf and g might each decrease by at most A, yielding upper bound of 2n on the total decrease during the algorithm. Since g" takes values within [0. n and go between [-nA, O). the number of steps when f(x) does not increase is at most A + nA. This gives bound of (n))²) on the number of steps taken by the heuristics.
remains to show that heuristic LocStab (and LocPop for FEN-B games) converges in O(nA) steps. In FEN-B games, f always strictly increases, as we showed, hence we need ((Lá) steps. Otherwise, in FEN-AE and FEN-AF games, a switch i - C only performed in LocStab if fo 2 f (or if eec S e (n)): ): hence of (or g respectively) never decreases. Thus the number of steps when f does not increase is at most n. in FEN-AF and FEN-AE games, proving the claim for LoeStab. L.
By applying an efficient way to decide if a switch is locally dominating and by using a carefully maintained data structure for quickly finding such switches, our heuristics can be implemented in near-linear time if the maximum degree A of the friendship and enmity digraphs is constant; see Appendix B. As efficiency is often paramount in clustering, we believe that this result significantly widens the possibilities for applying our heuristics in practical clustering instances. Theorem is proven in Appendix B, while all further results marked with (*) are proven in Appendix D.
Theorem 3 (+). LocPop can be implemented to run in O(n 3 log n) time (or On log n) for FEN-B games) and LocStab can be implemented to run in Onn log n) time.
3.2 Asymmetric FEN games
The following example shows that heuristics LocPop and LocStab may not stop in asymmetric FEN game with friend-appreciating or enemy-averse preferences.
Example 1. In an asymmetric FEN-AF or FEN-AE game, heuristics LocPop and LocStab can run into cycle and never stop. Let there be seven agents: 0, 1..... 6. Each agent considers (i + 1) mod 7 a friend but (i + 2) mod 7 and (i + 3) mod 7 enemies; see Figure 1a for an illustration. (Here and anywhere else, all relations that are not explicitly mentioned are tacitly assumed be neutral.)
In the AF domain, let the initial partition be {(0, 1,2,3), [4,5, 5, 6)). Then agent 3 has an incentive to join {4, 5, 6) and this switch takes place, agents 0, 1, and 3 vote for it and only agent 2 votes against it By symmetry, this creates a loop: agent switches next, then agent 2, then agent 5, etc.
In the AE domain, let the initial partition be { 3). (4,5, 5, 5,6)). Then agent 4 has an incentive to join (2.3) and this switch takes place, as agents 4 and 3 vote for it and only agent 2 votes against it. Again, this creates loop: agent 2 switches next, then agent 0, then agent 5, etc.
Example 2. In an asymmetric FEN-B game, heuristic LocPop can run into a cycle and never stop. Let the agent set be (0. 1, 2). where each agent considers (i - 1) mod 3 a friend and (i 1) mod an enemy. Let the initial partition consist of two coalitions: {0, 1} and (2). Then both 0 and 2 vote

---

(a) The FEN game in Example 1. (b) An AF-gadget on 11 agents.
(c) A B-gadget.
Figure I: Illustration for Example I and Definitions and 3. We use thick, blue arrows for friendship ares and thin, red ones for enmity ares (some enmity ares in (b) are shown in gray for better visibility).
for the switch of 1 - {2), which hence takes place. Next, the switch 2 + {0} takes place, followed by the switch 0 + {1}, and the heuristic arrives back at the initial partition.
Contrasting Examples and 2, heuristic LocStab always stops agents' preferences are balanced.
Theorem 4 (+). In a possibly asymmetric FEN-B game, the total balanced utility of all agents strictly increases in each step of heuristic LocStab; consequently, heuristic LocStab always converges in (n)) steps to locally stable partition, irrespective of the initial partition.
Hardness results for local popularity and local stability
Friend-appreciating FEN games. Let us introduce the gadget which lies the heart of our hardness results on FEN-AF games; see Figure 1b for an illustration.
Definition 2. Let & 2 5 be an integer with (2k: + 1) mod 3 * 0. A set {0, 2k} of agents forms an Sai-AF-gadee gadget of size 2k + 1 if each agent i considers (i (i+1) mod (2k + 1) friend (so that the friendship graph is directed cycle) and considers (i 2), (i 3)...., (i- 4) mod (2k 1) enemies.
Theorem 5 (+). The asymmetric FEN-AF game consisting solely of AF AF-gadger admits locally popular partition.
Building on AF-gadgets, fail to exist. In fact, Theorem 7 shows that NP-hard to decide whether a locally popular or locally stable partition exists; our reductions are from 5-SAT and make ample use of AF-gadgets.
involved construction shows that even locally stable solution may
Theorem (+). There exists asymmetric FEN-AF game that admits locally stable partition.
Theorem (+). POCAL-POPULARITYY CHOOPULARTTYEXISTTENEE and complete for FEN-AF games.
EXILTTENE are NP.
Balanced FEN games. Turning our attention to balanced FEN games, recall that given a FEN-B game 7, heuristic LocStab always finds locally stable partition for in polynomial time, stated in Theorem 4. By contrast, we introduce a gadget that similar to the AF-gadget from Definition is tailored for showing that FEN-B games may not admit locally popular partition. Relying on B- gadgets, by a reduction from the NP-complete problem 3-COLORING we can show the -arhhrdssss of the related decision problem, stated in Theorem 9.
Definition 3. A set 10, 6} of agents forms B-gadget if each agent i considers (i + 1) mod 7 and (i + 2) mod 7 friend and considers (i + 3), 4), (i + 5) mod enemies.
Theorem 8 (+). The asymmetric FEN-B game consisting solely of a B-gadget admits no locally popular partition.
Theorem (+). LOCAL-POPULARITY EXISTENCE NP-complete for FEN-B games.
As we have shown in Theorem 4, heuristic LocStab increases the agents' total balanced utility- the potential function f-in each step when running on FEN-B game. Hence, partition maximizing (i) is locally stable but, Theorem 8 shows, not necessarily locally popular. Interestingly. not

---

da
012
111
Illustration of the AE-gadget defined in Definition 4. Here we denote friendship as thin, blue lines and enemy ares as thick, red lines.
Figure 2:
even a popular partition is guaranteed to reach the maximum total balanced utility, even in symmetric FEN-B games; see Proposition 10. Moreover, deciding whether there exists partition that achieves a given total balanced utility is NP-hard, as shown by Theorem 11.
Proposition 10 (+). There exists a symmetric FEN-B game that admits partition that is popular but does not maximize the agents' total balanced utility.
Theorem 11 (+). Given symmetric FEN-B game I and integer t, the problem of deciding whether admits partition π whose total balanced utility is at least & is NP-complete.
Evemy-averse FEN games. Similarly to the gadgets from Definitions 2 and 3, we introduce an AE-gadge for FEN-AE games for proving that such games may not admit a locally stable partition. A reduction from 3-SAT based on AE-gadgets shows the intractability of deciding the existence of locally popular or locally stable partitions. For E N {0}, we write [k] as shorthand for (1.2,...,,;, k.).
Definition An AE-gadget over a player set K = =c : : [12]] U (a;, 2; i [3]] has the following friendship and enemy relations: considers a; and d, for [3] friends and agents 1T, Z2, Vz. b11, and b12 enemies; b, considers e, bi41, and b,42 friend for each considers 610 friend, and b1o considers b11 friend; b11 and b12 consider each other and all agents in {b. 1 [10}} friends and c an enemy; a, considers T₁. d,, and a friend for each E [3]; d1, d2, and d3 consider friend; and z; considers a, friend for each E [3]. See Figure 2.
[8]: by
Theorem 12 (+). The asymmetric FEN-AE game consisting solely of an AE AE-gadget admits no locally stable partition.
Theorem 13 (x). LOCAL-POPULAIIYYEXXSSTECCC and DOCAL-STABILITY-XXIISTT are NP- complete for FEN-AE games.
5
Simulations
We complement theoretical study with range of experiments.
Setup. We implemented LocPop and LocStab in Python and run the simulations on a computer with AMD Ryzen 7735HS CPU and 16GB RAM. All codes are available in the supplementary material.
For our algorithms, we chose parameters f < e j0, 1] to create the friendship and enmity graphs: for two data points and at distance d(æ, 3) in an instance I, we added (xr y) to the friendship graph
'Wee points are described via their coordinates, we take the Euclidean distance, while in an instance described network, the distance of is measured by the number of edges of shortest py-path.

---

if d(x, y) I f diam(I) and to the enmity graph if d(z, y) > e diam(T), where diam(I) denotes the diameter of I. i.e. the maximum distance between any two points in We used the parameter values (f,e) E {(0.2, 0.2), (0.25, 0.35), 0.4)). For each parameterization, we considered the sppreciation-o-ffreeee (AF), aversion-to-enemice (AB), and the balanced (B) preference domains,
Community Detection. For community detection, we used four different datasets.
1. Karate club [23, 31, 43]: a 34-node benchmark dataset for community detection.
2. Jazz musicians [24, 32]: collaboration network of 198 jazz musicians; nodes represent musicians, edges represent co-membership in band.
3. Cora dataset [36, 35]: citation network of 2708 machine learning papers classified into seven classes; edges denote citation links.
4. Random-25: an instance containing 25 disjoint Lénds graphs (10 nodes each, with p 0.2) as communities; inter-community edges added independently with probability 0.05.
We compared our heuristics with two sate-of-the-art algorithms, called Louvain and Leiden [2]. We tested our heuristics with respect to several different parameters. In particular, we considered the following variations for the initial clustering: (i) putting each agent into singleton cluster (LocPop-S, LocStab-S), (ii) dividing agents randomly into & clusters where & the predicted number of clusters (LocPop-P, LocStab-P), P,, and (iii) using the output of the Leiden algorithm (LocPop-Ld, LocStab-Ld)
For evaluation, we used Rand index and modularity, both commonly used metrics. The Rand index assumes underlying true labels for the data points, and measures the similarity of the obtained clustering to the true clustering. More precisely, it computes the fraction of such (z, y) pairs where and are correctly put together or into different clusters. By contrast, modularity does not necessitate a true labeling, but instead evaluates how well the graph underlying the instance divided into clusters, based on the number of edges within the clusters in between different clusters. See Figure 3 and Appendix C.I.
Rand Index by Method on Karate Club
Index by Method on Random-25
1.0
0.8
0.900
Wand
0.875
0.6
0.850
0.855
Lorden
LucPop-S S
LocPop-P
LocPop Ld
Laiden
LucPoe-S
LocPop LD
Figure 3: Comparing Rand index of Leiden, Louvain, and LocPop variants on the Karate club dataset (left) and the synthetic dataset Random-25 (right). In all figures henceforth, 2-sigma error bars show the standard deviation of the plotted data.
Clustering. For our clustering simulations, we used four datasets.
1. Iris dataset [21]: 150 samples from three Iris species, features are sepal and petal sizes.
2. Breast cancer Wisconsin dataset [42]: 569 samples from diagnostic images (30 dimen- sional datapoints).
3. Moons dataset [38]: two half-moons generated by
(300 points, 0.05 noise). 4. 3-Circles dataset: 300 points in three slightly overlapping circles centered at (0.5, 0.5). (0.7, 0.3), and (..1,0.7) with radius 0.2 and Gaussian noise (std 0.05).
We compared our algorithms to two widely used clustering algorithms, k-means and DBSCAN, using their initial parameters. We tested our heuristic with respect to several different parameters. In particular, we considered the following variations for the initial clustering: (i) putting every agent into singleton cluster (LocPop-S, LocStab-S) (ii) dividing the agents randomly into & clusters where l: the predicted number clusters (LocPop-P, LocStab-P), (iii) using the output k-means (LocPop-kM, LocStab-kM) and (iv) using the output of DBSCAN (LocPop-D, LocStab-D).

---

Rand Index by Method lris
Silhouette Score Method on Iris
0.7
0.9
0.8
AE
002,
0.21
Sthouette Score
0.6
ME
01. 0.21
00.5, 0:35)
0.5
00.25, 0:35)
0.4
0.6
0.33
0.5
Kmmaas
L
LocPop LocPop-DN
LocPag-O
Kmeans
DESCAN
LocPop
LocPop LocPop-OM LocPop-O
Figure 4: Comparing Rand index (left) and silhouette score (right) of k-means, DBSCAN, and LocPop variants for the Iris dataset.
To evaluate the outputs, we considered the Rand index and silhouette score, both being commonly used metrics in clustering. As opposed to Rank index, silhouette score does not assume the existence of a true labeling of the given data points, but evaluates the quality of the obtained clustering by measuring the cohesion within clusters well as the separation between different clusters. See Figure 4 and Appendix C.2.
Key insights from experimental results. Our algorithms run within seconds, except for Cora, where computation takes 3-5 minutes, probably due to high degrees in the friendship and enmity graphs. LocPop and LocStab performed very similarly, with LocStab depending more the preference domain, so we discuss LocPop here. A more detailed evaluation can be found in Appendix C.3.
LocPop demonstrated strong and consistent empirical performance, performing very similarly over the three preference domains (AF, AE, and B) We observed that parameter tuning can significantly affect outcomes, usually either the setting (0.2, 0.2) or (0.4, 0.4) performed best, and (0.25, 0.35) performed consistently between them. Interestingly, stronger performance on standard clustering metrics (silhouette score) often did not align with being closer the true labels (Rand index).
In community detection tasks, LocPop matched or outperformed Louvain and Leiden with respect to the Rand index. particularly excelling on the Karate club (~ 50% better) and Random- 25 (~ 10% better) datasets. The LocPop-Ld variant also matched them with respect modularity. benchmarks, it mostly surpassed DBSCAN in both silhouette score and Rand index, and also matched or outperformed k-means (with up 20% Circles and Iris in silhouette score). These findings indicate that LocPop is both theoretically grounded and competitive in practice, offering flexible and efficient approach for structure discovery while providing additional robustness against deviations.
clustering
Conclusion
We have investigated the computational complexity of finding popular, locally popular, or locally stable partition in FEN-AF, FEN-AE, and FEN-B games and identified which cases were solvable efficiently and which were NP-hard. Our algorithms can also interpreted as dynamics of agents based on single-agent deviations and majority-based decision making.
Our experimental study provided sufficient background show that social-choice concepts like local stability and local popularity may lead to efficient clustering and community detection techniques. Furthermore, by their nature, these concepts may often provide fairer solutions that are also more stable against potential deviations, which- as argued in the introduction is particularly relevant in scenarios where data points correspond to agents capable of making independent actions.
Acknowledgments and Disclosure of F Funding
This work was supported part by Deutsche Forschungsgemeinschaft under DFG research grant (project 438204498). Csáji was also supported by the Hungarian Scientific Research Fund, OTKA, Grant No. K143858 and by the National Research, Development and Innovation fund, under the KDP-2023 funding scheme (grant number C2258525). Schlotter was also supported by the Hungarian Academy of Sciences under its Momentum Programme (I.P2021-2) and its János Bolyai Research Scholarship.
10

---

References
[1] D. J. Abraham, R. W. Irving. Kavitha, and K. Mehlhorn. Popular matchings. SIAM Journal on Computing, 3704):003-1045, 2007.
[2] D. Albert. Louvain and Leiden implementation. http:://ggtt.esclaa..eeeee/ee Louvain-leiden Sept. 2023.
[3] H. Aziz, F. Brandt, and H. Seedig. Computing desirable partitions additively separable hedonic games. Artificial Intelligence, 195:316-334, 2013.
[4] H. Aziz and R. Savani. Hedonic games. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and
A. Procaccia, editors, Handbook of Computational Social Choice, chapter 15, pages 356-376. Cambridge University Press, 2016.
[5] S. Banerjee, H. Konishi, and T. Sönmez. Core in simple coalition formation game. Social Choice and Welfare, 18(1):135-153, 2001.
[6] Biró, R. W. Irving, and D. F. Manlove. Popular matchings in the marriage and roommates problems. In Proceedings of the7th International Conference Algorithmms and Complexity, pages 97-108. Springer LNCS #6078, 2010.
[7] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and Lefebvre. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10): P000:00008 2008.
[8] A. Bogomolnaia and M. Jackson. The stability of hedonic coalition structures. Economic Behavior, 38(2):201-23) 2002.
Games and
[9] F. Brandt and M. Bullinger. Finding and recognizing popular coalition structures. Journal of Artificial Intelligence Research, 74:569-626, 2022.
[10] F. Brandt, M. Bullinger, and L. Tappe. Single-agent dynamics in additively separable hedonic games. In Proceedings of the 36th AAAI Conference Artificial Intelligence pages 4867-4874. AAAI Press, 2022.
[11] M. Bullinger,
E. Elkind, and J. Rothe. Cooperative game theory. In J. Rothe, editor, Economics and Computation. An Introduction Algorithmic Game Theory, Computational Social Choice, and Fair Division, Classroom Companion: Economics, chapter 3, pages 139-229. Springer, 2nd edition. 2024.
[12] M. Bullinger and M. Gilboa. Settlig the complexity of popularity in additively separable and fractional hedonic games. Technical Report arXiv:2411.05777 [cs.GT], ACM Computing Research Repository (CoRR), Nov. 2024.
[13] K. Cechlárová and A. Romero-Medina Stability in coalition formation games. International Journal of Game Theory, 29(4):887 2001.
[14] J. Chen, G. Csáji. S. Roy, and S. Simola. Hedonic games with friends, enemies, and neutrals: Resolving open questions and fine-grained complexity. In Proceedings of the 22nd Interna- tional Conference on Autonomous Agents and Multiagent Systems, pages 251-259. IFAAMAS. May/June 2023.
[15] A. Cseh. Popular matchings. chapter 6, pages 105-122. AI Access Foundation, 2017.
Endriss, editor, Trends in Computational Social Choice,
[16] D. Dimitrov, P. Borm, R. Hendrickx, and S. Sung. Simple priorities and core stability in hedonic games. Social Choice and Welfare, 26(2):421-433, 2006.
[17] Drèze and J. Greenberg. Hedonic coalitions: Optimality and stability. Econometrica, 48(4):987-1003, 1980.
[18] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density- algorithm for discovering clusters large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, pages 226-231. AAAI Press, 1996.

---

[19] A. E. Ezugwu, A. M. Ikotun, O. O. Oyelade, L. Abualigah, J. O. Agushaka, C. I. Eke, and A. A. Akinyelu. A comprehensive survey of clustering algorithms: State-of-the-an machine learning applications, taxonomy. challenges, and future research prospects. Engineering Applications of Artificial Intelligence, 110:104743, 2022.
[20] M. Feldman, L. Lewin-Fytaa and J. S. Naor. Hedonic clustering games. ACM Trans. Parallel Comput., 2(1):ar 4:1-48, 2015.
[21] R. A. Fisher. The use of multiple measurements in taxonomic problems. Annals of Eugenics, 179):199-188 1936.
[22] P. Gärdenfors. Match making: assignments based on bilateral preferences. Behavioural Science, 20:166-173, 1975.
[23] M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12):7821-7826 2002.
[24] P. M. Gleiser and L., Danon. Community structure in jazz. Advances in Complex Systems, 6(4):565-573 2003.
[25] S. Gupta, P. Misra, S. Saurabh, and M. Zehavi. Popular matching in roommates setting is NP-hard. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2810-2822, 2019.
[26] T. Kavitha, J. Mestre, and M. Nasre. Popular mixed matchings. Theoretical Computer Science, 412(24):2679-2660, 2011.
[27] A. Kerkmann, J. Lang, A. Rey, J. Rothe, H. Schadrack, and L. Schend. Hedonic games with ordinal preferences and thresholds. Journal of Artificial Intelligence Research, 67:705-756. 2020.
[28] A. Kerkmann and J. Rothe. Stability in FEN-hedonic games for single-player deviations. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, pages 891. IFAAMAS, May 2019.
[29] A. Kerkmann and J. Rothe. The complexity of verifying popularity and strict popularity in altru- istic hedonic games. Journal of Autonomous Agents and Mulli-Agent Systems, 38(2):Article 47, 2024.
[30] B. Klimt and Yang. The Enron Corpus: A new dataset for email classification research. In Proceedings of the 15th European Conference Machine Learning, volume 66, pages 217-226. Springer LNAI #3201,
[31] J. Kunegis. arenas- jaaz, 1977.
KONECT, Jazz musicians dataset.
http://konnet..cchetttokkk
[32] Kunegis. KONECT, Zachary karate club dataset. ucidata-zachary, 2003.
http:///ooeett.cc/netoooo
[33] Lang, A. Rey, J. Rothe, H. Schadrack, and L. Schend. Representing and solving hedonic games with ordinal preferences and thresholds. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems, pages 1229-1233 IFAAMAS. May 2015.
[34] MacQueen. Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, volume 5.1, pages 281-297. University of California press, 1967.
[35] A. K. McCallum. Cora. https://dx.... doi orgg 10. 21227 /112222/js4443...
20244 2024.
[36] A. K. McCallum, K. Nigam, Rennie, and K. Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163, 2000.
12

---

[37] K. Ohta, N. Barrot, A. Ismaili, Y. Sakurai, and M. Yokoo. Core stability in hedonic games among friends and enemies: Impact of neutrals. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 359-365. AAAI Press, Feb. 2017.
[38] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg. J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-288 22300, 2011.
[39] W. M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66(336):846-83555 1971.
[40] Rothe, H. Schadrack, and L. Schend. Borda-induced hedonic games with friends, enemies, and neutral players. Mathematical Social Sciences, 96:21-36, 2018.
[41] V. A. Traag, L. Waltman, and N. J. Van Eck. From Louvain to Leiden: Guaranteeing well- connected communities. Scientific Reports, 9(1):5233, 2019.
[42] W. Wolberg, O. Mangasarian, N. Street, and W. Street. Breast Cancer Wisconsin (Diagnostic). 2tgg/10.2 24432/C5DW25
UCI Machine Learning Repository, 1993. pettps//doot
[43] W. W. Zachary. An information flow model for conflict and fission in small groups. Journal of Authropological Research, 33(4):452-473, 1977.
13

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: In the abstract, we claim to study algorithmic questions related to graphical hedonic games-this done in detail in Sections 3 and 4-and argue that our algorithms are also applicable for general clustering and community detection tasks-which is backed up by our simulations in Section 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The main limitation for our algorithms is the relatively slow running time for very dense graphs, as stated in Theorems and This is discussed in detail in Appendix C.3 along with a possible way to overcome this issue.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide the formal definitions for our framework in Section 2 and prove each of our statements rigorously in Sections 3 and Note that due space constraints, many of these proofs are deferred to Appendix D.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide all the codes used for our simulations and synthetic datasets in the supplementary material files of the submission. For the publicly available datasets, we provided citations for their availability.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
15

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provided all the codes used for our simulations in our supplementary material files. We only used publicly available datasets, and synthetic datasets- which the codes are also included inchuied-rendering our simulations completely reproducible.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips.. cc/ public/guides/ gguides/CodeSubmiee wot.sumiisssoooiirrooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurIPS code and data submission guidelines (https: //iipsccooccoo cttpss/ccpppccccccccceeecccc htapllic/giieee guwdge/ddeeeeee /eed/CCeeSubmiiae SesSSummisiiiooooi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Our simulations did not include training, nor data splits. Regarding the tests, we provide all the parameters and setting we used in Section 5,
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We provide 2-sigma error bars for all our plots in Section 5. The caption of Figure 3 describes the type of error bars used. We note that in many cases, the bars are too small (e.g. 10-1) to be visible in the figure.
16

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Section 5, we provided sufficient details regarding the hardware used for our simulations and the exccution times.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: attps://neets http://eeeripp.eee http://eerree...ppptttt//ee/eeee wttp/ublccc.hhhccccieellllllllll
Answer: [Yes]
Justification:
All our research was conducted in line with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
17

---

Answer: [NA]
Justification: Our algorithms have no immediate societal impacts. However, we briefly discuss in Section 1 that using our algorithms for clustering agents, capable of performing actions and deviations, helps to avoid instability and strategic deviations. This may lead to some positive societal impacts in such cases. We believe that there are no negative societal impacts of our work.
Guidelines:
The answer NA means that there is no socictal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The paper proposes no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We provide citations for all the (publicly available) datasets that we used in Section 5.
18

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comdaatasess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: All details to reproduce the synthetic datasets that we generated are included in Section 5. Furthermore, the codes for these are also available in the supplementary materials the submission.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/coodemmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: There was no crowdsourcing nor research with human subjects in this project.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
19

---

Answer:
[NA]
Justification:
There was no research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were not used in core methodology.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: httts://nneurpp. cc/ /o/comfereeccce/2225//////////// for what should or should not be described.
20

---

Appendix A Existence of a popular partition in FEN games
Recall that Theorems 2 and 3 say that locally popular partitions always exist and can be efficiently found by simple heuristic in symmetric FEN-AF and FEN-AE games. In this section, we show that the same does not hold for popularity: there exist symmetric FEN games where for each possible partition π, there is deviation involving multiple agents that yields a partition x' with A(T, T') > O. Specifically, we show that the verification problem for popularity in symmetric FEN games is coNP- complete. Furthermore, we show that deciding whether popular partition exists in such games is computationally intractable as well; specifically, the existence problem for popularity in symmetric FEN games is coNP-hard. These results on the complexity of popularity verification and existence are the same as those known for other types of hedonic games, such as the altruistic hedonic games studied by Kerkmann and Rothe [29]. Interestingly. Bullinger and Gilboa [12] recently settled the complexity of whether there exist popular partitions in either additively separable or fractional hedonic games by showing that these two problems are complete for Np the second level of the polynomial hierarchy- the first results closing the gap between the computational upper and lower bounds for popularity existence in hedonic games. For our problems, we leave this question open.
We prove the following result for all FEN games, among them FEN-AF, FEN-AB, and FEN-B games.
Theorem 14, Given a FEN game I of some fixed, arbitrary type with symmetric preferences, verifying whether partition is popular in I is coNP -comleem,, while deciding whether a popular partition exists for I is coNd-hard.
Proof. It clear that verifying whether a given partition is popular in given FEN game I of some fixed, arbitrary type with symmetric preferences is in co.P, because we can nondeterministically guess a partition T' and check polynomial time whether A(T, T²) 0. This is the case for some partition n' exactly if I is not popular in I.
To prove hardnsss,,,s,, is a set U = {ui..... U3n) and a set family F = {Fi,... Fm with each F; being a size-3 subset of U; the task is to decide whether there exists set family S F of size n such that U UFee F,
present a reduction from the EXACT 3-COVER problem whose input
We construct a FEN game of the given type as follows; our reduction correct irrespective of the type of I. For each element u, U, we create agent U, and for each set F3 E F, we create an U}} and F {Fj F, F}. We further add two sets A and A' of anchor agents with |A| = |A'l = 5n + m and a set B of guard agents with [B] = 2n 1.
agent F,: use the notation U {ū
Hence, the set of agents in I is A J A' YUUBU BUUUU UF.
The relationships for I are defined as follows; recall that all relationships in I are symmetric:
Each anchor agent in A is friends with all other anchor agents in A and all agents in U.
Each anchor agent in A' is friends with all other anchor agents in A' and all guard agents.
Each guard agent is friends with all agents in F.
An agent V. E T is friends with an agent F, E F if and only if u, E Fj.
Each anchor agent in A and each anchor agent in A' are enemies.
We claim that admits a popular partition if and only if π* (AUU, A'U BUF) is a popular coalition, which in turn happens if and only if our input instance Ix (U, F) of EXACT 3-COVER does not have a solution, i.e., there is no exact cover of B in F.
First, let us show that if S C F is a solution to /xac, then n² is not popular. To this end, let us define = (F F2 E S}. We are going to show that A(T, x > 0 where the partition
== (AUUUS,
is obtained from by deviation of agents in 3; this implies that x² is not popular. Note that each element E U is contained in some set F3 E S, which means that each agent u; E U has more friends x (w:) than in n' (uu) (and zero enemies in both) and thus prefers æ to n² By contrast, each guard agent b E B has fewer friends in (T(b) than in x² (6) (and zero enemies
21

---

in both) and thus prefers x- to л. Furthermore, each agent F, E S gains three new friends and loses all of its guard friends when switching from x* to (and has zero enemies in both) and thus prefers x² to æ. Since every remaining agent is indifferent between иT and x'' we obtain that A(T,T") [0] [ S = 3n- (2n -
= 0.
Next, show that if x= is not popular, then Ixsc has solution. Let be partition that is more popular than ,,, i.e, Ar=". T) > 0. Observe that for an anchor agent a E AU A', all friends and no enemies of a are in nT (a), so anchor agents cannot prefer iT to x². Moreover, if some anchor agent prefers '² to 9, then at least [A| = | = 5n + m anchor agents do so; however, at most [+ + B = 3n-+ m 2n -1 agents may prefer π to x², which contradicts A(r", T) > O. Thus anchor agents must be indifferent between IT and n², which yields that contains two coalitions C and C" such that C' 2 AUU and C" A'U
Define S C F; note that |S| > 0, as otherwise, π 'τ. Note that each guard agent b B has fewer friends in (b) than in x² (b) (and zero enemies in both) and thus prefers т to πτ, and so do the agents in S as well (they gain three friends each from U but lose all guards from among their friends when deviating to π). Let V be the set of agents in U who prefer π to n²; notice that
V = T.. : , E 3 such that ua E F by construction.
Then the agents preferring x to π are those in V while those that prefer x to i are those in B BUS
Hence, A(T", m) = IV| [B] - |S| > 1, which implies that
2 (2n 1) + S +1
(3)
Recall also that
< 3n and
V S 3/5),
(4)
because each agent in S has three friends in V. Taking the linear combination of these two incqualities,
we obtain that [V] s 2n + [8], and thus the three inequalities in (3) and (4) must all hold with equality. In particular, [V| = 3n and |S| = n, and the former implies V = U, that is, UF,E3 P3 = U.
Therefore, the set family S {E) F,, E S} is solution to the EXACT 3-COVER instance Ix3c.
remains to show that x is not popular, then there is no popular partition ı at all. For the sake of contradiction, assume that is popular. We have already proven that A(T,,*) 2 0 implies that assumption that x* & R,, also know that & is
must be of the form (2) for some S C F. FFB. By nonempty. However, then the switch F, A' U B JF 3 locally blocks for any agent F, E S, because all guard agents as well as F3 votes for it, whereas at most three agents in U vote against it. This shows that no partition other than x may be popular in
Next, we show that popular partitions may fail to exist even in symmetric FE game where neutral relations are not allowed and thus every agent that is not a friend of i is an enemy of i, i... the friendship digraph and the enmity digraph are complements of each other. This suggests that the intractability shown in Theorem does not stem from the possibility of neutrality.
Proposition 15.
There exists FE game with symmetric and with symmetric and enemy-averse) preferences that does not admit a popular partition.
(or, equivalently,
Proof. Consider the FE game I with symmetric and friend-appreeiaatie (or equivalently, symmetric and enemy-averse preferences on agent set N = 1, 6} where the friendship graph is a bidirected cycle of length 7: every agent E N considers both (i - 1) mod 7 and (i + 1) mod 7 friend and each other agent in N \ (i) an enemy. We claim that does not admit a popular partition.
First, the grand coalition nN = {N} is not popular, as A(x M =N > 0 for each agent é: even though i and both friends of i vote against the switch i - 0. all four remaining agents vote for it.
Second, if x is a partition such that there are at least four agents i N with Fr < 1. then A(T, xN) > 0, because these four agents prefer the grand coalition to æ. It follows that any popular partition must be of the form n = {[i), N {i)) for some i N. However, in this case, the switch (i + 1) mod 7 - (i) locally blocks T because all agents vote for this switch except for the agent (i + 2) mod 7: in partieular, A(T², o (T(++) mod ( > 0, contradicting the popularity
of .'. Hence, no popular partition exists for I.
22

---

Appendix B Efficient implementation for LocPop and LocStab
In this section, we present an efficient implementation of LocPop and LocStab that proves Theorem 3. Theorem 3 (+). LocPop can be implemented to run in O(n 3 log n) time (or ( log n) for FEN-B games) and LoeStab can be implemented to run in On log n) time.
Proof. Regarding the running time of LocPop and LocStab, it is clear that each step can be performed in (n))k) time even in asymmetric FEN games, where k denotes the number of coalitions in the
current partition: to check for each agent i E and each coalition C' E π J {0} whether i - C locally dominates or locally blocks, it suffices know the number of agents in C and in tTi) who regard i a friend or an enemy and of those whom i considers a friend or an enemy. As the number of such agents is most 2 each step can be done in [ + 1))(A) = (nk) time.
In the following, we show how our heuristics can implemented much more efficiently; we will focus symmetric FEN games due to their practical relevance. We start with a way to characterize when a switch i + C' locally dominates a partition x.
Lemma 16. Given a symmetric FEN game with a partition n, consider the following conditions for some agent i and coalition C C π U {0}:
(c0) fc ec 2 (()) =() +1;
(c3) 2fc cgc > =ffx()) "z(()) (c4)
(c1) fC cg 2 (()) (() + 2;
ft - 2ec > fa(s) 20
(c2) f*())= (0()) +12 fc eg 2 ST()
I is FEN-B FI-B/FEN-AF / FEN-AE game, then the switch i - C' locally dominates if and only if condition (c0) / condition (cl) V ((c2) A (c3)) / condition (cl) ((c2) A (c4)), respectively, hold.
Proof. Statement (b) of Lemma yields
A m.-c) = - S=(0) e0(0) vote:(T, m--)).
(5)
We first show that the respective conditions imply that + C' locally dominates π.
First, if (c1) holds, then A(T, TT-C) 2 2 vote,( ---c) (T. > 0 due to (5), so the switch i + C locally dominates even if votes against it, irrespective of the type of I. If I is FEN-B game, then (cO) already suffices to ensure that + C' locally dominates ग, because it implies vote, (T, T.-c) 2 1 by the definition of balanced preferences, which turn yields A(T, m.-cc 2 due to (5).
If (c2) holds, then ((T, Ti-C) 2 vote;(T, -i-cC due to (5) and, hence, it suffices to show that (c3) implies that i - C is Nash deviation under friend- apprrccicciiii preferences, whereas (c4) implies that i + C' is a Nash deviation under enemy-averse preferences:
Assume first that / is a FEN-AF game where (c2) and (c3) hold, but i C is not a Nash deviation. Then either f=()) = fC and e'(()) I E or fi()) > fc- The former case cannot happen, as contradicts (c3). Hence, we must have f=(0) 2 ft + 1; however, adding this inequality to fi()) (0)) + +12 2 fC cgc we get contradiction to (c3) again.
Assume now that / is FEN-AE game where (c2) and (c4) hold, but + is not a Nash deviation; our reasoning mirrors the previous case. Then either ex((() E and fi 2 for
or ed (()) < Ec The former case cannot happen, as it contradicts (c4). Hence, we must have e 2 (1())) + 1; however, adding this inequality fa() ex(()) l6 e get
contradiction to (c4) again.
For the other direction, suppose that i + C locally dominates i.c., A(T, (())) > 0. Then A_1 TT-C) 2 0; recall that A == fg E'c - fZ()) + E2()) by statement (b) of Lemma 1, so we get
(6) If A A- TT)) 2 2, then (c1) satisfied. Else, A-1(T, TC-C) E (0, which implies (c2), and we also get vote; (T, T..C) 2 0 due to (5) and the assumption that i - C' locally dominates æ. In
- de f7()) ex()-
23

---

fact, (T, = 0 is not possible, as that would mean f4()) - =x)) = - ATT, T(-c)= = 0 by (5); contradiction
- c' implying assumption that A(T, T--O) > 0. Therefore, C
must be a Nash deviation; using this, we now show that the required conditions hold.
For balanced preferences, this means that (5) implies A(T, TT-sC) 2 2 which, due to (5), implies (c0).
For friend-appreciaatng preferences, we get fc > fa(0 or SC = fa(1 and d' < (N))
taking (6) into account, both of these cases yield 2 - e/c 20a(0)) "x) i.e. (c3) holds.
For enemy-averse preferences, we get ec < e x(p or ec = c and fC > (a() taking (6)
into account, both of these cases imply fo 2cc > f*(0) 2c 7(i) (0)) i.e, (c4) holds.
This completes the proof of Lemma 16.
Implementation. Let us describe the implementation of heuristics LocPop and LocStab in detail.
The key idea is that for each agent i E N, we maintain two vectors x; and x; that are used to store the following values corresponding each coalition C E न {0]. The first vector stores the values z (C) = fC ec - ((()) + (x))) while the values stored in the second vector depend on the type of the game: If condition (c2) of Lemma 16 holds, then xt stores x (C) = 25c e' 2f7()) + S00 if preferences are friend-appreciattigg and (C) fC 2ec (a()) + 20)(() if preferences are enemy-averse, while we set (C) = oo if (c2) fails. For balanced preferences, the vector x? not used.
Notice that maintaining the values (C) and x2 for each agent and for all coalitions C [( for the current partition would suffice to determine whether there exists a switch i - C for some coalition C E æ U [0] that locally dominates or locally blocks æ, due to Lemma 16. However, is not hard to observe that it suffices to focus for each agent i E N on the set C2 of coalitions in x in which has at least one friend or enemy. Then is sufficient to maintain the values (C') and x²(C)
for each agent i only for coalitions C' E C² together with the values s: and m(()) Indeed, for every coalition C' E U {0} \ C' we know ef = ff = 0, and thus the values x!! (C) and (C) can be calculated easily: first, we have (C)
-f7(() + (a)) second, to determine x. (C),, we first check whether condition (c2) holds (using of j = 0 again) and set x² (C) -oc if (c2) fails and, otherwise, set (C) 2f + (6) in FEN-AF games and x²((C) = fi + 2e in FEN-AE games. Notice that the values x!! (C) and x. (C) therefore are the same for each coalition C in π U {0}} C'.
Therefore, the vectors x! and x are indexed by the set of all coalitions in C³ together with one dummy coalition representing all coalitions æ U [0} C².
To facilitate an efficient search for a locally dominating or locally blocking switch, we keep the entries in the vectors z! and of ordered. Furthermore, we additionally order the set X fa! vectors according to their first coordinates, and order the vectors in X = {2द i E N} similarly. Observe that the largest entry occurring in any vector of X 1 is therefore the first coordinate of the first vector in X and, similarly, the largest entry occurring in any vector of x is the first coordinate of the first vector in X². We will maintain this property throughout the algorithm; call it property (x).
N) of
The initialization. To initialize Ci and the vectors ar and x² for the starting partition To, we start by computing the values fö and e/c for all agents i N and coalitions C' E mo in which i has friend or an enemy. This takes (nnA) time in total for all agents using the friendship and enmity digraphs.
Next, we order the (A)) values in each of the 2n vectors X X2; this takes O(nA log A) time. Then we order the set X1 = {ar] : N) of vectors according to their first coordinates, and order On log n) time. The required running time for the initializations is therefore OnnA + nA log A + n log n) O(n logn) as 1 S A < n.
the vectors in X {a} : i E N) similarly
24

---

The computation of a step in the heuristic. We check if the largest entry in the vectors in X is least by looking the first coordinate of the first vector in (11) time. If yes, we have found a locally dominating switch i - C; note that if the coalition achieving the largest enty in X is a dummy coalition representing all coalitions in U (0) \ C' for some agent i, then a coalition ((A) time."
2 To maintain the vectors x; and ar as well as the sets C. for all agents E N, we only need to update these vectors and sets for the (A)) agents in {i U (i) U F(i) and, regarding the vectors, only at the coordinates corresponding to (i) and to C: note that this update may result adding a new coordinate to the vector or deleting one from it. Then, in order to maintain property (+), have reorder X' and X again- butt we do not have to perform a complete ordering from scratch; we just have to find the correct places of the updated elements in the already existing ordering. Hence, this can be implemented in ((A(lo A + log n)) time, as there are ( elements to update and an insertion of an element to an ordered list of length & can be done in (loo E) time.
C' E ι U {0} \ C can be found in O(CC))
If the largest entry the vectors of X is or 1, then we check the largest entry in the vectors of X² (recall that 2 stores nonnegative entry for coalition C' only if condition (c2) holds for i and C)) and check if the first coordinate is larger than or not. not, then æ is locally popular by Lemma 16. Otherwise, we again have found locally dominating switch; we then perform this switch and update the sets C' and the vectors in X and X2 in O(A log n.) time as in the previous case.
Checking whether i + C' is a Nash deviation for LocStab can also be implemented in the same running time. We just have to append the condition that improves to each case in Lemma 16, which is also a condition that can be checked in (1) time. In fact, we can redefine the values ar! (C) and x (C) to -o if has no incentive to join C. This way, remains true that the value of x! (C), and also of x? (C), coincides for all coalitions where i has neither friend nor an enemy; thus, our approach still works.
Summarizing all of the above, we get the running time of O(nA log n K #seps A log n.) where K #steps is the number of steps (i.e., number of switches) performed by the algorithm. Combining this with Theorem 2 proves Theorem 3.
"e can take C' = 0 unless we aim for a variant of the algorithm that keeps the number of coalitions constant: in this case, we can iterate over the coalitions of the current partition until we find one that is not in C* in O(A) time.
25

---

Appendix C Additional material for the simulations
We remark that all codes used for our simulations are available in the supplementary material files of our submission. In Section C.I, we present our simulation result for community detection in the form of some figures; we do the same for clustering in Section C.2. Finally, we present detailed evaluation of our results Section C.3.
C.1 Community detection: omitted figures
This section contains all figures depicting our simulation results for the Karate club (Figure 5), Jazz musicians (Figure 6), Cora (Figure 7), and Random-25 (Figure 8) datasets, comparing our heuristics LocPop and LocStab with the Louvain and Leiden algorithms terms of Rand index and modularity. As the Jazz dataset has no true labels, we did not compute the Rand index for it.
Index by Karate
Modularity by Method Karate
0.6
1.0
0.5
Wobulartty
0.8
0.2
0.4
0.1
LocPop
LocPop-Ld
Louesin
LocPop
LocPop
LocPop-Ld
Rand Inclex by Method Karate Club
Modulanty by Method Karate Club
0.4
0.8
10:25, 0.351
10.2, 0.
ModkJaiit
12.25, 0.35)
18.2. 0.2)
(0.4.0 0.4)
0.2
(2..000
0.6
Lauvain
Lukden
LocStab-5
LocStab-P
Lowwain
Latden
LocScab-5
LocStab-P
LocStabiud
Figure 5: Comparing Rand index (left) and modularity (right) of Louvain, Leiden, and LocPop (top) LocStab (bottom) variants for the Karate club dataset.
Modularity by Method on Jazz
Modularity by Method on jazz
B
AF
AC
0.3
10.23.031
(02.022
2.20022
(0:25, 0.351
0.2
(04.044)
0.2
(0.4.0.4
0.1
Lauvoln
Leidon
LocPop
Loc7op
LooPop-Ld
Louvein
Loiden
LocStelt-5
LocStabb-
LocStan-L
Figure 6: Comparing modularity of Louvain, Leiden, and LocPop (left) or LocStab (right) variants for the Jazz dataset.
26

---

Rand Index by Methed on Core
Modularity by Methed on Cora
0.8
8
0.5
AE
(02.022
Woduanit
0.6
10
2.00
10.5. 0.351
10
0.6
(0..0.4)
(04,0.4)
0.4
0.4
Laueoln
Leiden
LocP3p
LocPop
LocPop-Ld
Louvol
Leiden
LocPop
LocFop
LocPop-Ld
Rand Index by Method on Cora
Modularity by Method Cora
0.7
Wodularto
0.6
0.6
10.4,
0.4
0.4
0.7
Lounon
Leiden
Lox
LoxStal-P
Louvain
Loiden
Lox
LocStab-P
Figure 7: Comparing Rand index (left) and modularity (right) of Louvain, Leiden, and LocPop (top) or LocStab (bottom) variants for the Cora dataset.
by Method Random-22
Modularity by Random-25
0.925
Modkiantt
0.20
0.800
0.875
0.850
0.10
0.825
Leldon
P
Loctopddd
Leiden
Locfop-Ld
Rand Index Method on Random-25
Modularity Method Handam-25
0.950
AF
AF AE
0.925
AE
15.2. 0:21
Moduarryy
0.200
052.002)
0.900
10.25, 0.35)
[5.4 6.4)
85.25, 0.35)
(54.0.4)
0.875
0.15
0.850
Loursin
Leianh
LocScaD-5
1oc3tab-2
LocStab-ka
Louvsin
Leiden
LocStab
LocSpib-
LocStab-Lud
Figure 8: Comparing Rand index (left) and modularity (right) of Louvain, Leiden, and LocPop (top) LocStab (bottom) variants for the Random-25 dataset.
C.2 Clustering: omitted figures
This section contains figures depicting our simulation results on Iris (Figure 9), Breast Cancer Wisconsin (abbreviated as Cancer, Figure 10), Moons (Figure 11), and 3-Circles (Figure 12) datasets, comparing our heuristics LocPop and LocStab with the k-means and DBSCAN algorithms in terms of Rand index and silhouette score.
27

---

Rond Index by Method lris
Silhouetre Score Method on Iris
0.7
Sthouette Score
0.6
AE
0.8
002, 6.21
01. 0.21
00.25 0:35)
0.5
00.25, 0:35)
0.6
0.6
0.3
0.5
0.7
LocPop LocPopiP LocPop-ox LocPap-O
DBSCAN LocPop LocPop LocPop-OX
Rand Index by Method
Silhwuette Score by Method on lris
0.8
Sihouette Score
8
[02, 0.20
0.4
10:25, 0.351
12.25, 0.351
0.6
1044,00 0.4)
(C4, 0.4)
0.0
Kmeans
DBSCAN
LocStab-S LocStab- LocStab LocStaae-
Kmeans
CBSCAN LotStab-5 Plocstab
Figure 9: Comparing Rand index (left) and silhouette score (right) of k-means, DBSCAN and LocPop (top) or LocStab (bottom) variants for the Iris dataset.
Index by Method Cancer
Silhouette Score by Method on Cancer
0.75
B
0.70
AF
0.70
0.69
AAA
AAA
0.65
Sthovatte
0.68
0.67
0.60
0.00
0.55
0.55
Kimenn
CBSCAN
LacPop Loctop LocPop KM Lo:Pop-O
Kimcars
DBSCAM
LocPop LocPop P LocPop sN Loatop
Rand Index by Method Cancer
Silhouette Score Method Cancer
1.0
0.75
(0:2
0.21
Sthouette R
0.6
0.8
AE
(0.2.02)
0.62
0.4
0.60
0.2
0.0
Figure 10: Comparing Rand index (left) and silhouette score (right) of k-means, DBSCAN and
LocPop (top) LocStab (bottom) variants for the Cancer dataset.
Rand Index by Method on Circles
Silhouette Score by Method on Circles
0.8
0.5
0.7
Sihouette Scate
0.3
0.6-
[044,0 0.4)
1C.4000 0.4)
0.3
0.4
-0.1
DBSCAN LocPop-S
LocPop-P P LocPoc KM LocPop
Kmesns
OBSCAN LocPop Locfoo LocPop LocPap-O
Method Circles
Silhouette Score by Method Circles
AF
0.5
AF
0.7
Shoueete Score
0.4
0.3
0.6
(0.4, 0.4)
0.4)
0.2
0.5
0.1
0.4
0.0
Kmaons
DBSCAN
L
LocStab- Loctaab-
Kmaans
DESCAN
LocStab-S
LocStab-P Lo:Stab LocStabiD
Figure 12: Comparing Rand index (left) and silhouette score (right) of k-means, DBSCAN and
LocPop (top) LocStab (bottom) variants for the33-Cirche dataset.

---

Rand Index Method on Moons
Siloouette Score by Method on Moons
0.5-
1.0
Sirmatte Score
10.25, 0.35)
10.2. 0.2)
0.5
10.25, 0.35)
8S.2, 0
0.8
1044,00 0.4)
(54,000
0.4
0.6
0.3
Kimcons
DBSCAN
LocPop
LocPop-P LocPop KM LocPop D
Kimaans
DBSCAN
LocPop-5 LocPop LocPop- LacPop-O
Rand Index by Method on Moons
Silhouette Score by Method on Moons
0.6
1.0
Sihouette Score
[022, 0.20
0.4
(0.2,
10.25, 0.351
10 0.35)
0.8
10.4.00 0.4)
(0.4, 9.4)
022
0.6
0.0
0.4
6means
DBSCAN
LocStab-S LocStab-P LacStabb LocStaa-
Kmaans
DESCAN
LocStab-S LocStab PLocStab- KVLocStab-D
Figure 11: Comparing Rand index (left) and silhouette score (right) of k-means, DBSCAN and LocPop (top) or LocStab (bottom) variants for the Moons dataset.
C.3 Evaluation of results
General takeaways for LocPop and LocStab. LocPop and LocStab produced very similar results, although the scores of LocStab were more dependent on the preference domains. The best threshold parameters were also mostly the same for LocPop and LocStab. different preferences domains (AF, AE, and B) lead to quite similar results across all instances. This is probably due to the fact that only the agent who switches may vote differently in these cases, and single vote usually has no substantial influence. In the case of local stability, where a Nash deviation is needed, larger diffcrentiation was observed. The simulations also showed that-while no preference domain was consistently performing better than the two others the balanced one performed best or close to the best for both LocPop and LocStab. Hence, in light of Theorems and 4, have faster runtime guarantee, and it is the
LocPop variants, the three
using balanced preferences seems most preferable, only preference domain where the LocStab heuristic converges in polynomial time for asymmetric graphs. Hence, we suggest that future research focuses on the balanced preference domain.
In general, the -P and -S variants both performed well. However, the -S variant often requires much more steps to reach an outcome, which is expected, as it starts with n clusters. Hence, if there is good estimate (or even an upper bound) on the expected number of clusters, then the -P variant may be the optimal. The LocPop-P and LocStab-P variants implemented also had constraint that new coalitions could only be created if the current number of clusters was smaller than their predicted number.
In most cases, the (0.4, or the (0.2, parameters lead to the best results, but these parameters also often lead to the worst results; while the parameter (0.25, 0.35) performed consistently between them. This suggests that parameter tuning can have a large effect on achieving the best possible outcome.
Since LocPop and LoeStab are not deterministic (randomness comes from (i) the initial clustering. (ii) the indexing of the data points, and (iii) the choice of the implemented switches), we did 10 repetitions, each time randomly permuting the data points and with random initial partition with the predicted number of clusters for LocPop-P and LocStab-P (for the other variants the initial partition is fixed) to estimate the mean and standard deviation of the scores. The algorithm was implemented in way such that switches involving smaller-indexed agents were preferred, but by randomly permuting the indices, this bias was eliminated. The standard deviations observed were at most 0.01-0.02 on average after doing 10 repetitions, except for the Karate club dataset (~ 0.05). Hence, for that dataset, we increased the number of repetitions to 30 for more robust results. We also note that many cases, the standard deviations were too small to be visible in the figures (e.g.. 10 10-3).
29

---

lead to more efficient Comparison with mainstream algorithms. Let us compare the performance of our algorithms with the most widely used mainstream methods, both for community detection and for clustering.
Community detection. Using the output of Leiden, variants of LocPop-Ld (and LocStab-Lon Ld) achieved similar value in modularity, and slightly outperformed w.r.t. the Rand index. Hence, starting from the output of Leiden was very beneficial in terms of achieving better modularity scores. For the Random-25 dataset, LocPop-S and LocPop-S were able to significantly outperform Louvain and Leiden (by more than 10%) w.r.t. the Rand index, but LocPop-P and LocPop-S were close to a 10% improvement too. For the Karate club dataset, LoePop and LocStab variants were able to outperform Louvain and Leiden by more than 50% in Rand index.
Clustering, In clustering, with the parameter (0.4, 0.4), LocPop performed up to 20% better than k-means w.r.t. the silhouette score in the Iris and 3 Circles datasets (and performed similarly for the others), while the other parameters led to (sometimes significantly) worse results. DBSCAN performed the worst in terms of the silhouette score, and it often put all points together, in which case the silhouette score is undefined. Regarding the Rand index, (0.4, 0.4) turned out to be the worst parameter in general, which highlights that silhouette score may often not be the best measure to asses the quality of a clustering with regards to label prediction. This was most apparent in the Cancer dataset.
With respect to the Rand index, the best performing variants of LocPop and LocStab, which were the ones with the parameter (0.2, 0.2) (except in the 3 Circles case) were within 10% of k-means, often matching it, LocPop-P and LocStab-D outperformed it by roughly 50% for the Moons dataset (LocStab-P being close behind them, but all variants performed better than k-means), where DBSCAN was able to find the true clusters completely. As opposed to community detection, for LocPop. here we found no clear benefit of using the output of DBSCAN or k- k-means to start with, while starting with a correctly predicted number of random clusters helped significantly for the Moons dataset. With LocStab-D, D, starting with these outputs did lead to better results for the Moons dataset.
Summarizing our observations, we conclude that the variants of LocPop and LocStab performed well and consistently, often leading to the best results in both community detection and clustering.
Other observations, runtimes and outlook. For heuristics LocPop and LocStab started with the outputs of I Leiden and k-means, we tracked the Rand index between their initial partition (i.e., the output of Leiden or k-means, respectively) and the final partition. We observed that even these cases, both algorithms often made quite lot of changes. For LocPop, we observed an average Rand index-here used to measure the difference between the initial and the final partition-of 0.65 with a minimum of 0.33 across community detection datasets; for clustering datasets, these values reached an average of 0.55 with a minimum of 0.34. For LocStab, the obtained numbers were slightly higher, as expected. For community detection datasets, the average Rand index was 0.67 with a minimum of 0.33 and for clustering datasets, an average of 0.65 with a minimum of 0.43.
We also tracked the running times. Our LocPop algorithms run within a couple of seconds even on a mid-range hardware, except for Cora, the largest dataset, where computation took 3-5 minutes, LocPop-S and LocStab-S being the slowest as expected. For these variants, to speed up computation, we used random clusters of size 6, instead of singleton clusters, still modeling the same behavior. We emphasize that our implementation is not the most efficient simpler approach that iterates through the agents and the current clusters in each step. Furthermore, our approach to constructing the friendship and enmity graphs did not guarantee bounded degrees, causing a limitation, since then the running time in Theorem 3 are not guaranteed to be linear. For instances of even larger size, constructions that guarantee bounded degrees- e.g., taking the d nearest neighbors as friends and the d farthest ones as enemies for each computation. We leave this for future work.
discussed in Section 3, but
There are many more ways to generate friendship and enmity relations among agents, and it might be interesting to see whether there are approaches that lead to improved results. Further, another limitation is that LocPop might have a problem with instances containing clusters of different sizes, since large clusters can get rid of unwanted agents simply due to their voting power. It will be interesting to test this in future work. Finally, note that LoeStab might be a fix for those instances, since agents cannot be pushed out of cluster "against their will" (and maybe that is the reason why it performs better on the Cancer dataset).
30

---

Appendix D Omitted proofs
This section contains all proofs omitted from the main body of our paper, except for the proof of Theorem 3 which we proved in Appendix B. Sections D.I, D.2, and D.3 contain the omitted proofs of our results on FEN-AF, FEN-B, and FEN-AE games, respectively.
As already mentioned in Example 1, throughout this paper, all relations among agents that are not explicitly mentioned are tacitly assumed be neutral.
D.1 Omitted proofs for our results on FEN-AF games
Before we restate and prove our intractability results concerning FEN-AF games, we state some structural observations concerning AF-gadgets in Section 1.1.1. We then proceed to provide all omitted proofs our results on FEN-AF games in Sections D.1.2-D.1.4.
D.1.1 A structural lemma on A AF-gadgets
Given an AF-gadget G, let us define the distance of agents and j within G as the minimum number of arcs on a path from i to j or from j to within the friendship graph of Moreover, whenever an AF-gadget is defined over agent set K = {0, 1, 1,.... 2k the agent + c always interpreted as (i + c) mod (2k + 1) for each agent
K and constant integer c.
Lemma 17. Consider a FEN-AF game that admits a locally stable partition æ and contains an AF-gadget G over agent set K. If some coalition C. E with C C K contains two agents whose distance in is at least 4, then = K.
Proof. Note that any two agents whose distance in G is at least 4 are mutual enemies. Hence,
two such agents and] j belong some coalition C K, then each of them must have friend
in C: indeed, assuming that one of them, say agent i, does not have a friend in C, we get that the switch -> locally blocks æ, because i and i's enemies in C vote for it, while only i 1 may vote
against it. The distance between the friend of i and the friend of j (i.e.. agents i+ and j + 1) within G again least so by the same reasoning, each of them must have friend within C. Repeating
this argument, we get that every agent of C' must have a friend within C,, which implies K C C. By C K we get C K, required.
D.1.2 Proof of Theorem
Theorem 5 (+). The asymmetric FEN-AF game consisting solely of an AF-gadger admits no locally popular partition.
Proof. Consider an AF-gadeet of size 2k + containing agents 0, 1...., 2k. Suppose for the sake of contradiction that is a locally popular partition.
If π is the grand coalition, then for arbitrary agent i, the switch i + locally dominates æ, because (recalling that 2 5) exactly 2 - > agents vote for (those who consider an enemy) and only the two agents i and vote against it (as they both lose a friend). This contradicts the local popularity of n.
Thus π is not the grand coalition. By Lemma 17, this implies that for any two agents i and with (1) = T(j), the distance of i and j in G at most 3, so each coalition in i is a subset of {i,i L, 2, 3} for some agent i.
Suppose now that some agents i and + 1 is not in C. Then i i+1 1 has an incentive to join C, that is, i + 1 votes for the switch 1+1 C. and so does i. Since the distance between any two agents of C' is most 3 in G. there can be at most one agent in C' who considers + 1 an enemy, namely agent votes against the switch + + C, and note also that no agent 7(i + 1) votes against it. Hence, contradiction. This shows that each coalition in a must either contain most four agents who, additionally, appear consecutively on the friendship cycle of G, or must be of the form {i, + 3} for some i.
are both within some coalition C = 7(i + 22, but
1. Thus at most one agent in C
i i+1 + C locally blocks
31

---

If there is coalition of the form { + 3), then the switch i + - . + 4) locally blocks π. as both as i + 3 vote for and the only agent who may vote against is +
there is a coalition containing four agents {ł, 1ii,,1it i+2, i+3), then again, the switch i+3 - x (i++4) locally blocks the only agents who may vote against it are + 2 and + 7, whereas agents i + and + 3 all vote for it.
Therefore, every coalition must contain at most three agents who appear consecutively the friendship cycle of G. Suppose there is a coalition with exactly three agents. Then, as does not divide 2k + 1, there is one coalition, say { (2, 1, 2), which is followed (along the friendship cycle of G) by a coalition of size two, namely coalition {z + 3, i + 4}. Then the switch + 2 - (i + +) locally blocks as agents i and i vote for it, and only agent i + 1 votes against it.
Hence, each coalition contains at most tWo agents. If there is one containing exactly two agents, then there is one coalition, say {i. + },, which is preceded (on the friendship cycle of G) by coalition of size one, namely {i ( 1]. as 2k + odd. Hence, the switch blocks It follows that each coalition in must be singleton. But then the switch where any agent i joins {i + } locally blocks n, again a contradiction. It follows that no locally popular partition exists for this hedonic game.
1 - {i. i + 13 locally
Note that for the hedonic game defined in the proof of Theorem 5, there does exist a unique locally stable partition: the grand coalition containing all agents. In fact, the proof of Theorem 5 even implies the following slightly stronger claim.
Remark 1. Suppose that a hedonic game with friend -ppreccapeee preferences contains an AF-gadget over agent set K, and admits a locally stable partition π. If no coalition of i contains agents both in and outside of K, then K itself is a coalition in π.
D.1.3 Proof of Theorem 6
Theorem 6 (+), There exists an asymmetric FEN-AF game that admits no locally stable partition.
Proof. As a counterexample, consider a FEN-AF game that contains an AF-gadget over a set K (0,,,.... 2k} of agents together with additional set A {ai...., a2x-1} of agents such that
01:...; 02k are mutual enemies with 1,2,..., 2k 1,
02:.... 02k consider 0 an enemy,
0 considers d1 a friend and 02, a2k enemies,
d and d2 mutual friends, and
a; considers a:+1 a friend for ........22 5.
Suppose that π is a locally stable partition for I. First, we claim that if coalition C E л contains both an agent from K and an agent from A, then C contains 0 as well. To see this, consider the "largest" agent j = maxiieknn of K in C. If 0 & C, then the switch j - 0 locally blocks π, because agent and all agents in AnC + 0 vote for it, while at most one agent (namely, agent 1) may vote against it.
Next, we claim that if some coalition C' E contains both 0 and a, for some i, then C also contains 4+41 if it exists. For i 1, this follows from the fact that, otherwise, d₁ has an incentive to join (T22), both 0₁ and d2 vote for the switch 0₁ + (aa) and only agent 0 votes against it (note that only agents in K consider an an enemy, and we have K n π (az) = 0 by the previous paragraph), contradicting that if a & C, then the switch a; + π (a:41) locally blocks n: both a; and vote for it, and only agent a may vote against it.
assumption that is locally stable. For i > 1,
similarly show
As consequence, no coalition æ contains both an agent from K and an agent from A. Indeed, assuming otherwise, the coalition C' would contain agents 0 and 02k-1 by the previous two claims,
32

---

in which case the switch a2k-4 + 0 locally blocks т. both d2k-1 and 0 vote for it, while at most one agent (namely, agent d2k-3) may vote against
Due to Remark 1, it follows that the agents of K must form a single partition in æ. In particular, agent 0 has one friend and 2k: enemies within r0)). Also, agent 0 has at least one friend and at most 2k - 5 enemies in the coalition T(a1). so 0 has an incentive to join T(a1). Finally, the switch + (ai) locally blocks т,, because 2k + 1 agents from K vote for (namely, agent and all those regarding 0 an enemy), while only one agent from K (namely, agent 2k) and 2k: - 5 agents from (all of them except a1) vote against it. This contradiction shows that π cannot be locally stable.
D.1.4 Proof of T'eeorem
Theorem (+). POOCAL-POULLARIYYEXIIIIII complete for FEN-AF games.
and
are NP-
It is clear that both problems are in NP, as given FEN-AF game, we can nondeterministically guess a partition и and then verify in polynomial time that no possible switch locally dominates or locally blocks æ (note that the number of switches for is most quadratic in the number of agents). We WEI--SSABBLIIT--EEEE separately in Theorems 18 and 24, starting with the former. is NP-hard for FEN-AF games.
complete the proof of Theorem 7 by proving the NP- NP-hardness of and DOCAA--PPUULARRTY-EXISSISS
Theorem 18.
Proof. We provide a reduction from 5-SAT which, given a Boolean formula yp in conjunctive normal form with five literals per clause, asks whether yo is satisfiable. Let y be input S-SAT formula with variables U1..... 2n and clauses C1...., Cm- By adding dummy clauses if needed, we may assume that
1 mod 3 and that m mod 2.
We create an instance of LOCAL.-
as follows. Let = 5 11m 55m; then A: = 1 mod and A: = mod 3 For each clause Cj. we create clause gadget G, that is an AF-gadget of size k. The agents of Gj, ordered along the friendship cycle of Gj. are æ²... zz...., 2 555m 55mm1 Every 11m-th agent 2f..2)1.m a.a. 22 274m clause C (l V... V...V 1jz):
along this cycle corresponds one of the literals in the these are called literal agents. We also add set Ai...., Asm of 5m auxiliary gadgets, each of them an AF-gadget of size k = 55m. Each auxiliary gadget A, has single distinguished agent 0. we refer to such agents as enforcer agents. We also add an agent T. Intuitively, in locally stable partition, the coalition containing T will also include literal agent from each clause corresponding to a true literal. We proceed by describing the relationships between the agents on different cycles:
Every literal agent considers friend and is considered by an enemy.
Every enforcer agent considers T friend but considered by T as neutral.
T and every non-literal, non-enforcer agent consider each other mutual enemies.
Any two agents and from different clause gadgets are mutual enemies, unless y and z are both literal agents that do not correspond to positive and a negative literal of the same variable, in which case they are mutually neutral.
Any two agents y and from two different auxiliary gadgets are mutual enemies, unless both are enforcer agents, in which case they are mutually neutral.
Finally, for a vertex x from clause gadget and a vertex from an auxiliary gadget,
y is not literal agent or z is not an enforcer agent, then they are mutual enemies; - if y is the literal agent corresponding to the f-th literal of the j-th clause, then and mutual enemies if 2 ag ((j-1) e)+ and they are mutually neutral if is enforcer agent other than d 95g--1++*
This completes our construction of the instance of DOOAAT-STABLLTY-EXSTEEEE from the given 5-SAT instance sp. It remains prove the correctness of the reduction: / is yes-instance
33

---

of LOCALLSTABILLTYY-ENE EXIISEENE if and only if yp is satisfiable. This will follow from a series of claims.
Direction "="; Let us first assume that there exists a locally stable partition и for J.
Claim 19. Coalition xt (T) contains at most 20m agents. Consequently, (T)) cannot contain all agents from a clause or an auxiliary gadget.
Proof of claim. For a contradiction, suppose that more than 20m 1 agents in the same coalition as T. Then at least 10m of them are mutual enemies of T, as only 10m agents consider 7 a friend, and agent considers 7 neutral. Recall also that T considers no agent friend and thus has an incentive to leave क (T). Hence, the switch T + & locally blocks π, a contradiction.
Claim 20. No coalition
can contain all agents from some clause or auxiliary gadget.
Proof of claim. For the sake of contradiction, assume that some coalition C. contains some clause or auxiliary gadget K. Claim 19 implies C # (T)). Let y a literal or enforcer agent in K. Since has one friend and exactly 55m enemies within K, y has an incentive to join T(T) by Claim 19. Thus the switch y > π (T) locally blocks æ:: at least (55m 5) + agents- all enemies of y within K and y itself-vote for it, whereas at most (20m- 1) agents-enemies of y in π (T) and the unique agent in K who considers y a friend-vote against it, a contradiction.
Claim 21. If a coalition C with T & C contains agents from two different clause auxiliary gadgets, then C cannot contain a non-literal, non-enforcer agent.
Proof of claim. Suppose for the sake of contradiction that C with T & C contains some agent y from a (clause or auxiliary) gadget K, some agent y' from a different gadget K", and a non-literal, non-enforcer agent w. Note that neither K nor K' is fully contained in C due to Claim 20. Therefore, using also I" & C, we get that C' contains an agent E K and an agent z' E K' such that neither nor z' considers any agent in C7 friend. Morcover,
mutual enemy with some z" {2, 22, This implies that the switch z" - 0 locally blocks ग, because both 2" and w vote for it, while at most one agent (who considers z" a friend) may vote against it, contradiction.
Claim 22. Coalition x contains at least one agent from each clause gudget and each auxiliary gadget.
Proof of claim. For contradiction, suppose that (T) contains no agent from some clause or auxiliary gadget K. If no agent from K is contained in the same coalition as some agent from a different gadget, then Remark implies K E π, contradiction coalition that contains some agent y from K and some agent from a different gadget. By Claim 21, get that y is either a literal or enforcer agent. Suppose that literal agent y x² for some clause gadget K = G; the case when K is an auxiliary gadget and y is an enforcer agent is analogous.
Claim 20. Hence, there is
Note that 2f+1 is the only agent 2t considers a friend, while the only agent who considers z} friend is G2 Since both Gr and 2f/t are non-literal, non-enforeer agents, neither of them is contained in C due to Claim 21. In particular, xrj has an incentive to join x (xr))) Since the switch 2) x (x)+t)) cannot locally block n, we obtain that there must be some agent in 7 (xa)1) who considers ærj, an enemy. Observe that T & (x( by our choice of K Gj. so by Claim 21 we know that all agents of (z, belong to Gj. Using Lemma 17 and Claim 20, we get that ((a(t)) cannot This implies i+1), )), so the agent within π ((att)
contain two agents whose distance along G, more than 3; we refer to this fact as
e (1 who considers æ² an enemy must be _ or =;) Moreover, (x/- .xy ++44 E <<rst also follows. We distinguish between two cases and arrive at contradiction in both, which proves the claim.
2, i 3, + 43 for every agent x E (
-1111 due to If oy i+1 has an incentive to join क ( Since the switch u)
$ (x))t)), then (xa)t2 does not locally block but both 2)- and 21-² vote for it, it follows that at least two agents must consider 2; an enemy
Case A: 23 E ((a)t)). Then 7 (aa++))
(x)
in T (z))t)) However, due to these agents could only be 2 i-1 and 2,4 but they cannot both be
34

---

in (x))²)) a contradiction. Thus it must be the case that π ((z)t1)- = {2) 2 1-1
; 2
Then a
has an incentive to join =(a)+)); recall that T & x xaxf), so æ² has no friend in (x Observe that the switch æ/ - (x]]t) locally blocks w: both or and af vote for it, but only "3 votes against it, contradiction.
Case B: = E ( Then <( ((a)tt) S (zftt " , a { 2tt)). Then 2j has an incentive to join Tt so both aj-1 and my vote for the switch 2/ + m(a)tt). Since 'T locally stable, there must be two agents who vote against this switch. If ++3 & x(2)+)), ) then these must a
be two agents in ((z) who consider 2²/t an enemy. Due to ), these can only be agents a/++ and 2iits, but at most one of them can be in TT (22)+9), contradiction. Hence, 224 E (aa)t)). Since the switch of+² - ((x) does not locally block æ, it follows that x//² T(a)t)) as well, which yields {x]=( :2) , .2y .
242 i+3 1m4 E т. Then the switch 25/t + T(2)+ locally blocks т, because 1+2 and zr) 1r)-d) vote for it and at most two may vote against it (z/+3 and possibly 2 ), contradiction.
three agents (namely, 23 zij
Claim 23. Coalition x (T) contains no non-literal, non-enforcer agents. Also, each literal agent in xt (T) can have at most one mutual enemy in π (TT), which is necessarily an enforcer agent.
Proof of claim. For the sake of contradiction, assume that y + T is a non-literal, non-enforcer agent in x (T). Take agent rTT) from clause Gj not containing y such that the unique friend of within K is not in (T)) By Claims 22 and 19, there must be such an agent 2. Note that y and 2 are mutual enemies. If is not literal agent, then z has friend in π (7)), the switch - 0 locally blocks ग, a contradiction. If = x is a literal agent, then 2 is mutual enemies with every agent from at least one auxiliary gadget by construction, so has at least two mutual enemies in π (T').
It now suffices to show that the assumption that has at least two mutual enemies in π (T') leads to contradiction.
Assume first that z has an incentive to join . ((z))t). Then z²., T, and the two mutual enemies of a² in πt (T) vote for the switch z/ - x (xa)t1) and at most one agent in (T) votes against it. Moreover, due to Lemma 17 and Claim 20, each two agents in (xa)+)) )
are at distance at most 3 from each other along Gj. and thus the only agents in (xa)t) who consider 2² an enemy can be xj-2 and artt1 so fewer than four agents vote against the switch, a contradiction.
It follows that zy has no incentive to join π (xx)+)), which happens only if oj regards at least two agents in I mafttl
enemies. This implies that (aaftl) contains at least two agents from (aftt t+ saj x.t)). As x is locally stable, it follows that (att?
, , ,25t3) S (aftt)) Sup- pose that wftd E x(aft)) well. Then the switch xft + x(x]+5) locally blocks т, because atta, , agt?, and wift all vote for it, whereas only a 43 and witt may vote against it. Oth- erwise, x(aft))
af42 , 1443). The switch or) m(aft)) locally blocks v unless (aftt) = {afts 45 666 447 2. j. In this case, however, the switch wits + mur5tp) locally blocks by the argument used in the previous case.
(aft1 a
We are now ready prove that yp is satisfiable.
By Claim 22, at least one literal agent from each clause gadget Gj must be contained in (T'). We claim that the corresponding literals can be set to true at the same time. For a contradiction, suppose that there are two literal agents, y and z, in π (TT) such that one of them corresponds to literal v; and the other one to its negation F. By Claim 23, ag E (T') for any auxiliary gadget Ay, which means that every literal agent is mutual enemies with at least one enforcer agent in π (T). Since and are also mutual enemies by construction, each of these two literal agents have at least two mutual enemies, which is a contradiction to Claim 23. Hence, &o is satisfiable.
Direction " Let us now assume that y is satisfiable.
Consider a truth assignment that makes y true. Create a partition " as follows. For each auxiliary gadget Aj. group sy together with T. Also, from each clause gadget, choose literal agent r)
35

---

corresponding to true literal and group it together with T, too. Finally, for each clause or auxiliary gadget K, create coalitions of size two from the agents of K not put into TT²") such that each of these coalitions contains two agents appearing consecurively on K.
We claim that is locally stable. Agent T has an incentive to join every coalition C' in U {0) other than π (T).. However, at least 6m agents vote against such a switch '' + C² and at most one votes for it. Note that literal or enforcer agent in (T) has one friend in π (2") ) and at most one enemy: Indeed, each enforcer agent is mutual enemies with exactly one literal agent-which may or may not be xTT) and vice versa; moreover, two literal agents are mutual enemies only if they correspond to literal V; and its negation U respectively. This, however, cannot happen, as only literal agents corresponding to true literals are in x (T)). Since each literal or enforcer agent has at most one friend in every coalition C' & (T"), and if they do have a friend in C' then they also have an enemy in C, so they have no incentive to join C.
For a non-literal, non-enforcer agent y. let [v: y') denote the coalition (t)) On the one hand, if regards y' as a friend, then y has incentive to join any coalition in π (9). If, on the other hand, y regards as a friend, then y has an incentive to join the unique coalition containing its sole friend y". but the switch y + (yy") does not locally block म, because only y votes for it but y votes against
We conclude that π is locally stable, proving the correctness of our reduction.
We now turn to the existence problem for local popularity and its computational complexity. Theorem 24.
is NP-hard for FEN-AF games.
Proof. We again provide a reduction from 5-SAT by slightly modifying the reduction presented in the proof of Theorem 18.
Let yp be 5-SAT formula with variables u1,.... Un and clauses Ci...., Cm. By adding dummy clauses if needed, we may again assume that m mod 3 and m. = mod 2.
From o we create an instance T of LOCAL- WEW.IAARRRYY-EEEENCCEEEE EXISTENCE as follows. Again, let set k == 1-mm = 55m; then k = 1 mod 2 and A = 1 mod 3. For each clause Cj. we create clause gadger Gy that is an AF-gadget of size k. The agents of G, are again referred to as z). ......... 22 555mm1 ordered along the friendship cycle of Gj. and every 11m-th agent 2). xr]
23 2d along this cycle corresponds to one of the literals in C, = (L,, V V V1,)). These are again called literal agents. Note that we do not create the auxiliary gadgets and enforcer agents used in the proof of Theorem 18, but we do add an agent T. As before, locally popular partition will always group T together with an agent corresponding to a true literal from each clause. We proceed by describing the relationships between agents different gadgets:
Every literal agent considers T friend, whereas considers everyone an enemy and is considered an enemy by every non-literal agent.
Furthermore, two agents and from two different clause gadgets are mutual enemies, unless y and are both literal agents that do not correspond positive and a negative literal of the same variable, in which case they are mutually neutral.
We are going show that the constructed instance I of LOCAL-POPULARITY EXXISTEECE admits locally popular partition if and only if &p is satisfiable.
Direction "="; Let us first assume that there exists a locally popular partition for I. Claim 25. No coalition C E x may contain all agents from some clause gadget.
Proof of claim. For contradiction, suppose that coalition in π contains all agents of clause gadget Gy. Then the switch 2 + @ for an arbitrary agent x in G, locally dominates π,, because at least 55m. 5 agents vote for such a switch and at most one agent votes against it, a contradiction.
Claim 26. If a coalition C E n with T & C' contains agents from two different clause gadgets, then C cannot contain a non-literal agent.
Proof of claim. Exactly the same arguments used in the proof of Claim 21 prove the claim.
36

---

Claim 27. Coalition (T)) contains at least one literal agent from each clause gadget.
Proof of claim. For a contradiction, suppose that there is clause gadget G3 that contains no agent in π (T). If agent of G is in the same coalition some agent from different gadget, then cannot be locally popular, because we have shown in Theorem 5 that an AF-gadget does not admit a locally popular partition.
By Claim 26, it follows that there must be a literal agent zj in Gj such that C' I T<²)) contains only literal agents, with at least one of them not in Gj. By T & C, we know that zy has an incentive to join ((x))t). Hence, as no agent considers zfj a friend in C, there must be an agent in T(a)*) who considers ur} an enemy, as otherwise, the switch 2) + ((a)t) locally blocks x. Note that T $ (xc)+t) by our choice of Gy. and since uit a non-literal agent, we know that ((x)t) S Gj by Claim 26. Therefore, by Lemma 17 and Claim 25, we know that all agents in π (2))" +1) are at distance at most from =r]t allog Gy. Hence, the agent in (xx) 1 who considers 2) an enemy
must be x 2-2 or 2z)- and they cannot both be contained in π T (z)) Distinguishing between the cases 2) E π ( and 2 2:444 E π ( and using exactly the same arguments in Cases and B in the proof of Theorem 18 we obtain contradiction to the local stability and, hence, to the local popularity x.
We are now ready prove that yo is satisfiable.
By Claim 27, π (T') contains at least one literal agent from each clause gadget. We claim that the corresponding literals can be made true at the same time. For contradiction, suppose that there are two literal agents, y and 2, corresponding to some variable v; and its negation 7. respectively, that both in T (T)) Then y and as both T and x vote for it and only y votes against it, a contradiction. Hence, this yields a truth assignment satisfying yp
mutual enemies. Hence, the switch y - 0 locally dominates
Direction "="; Assume now that there is truth assignment satisfying yp.
Create partition π as follows. For each clause gadget G,, choose literal agent corresponding to literal set true and group it with T. Then for each clause gadget K, create coalitions of size two from the agents of K not put into ((') such that each of these coalitions contains two agents appearing consecutively on K.
We claim that π is locally popular. Let C' E π U (0]. Note that the only agent who may vote for a switch T + C is T, while at least agents vote against it. For literal agent z². (T)), the only agents who vote for a switch zi + C can be T and possibly agent zz-1, while z² itself votes against it, and moreover, if anj C votes for the switch, then -/j-² E C votes against it. Hence, 2². C does not locally dominate æ. For an agent y in coalition {a), 2. _1+11 E T of size two, only one agent may vote for the switch y C. and this happens only if either y 2f+1 and y has friend in C, in which case zr votes against the switch, or if y = z and C= (a) 1- -n-1), in which case both at 2 and nf vote against the switch. Hence, no switch locally dominates so a is locally popular, which completes the proof of correctness for our reduction.
D.2 Omitted proofs for our results on FEN-B games
We start with restating and proving Theorem 4, stating the polynomiality of LocStab on FEN-B games, in Section 1.2.1. We move on with some structural observations concerning B-gadgets in Section D.2.2. We then proceed to provide all omitted proofs of our results on FEN-B games in Sections D.2.3-D.266.
D.2.1 Polynomiality of LocStab
Theorem 4 (x). In a possibly asymmetric FEN-B gume, the total balanced utility of all agents strictly increases in each step of heuristic LoeStab; consequently heuristic LoeStab always converges in O( steps to locally stable partition, irrespective the initial partition.
37

---

Proof. Let N denote the set of agents. Consider a step of the heuristic where a partition π is replaced by - for some agent i and coalition C' [ is such that C'(fi} >5 (t) and A(T, ks-c) 0. As A(T, Ti-c) > 0 we have A- (-, mi-c) 2 0. So, by statement (a) of Lemma 1,
Σ
(T)-)) (T(T)) (T) = A A - 2 O.
JENUO
Finally, u. (C( 10---- (T))) > O because the switch is performed by heuristic LocStab based on the condition that it is Nash deviation, i.e., i has incentive to join C' (recall that preferences are balanced). Hence, f(TI-=c) - f(z) = EjeN (²(T:-c) - u²((T) ) > 0, which proves the first
statement of the theorem. Since the total balanced utility is between -nA and nA, the claimed
bound on the number of steps follows as well.
D.2.2 A structural lemma on B-gadgets
Let us say that coalition C' in a B-gadget over agent set K = {0, (0.1.....66 .6} is consecutive if C' = { 1...,,..,, L} for some integer 8 [6].
Lemma 28. Let be a partition for B-gadget, and let C be a coalition with either |C| 2 4, or |C| = 3 and C' is not consecutive. Then + 0 locally dominates π for some agent E C.
Proof. Let ı be partition for the B-gadget over agent set K {0, 16, and let C' E w. If C is the grand coalition, then i + @ locally dominates ग, because i, i 2, 3, and i + all vote for it, while only
and
vote against it.
4 |C| < 6, then let E C be an agent such that i 1 C' and, if C' is not consecutive, then (i, 2} & C: observe that such agent i exists. Consider the switch i - 0. If - C. then at least two agents in {i + 2, + 3, i + 4} NC vote for this switch, while + 1 is indifferent between и and Tz-6-- Hence, even if 1 votes against it, get A(T, m=- 2 1. If 2 E Cnd C consecutive, then C = K {i - 1}. in which case agents i, i 2, + and i + 4 all vote for the switch - 9. and only i 2 votes against it. If i 2 E C but C is not consecutive, then due to our choice of i, we know that C' does not contain both i + 1 and i + 2, and thus få = 1. implying also ec 2 2 (because |C| 2 4 and - 1 & C). Hence, i has an incentive to join Moreover, at least one agent in (i + 2, 3, + 4} n C' votes for i + 0, while only i 2 votes against it. Hence, get (T, 00) 2 again, which means that + locally dominates म, as required.
It remains to consider the case when |C| = 3 and C' is not consecutive. If [ú,j. + +1 S C for some agent J. then j & (i - 2 1, 1}. If E (i + 2, i + 3). then both j and j + regard as an enemy, and thus they both vote for the switch i 0. If j
+ 4, then both i and i the switch + 0. Hence, we get A(T, nT-0) 2 1 in both cases. Finally, [j.j + 1} g C for any agent) j E K, then C' must be of the form (i, + 2, i 4) for some i E K. Then both i + 2 and i + 4 vote for i > 0. yielding again a switch that locally dominates I.
vote for
D.2.3 Proof of Theorem 8
Theorem 8 (+). The asymmetric FEN-B game consisting solely of a B-gadget admits no locally popular partition.
Proof. Assume for the sake of contradiction that π a locally popular partition for the B-gadget over agent set K = {0, 1, 1,..., 6). By Lemma 28 we know that π contains no coalition of size more than 3. and morcover, all coalitions size 3 must be consecutive. If πT contains a nonconsecutive coalition C of size 2, then C² must be of the form {i, i + 2). otherwise, its two agents mutual enemies, and thus either of them switching to 0 locally dominates æ. We may further assume that - 1 1 i + 1) (as otherwise, we can pick the coalition {i 1, + 1} instead of C); hence, either (i + 1) is singleton in x or (i + 1, +3 E x. Consider the switch i + > л(1 + 1): both é + and vote for it, while only votes against it (note that i + 3 is indifferent between ' and 7 Hence, this switch locally dominates π, a contradiction that shows that all coalitions in x must be consecutive.
If C (i, + 1} E n, then both and + vote for the switch i + - C, and only i (but neither + 3 nor i + 4) may vote against it, contradicting again the local popularity of क. Thus x can
38

---

only contain singletons and (consecutive) coalitions of size 3. If and i+ 1 both form singletons in Rt, then i has an incentive join {i + 1], and + does not vote against it, so i + {i + 1 locally dominates л. Hence, the only remaining possibilityy is that contains a singleton and two coalitions of size 3, say {i - 3, 2, i 1} and (i. i 1, 2] for some agent However, in this case the switch + (( 1) locally dominates v, because agents i 1, 2, and + 2 vote for it, while only and i 3 vote against it. This contradiction completes the proof.
D.2.4 Proof of Theorem 9
Before proving Theorem 9, we start with simple lemma that gives the bases of our reductions for Theorems 9 and 11.
Lemma 29. Consider a FEN-B game containing three special agents, $1, 82. and 83. a set D1 DD D3 of dummy agents, and a set A of vertex agents with |D]] = | = |D3] 3] For each i [3]. let D D; U { and let the friendship and enmity relations in I be such that
every agent in D regards all other agents in DJ a friend and regards every remaining special or dummy vertex a friend, and
vertex agents are mutually neutral with every dummy agent.
Then every locally stable partition π. contains three coalitions, C1, Cz. and Cz, such that D C C. for each E [3].
Proof. First, assume that there exists a coalition C such that C. contains agents both from D and DJ for some indices + j; we will call such coalitions mixed. Pick an index such that |Dt aphncl S DDJ nCI. If DJ+ nC DCC contains a dummy agent d, then the switch d -> 9 locally blocks æ, because all agents in DJ well as d vote for it, while only the agents in D {d} vote against it; contradiction. Hence, we know that C n DJ = {s:}. In this case we must have [C'n D S |A], as otherwise, s; + locally blocks n, because only vertex agents in C may vote against it, while all agents in D as well as s; vote for it. Thus each mixed coalition C' contains dummy agents from at most one set Dj among D1, D2, and D3 (and then must contain special vertex other than 8y), and moreover, a mixed coalition can contain at most |A| agents from DJ.
Fix some index j E [3]. and assume now that there are coalitions C' and C" in x such that both contain agents from Dj. IC DJI S IC' n DJt. and C' is non-mixed. Let us pick an arbitrary agent d E CCDD.. Then the switch d C' locally blocks n, all agents in (C' n DD ) U {d) vote for it, while the only agents who vote against it are those in (C" This contradiction shows that there is at most one non-mixed coalition that contains agents from Dj. and moreover, it contains fewer agents from D than any mixed coalition containing an agent of Dj-
) \ {d) because C' is non-mixed.
If i contains at least one mixed coalition C' with CnD, A 0. then the unique (or possibly nonexistent) non-mixed coalition that contains agents from D, must contain fewer than |A| agents from DJ. However, since there can be at most two mixed coalitions containing agents of D, (as each of them must contain a special agent other than 8j). we obtain that a total of at most 3/A| of D, can be contained in coalitions of m, contradicting |D,l 3) A). This proves that there agents mixed coalitions containing agents of D, and hence all agents of Dú must be contained in a unique non-mixed coalition Cj. Note also that 8y E C, follows, otherwise, 8j Cj locally blocks This proves the claim.
Theorem (x).
NP-complete for FEN-B games.
Proof. It clear that this problem is in NP, as given a FEN-B game, guess a partition π and then verify in polynomial time that no possible switch locally dominates π (note again that the number of switches for is most quadratic in the number of agents).
nondeterministically
To show NP-hardness, we reduce from the NP-hard 3-COLORRING problem: given an undirected graph G (V, E), the task is to decide whether G admits a coloring X : V + [3] that is proper, i.c.
39

---

there is edge {u, 2 E with x(u) = x(v). We will call a proper coloring tight if each vertex has two neighbors whose colors differ from each other.
Given an instance G = (V, E) of 3-COL.ORING, we start by creating a graph H as follows: for each vertex V, we add new vertices v², v², and y G forming triangle, and connect v and u² to by an edge. Observe that a proper coloring of G can be extended into a tight coloring of И and, in fact, every proper coloring of I is tight. Let H (V', E") denote the constructed graph and let - [V].
Next, we create FEN-B game / based on H follows. We introduce set D1 D2 U Da of dummy agents with [1 = [2] D3 = 21n, three special agents, $1, $2, and 83, and for each vertex E V", set A. {u, {0, i,... ................................ 6}}
} of seven vertex agents who form a B-gadget. We will use the notation DTT D, U { for each E [3]. the set of agents is N User3) DJ U.lvv A
The remaining relationships between the agents are as follows:
For each i [3], every agent in D considers each other agent in D friend and every remaining special or dummy agent an enemy.
Two vertex agents, u, E Au and oj E A,, are mutual enemies and only if {w,, 0j} E"; otherwise, they are mutually neutral.
Each vertex agent is mutual friends with every special agent and mutually neutral with every dummy agent.
This completes our construction of the instance of given 3-COLORING instance G. We are going to show that the constructed FEN-B game I admits a locally popular partition if and only if G admits a proper 3-coloring.
from the
Direction " Assume first that there exists locally popular partition for T.
Let us fix an arbitrary vertex the set of all coalitions C' E π with C' C, # 0. Let Lu be the FEN-B game comprising solely of Av, and let n/"" = {C' A. : C' E C denote the partition for I, that can be thought of as the projection of π onto A,. Let the level of coalition C E C. be
V and consider the corresponding B-gadget on A.. Let C. denote
lev(C) = (u:) (C \ A.) (B(ss) n (C A.))
for an arbitrary & E A. note that this notion is well-defined, as all vertex agents in Ag have the same friends and enemies outside A,,
Observe now that 7 satisfies the conditions in Lemma 29: hence, as is locally stable, we get that there exist coalitions C1, C2 C3 E и such that D C C2 for each i E [3]. Since vertex agents in Ag regard only special agents friends outside A., it follows that the level of any coalition in C, is at most 1.
Claim 30. Each coalition C C. has level at least 0.
Proof of claim. For the sake of contradiction, assume that C' E Cp has level at most 1
If C' satisfies the condition of Lemma 28 (i.e., either |Cn.,pl > 4, |C'n = 3 and Cn not consecutive), then we know that there exists an agent v; C n A. such that the switch v; - Notice that agents in A, \ {ea} do not consider their relationships outside A, when voting for or against the switch v, + 0. so they vote the same way in I as in I,.. Moreover, we have
vote,, (π,, +o) 2 vote,, (x -v (
because vi has more enemies in C A than friends (since C has level most -1). Finally, both friendship and enemy relationships between two agents who do not belong to the same B-gadget are symmetric, so we know that
Σ aEC
vote, (TT, Te, Te. -le((C) 2 1.
Summing up all these insights, we obtain that A(T, -T) 2 llee((C) 2 2, contradicting the local popularity of x.
40

---

Assume now that |C = 3 and C A. is consecutive, that is, Cn A, = fer, 2++1, V1-2) for some E [6] (henceforth, we treat indices within A, modulo 7). Then v; + locally dominates л. agent v votes against it, 24+2 votes for it, 1++1 does neither, while the total vote of all agents in C'A A sums up to Iev(CC) 2 1, yielding A Te,-)) 2
If | Aul = 2 and C' n A. is nonconsecutive, then the switch + 0 for any o/ E C' locally dominates π, because at least one agent C' n Av votes for it, while the total vote of all agents in C² A. sums up to -lev(C) 2 1, yielding A(T, To, 2 1.
IFCA, = fu, o for some agent U; C, then again v; - 0 locally dominates by u., (TT 0, both 02 and 1 are indifferent between π and = and the total vote of all agents in C' A, sums up to leo-lev()) 2 1, yielding A(T, -o) )) 2 1. Finally, if C' n A, = {u,,, then again + 0 locally dominates т, because vs votes for it, and the total vote of all agents in C \ Ay sums up to ICv 2 I, yielding A(T, TT, = 2.
We next show that it is not possible for all coalitions in C, to have level exactly 0. Assume the contrary. By Theorem 8, we know that T!" cannot be locally popular in Lu so there exists an agent os and a coalition C' E n/ U {0} such that the switch v; - C' locally dominates T/" in Z,. Let C' E a be the coalition satisfying C C' n A,, We will show that the switch e; C' locally dominates in I. First, agents in A, n (T(1) UC)) (T())))))) {re) vote for or against the switch without regard for the agents outside A,. Second, the contribution of all agents outside A, the balanced utility of us remains the same in C" as in x(u)) due to lev (C') = lev(m(v:)) = 0. Third, the total vote of all agents regarding the switch 2. + C" sums up exactly (I) + lev(C) O. Summing up all this, we get A(T, -O) 2 I, as promised.
By Claim 30, this shows that for each E V', there exists some C E C, with lev(C) 1; if there are multiple such coalitions, then fix one arbitrarily. Notice that C' must contain a unique special agent 8; due to lev(C) 1; we then define x(v)= = í. We claim that x is proper coloring of H: Assuming that the endpoints of an edge {u, v) E E' (recall that E' is the edge set of H) have the same color
get that C; = π (8;)) contains agents both from A,, and A however,
they are
mutual enemies and the only friend of vertex agents outside their gadget must be a special agent, we obtain that agents in A, n C, have least many enemies as friends in Ci \ A., contradiction to lev(C") = 1. It follows that H and, hence, its subgraph G admits a proper 3-coloring.
Direction "z"": Assume now that G admits a proper coloring, so H admits a proper and tight coloring X V + [3]. Create the partition ग consisting of three coalitions
G = D UfA: VE V', x(1) i}
for i 3. We claim that is locally popular. For the sake of contradiction, assume that some switch a - C' locally dominates æ.
First, if a is a dummy or special agent in C. for some i E [3), then all agents in DJ vote against -> C. and the only agents that may vote for it are vertex agents (in case a = 8;); hence, A(T, Ta-sc) S 0 by |D#1 > 7n.
Second, if a is a vertex agent in Ag, then three agents in A, vote for a - C, while two agents in A, vote against it. We also know that (x)) ) = because it has three enemies in A. and two friends in A. plus st. Moreover, no vertex agent in A, votes for the switch + C: since is a proper coloring, there are no enemies of in C Ay; the special agent s; votes against it, and dummies in C, are indifferent between श and Ta-sc- This already shows that a -> 0 does not locally dominate n, because A(π, nz-16) = Eorec, votc. (H, nz- = 0. To deal with the case when C ==C, C, E π for some j # i, recall that since X tight, there is at least one vertex u E V among the neighbors of with (") = j. This means that all seven agents in A, C C₁ vote against a - Cy: while the only agent in Cj that votes for it is 8y. Therefore, A(T, Ta->;)) ) < -6. This contradiction proves that is indeed locally popular.
D.2.5 Proof of Proposition 10
Proposition 10 (+). There exists a symmetric FEN-B game that admits a partition that is popular but does not maximize the agents' total balanced utility.
41

---

Proof. Consider the symmetric FEN-B game I on agent set = AUB where A = fa; : E [7]} and B {b; [7]]. To create the (undirected) friendship graph G of I, we add clique on A. clique on B. plus the three edges in ({,; b:) E [3]. The (undirected) enmity graph G of T
contains only the four edges in {{77, b3} : 6,
We claim that the grand coalition x N {NT is popular for I. Assume for the sake of contradiction that there is a partition π with A A(T . > O. Note first that no agent in N \ {ar, ba, by, be, by may prefer и to x they have all their friends with them and enemies in the coalition N. Thus at most five agents may prefer π to π> Second, if some agent prefers π to x then x must put d7 and least agent in {b,, by, bo, by) in different coalitions.
there is no coalition in π containing A, then all six agents in A {a7} prefer xN to π.
If some agent other than prefers to Tr then B must also be contained in some coalition of n. Otherwise, no agent in fbg, by, b6, b7] prefers и to N as they lose at least one friend and lose at most one enemy when switching from T to Hence, in this case only π = {A, B} is possible, but then all six agents in {a,, b,
[3]} prefer n π.
Finally, if only prefers π to x²,, then must contain a coalition C' with C ç B. However, then all agents b,, i [3], prefer n n.
This proves that x N is indeed popular.
The total balanced utility of NN is f(*²) -4- 4- +2--2------- but this is lower than the total balanced utility of the partition B} by f([A, = 4 (2) < f(r This proves our statement.
D.2.6 Proof of Theorem
Theorem 11 (*). Given a symmetric FEN-B game I and an integer t, the problem of deciding whether I admits a partition i whose total balanced utility is at least t is -cmcolpeete
Proof. It is clear that the problem is in NP, as we can compute the total utility of any partition efficiently. To prove Na-hardness, we again present reduction from 3-COLORING based on the construction in Lemma 29. Given an input graph G = (V, E) over n vertices, let us create a symmetric FEN-B game I as follows. We introduce set D1 D2 U D3 of dummy agents with D1l = D22 = Dal 3n, three special agents, $1, 82, and 83, and a vertex agent v' for each vertex v E V. We will again use the notation D = D; U {8t} for each i E [3].
The friendship and enmity relationships between the agents
follows:
For each i E [3] every agent in D considers each other agents in D friend and every remaining special or dummy agent an enemy.
Two vertex agents, u' and v', are mutual enemies if and only if {u, d) E E; otherwise, they are mutually neutral.
Each vertex agent is mutual friends with every special agent and mutually neutral with every dummy agent.
Additionally, we set our target value as t = 6(²) + 2n.
This completes our construction of the instance I from the given 3-COLORING instance G. We are going to show that the constructed FEN-B game admits partition with f and only G admits a proper 3-coloring.
Direction "="; Assume first that there exists a popular partition for T with f()) 2 f; without loss of generality, we may assume that æ maximizes the total balanced utility over all partitions for In particular, this implies that I is locally stable: otherwise, a switch that locally blocks would result in a strict increase in f as shown in Theorem 4; a contradiction. Therefore, Lemma 29 can be applied, and we obtain that π contains three coalitions C₁ C2, C3 E π such that D C C, for each [3].
Since each vertex agent can belong to at most one of the sets C₁ C2, and C3. the total balanced utility of all dummy and special agents is at most 6 (() + Moreover, the balanced utility of any
42

---

da
02
dg
012
dy
b
Figure 13: Illustration of the AE-gadget as defined in Definition 4 (repeated from Figure 2). We denote friendship ares as thin, blue lines and enemy ares as thick, red lines.
vertex agent v' is at most 1, as the only agents regarded friends by r' are special agents, and o' can share a coalition with at most one of them. Hence, f((T) S 6()) + 2n = I, and equality can only be achieved each vertex agent v is in coalition C for some i [3] and has enemies in TT²') C. However. this implies that each set {u V v' E C.} is an independent set in G (i.e., no two of its vertices are connected by an edge of G), proving that G admits a proper 3-coloring.
Direction "<"; Assume now that admits a proper 3-coloring X ~ [3]. Define coalitions === = D U fo' v E V and (v) = i} for E [3]. Then the partition π = {C1, C2. C3} has total balanced utility exactly fTT = 6 (() + 2n = t. proving the correctness of our reduction.
D.3 Omitted proofs for our results on FEN-AE games
After stating some structural observations in Section D.3.1, we provide all omitted proofs for FEN-AE games Sections D.3.2-D.3.3. See Figure for an illustration of AE-gadget, our building block for all of our nonexistence and hardness results concerning FEN-AE games.
D.3.1 A structural lemma on AF-gadgets
Lemma 31. Consider FEN-AE game I that contains an AE- Aadgeteet as described in Definition over agent set K = [c=cc] (b; : [U di, : i [3), and let n be locally stable partition for T. Assume that no agent outside K considers anyone within K a friend, and among agents of K, only FA, D2, and F3 may have friends outside K. Furthermore, assume that coalitions (c),, r(b1)), and π (b122) only contain agents from K. Then
(a) {ai, a2, as, d1, d2, da} S (());
(b) if. for some i E (3), agent considers agent in π m(xz) \ K a friend, then E ([)); and (c) {b: : [12]} S (bb)) * x(c).
Proof. To show (a), we first show that E (c) for each [3]. By our assumptions, the only agents who consider d, friend are and whereas d; has only as friend and has no enemies in (e). Therefore, d, & T()), then d, has an incentive to join π (c), and thus the switch d, - (c) locally blocks both d, and vote for and only a may vote against it. This proves d, T(c).
43

---

This implies that among the three agents whom a,, for some E [3], considers friends, two are contained in x (c), and due our assumptions, a; has no enemies in (c). Hence, if a, $ T()), then a; has an incentive to join (c)). The switch a; x (c) then locally blocks x: both and e vote for it, while only z; (the only agent who considers o; a friend) may vote against it. This contradiction proves (01, 02, 43. d1, d2, d3} C (c), as desired.
To show (b), assume for the sake of contradiction that x, & (T)) and x; has no friends in x (x;; \ K. Then I; has no friends in π (x;), because the only agent whom 2; considers a friiedd is a; E (c).
Since 2i has no enemies in i7 (e) S K due to our assumptions, 2y has an incentive to join TT)). Hence,
I; + (c)) locally blocks π. as both I; and a; vote for it, and only e votes against it; a contradiction proving (b).
remains to show (c). First observe that e E π (112) must hold, as otherwise, the switch b12 + 0 would locally block n, both e and b12 would vote for it (as they are mutual enemies) and only d may vote against it. Similarly, e & x (bb1)) also holds, as otherwise, the switch b1 - 0 would locally block n, since both and b1 would vote for it and only b10 may vote against it (note that b12 & (c)) as we have just shown).
Next, we claim that r(b11) T(b12). Suppose the contrary: T(b11) + Tb12).. Choose and j' such that {i.3"} = [11,12) and Tbb)) contains at least as many agents from {b, : i E [10]] as π (b ). Since b11 and b12 consider each other friend and, apart from each other, they have the same set of friends, and their only enemy e is not in either of ((b1)) or т (b12). it follows that the switch by - xbby) locally blocks æ, as both b and b12 vote for it and only dio may vote against it.
follows that dig E T(b1),, as otherwise, dıo has an incentive to join x (b11), and the switch b10 + T(b11) locally blocks w: agents b10. b1g and b all vote for it and only 0g and by may vote against it. Similarly, we obtain b9 E =bb1)). Finally, once we know that by E (b11) for all i' > i for some i [8]. then b, E T(b11) follows, as otherwise, b; - ((b1) would locally block n:: among the three agents whom b, considers friends, rbb1)) contains two and contains no enemies of b, by (bb1) S K, so b, together with d11 and b12 vote for b, n (bb1), while only b,-1 and b may vote against it. Hence, {b, : : E [12]] S (bb1)) = (b)) # T()).
D.3.2 Proof of Theorem 12
Theorem 12 (+). The asymmetric FEN-AE game consisting solely of an AE-gadget admits no locally stable partition.
Proof. Consider a FEN-AE game that solely consist of an AE-gadget as described in Definition 4 over agent set K u (b, : E [12]] de, n,
[3]] By Lemma 31, the only partition that
may be locally stable for 7 is π = {(az, di, d4, c: E [3]] (b. i E [12]}]- Observe that e has two
enemies and zero friends in π (b1). whereas has three enemies in π (c). and hence, e prefers (b,)
to (c)) Therefore, the switch c - (bb)) locally blocks π: nine agents (namely, c and by for j E [8)
vote for it, while only eight agents (namely, a, and d; for E [3] as well 11 and b12) vote against it. Thus no partition for is locally stable.
D.3.3 Proof of Theorem 13
Theorem 13 (+), complete for FEN-AE games.
and LOCAL-STABILITY -EXILIITYEEEITENCEE are NP-
Proof. It clear that both problems are in NP, as given FEN-AE game, we can nondeterministically guess partition t and then verify in polynomial time that no possible switch locally dominates or locally blocks æ (recall that the number of switches for æ is at most quadratic in the number of agents).
To show the NP-hardness of these problems, present reduction from 3-SAT that works for both problems. Let yp = C A... A C be an instance of 3-SAT, i.c., a Boolean formula over variables 11, ..... Un, with three literals per clause; without loss of generality, we assume that m 2 2. and LOCAL-STABILLTTY
We create a FEN-AE game I of EXISTENCE as follows. For each clause C³, we create an AE-gadget G as described in Definition 4 over agent set KJ ( : [12]] U (a] di af li [3]]. We will call of clause agent
44

---

and agents z1, zzg. and zgg literal agents, corresponding to the three literals in C2. We further add an agent T.
The friendship and enmity relations between agents from different AF-gadgets are as follows:
전 considers T friend for each E [3] and E [m]] while all other agents consider T an enemy.
T considers x/ neutral for each E 3 and j E [m]] but considers every other agent an enemy.
Two agents, and v, from different AE -agggges mutual enemies unless both of them literal agents corresponding to literals that are not negations of each other, in which case they are mutually neutral.
We prove the correctness of the reduction via Claims 32 and 33.
Claim 32. If I admits locally stable partition, then yp is satisfiable.
Proof of claim. Let x be a locally stable partition for T. For the sake of contradiction, suppose that an agent e E {(c bii, b[2} is contained in the same coalition of π as some agent u from a different AE-gadget Gh. Let l denote the largest integer such that both u and v have at least & enemies in (u) (v). Since and are mutual enemies, we know L 2 and thus both u and have an incentive to join 0. However, none of the switches u - 0 and v - can locally block π, so there must exist set F,, of at least l + agents in x (u) (v) who consider
friend and, similarly, set F. of at least e + 1 agents who consider a friend in (T) = πu)). In particular, u is not literal agent af E K for some E [3], as x. regarded as a friend only by af. Moreover, as all friendship relations lie within some AB-gadget, we get that F, C Khh and Fg C KJ, However, u must then be mutual enemies with all + agents in F, (1), and mutual enemies with all l + agents in Fu S (V). which contradicts the definition
Again for the sake of contradiction, suppose now that an agent v E {cl, b/ b22)) ) contained π (T)). Since and T are mutual enemies but + 0 does not locally block π, there must be at least two agents in x(T) who consider u a friend. These two agents cannot be literal agents by the choice of v, they are also mutual enemies with T. Hence, at least four agents vote for the switch T - 0 including T. However, we have already shown that no agent from an AE-gadget other than G can be contained in π (T) (T)); therefore, most three agents in x (T) consider T friend, implying that 7 + 0 locally blocks π, a contradiction.
We conclude that coalitions =(e), (b{1), and T (l(2)) only contain agents from G This means that all conditions of Lemma 31 are satisfied. Hence, if no agent xf E [o] 22, 2r)) considers at least one agent in π (xx²) ) \ K a friend, then by Lemma 31 we get T(e)) = {=] of dj o : E [3] and (1/) (b. i [12])- However, then it follows from Theorem 12 that some switch, namely the switch e + T (b)), locally blocks म, a contradiction.
This means that for each AE-gadget G¹, there exists a literal agent x! E K that considers at least one agent in π (x:) \ K2 a friend; by construction, this agent can only be T. Let Xx denote the set of literal agents in 7 (T); then we have just proven that Xy n K * for each j E [m]]. Suppose mutual enemies (which happens if they correspond to literals v; and v,
that two agents in Xy for some variable Uz). Then both of them have an incentive to join 0, and thus both of them vote for the corresponding switches, whereas at most one agent may vote against them (because for each literal agent u². there is only one agent, namely a². who considers se friend); thus, either of these switches locally blocks т, contradiction.
Therefore, can create truth assignment by setting e to true if and only if there is literal agent corresponding to v; in Xy. By the above arguments, this is a consistent truth assignment and yields a true literal in each clause, thus satisfying sp.
Claim 33. If to is satisfiable, then I admits locally popular partition.
45

---

Proof of claim. Suppose that + is satisfiable by truth assignment μ. We create a partition as follows. We let x (T') contain-besttn T-aal literal agents that correspond true literals. Additionally, we create a coalition {6} ::E [[2]] and a coalition {ar di x : E [3] ((T) for each AE-gadget G².
We claim that и is locally popular. Since 1s satisfies y,, each clause agent e² has at most two enemies and six friends in TT Tc²), ), has two enemies and zero friends in π T( and has at least m + 1 2 3 enemies in (T)). Hence, the only possible coalition in U {0} that e² has incentive to join is via the switch el + V. Regarding the remaining (i.e., all non non-clause) agents, observe that none of them has enemies in its coalition under и. Using this, we get the following:
Neither T nor any agent d' votes for any possible switch.
An agent by may only vote for the switch e² + T(t)). However, such a switch does not locally dominate as all agents in fc², ad, di i [3] U [b) b/2 vote against such switch, whereas only the agents in {6} : E [8]] vote for it.
As we have argued, a clause agent votes only for the switch e² + 0: however, such a switch does not locally dominate æ, only e votes for it, whereas all six agents in the set {a/ de E [3]} vote against it.
An agent af votes only for switches of the form z - xaa), where x/ E (T)) However, such switch does not locally dominate as only a: votes for it, while e² votes against it.
Finally, an agent xa may only vote for switch of the form T + π(x;) or a² + (x²). A switch T + TTx²) for some xi & TTT) is voted for only by the at most two literal agents in (=x),, while
voted against by and all remaining seven agents in T( A switch af + (<x) for some xi E (T') is voted for only by the at most three literal agents in x (T) n K2, while T, c², and least m 2 1 literal agents from i (T) \ K vote against it. Thus none of these switches locally dominates
We obtain that switch for which at least agent votes locally dominates æ, that is, π is locally popular.
As locally popular partition is locally stable by definition, NP-hardness of both EXISTENCE and SEECL--PPPLLRTTEE EEILLAARRTTE-IIEEECEECE EXISTENCE follows.
46


Reviews:
[{"review_id": "l9GyuBdjTx", "reviewer": "Reviewer_NTLN", "summary": "This paper approaches clustering problems as the problem of finding clusters by setting up a \"friends-and-enemies\" game where the objects to be clustered become the agents, who want to join friends and avoid enemies. \nWhen used to cluster objects that are given by pairwise distances, two objects are declared friends when their distance is below some fixed fraction $f\\in [0,1]$ of the largest distance $D$ between the objects, while they are declared as enemies when their distance is greater than $e D$ for some value of $f<e\\in [0,1]$. \nTwo clustering objectives are defined: One is to find a partitioning of the agents (the common node set of the friends and enemies graphs) such that the partition is *locally popular*, the other is that the partition is *locally stable*. Here we call a partition locally stable if no agent can join a group or create its own group in a way that every agent would prefer this switch. Further, we call a partition locally stable if there is no agent that could join a group or create its own group such that the agent would prefer this switch, while everyone else also prefers this switch. Here, the degree of preference of an agent towards a group is $\\alpha \\cdot f - \\beta \\cdot e$ where $f$ ($e$) is the number of friends (respectively, enemies) the agent has in the considered group and $\\alpha,\\beta>0$ are fixed parameters.\n\nIn terms of the choice of $(\\alpha,\\beta)$, three cases are considered: With $N$ agents, these are $(N,-1)$ (\"appreciation of friends\"), $(1,-N)$ (\"aversion of enemies\") and $(1,1)$ (\"balanced\"). In addition, both symmetric and asymmetric graphs are considered.\n\nThe main technical contributions are complexity results (algorithms when appropriate) for the existence of a locally stable/popular partitions for the 3x2=6 types of \"games\". In short, for symmetric graphs these problems are in P (and simple local heuristics solve the associated search problems, efficiently), for asymmetric graphs, only the problem corresponding to the balanced case is in P. The remaining problems are proven to be NP-complete.\n\nExperimental results corroborate the theory, where the two local search methods are compared with some standard methods (k-means, DBSCAN). The new methods appear to be reasonable.", "questions": "Can we motivate the approach from \"first principles\"? Or at least relate to other \"first principles\" approaches to clustering.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1. The approach is intuitive; I like that there is a clear (intuitive?) definition of the objective for finding clusterings. \n2. The paper feels quite complete; I appreciate the work that went into developing these ideas. It is appealing that the local search methods provably work in the \"nice\" cases.\n3. The text is clear. No issues with clarity.\n\nWeaknesses:\n\n1. While there is an intuitive appeal to the approach, overall, as typical in clustering, it is unclear what are the settings where this approach is expected to be \"good\".\n2. While there is no issue with clarity, things feel a bit more complicated than what they need to be. There is quite a bit of terminology that is not necessary and is not helping the readers. A more straightforward approach to presenting the results could be better. Relatedly, the abstract promises that \"fundamental connections\" between coalition formation games and clustering will be studied. This is not true. What happens is that ideas from coalition formation games are used to derive clustering algorithms. To study connections one would need some kind of definitions concerned with clustering objectives, that one could perhaps relate to coalition formation. I think the multidisplinarity is also oversold. Similarly, I could not relate the last sentence of the abstract to the paper.", "was_revised": true, "final_justification": "I maintain this is a fine paper, that requires minor work only which the authors are willing to do. \nI remain positive.", "rebuttal": "Thank you very much for your helpful comments and questions, which we answer below.\n\n*******\n**Comment**: While there is an intuitive appeal to the approach, overall, as typical in clustering, it is unclear what are the settings where this approach is expected to be ``good''.\n\n**Answer**: We believe that settings where data points are agents and fairness is important are the main applications, such as detecting communities in social networks, crowdsourcing, etc. We will emphasize possible applications in more detail.\n\nFurthermore, our simulations suggest that our algorithms perform best when the expected cluster sizes are similar.\n********\n**Comment**: Relatedly, the abstract promises that ``fundamental connections'' between coalition formation games and clustering will be studied. This is not true. What happens is that ideas from coalition formation games are used to derive clustering algorithms. To study connections one would need some kind of definitions concerned with clustering objectives, that one could perhaps relate to coalition formation. I think the multidisciplinarity is also oversold. Similarly, I could not relate the last sentence of the abstract to the paper.\n\n**Answer**: \nWe agree that we may have oversold the interdisciplinary nature of our work, as we indeed have not unearthed any strong bidirectional formal connections between the two fields. The fundamental connection is more on the intuitive level---between our solution concepts in hedonic games and the classic quality measures in clustering---and not on the conceptual level of definitions or theorems. The purpose of the paper (besides our strong theoretical interest in FEN games) was to try to see whether this underlying intuitive connection can lead to efficient clustering algorithms that rely on solution concepts from hedonic games but are useful in clustering too. In view of our experiments, this seems to be the case.\n\nRegarding the admittedly too much exaggerating last sentence of the abstract, we are happy to delete it. \n\n**********\n**Question**: Can we motivate the approach from \"first principles''? Or at least relate to other \"first principles'' approaches to clustering.\n\n**Answer**: \nWe think that our approach cannot be formulated as a ``first principles'' approach to clustering, since it requires the construction of the friendship/enmity graph over the data points. Hence, this part of our approach is inherently not data-driven. However, it is not impossible to conceive some method which sets the similarity/dissimilarity thresholds that define friendships and enmities via some data-driven, perhaps iterative, process. \nNevertheless, in its current form, our method does not work from first principles."}, {"review_id": "W9ygXfjODp", "reviewer": "Reviewer_mtec", "summary": "This paper studies the notions of local popularity and local stability in friends-enemies-neutrals (FEN) Hedonic Games (HGs) and possible applications to clustering. FEN games are additively separable HGs in which every agent divides the others into friends enemies and neutrals, and assigns values $\\alpha_f, \\alpha_e$ to friends and enemies and 0 to neutrals. These games can be represented via a friendship digraph and an enmity one and they are symmetric if the relations are symmetric. Local popularity means that there is no deviation of a single agent s.t. the number of agents gaining from that is strictly more than the rest. Local stability (which was already introduced) requires a deviation to be a Nash one. The authors study 2 simple dynamics LocStab and LocPop and show convergence in the symmetric case. They show convergence of LocStab also in the asymmetric case and then they show possible non-existence and NP-hardness results for the different classes of FEN games considered. They then perform clustering experiments using the mentioned procedures and compare them with usual clustering algorithms.", "questions": "I have listed my concerns above. I am curious on how the authors chose the values $(f,e)$ for the experiments and if they have any explanation for the reasons why some parameters work better than others.", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper is generally well written and easy to follow.  The results obtained by the authors seem sound and the hardness results non-trivial. I personally am not particularly surprised by the convergence of the simple dynamics in the symmetric games: the very definitions of local stability and popularity seem amenable to the use of a potential argument.\n\n My main concern about the paper, however, is that, from my perspective, it is hardly about clustering. This is a paper introducing a slightly new concept of stability (local popularity) and studying it along with local stability, in a specific class of Hedonic Games. The relation between coalitional/Hedonic games and clustering is not new (for instance see Hedonic Clustering Games by Feldman Lewin-Eytan and Naor, which is not in the references of the work) and the authors really deal with clustering only in the experimental results. There is no formal comparison between the results of other clustering procedures and the one presented in the paper. This way, I am unsure if I should evaluate this paper as a HGs one or a clustering one.\nAll the comments above motivate my score.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your helpful comments and questions, which we answer below.\n\n*******\n**Comment**: My main concern about the paper, however, is that, from my perspective, it is hardly about clustering. We also agree that multidisciplinarity and fundamental connections may be oversold in the paper. This is a paper introducing a slightly new concept of stability (local popularity) and studying it along with local stability, in a specific class of Hedonic Games. The relation between coalitional/Hedonic games and clustering is not new (for instance see Hedonic Clustering Games by Feldman Lewin-Eytan and Naor, which is not in the references of the work) and the authors really deal with clustering only in the experimental results. There is no formal comparison between the results of other clustering procedures and the one presented in the paper. This way, I am unsure if I should evaluate this paper as a HGs one or a clustering one. All the comments above motivate my score.\n\n**Answer**: We agree that the paper focuses more on hedonic games than clustering. \nWe thank the reviewer for leading us to the paper by Feldman, Lewin-Eytan, and Naor. However, Feldman et al. take a very different route from ours (see a more detailed comparison below), and so we believe that our submission is the first work that shows the applicability of hedonic games and social choice concepts to general clustering tasks. To the best of our knowledge, there is no previous paper that provides a method for clustering stemming from social choice theory with the following two traits:\n\n1. Relies on a concept that is intuitive, always exists in important, nontrivial cases, is efficiently computable, and flexible enough to be generalizable to different kinds of clustering tasks.\nNote further that our algorithm is polynomial even for _asymmetric_ preferences (in LocStab, balanced case), whereas all known best response dynamics convergence results so far seem to depend on _symmetric_ preferences. This is another useful flexibility factor. \n\n2. Provides large-scale simulation studies, not just for instances where the solution concepts are most natural, but for very distinct and seemingly unrelated tasks like classifying cancerous images, observing impressive results in all cases. \n\nWe explain the similarities and dissimilarities with the paper by Feldman et al. in detail below:\n\n\n1. The central contribution of our paper is a novel clustering framework rooted in _cooperative_ game theory, whereas Feldman et al. adopt a _noncooperative_ game-theoretic approach centered around Nash equilibria.\n\n2. Feldman et al. analyze the **price of anarchy** and **price of stability**, quantifying the efficiency loss due to selfish agent behavior in equilibrium. In contrast, we focus on _cooperative_ fairness-driven solutions derived from social choice theory.\n\n3. Their closest model to ours is ``correlation clustering'' where the players' utilities depend on the similarities with other agents in their own cluster and the dissimilarities with agents from other clusters. Here, this similarity is measured by a real number between 0 and 1. Both this and our framework are special cases of additively separable hedonic games. \n\n4. A major limitation of the Nash equilibrium approach is its restrictive applicability: existence and convergence are guaranteed only in special metric spaces (e.g., agents on a line or a tree). Our framework, by contrast, operates over arbitrary metrics and can be applied to a much broader class of clustering scenarios.\n\n5. While Feldman et al. establish theoretical existence and convergence results, they do not provide practical or efficient algorithms. For the closest case, the correlation clustering case, Feldman et al. show that finding a Nash equilibrium is computationally hard (namely, PLS-complete), which is a serious bottleneck if it were to be used for larger clustering tasks. Our work however, does not have this issue, as we design algorithms that are both efficient and scalable. \n\n6. Unlike our work, Feldman et al. do not benchmark their method against existing clustering algorithms, nor do they claim general applicability to standard clustering tasks. They do not discuss how Nash equilibria are expected to perform according to traditional metrics. One of the key takeaways from our paper is that, despite originating in cooperative game theory and social choice theory, our framework performs comparably to---or sometimes even better than---classical clustering algorithms on standard datasets.\n\n7. Both models allow agents to express preferences over cluster memberships. However, in the paper by Feldman et al., agents move unilaterally between clusters based on individual utility, whereas in our setting, cluster changes must be _collectively_ acceptable, reflecting a more community-aware and more global notion of stability.\n  That is the great advantage offered by _cooperative_ game theory.\n\n8. A distinguishing feature of our model is the use of **FEN games**, which reduces the complexity of utility representation by classifying relationships into discrete categories: friend, enemy, or neutral. This abstraction simplifies the input space without compromising the effectiveness of the resulting clusterings.\n\n\nWe hope that this detailed comparison clarifies the complementary nature of the two approaches and highlights the distinct contributions of our work.\n\n*****\n**Question**: I have listed my concerns above. I am curious on how the authors chose the values $(f,e)$ for the experiments and if they have any explanation for the reasons why some parameters work better than others.\n\n**Answer**: We chose these based on preliminary experimenting, searching for parameters that seemed most robust across all datasets simultaneously. We think that, intuitively, if the $f$ and $e$ values are close to the average ratio between the desired cluster size and total number of points, then our algorithms perform better; however, this is a mere conjecture we have not yet verified."}, {"review_id": "n7RqGyZY4W", "reviewer": "Reviewer_sZgp", "summary": "The paper proposes the usage of algorithms and solution concepts from the hedonic games literature for clustering. For this, they introduce two new solution concepts in a subclass of hedonic games and provide algorithms that are guaranteed to produce an outcome fulfilling these concepts (by showing the guaranteed convergence of the best response dynamics via a potential function algorithm). They also show that finding stable outcomes in slightly more general subclasses of games is computationally hard. They demonstrate in experiments that their method outperforms several clustering algorithms in clustering tasks.", "questions": "1.\tCan you please elaborate on the relationship between your paper and the “Hedonic clustering games” paper referenced above?\n2.\tIs your theoretical contribution needed to apply hedonic games to clustering? Are alternative solution concepts / subclasses of hedonic games either computationally intractable or non-applicable?\n3.\tCould you please expand on the relation between your solution concepts and the classic quality measures from the clustering community? \n4.\tIs the complexity of your solution concepts in general FEN-games (for arbitrary parameters) an open question?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Currently, I view the submission as a borderline paper, but I am very open to increasing my score and supporting acceptance if the authors respond satisfactorily to my questions.\n\n### Reasons to Accept\n\n- Using hedonic games for clustering is a mostly original idea (see below) that provides a contribution to both communities and might open up new directions for fruitful future work. I fully agree with the statement of the authors that the paper “can spark a stronger cooperation between these fields to explore the applicability of coalition formation games in clustering.”  \n- The paper makes a good conceptual, technical, and experimental contribution, which makes it a generally appealing read.\n- The theoretical contribution is solid and original (using standard techniques).  \n- The paper is generally well-written and clear.  \n- The paper shows that the solution approach via hedonic games leads to better performance in experiments.  \n- The paper also contributes to a new line of work on the convergence of best response dynamics in hedonic games.\n\n### Reasons to Reject\n\n ***Missing Related Paper***\n\nThe following paper feels conceptually closely related to the submission, but is not cited or discussed:  \n*Moran Feldman, Liane Lewin-Eytan, and Joseph (Seffi) Naor. 2015. Hedonic clustering games. ACM Trans. Parallel Comput. 2015.*\n\n***Framing***\n\nReading the paper, I was struggling with its framing and goal. The paper feels like a mix of two papers: one that introduces how to use clustering for hedonic games (which feels quite original), and a second, standard hedonic games paper with some new results on two stability concepts. In particular, given the paper’s clustering framing, I would have expected that every contribution would be tied to the clustering application, and a clearer discussion on why the studied solution concepts are desirable in the clustering domain. I think the paper would get a lot stronger if the authors could argue that their work was necessary to apply hedonic games to clustering.\n\n***Clarity Issues***\n\nThere is some room for improvement in the introduction section:\n\n- The first part of the introduction switches multiple times between motivation and contribution (e.g., Lines 40–45 feel like a contribution section) and then has a separate contribution section at the end. Separating these aspects more clearly could make the introduction easier to digest and less redundant.\n- I would have appreciated a clearer discussion on how your solution concepts relate to classic quality measures from the clustering world. Do you perceive your methods as proxies to optimize existing quality measures, or do you rather view them as appealing in themselves?\n- The introduction feels pretty dense in terms of technical jargon, descriptions, and discussions. Especially for readers from the clustering community, I fear that the initial part of the paper will be quite hard to follow.\n- Over the whole paper, at the beginning of a section and subsections, I was oftentimes missing a roadmap of what follows, and was thus unsure what to expect in the following. Generally, the writing in Section 3 feels very statement-heavy with limited intuition.\n\n***Some Questions I Had When Reading the Paper*** (no need to address them in the rebuttal)\n\n- I would be curious how far standard clustering solutions are from being stable.\n- I found the name “local stability” quite confusing, as the popularity condition is still baked into this solution concept but not reflected in the name at all.\n- Is the NP-completeness of your problems a practical hurdle for computing solutions fulfilling the concept, e.g., using heuristics that empirically often converge or ILPs?\n- Any intuition on whether there is also a more direct/constructive algorithm to compute LocPop and LocStab?\n- I would have appreciated a slightly more detailed discussion of the idea behind the Rand index and silhouette score in Section 5.", "was_revised": true, "final_justification": "I have increased my score to borderline accept, in light of the fact that the authors have addressed my concern related to missing related work. \nTo increase my score further, I would need to see a revised version of the paper with a reworked framing that would argue in a more convincing way why the theoretical contributions were necessary to achieve the experimental results.", "rebuttal": "Thank you very much for your helpful comments and questions, which we answer below.\n*******\n**Question**: 1. Can you please elaborate on the relationship between your paper and the “Hedonic clustering games” paper referenced above?  \n\n**Answer**:\nWe thank the reviewer for leading us to the work by Feldman et al. Their topic is, of course, closely related to ours (as it also connects social choice theory and clustering), but their approach is quite different.\nNotwithstanding that we very much appreciate the results of this interesting paper, we provide a structured comparison of the two approaches, and we will include a condensed version of this discussion in the final version of the paper.\n\n\n1. The central contribution of our paper is a novel clustering framework rooted in _cooperative_ game theory, whereas Feldman et al. adopt a _noncooperative_ game-theoretic approach centered around **Nash equilibria**.\n\n2. Feldman et al. analyze the **price of anarchy** and **price of stability**, quantifying the efficiency loss due to selfish agent behavior in equilibrium. In contrast, we focus on _cooperative_ fairness-driven solutions derived from social choice theory.\n\n3. Their closest model to ours is ``correlation clustering'' where the players' utilities depend on the similarities with other agents in their own cluster and the dissimilarities with agents from other clusters. Here, this similarity is measured by a real number between 0 and 1. Both this and our framework are special cases of additively separable hedonic games. \n\n4. A major limitation of the Nash equilibrium approach is its restrictive applicability: existence and convergence are guaranteed only in special metric spaces (e.g., agents on a line or a tree). Our framework, by contrast, operates over arbitrary metrics and can be applied to a much broader class of clustering scenarios.\n\n5. While Feldman et al. establish theoretical existence and convergence results, they do not provide practical or efficient algorithms. For the closest case, the correlation clustering case, Feldman et al. show that finding a Nash equilibrium is computationally hard (namely, PLS-complete), which is a serious bottleneck if it were to be used for larger clustering tasks. Our work however, does not have this issue, as we design algorithms that are both efficient and scalable. \n\n6. Unlike our work, Feldman et al. do not benchmark their method against existing clustering algorithms, nor do they claim general applicability to standard clustering tasks. They do not discuss how Nash equilibria are expected to perform according to traditional metrics. One of the key takeaways from our paper is that, despite originating in cooperative game theory and social choice theory, our framework performs comparably to---or sometimes even better than---classical clustering algorithms on standard datasets.\n\n7. Both models allow agents to express preferences over cluster memberships. However, in the paper by Feldman et al., agents move unilaterally between clusters based on individual utility, whereas in our setting, cluster changes must be _collectively_ acceptable, reflecting a more community-aware and more global notion of stability.\nThat is the great advantage offered by _cooperative_ game theory.\n\n8. A distinguishing feature of our model is the use of **FEN games**, which reduces the complexity of utility representation by classifying relationships into discrete categories: friend, enemy, or neutral. This abstraction simplifies the input space without compromising the effectiveness of the resulting clusterings.\n\n\nWe hope that this detailed comparison clarifies the complementary nature of the two approaches and highlights the distinct contributions of our work.\n\n********\n**Question**: 2. Is your theoretical contribution needed to apply hedonic games to clustering? Are alternative solution concepts/subclasses of hedonic games either computationally intractable or non-applicable? \n\n**Answer**: There are very few other notions for cooperative FEN games or, more generally, for additively separable hedonic games that have both guaranteed existence and can be computed efficiently. One such notion is contractional individual stability, which requires that there is no player who wants to switch coalitions, and this switch does not make anyone worse off. This leads to overly restrictive notions compared to our notions of local stability and local popularity, so it lacks the flexibility necessary for being useful in clustering. \n\nRestricted to FEN games, a few more notions become tractable like ``weak core stability.'' However, they either lack the flexibility that our framework has (e.g., weak core partitions can only be found efficiently by computing the strongly connected components of the friendship graph as clusters, which most often would lead to just one single cluster), or they pose too few restrictions (e.g., Pareto optimality).\n\nWe refer to Table 1 in a paper by Aziz, Brandt, Seeding, ``Computing desirable partitions in additively separable hedonic games'' (Artificial Intelligence 195:316--334, 2013), for a tractability map of different concepts in ASHGs.\n\nTo the best of our knowledge, there has been no paper previously that provides a method for clustering stemming from social choice theory that has the following two traits:\n\n1. Relies on a concept that is intuitive, always exists in important, nontrivial cases, is efficiently computable, and flexible enough to be generalizable to different kinds of clustering tasks.\nNote further that our algorithm is polynomial even for _asymmetric_ preferences (in LocStab, balanced case), whereas all known best response dynamics convergence results so far seem to depend on _symmetric_ preferences. This is another useful flexibility factor. \n\n2. Provides large-scale simulation studies, not just for instances where the solution concepts are most natural, but for very distinct and seemingly unrelated tasks like classifying cancerous images, observing impressive results in all cases.\n\nHence, we strongly believe that the notions studied in our paper are the first ones that make hedonic games truly applicable for clustering tasks. \n\n*********\n**Question**: 3. Could you please expand on the relation between your solution concepts and the classic quality measures from the clustering community?\n\n\n**Answer**:\nWe do not claim any formal relationship between our solution concepts and any classic quality measures for clustering; we are not aware of any such direct connections. \nHowever, we would like to stress that despite the lack of formal relations between clustering measures and our solution concepts, the underlying ideas are fundamentally very similar: In the FEN model, we are looking for a coalition structure where coalitions contain as many friendships and as few enmities as possible; this is very similar to the situation in clustering where we aim for similar data points to be allocated to the same cluster, and very different data points to be allocated to separate clusters---which is the main idea behind many of the classic measures such as Rand index. The array of various clustering measures tries to capture this somewhat vague notion of a _good clustering_, and our solution concept tries to do the same in the context of coalition formation where, apart from similarities and dissimilarities (expressed as friendships/enmities), we may also care about fairness and collective decision-making. \n\n******\n**Question**: 4. Is the complexity of your solution concepts in general FEN-games (for arbitrary parameters) an open question? \n\n\n**Answer**: Things that we proved to be NP-hard are of course NP-hard for more general cases too. Some of our positive results, such as the existence reults, may extend to symmetric ASHGs, but we expect that their computation will be hard (e.g. PLS-hard) as the potential function may not be polynomially bounded, so the restriction to FEN games is likely a necessary step for the needed efficiency guarantees for clustering. \n\nWe refer to the referenced papers by Brandt and Bullinger [10], by Brandt, Bullinger, and Tappe [11], and by Bullinger and Gilboa [13] for an overview of complexity results for various similar solution concepts.\n\n\n*******\n**Small Comments**:\n   -  I would be curious how far standard clustering solutions are from being stable.\n   \n   - I found the name “local stability” quite confusing, as the popularity condition is still baked into this solution concept but not reflected in the name at all.\n   \n- Is the NP-completeness of your problems a practical hurdle for computing solutions fulfilling the concept, e.g., using heuristics that empirically often converge or ILPs?\n\n   - Any intuition on whether there is also a more direct/constructive algorithm to compute LocPop and LocStab?\n    \n    - I would have appreciated a slightly more detailed discussion of the idea behind the Rand index and silhouette score in Section 5.\n\n**Answers**:\n- This is an interesting future direction and we will look at it.\n\n- We agree that the name is not optimal, and we consider switching it. A better name could be _``Nash-stable local popularity.''_\n\n- We do not believe ILPs would be able to provide efficient solutions, especially for large datasets. Heuristics may be able to converge fast for datasets; this is again an interesting future direction.\n\n- We are not aware of any more direct/constructive algorithm to compute LocPop and LocStab. Since maximizing total balanced utility is NP-hard by Theorem 11 we expect that local search may be the best efficient method.\n\n- We will try to add more details on Rand index and Silhouette score if space allows."}, {"review_id": "A2xkZjc2nz", "reviewer": "Reviewer_Wf17", "summary": "This paper adopts concepts from FEN (friends–enemies–neutrals) hedonic games to study clustering, drawing a parallel between the two areas: data points are seen as agents with preferences over coalitions, similarities/dissimilarities are represented as friendship/enmity graphs. The authors extend the concept of local stability from FE games to FEN games, and introduce a stronger stability notion called local popularity. They develop clustering heuristics based on local improvements of these stability criteria and prove polynomial-time convergence results for various setting of the clustering game, including symmetric, asymmetric, FEN-AF, FEN-AE, and FEN-B settings. They complement their algorithmic results by showing NP-completeness of the decision problem on existence of locally stable or popular partitions in asymmetric cases, and demonstrate their algorithms with experiments.", "questions": "1. Regarding weakness item 1, can the authors please provide some motivation for local popularity?\n2. Could the authors provide some intuition and explanation on why the hardness results for FEN-AF and FEN-AE differ? It seems to me that they are ``symmetric'' settings of each other.", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper bridges concepts from hedonic games and clustering, where the stability concepts are meaningful as local interactions and preferences, and they develop provably efficient algorithms based on these local stability/popularity properties to produce clusterings that are robust against local deviations.\n2. The authors thoroughly analyzed the two algorithms LocPop and LocStab under various settings based on preference domains (AF, AE, B), symmetric/asymmetric relationships, and provide comprehensive theoretical results for both upper bounds (polynomial-time convergence) and matching hardness results (NP-completeness), offering a complete picture.\n\nWeaknesses:\n1. A stronger stability notion of local popularity was introduced, but the practical benefits are unclear to me. It increases the computational complexity by a factor of $\\Delta$ (and especially for asymmetric FEN-B it is a difference of P v.s. NP), but as pointed out by the authors, LocPop and LocStab have very similar empirical performances with respect to the tested evaluation metrics.\n2. The paper provides guarantees of convergence to locally stable or popular clustering irrespective of the initial partition, but the high variances in some of the experiment results suggest the quality of the final clustering, in terms of the selected metrics, is very sensitive to initial partitions.\n3. To define friendship and enmity graphs in the experiments, the parameters $f$ and $e$ requires fine tuning, and as pointed out by the authors themselves, these parameters can significantly affect experiment performances, and which values perform well are arbitrary.", "was_revised": true, "final_justification": "I remain positive about the paper and will keep my rating as is.", "rebuttal": "Thank you very much for your helpful comments and questions, which we answer below.\n\n******\n**Comment**: The paper provides guarantees of convergence to locally stable or popular clustering irrespective of the initial partition, but the high variances in some of the experiment results suggest the quality of the final clustering, in terms of the selected metrics, is very sensitive to initial partitions.\n\n**Answer**: We agree that the initial partition can play an important role in the quality of the final clustering. Hence, it should be emphasized that starting from a good solution---e.g., from the output of another clustering algorithm, as we have done in some of the experiments---can be beneficial for our method. In general cases, we used a random initial partition to neutralize this dependency, leading to higher variance. \n\n**********\n**Comment**: **weakness item 1**. A stronger stability notion of local popularity was introduced, but the practical benefits are unclear to me. It increases the computational complexity by a factor of $\\Delta$ (and especially for asymmetric FEN-B it is a difference of P v.s. NP), but as pointed out by the authors, LocPop and LocStab have very similar empirical performances with respect to the tested evaluation metrics.\n\n**Question**: 1. Regarding **weakness item 1**, can the authors please provide some motivation for local popularity?\n\n**Answer**: First of all, as mentioned in Theorem 2, the additional factor of $\\Delta$ does not appear in the symmetric balanced preference domain, and by our experiments, the balanced version performs just as good as the others. Hence, we believe that local popularity in the balanced case is the notion that provides the best balance between flexibility and efficient computation. Local stability may give too much power to single agents, as they can reject a switch if they do not prefer it, which can sacrifice flexibility in some cases. \n    \n******\n**Question**: 2. Could the authors provide some intuition and explanation on why the hardness results for FEN-AF and FEN-AE differ? It seems to me that they are ``symmetric'' settings of each other.\n\n**Answer**: FEN-AF and FEN-AE games provide different dynamics. In FEN-AF games, coalitions that are desirable can contain both enemies and friends. However, in FEN-AE games the aversion of enemies dictates that only coalitions with no enemies can be desirable to being alone.\nFor this reason, in a reduction to the problem of finding a locally stable or locally popular partition in FEN-AE games, the enmity relations needed to be constructed with much more attention and technical finesse, and even examples with no locally stable or locally popular solutions required more complex components."}]

Author rebuttal:

Meta-review: The paper proposes a well defined and quite intuitive definition of an objective for clustering. It then provides a thorough investigatio of the computational complexity of optimizing this objective in several cases. The writeup is clear and teh results are clean. The main criticism the reviewers express is that the paper is oversold, bith in terms of how fundamental the proposed objective is and in terms of the applicability of the results. In their rebuttals, the authors promis to address these issues in tehir final version.
Decision: Accept (spotlight)