# Maximizing Social Welfare in Score-Based
Social Distance Games

Robert Ganian TU Wien
Vienna, Austria<EMAIL_ADDRESS>Utrecht University
Utrecht, NetherlandsCzech Technical University in Prague
Prague, Czech RepublicPenn State University
Pennsylvania, USACzech Technical University in Prague
Prague, Czech RepublicCzech Technical University in Prague
Prague, Czech Republic Thekla Hamm Utrecht University
Utrecht, Netherlands<EMAIL_ADDRESS>Czech Technical University in
Prague
Prague, Czech RepublicPenn State University
Pennsylvania, USACzech Technical University in Prague
Prague, Czech RepublicCzech Technical University in Prague
Prague, Czech Republic Dušan Knop Czech Technical University in Prague
Prague, Czech Republic<EMAIL_ADDRESS>Penn State University
Pennsylvania, USACzech Technical University in Prague
Prague, Czech RepublicCzech Technical University in Prague
Prague, Czech Republic Sanjukta Roy Penn State University
Pennsylvania, USA<EMAIL_ADDRESS>Czech Technical University in Prague
Prague, Czech RepublicCzech Technical University in Prague
Prague, Czech Republic Šimon Schierreich Czech Technical University in Prague
Prague, Czech Republic<EMAIL_ADDRESS>Czech Technical University in
Prague
Prague, Czech Republic Ondřej Suchý Czech Technical University in Prague
Prague, Czech Republic<EMAIL_ADDRESS>
###### Abstract

Social distance games have been extensively studied as a coalition formation
model where the utilities of agents in each coalition were captured using a
utility function $\operatorname{u}$ that took into account distances in a
given social network. In this paper, we consider a non-normalized score-based
definition of social distance games where the utility function
$u^{\vec{\operatorname{s}}}$ depends on a generic scoring vector
$\vec{\operatorname{s}}$, which may be customized to match the specifics of
each individual application scenario.

As our main technical contribution, we establish the tractability of computing
a welfare-maximizing partitioning of the agents into coalitions on tree-like
networks, for every score-based function $u^{\vec{\operatorname{s}}}$. We
provide more efficient algorithms when dealing with specific choices of
$u^{\vec{\operatorname{s}}}$ or simpler networks, and also extend all of these
results to computing coalitions that are Nash stable or individually rational.
We view these results as a further strong indication of the usefulness of the
proposed score-based utility function: even on very simple networks, the
problem of computing a welfare-maximizing partitioning into coalitions remains
open for the originally considered canonical function $\operatorname{u}$.

##  1 Introduction

Coalition formation is a central research direction within the fields of
algorithmic game theory and computational social choice. While there are many
different scenarios where agents aggregate into coalitions, a pervasive
property of such coalitions is that the participating agents exhibit
_homophily_ , meaning that they prefer to be in coalitions with other agents
which are similar to them. It was this observation that motivated Brânzei and
Larson to introduce the notion of _social distance games_ (SDG) as a basic
model capturing the homophilic behavior of agents in a social network [15].

Brânzei and Larson’s SDG model consisted of a graph $G=(V,E)$ representing the
social network, with $V$ being the agents and $E$ representing direct
relationships or connections between the agents. To capture the utility of an
agent $v$ in a coalition $C\subseteq V$, the model considered a single
function: $u(v,C)=\frac{1}{|C|}\cdot\sum\nolimits_{w\in
C\setminus\\{v\\}}\frac{1}{d_{C}(v,w)}$ where $d_{C}(v,w)$ is the distance
between $v$ and $w$ inside $C$.

Social distance games with the aforementioned utility function
$\operatorname{u}$ have been the focus of extensive study to date, with a
number of research papers specifically targeting algorithmic and complexity-
theoretic aspects of forming coalitions with maximum social welfare [2, 3, 4,
29]. Very recently, Flammini et al. [22, 23] considered a generalization of
$\operatorname{u}$ via an adaptive real-valued scoring vector which weights
the contributions to an agent’s utility according to the distances of other
agents in the coalition, and studied the price of anarchy and stability for
non-negative scoring vectors. However, research to date has not revealed any
polynomially tractable fragments for the problem of computing coalition
structures with maximum social welfare (with or without stability-based
restrictions on the behavior of individual agents), except for the trivial
cases of complete (bipartite) graphs [15] and trees [36].

#### Our Contribution.

The undisputable appeal of having an adaptive scoring vector—as opposed to
using a single canonical utility function $\operatorname{u}$—lies in the fact
that it allows us to capture many different scenarios with different dynamics
of coalition formation. However, it would also be useful for such a model to
be able to assign negative scores to agents at certain (larger) distances in a
coalition. For instance, guests at a gala event may be keen to accept the
presence of friends-of-friends (i.e., agents at distance $2$) at a table,
while friends-of-friends may be less welcome in private user groups on social
networks, and the presence of complete strangers in some scenarios may even be
socially unacceptable.

Here, we propose the study of social distance games with a family of highly
generic non-normalized score-based utility functions. Our aim here is twofold.
First of all, these should allow us to better capture situations where agents
at larger distances are unwelcome or even unacceptable for other agents. At
the same time, we also want to obtain algorithms capable of computing welfare-
maximizing coalition structures in such general settings, at least on well-
structured networks.

Our model considers a graph $G$ accompanied with an integer-valued, fixed but
adaptive _scoring vector_ $\vec{\operatorname{s}}$ which captures how
accepting agents are towards other agents based on their pairwise
distance.111Formal definitions are provided in the Preliminaries. The utility
function $u^{\vec{\operatorname{s}}}(v,C)$ for an agent $v$ in coalition $C$
is then simply defined as $u^{\vec{\operatorname{s}}}(v,C)=\sum\nolimits_{w\in
C\setminus\\{v\\}}\vec{\operatorname{s}}(d_{C}(v,w))$; we explicitly remark
that, unlike previous models, this is not normalized with respect to the
coalition size. As one possible example, a scoring vector of $(1,0,-1)$ could
be used in scenarios where agents are welcoming towards friends, indifferent
to friends-of-friends, slightly unhappy about friends-of-friends-of-friends
(i.e., agents at distance $3$), and unwilling to group up with agents who are
at distance greater than $3$ in $G$. A concrete example which also illustrates
the differences to previous SDG models is provided in Figure 1.

Figure 1: A social network illustrating the difference of maximising social
welfare in our model compared to previous SDG models. (1) In Brânzei and
Larson’s SDG model, the welfare-maximum outcome is the grand coalition. (2) A
welfare-maximum outcome in the normalized model of Flammini et al. with a
scoring vector of $(1,0,0,0)$ is marked with dashed lines, while the same
scoring vector in our non-normalized model produces the grand coalition. (3) A
scoring vector of $\vec{\operatorname{s}}=(1,0,-1)$ in our model produces the
welfare-maximizing outcome marked with bold lines, with a welfare of $18$. (4)
A ‘less welcoming’ scoring vector of $\vec{\operatorname{s}}=(1,-3)$ leads to
the welfare maximizing dash-circled partition with a welfare of $14$ (compared
to only $12$ for the bold-circled one).

While non-normalized scoring functions have not previously been considered for
social distance games, we view them a natural way of modeling agent utilities;
in fact, similar ideas have been successfully used in models for a variety of
other phenomena including, e.g., committee voting [21], resource allocation
[14, 13] and Bayesian network structure learning [25, 37]. Crucially, it is
not difficult to observe that many of the properties originally established by
Brânzei and Larson for SDGs also hold for our non-normalized score-based model
with every choice of $\vec{\operatorname{s}}$, such as the small-world
property [15, 28] and the property that adding an agent with a close (distant)
connection to a coalition positively (negatively) impacts the utilities of
agents [15]. In addition, the proposed model can also directly capture the
notion of _enemy aversion_ with symmetric preferences [5, 35] by setting
$\vec{\operatorname{s}}=(1)$.

Aside from the above, a notable benefit of the proposed model lies on the
complexity-theoretic side of things. Indeed, a natural question that arises in
the context of SDG is whether we can compute an outcome—a partitioning of the
agents into coalitions—which maximizes the social welfare (defined as the sum
of the utilities of all agents in the network). This question has been studied
in several contexts, and depending on the setting one may also require the
resulting coalitions to be stable under _individual rationality_ (meaning that
agents will not remain in coalitions if they have negative utility) or _Nash
stability_ (meaning that agents may leave to join a different coalition if it
would improve their utility). But in spite of the significant advances in
algorithmic aspects of other coalition formation problems in recent years [10,
11, 17, 24], we lack any efficient algorithm capable of producing such a
welfare-optimal partitioning when using the utility function
$\operatorname{u}$ even for the simplest types of networks.

To be more precise, when viewed through the refined lens of _parameterized
complexity_ [18, 20] that has recently become a go-to paradigm for such
complexity-theoretic analysis, no tractable fragments of the problem are
known. More precisely, the problem of computing a welfare-maximizing outcome
under any of the previously considered models is not even known to admit an XP
algorithm when parameterized by the minimum size of a vertex cover in the
social network $G$—implying a significant gap towards potential fixed-
parameter tractability. This means that the complexity of welfare-maximization
under previous models remains wide open even under the strongest non-
trivializing restriction of the network.

As our main technical contribution, we show that non-normalized score-based
utility functions do not suffer from this drawback and can in fact be computed
efficiently under fairly mild restrictions on $G$. Indeed, as our first
algorithmic result we obtain an XP algorithm that computes a welfare-
maximizing partitioning of the agents into coalitions parameterized by the
treewidth of $G$, and we strengthen this algorithm to also handle additional
restrictions on the coalitions in terms of individual rationality or Nash
stability. As with numerous treewidth-based algorithms, we achieve this result
via leaf-to-root dynamic programming along a tree-decomposition. However, the
records we keep during the dynamic program are highly non-trivial and require
an advanced branching step to correctly pre-computed the distances in the
stored records. We remark that considering networks of small treewidth is
motivated not only by the fundamental nature of this structural graph measure,
but also by the fact that many real-world networks exhibit bounded treewidth
[34].

In the next part of our investigation, we show that when dealing with simple
scoring functions or bounded-degree networks, these results can be improved to
fixed-parameter algorithms for welfare-maximization (including the cases where
we require the coalitions to be individually rational or Nash stable). This is
achieved by combining structural insights into the behavior of such coalitions
with a different dynamic programming approach. Furthermore, we also use an
entirely different technique based on quadratic programming to establish the
fixed-parameter tractability of all 3 problems under consideration w.r.t. the
minimum size of a vertex cover in $G$. Finally, we conclude with some
interesting generalizations and special cases of our model and provide some
preliminary results in these directions.

##  2 Preliminaries

We use $\mathbb{N}$ to denote the set of natural numbers, i.e., positive
integers, and $\mathbb{Z}$ for the set of integers. For $i\in\mathbb{N}$, we
let $[i]=\\{1,\ldots,i\\}$ and ${[i]_{0}=[i]\cup\\{0\\}}$. We assume basic
familiarity with graph-theoretic terminology [19].

#### Social Distance Games.

A _social distance game_ (SDG) consists of a set $N=\\{1,\ldots,n\\}$ of
_agents_ , a simple undirected graph $G=(N,E)$ over the set of agents called a
_social network_ , and a non-increasing _scoring vector_
$\vec{\operatorname{s}}=(s_{1},\dots,s_{{\delta}})$ where  a) for each
$a\in[{\delta}]$, $s_{a}\in\mathbb{Z}$ and  b) for each $a\in[{\delta}-1]$,
$s_{a+1}\leq s_{a}$.

In some cases, it will be useful to treat $\vec{\operatorname{s}}$ as a
function from $\mathbb{N}$ rather than a vector; to this end, we set
$\vec{\operatorname{s}}(a)=s_{a}$ for each $a\leq{\delta}$ and
$\vec{\operatorname{s}}(a)=-\infty$ when $a>{\delta}$. The value “$-\infty$”
here represents an inadmissible outcome, and formally we set
$-\infty+z=-\infty$ and $-\infty<z$ for each $z\in\mathbb{Z}$.

A _coalition_ is a subset $C\subseteq N$, and an outcome is a partitioning
$\Pi=(C_{1},\dots,C_{\ell})$ of $N$ into coalitions; formally,
$\bigcup_{i=1}^{\ell}C_{i}=N$, every $C_{i}\in\Pi$ is a coalition, and all
coalitions in $\Pi$ are pairwise disjoint. We use $\Pi_{i}$ to denote the
coalition the agent $i\in N$ is part of in the outcome $\Pi$. The _utility_ of
an agent $i\in N$ for a coalition $\Pi_{i}\in\Pi$ is

$\operatorname{u}^{\vec{\operatorname{s}}}(i,\Pi_{i})=\sum_{j\in\Pi_{i}\setminus\\{i\\}}\vec{\operatorname{s}}(\operatorname{dist}_{\Pi_{i}}(i,j)),$

where $\operatorname{dist}_{\Pi_{i}}(i,j)$ is the length of a shortest path
between $i$ and $j$ in the graph $G[\Pi_{i}]$, i.e., the subgraph of $G$
induced on the agents of $\Pi_{i}$. We explicitly note that if $\Pi_{i}$ is a
singleton coalition then
$\operatorname{u}^{\vec{\operatorname{s}}}(i,\Pi_{i})=0$. Moreover, in line
with previous work [15] we set $\operatorname{dist}_{\Pi_{i}}(i,j):=+\infty$
if there is no $i$-$j$ path in $G[\Pi_{i}]$, meaning that
$\operatorname{u}^{\vec{\operatorname{s}}}(i,\Pi_{i})=-\infty$ whenever
$G[\Pi_{i}]$ is not connected.

For brevity, we drop the superscript from $u^{\vec{\operatorname{s}}}$
whenever the scoring vector $\vec{\operatorname{s}}$ is clear from the
context. To measure the satisfaction of the agents with a given outcome, we
use the well-known notation of _social welfare_ , which is the total utility
of all agents for an outcome $\Pi$, that is,

$\operatorname{SW}^{\vec{\operatorname{s}}}(\Pi)=\sum_{i\in
N}\operatorname{u}^{\vec{\operatorname{s}}}(i,\Pi_{i}).$

Here, too, we drop the superscript specifying the scoring vector whenever it
is clear from the context.

We assume that all our agents are selfish, behave strategically, and their aim
is to maximize their utility. To do so, they can perform _deviations_ from the
current outcome $\Pi$. We say that $\Pi$ admits an _IR-deviation_ if there is
an agent $i\in N$ such that $\operatorname{u}(i,C)<0$; in other words, agent
$i$ prefers to be in a singleton coalition over its current coalition. If no
agent admits an IR-deviation, the outcome is called _individually rational_
(IR). We say that $\Pi$ admits an _NS-deviation_ if there is an agent $i$ and
a coalition $C\in\Pi\cup\\{\emptyset\\}$ such that
$\operatorname{u}(i,C\cup\\{i\\})>\operatorname{u}(i,\Pi_{i})$. $\Pi$ is
called _Nash stable_ (NS) if no agent admits an NS-deviation. We remark that
other notions of stability exist in the literature [14, Chapter 15], but Nash
stability and individual rationality are the most basic notions used for
stability based on individual choice [30, 39].

Having described all the components in our score-based SDG model, we are now
ready to formalize the three classes of problems considered in this paper. We
note that even though these are stated as decision problems for complexity-
theoretic reasons, each of our algorithms for these problems can also output a
suitable outcome as a witness. For an arbitrary fixed scoring vector
$\vec{\operatorname{s}}$, we define:

$\vec{\operatorname{s}}$-SDG-WF Input: A social network $G=(N,E)$, desired
welfare $b\in\mathbb{N}$. Question: Does the distance game given by $G$ and
$\vec{\operatorname{s}}$ admit an outcome with social welfare at least $b$?

$\vec{\operatorname{s}}$-SDG-WF-IR and $\vec{\operatorname{s}}$-SDG-WF-Nash
are then defined analogously, but with the additional condition that the
outcome must be individually rational or Nash stable, respectively.

We remark that for each of the three problems, one may assume w.l.o.g. that
$s_{1}>0$; otherwise the trivial outcome consisting of $|N|$ singleton
coalitions is both welfare-optimal and stable. Moreover, without loss of
generality we assume $G$ to be connected since an optimal outcome for a
disconnected graph $G$ can be obtained as a union of optimal outcomes in each
connected component of $G$.

The last remark we provide to the definition of our model is that it trivially
also supports the well-known _small world_ property [28] that has been
extensively studied on social networks. In their original work on SDGs,
Brânzei and Larson showed that their model exhibits the small world property
by establishing a diameter bound of $14$ in each coalition in a so-called
_core partition_ [15]. Here, we observe that for each choice of
$\vec{\operatorname{s}}$, a welfare-maximizing coalition will always have
diameter at most ${\delta}$.

#### Parameterized Complexity.

The _parameterized complexity_ framework [18, 20] provides the ideal tools for
the fine-grained analysis of computational problems which are NP-hard and
hence intractable from the perspective of classical complexity theory. Within
this framework, we analyze the running times of algorithms not only with
respect to the input size $n$, but also with respect to a numerical parameter
$k\in\mathbb{N}$ that describes a well-defined structural property of the
instance; the central question is then whether the superpolynomial component
of the running time can be confined by a function of this parameter alone.

The most favorable complexity class in this respect is FPT (short for “fixed-
parameter tractable”) and contains all problems solvable in $f(k)\cdot
n^{\mathcal{O}(1)}$ time, where $f$ is a computable function. Algorithms with
this running time are called _fixed-parameter algorithms_. A less favorable,
but still positive, outcome is an algorithm with running time of the form
$n^{f(k)}$; problems admitting algorithms with such running times belong to
the class XP.

#### Structural Parameters.

Let $G=(V,E)$ be a graph. A set $U\subseteq V$ is a _vertex cover_ if for
every edge $e\in E$ it holds that $U\cap e\not=\emptyset$. The _vertex cover
number_ of $G$, denoted $\operatorname{vc}(G)$, is the minimum size of a
vertex cover of $G$. A _nice tree-decomposition_ of $G$ is a pair
$(\mathcal{T},\beta)$, where $\mathcal{T}$ is a tree rooted at a node $r\in
V(\mathcal{T})$, $\beta\colon V(\mathcal{T})\to 2^{V}$ is a function assigning
each node $x$ of $\mathcal{T}$ its _bag_ , and the following conditions hold:

  * •

for every edge $\\{u,v\\}\in E(G)$ there is a node $x\in V(\mathcal{T})$ such
that $u,v\in\beta(x)$,

  * •

for every vertex $v\in V$, the set of nodes $x$ with $v\in\beta(x)$ induces a
connected subtree of $\mathcal{T}$,

  * •

$|\beta(r)|=|\beta(x)|=0$ for every _leaf_ $x\in V(\mathcal{T})$, and

  * •

there are only tree kinds of internal nodes in $\mathcal{T}$:

    * –

$x$ is an _introduce node_ if it has exactly one child $y$ such that
$\beta(x)=\beta(y)\cup\\{v\\}$ for some ${v\notin\beta(y)}$,

    * –

$x$ is a _join node_ if it has exactly two children $y$ and $z$ such that
$\beta(x)=\beta(y)=\beta(z)$, or

    * –

$x$ is a _forget node_ if it has exactly one child $y$ such that
$\beta(x)=\beta(y)\setminus\\{v\\}$ for some $v\in\beta(y)$.

The _width_ of a nice tree-decomposition $(\mathcal{T},\beta)$ is $\max_{x\in
V(\mathcal{T})}|\beta(x)|-1$, and the treewidth $\operatorname{tw}(G)$ of a
graph $G$ is the minimum width of a nice tree-decomposition of $G$. Given a
nice tree-decomposition and a node $x$, we denote by $G^{x}$ the subgraph
induced by the set $V^{x}=\bigcup_{y\text{ is a descendant of }x}\beta(y)$,
where we suppose that $x$ is a descendant of itself. It is well-known that
optimal nice tree-decompositions can be computed efficiently [8, 31, 32].

Integer Quadratic Programming. Integer Quadratic Programming (IQP) over $d$
dimensions can be formalized as the task of computing

$\max\left\\{x^{T}Qx\mid Ax\leq b,\,x\geq 0,\,x\in\mathbb{Z}^{d}\right\\}\,,$
(IQP)

where $Q\in\mathbb{Z}^{d\times d}$, $A\in\mathbb{Z}^{m\times d}$,
$b\in\mathbb{Z}^{m}$. That is, IQP asks for an integral vector
$x\in\mathbb{Z}^{d}$ which maximizes the value of a quadratic form subject to
satisfying a set of linear constraints.

######  Proposition 1 ([33, 40], see also [26]).

Integer Quadratic Programming is fixed-parameter tractable when parameterized
by $d+\|A\|_{\infty}+\|Q\|_{\infty}$.

##  3 Structural Properties of Outcomes

As our first set of contributions, we establish some basic properties of our
model and the associated problems that are studied within this paper. We begin
by showcasing that the imposition of individual rationality or Nash stability
as additional constraints on our outcomes does in fact have an impact on the
maximum welfare that can be achieved (and hence it is indeed necessary to
consider three distinct problems). We do not consider this to be obvious at
first glance: intuitively, an agent $i$’s own contribution to the social
welfare can only improve if they perform an IR- or NS-deviation, and the fact
that the distance function $\operatorname{dist}_{\Pi_{i}}$ is symmetric would
seem to suggest that this can only increase the total social welfare.

Social Network from Lemma 2.[.48]  $x$ $P$ $K$ Social Network from Lemma
3.[.48]  $x$ $y$ $P$ $K$

######  Lemma 2.

There is a scoring vector $\vec{\operatorname{s}}$ and a social network $G$
such that the single outcome achieving the maximum social welfare is not
individually rational.

###### Proof.

Consider a scoring function $\vec{\operatorname{s}}$ such that
$\vec{\operatorname{s}}=(1,1,-1,-1,-1,-1)$. Consider the social network $G$ in
Section 3 formed from a path $P$ on $5$ vertices and a clique $K$ on $5$
vertices by connecting the endpoints of $P$ to all vertices of $K$. Let $x$ be
the central agent of $P$. Let $C$ be the grand coalition in $G$. The graph can
be viewed as a $6$-cycle with $K$ forming one “bold” agent. All vertices on
the cycle contribute positively to the agent’s utility, except for the one
that is exactly opposite on the cycle. Hence, $\operatorname{u}(x,C)=4-5=-1$,
while utility of all other agents is $8-1=7$ in $C$. This gives total social
welfare of $62$ for the grand coalition.

However, if $x$ leaves the coalition to form its own one, their utility will
improve from $-1$ to $0$, whereas the total social welfare drops. Indeed, in
$C\setminus\\{x\\}$ there are 2 agents with utility $6-2=4$, 2 agents with
utility $7-1=6$ and 5 agents with utility $8-0$, giving total social welfare
of $60$. If any $y\neq x$ was to be excluded from $C$ to form outcome
$\\{y\\},C\setminus\\{y\\}$, then $y$ joining $C$ improves social welfare,
proving that it was not optimal. Finally, if the outcome consists of several
coalitions with the largest one of size 8, then the welfare is at most $8\cdot
7+2\cdot 1=56$, if the largest size is 7, then we get at most $7\cdot 6+3\cdot
2=48$, for 6 it is $6\cdot 5+4\cdot 3=42$ and for 5 it is $5\cdot 4+5\cdot
4=40$.

Hence the grand coalition $C$ is the only outcome with maximal social welfare,
but it is not individually rational (and therefore not Nash stable), as
$\operatorname{u}(x,C)=-1$. ∎

######  Lemma 3.

There is a scoring vector $\vec{\operatorname{s}}$ and a social network $G$
such that the single individually rational outcome achieving the maximum
social welfare among such outcomes is not Nash stable.

###### Proof.

Consider again the scoring function
$\vec{\operatorname{s}}=(1,1,-1,-1,-1,-1)$. Similarly to previous lemma,
consider the social network $G$ in Section 3 formed from a path $P$ on $5$
vertices and a clique $K$ on $4$ vertices by connecting the endpoints of $P$
to all vertices of $K$ and adding a agent $y$ only connected to the central
agent of $P$ which we call $x$. Let $C$ be the coalition containing all
vertices of $G$ except for $y$. As in the previous lemma, $G[C]$ can be viewed
as a $6$-cycle with $K$ forming one “bold” agent. Hence,
$\operatorname{u}_{x}(C)=4-4=0$, while utility of other agents in $C$ is
$7-1=6$. Trivially $\operatorname{u}_{y}(\\{y\\})=0$, hence the outcome
$(\\{y\\},C)$ is individually rational. It has total social welfare of $48$.
However, it is not Nash stable, as $x$ wants to deviate to $\\{x,y\\}$ giving
them utility $1$.

However, the outcome $(\\{x,y\\},C\setminus\\{x\\})$, which is Nash stable,
has total social welfare only $46$. Note that
$\operatorname{u}_{z}(C\setminus\\{x\\})\geq 3$ for every agent $z\in
C\setminus\\{x\\}$, so any outcome $(\\{x,y,z\\},C\setminus\\{x,z\\})$ cannot
be Nash stable. While the total social welfare of the grand coalition is $46$,
the utility of $y$ is $3-6=-3$ in this coalition, so this outcome is not even
individually rational. From the computations in the previous lemma, it
follows, that to attain the social welfare of $48$, the largest coalition in
the outcome must be of size at least $7$. Moreover, if it is of size exactly
$7$, then these $7$ vertices must be at mutual distance at most $2$. However,
there are no $7$ vertices in mutual distance at most $2$ in $G$. Hence, in any
outcome with social welfare $48$ the largest coalition must be of size at
least $8$. Agent $y$ has only $3$ agents in distance at most $2$ in $G$.
Hence, for $y$ to get a positive utility from some coalition, the coalition
must be of size at most $7$, i.e., $y$ cannot be part of the largest coalition
in any outcome with social welfare at least $48$. However, for every $z\in C$,
$z$ joining the coalition $C\setminus\\{z\\}$ improves the social welfare of
the outcome, proving that it was not optimal.

Hence the outcome $(\\{y\\},C)$ is the only individually rational outcome with
maximal social welfare, but it is not Nash stable. ∎

It should be noted that Lemmas 2 and 3 also contrast many other models where
outputs maximizing social welfare are stable for symmetric utilities [12, 7,
16].

As our next two structural results, we prove that on certain SDGs it is
possible to bound not only the diameter but also the size of each coalition in
a welfare-maximum outcome. Notably, we establish such bounds for SDGs on
bounded-degree networks and SDGs which have a simple scoring vector on a tree-
like network. While arguably interesting in their own right, these properties
will be important for establishing the fixed-parameter tractability of
computing welfare-optimal outcomes in the next section.

######  Lemma 4.

For every scoring vector $\vec{\operatorname{s}}=(s_{1},\ldots,s_{\delta})$,
if $G$ is a graph of maximum degree $\Delta(G)$ and $C$ is a coalition of size
more than $(s_{1}+1)\cdot\Delta(G)\cdot(\Delta(G)-1)^{{\delta}-1}$, then for
every $i\in C$ we have $\operatorname{u}(i,C)<0$.

###### Proof.

Let $i\in C$. There are at most $\Delta(G)\cdot(\Delta(G)-1)^{{\delta}-1}$
agents in distance at most ${\delta}$ from $i$. Each of these agents
contributes at most $s_{1}$ to $\operatorname{u}(i,C)$. Every other agent
contributes at most $-1$. Hence, if there are more than
$(s_{1}+1)\cdot\Delta(G)\cdot(\Delta(G)-1)^{{\delta}-1}$ agents in $C$, then
more than $s_{1}\cdot\Delta(G)\cdot(\Delta(G)-1)^{{\delta}-1}$ of them have a
negative contribution to $\operatorname{u}(i,C)$ and

$\operatorname{u}(i,C)<s_{1}\cdot\Delta(G)\cdot(\Delta(G)-1)^{{\delta}-1}-1\cdot
s_{1}\cdot\Delta(G)\cdot(\Delta(G)-1)^{{\delta}-1}=0.\qed$

######  Lemma 5.

Let $\vec{\operatorname{s}}=(s_{1},\ldots,s_{\delta})$ be such that $s_{2}<0$.
If $G$ is a graph of treewidth $\operatorname{tw}$ and $C$ is a coalition of
size more than $2(s_{1}+1)\cdot\operatorname{tw}+1$, then $\sum_{i\in
C}\operatorname{u}(i,C)<0$.

###### Proof.

Each agent adjacent to $i$ contributes $s_{1}$ to $\operatorname{u}(i,C)$,
whereas all the other agents contribute at most $-1$. Since a graph of
treewidth $\operatorname{tw}$ is $\operatorname{tw}$-degenerate, there are
$|E(G[C])|\leq|C|\cdot\operatorname{tw}$ pairs of adjacent agents and
$\binom{|C|}{2}-|E(G[C])|$ pairs of non-adjacent agents. We have

$\displaystyle\sum_{i\in C}\operatorname{u}(i,C)$ $\displaystyle=\sum_{i,j\in
C;i\neq j}\vec{\operatorname{s}}\left(\operatorname{dist}(i,j)\right)$
$\displaystyle\leq
2\left(s_{1}\cdot\left|E\left(G[C]\right)\right|-\left(\binom{|C|}{2}-\left|E\left(G[C]\right)\right|\right)\right)$
$\displaystyle=2\left((s_{1}+1)\cdot\left|E\left(G[C]\right)\right|-\binom{|C|}{2}\right)$
$\displaystyle\leq 2(s_{1}+1)\cdot|C|\cdot\operatorname{tw}-|C|(|C|-1)$
$\displaystyle=|C|\left(2(s_{1}+1)\cdot\operatorname{tw}-(|C|-1)\right)$
$\displaystyle<|C|\left(2(s_{1}+1)\cdot\operatorname{tw}-\left(2(s_{1}+1)\cdot\operatorname{tw}+1-1\right)\right)=0.\qed$

##  4 Computing Optimal Outcomes

###  4.1 Intractability

As our first step towards an understanding of the complexity of computing a
welfare-optimal outcome in an SDG, we establish the NP-hardness of
$\vec{\operatorname{s}}$-SDG-WF, $\vec{\operatorname{s}}$-SDG-WF-IR and
$\vec{\operatorname{s}}$-SDG-WF-Nash even for a very simple choice of
$\vec{\operatorname{s}}$.

######  Theorem 6.

Let $\vec{\operatorname{s}}=(s_{1})$ for any $s_{1}>0$. Then
$\vec{\operatorname{s}}$-SDG-WF, $\vec{\operatorname{s}}$-SDG-WF-IR and
$\vec{\operatorname{s}}$-SDG-WF-Nash are NP-hard.

###### Proof Sketch.

As our first step, we prove the NP-hardness of the intermediate problem called
3-Coloring Triangle Covered Graph (3CTCG) via an adaptation of a known
reduction from NotAllEqual-3-SAT [38, Theorem 9.8]:

3-Coloring Triangle Covered Graph (3CTCG)
Input: An undirected graph $G=(V,E)$ with $|V|=3n$ vertices such that $G$
contains a collection of $n$ mutually vertex disjoint triangles. Question:
Does $G$ have a 3-coloring?

Next, we reduce 3CTCG to our three problems via a single construction. Let $G$
be an instance of 3CTCG with $3n$ vertices and $T_{1},\ldots,T_{n}$ the
corresponding collection of triangles. Let $\overline{G}$ be a complement of
$G$, let $s_{1}=s_{1}(\vec{\operatorname{s}})$ and let $b=3ns_{1}\cdot(n-1)$.
To establish the NP-hardness of $\vec{\operatorname{s}}$-SDG-WF, it suffices
to show that $G$ is a Yes-instance of 3CTCG if and only if $\overline{G}$
admits an outcome with social welfare at least $b$; for the remaining two
problems, we additionally show that such an outcome will furthermore be
individually rational and Nash stable. ∎

###  4.2 An Algorithm for Tree-Like Networks

We complement Theorem 6 by establishing that all three problems under
consideration can be solved in polynomial time on networks of bounded
treewidth—in other words, we show that they are XP-tractable w.r.t. treewidth.
We first describe the “baseline” algorithm for solving
$\vec{\operatorname{s}}$-SDG-WF, and then prove that this may be adapted to
also solve the other two problems by expanding on its records and procedures
(see the appendix).

######  Theorem 7.

For every fixed scoring vector $\vec{\operatorname{s}}$, the
$\vec{\operatorname{s}}$-SDG-WF, $\vec{\operatorname{s}}$-SDG-WF-IR, and
$\vec{\operatorname{s}}$-SDG-WF-Nash problems are in XP when parameterized by
the treewidth of the social network $G$.

###### Proof Sketch.

Our algorithm is based on leaf-to-root dynamic programming along a nice tree-
decomposition of the input social network with rather complicated structure.
In each node $x$ of the tree-decomposition, we store a set $\mathcal{R}_{x}$
of partial solutions called _records_. Each record realizes a single
_signature_ which is a triple $(C,S,T)$, where

  * •

$C$ is a partition of bag agents into parts of coalitions; there are at most
$\operatorname{tw}+1$ different coalitions intersecting $\beta(x)$ and, thus,
at most ${tw^{\mathcal{O}(\operatorname{tw})}}$ possible partitions of
$\beta(x)$.

  * •

$S$ is a function assigning each pair of agents that are part of the same
coalition according to $C$ the shortest intra-coalitional path; recall that
for fixed $\vec{\operatorname{s}}$, the diameter of every coalition is bounded
by a constant ${\delta}$ and, therefore, there are
${n^{\mathcal{O}({\delta})}=n^{\mathcal{O}(1)}}$ possible paths for each pair
of agents which gives us ${n^{\mathcal{O}(\operatorname{tw}^{2})}}$
combinations in total.

  * •

$T$ is a table storing for every coalition $P$ and every possible vector of
distances to bag agents that are in $P$ the number of agents from $P$ that
were already forgotten in some node of the tree-decomposition; the number of
possible coalitions is at most $\operatorname{tw}+1$, the number of potential
distance vectors is
${\delta}^{\operatorname{tw}+1}=2^{\mathcal{O}(\operatorname{tw})}$, and there
are at most $n$ values for every combination of coalition and distance vector
which leads to at most ${n^{2^{\mathcal{O}(\operatorname{tw})}}}$ different
tables $T$.

The value of every record is a pair $(\pi,w)$, where $\pi$ is a partition of
$V^{x}$ such that $\operatorname{SW}(\pi)=w$ and $\pi$ witnesses that there is
a partition of $V^{x}$ corresponding to the signature of the record, as
described above. We store only one record for every signature – the one with
the highest social welfare. Therefore, in every node $x$, there are at most
$n^{2^{\mathcal{O}(\operatorname{tw})}}$ different records.

Once the computation ends, we check the record in the root node $r$ and based
on the value of $w$, we return the answer; Yes if $w\geq b$ and No otherwise.
Moreover, as $G^{r}=G$, the partition $\pi$ is also an outcome admitting
social-welfare $w$. ∎

###  4.3 Fixed-Parameter Tractability

A natural follow-up question to Theorem 7 is whether one can improve these
results to fixed-parameter algorithms. As our final contribution, we show that
this is possible at least when dealing with simple scoring vectors, or on
networks with stronger structural restrictions. To obtain both of these
results, we first show that to obtain fixed-parameter tractability it suffices
to have a bound on the size of the largest coalition in a solution (i.e., a
welfare-optimal outcome).

######  Theorem 8.

For every fixed scoring vector $\vec{\operatorname{s}}$, the variants of
$\vec{\operatorname{s}}$-SDG-WF, $\vec{\operatorname{s}}$-SDG-WF-IR,
$\vec{\operatorname{s}}$-SDG-WF-Nash where we only consider outcomes
consisting of coalitions of at most a prescribed size are FPT parameterized by
the treewidth of the network and the maximum coalition size combined.

###### Proof Sketch.

Similar to the previous ones, we design a dynamic programming (DP) on a nice
tree decomposition, albeit the procedure and records are completely different.

Given a subset of agents $X\subseteq N$, let
$\Pi=(\pi_{1},\pi_{2},\dots,\pi_{\ell})$ be a partition of a set containing
$X$ and some “anonymous” agents. We use _$\mathsf{T}(\Pi)$_ to denote a set of
graph topologies on $\pi_{1},\pi_{2},\dots,\pi_{\ell}$ given $X$. That is,
$\mathsf{T}(\Pi)=\\{\mathsf{T}(\pi_{1}),\dots,\mathsf{T}(\pi_{\ell})\\}$ where
$\mathsf{T}(\pi_{i})$ is some graph on $|\pi_{i}|$ agents, namely $\pi_{i}\cap
X$ and $|\pi_{i}\setminus X|$ “anonymous” agents, for each $i\in[\ell]$. The
maximum coalition size of any welfare maximizing partition is denoted by
$\operatorname{sz}$. Table, M, contains an entry M$[x,C,\mathsf{T}(\Pi)]$ for
every node $x$ of the tree decomposition, each partition $C$ of $\beta(x)$,
and each set of graph topologies $\mathsf{T}(\Pi)$ given $\beta(x)$ where
$\Pi$ is a partition of at most $\operatorname{sz}\cdot\operatorname{tw}$
agents. An entry of M stores the maximum welfare in $G^{x}$ under the
condition that the partition into coalitions satisfies the following
properties. Recall that for a partition $P$ of agents and an agent $a$, we use
$P_{a}$ to denote the coalition agent $a$ is part of in $P$.

  1. 1.

_$C$ and $\Pi$ are consistent_, i.e., the partition of the bag agents
$\beta(x)$ in $G^{x}$ is denoted by $C$ and $C_{a}=\Pi_{a}\cap\beta(x)$ for
each agent $a\in\beta(x)$.

  2. 2.

The coalition of agent $a\\!\in\\!\beta(x)$ in the graph $G^{x}$ is $\Pi_{a}$.

  3. 3.

_$\mathsf{T}(\Pi)$ is consistent with $G^{x}$_ i.e., the subgraph of $G^{x}$
induced on the agents in coalition of $a$ is $\mathsf{T}(\Pi_{a})$, i.e.,
$G^{x}[\Pi_{a}]=\mathsf{T}(\Pi_{a})$.

Observe that we do not store $\Pi$. We only store the topology of $\Pi$ which
is a graph on at most $\operatorname{sz}\cdot\operatorname{tw}$ agents.

We say an entry of M$[x,C,\mathsf{T}(\Pi)]$ is _valid_ if it holds that

  1. 1.

_$C$ and $\Pi$ are consistent_, i.e., $C_{a}=\Pi_{a}\cap\beta(x)$ for each
agent $a\in\beta(x)$,

  2. 2.

Either $C_{a}=C_{b}$, or $C_{a}\cap C_{b}=\emptyset$ for each pair of agents
$a,b\in\beta(x)$,

  3. 3.

_$\mathsf{T}(\Pi)$ is consistent with $G^{x}$ in $\beta(x)$_, i.e., for each
pair of agents $a,b\in\beta(x)$ such that $\Pi_{a}=\Pi_{b}$, there is an edge
$(a,b)\in\mathsf{T}(\Pi_{a})$ if and only if $(a,b)$ is an edge in $G^{x}$.

Once the table is computed correctly, the solution is given by the value
stored in M$[r,C,\mathsf{T}(\Pi)]$ where $C$ is empty partition and
$\mathsf{T}(\Pi)$ is empty. Roughly speaking, the basis corresponds to leaves
(whose bags are empty), and are initialized to store $0$. For each entry that
is not valid we store $-\infty$. To complete the proof, it now suffices to
describe the computation of the records at each of the three non-trivial types
of nodes in the decomposition and prove correctness. ∎

Similarly to Theorem 7, we design a dynamic programming on a nice tree
decomposition, albeit the procedure and records are completely different.

From Lemma 5 it follows that if $s_{2}<0$ and $\operatorname{tw}(G)$ is
bounded, then the maximum coalition size of a welfare maximizing outcome is
bounded. Hence, using Theorem 8 we get the following.

######  Corollary 9.

$\vec{\operatorname{s}}$-SDG-WF-Nash, $\vec{\operatorname{s}}$-SDG-WF-IR, and
$\vec{\operatorname{s}}$-SDG-WF are fixed-parameter tractable parameterized by
the treewidth $\operatorname{tw}(G)$ if $s_{2}<0$.

Turning back to general scoring vectors, we recall that Lemma 4 provided a
bound on the size of the coalitions in a welfare-optimal outcome in terms of
the maximum degree $\Delta(G)$ of the network $G$. Applying Theorem 8 again
yields:

######  Corollary 10.

$\vec{\operatorname{s}}$-SDG-WF-Nash, $\vec{\operatorname{s}}$-SDG-WF-IR, and
$\vec{\operatorname{s}}$-SDG-WF are fixed-parameter tractable parameterized by
the treewidth $\operatorname{tw}(G)$ and the maximum degree $\Delta(G)$ of the
social network.

As our final contribution, we provide fixed-parameter algorithms for computing
welfare-optimal outcomes that can also deal with networks containing high-
degree agents. To do so, we exploit a different structural parameter than the
treewidth—namely the vertex cover number of $G$ ($\operatorname{vc}(G)$). We
note that while the vertex cover number is a significantly more “restrictive”
graph parameter than treewidth, it has found numerous applications in the
design of efficient algorithms in coalition formation, including for other
types of coalition games [6, 9, 27].

######  Theorem 11.

$\vec{\operatorname{s}}$-SDG-WF-Nash, $\vec{\operatorname{s}}$-SDG-WF-IR, and
$\vec{\operatorname{s}}$-SDG-WF are fixed-parameter tractable parameterized by
the vertex cover number $\operatorname{vc}(G)$ of the social network.

###### Proof Sketch.

Let $k=\operatorname{vc}(G)$ and let $U$ be a vertex cover for $G$ of size
$k$. Observe that in each solution there are at most $k$ non-singleton
coalitions, since $G$ has a vertex cover of size $k$ and each coalition must
be connected. Furthermore, the vertices of $G-U$ can be partitioned into at
most $2^{k}$ groups according to their neighborhood in the set $U$. That is,
there are $n_{W}$ vertices in $G-U$ such that their neighborhood is $W$ for
some $W\subseteq U$; denote this set of vertices $I_{W}$.

We perform exhaustive branching to determine certain information about the
structure of the coalitions in a solution—notably:

  1. 1.

which vertices of $U$ belong to each coalition (i.e., we partition the set
$U$); note that there are at most $k^{k}$ such partitions, and

  2. 2.

if there is at least one agent of $I_{W}$ in the coalition or not ; note that
there are at most $(2^{2^{k}})^{k}$ such assignments of these sets to the
coalitions.

We branch over all possible admissible options of the coalitional structure
described above possessed by a hypothetical solution. The total number of
branches is upper-bounded by a function of the parameter value $k$ and thus
for the problems to be in FPT it suffices to show that for each branch we can
find a solution (if it exists) by a fixed-parameter subprocedure. To conclude
the proof, we show that a welfare-maximum outcome (which furthermore satisfies
the imposed stability constraints) with a given coalitional structure can be
computed by modeling this as an Integer Quadratic Program where
$d+\|A\|_{\infty}+\|Q\|_{\infty}$ are all upper-bounded by a function of
$k$—such a program can be solved in FPT time using Proposition 1.

The (integer) variables of the program are $x^{C}_{W}$, which express the
number of vertices from the set $I_{W}$ in the coalition with $C\subseteq U$;
thus, we have $x^{C}_{W}\in\mathbb{Z}$ and $x^{C}_{W}\geq 1$. Let
$\mathcal{C}$ be the considered partitioning of the vertex cover $U$. We use
$C\in\mathcal{C}$ for the set $C\subseteq U$ in the coalition and $C^{+}$ for
the set $C$ and the guessed groups having at least one agent in the coalition.
We require that the vertices of $G-U$ are also partitioned in the solution,
i.e.,

$\sum_{C\in\mathcal{C}}\sum_{W\in C^{+}}x^{C}_{W}=n_{W}\qquad\forall
W\subseteq U.$ (1)

The quadratic objective expresses the welfare of the coalitions in the
solution while the linear constraints ensure the stability of the outcome; for
the latter, we rely on the fact that it is sufficient to verify the stability
for a single agent from the group $I_{W}$ in each coalition. ∎

##  5 Conclusions and Future Research Directions

In this work, we studied social distance games through the lens of an
adaptable, non-normalized scoring vector which can capture the positive as
well as negative dynamics of social interactions within coalitions. The main
focus of this work was on welfare maximization, possibly in combination with
individual-based stability notions—individual rationality and Nash stability.
It is not surprising that these problems are intractable for general networks;
we complement our model with algorithms that work well in tree-like
environments.

Our work opens up a number of avenues for future research. One can consider
other notions of individual-based stability such as individual stability [14,
pp. 360–361][24], or various notions of group-based stability such as core
stability [14, p. 360][15, 35]. Furthermore, our results do not settle the
complexity of finding stable solutions (without simultaneous welfare
maximization). Therefore, it remains open if one can find a Nash stable
solution for a specific scoring vector. Also, a more complex open problem is
to characterize those scoring vectors that guarantee the existence of a Nash
(or individually) stable solution.

Finally, we remark that the proposed score-based SDG model can be generalized
further, e.g., by allowing for a broader definition of the scoring vectors.
For instance, it is easy to generalize all our algorithms to scoring vectors
which are not monotone in their “positive part”. One could also consider
situations where the presence of an agent that is “far away” does not
immediately set the utility of other agents in the coalition to $-\infty$. One
way to model these settings would be to consider “ _open_ ” scoring vectors,
for which we set $\vec{\operatorname{s}}(a)=\vec{\operatorname{s}}({\delta})$
for all $a>{\delta}$—meaning that distances over ${\delta}$ are all treated
uniformly but not necessarily as unacceptable.

Notice that if $\vec{\operatorname{s}}({\delta})\geq 0$ for an open scoring
vector $\vec{\operatorname{s}}$, the grand coalition is always a social-
welfare maximizing outcome for all three problems—hence here it is natural to
focus on choices of $\vec{\operatorname{s}}$ with at least one negative entry.
We note that all of our fixed-parameter algorithms immediately carry over to
this setting for arbitrary choices of open scoring vectors
$\vec{\operatorname{s}}$. The situation becomes more interesting when
considering the small-world property: while the diameter of every welfare-
maximizing outcome can be bounded in the case of Nash stable or individually
rational coalitions (as we prove in our final Theorem 12 below), whether the
same holds in the case of merely trying to maximize social welfare is open and
seems to be a non-trivial question. Because of this, Theorem 7 can also be
extended to the $\vec{\operatorname{s}}$-SDG-WF-IR and
$\vec{\operatorname{s}}$-SDG-WF-Nash with open scoring vectors, but it is non-
obvious for $\vec{\operatorname{s}}$-SDG-WF.

######  Theorem 12.

Let $\vec{\operatorname{s}}=(s_{1},\dots,s_{{\delta}})$ be an arbitrary open
scoring vector and $G$ be a social network. Every outcome $\Pi$ containing a
coalition $C\in\Pi$ with diameter exceeding $\ell=2\cdot s_{1}\cdot{\delta}$
can be neither Nash-stable nor individually rational.

###### Proof Sketch.

Consider a shortest path $P$ in $C$ whose length exceeds $\ell$. We identify a
set of edge cuts along $P$ and show that at least one such cut must be near an
agent whose utility in $C$ is negative, due to the presence of a large number
of agents that must be distant from the chosen edge cut. ∎

#### Acknowledgements.

All authors are grateful for support from the OeAD bilateral Czech-Austrian
WTZ-funding Programme (Projects No. CZ 05/2021 and 8J21AT021). Robert Ganian
acknowledges support from the Austrian Science Foundation (FWF, project
Y1329). Thekla Hamm also acknowledges support from FWF, project J4651-N. Dušan
Knop, Šimon Schierreich, and Ondřej Suchý acknowledge the support of the Czech
Science Foundation Grant No. 22-19557S. Šimon Schierreich was additionally
supported by the Grant Agency of the Czech Technical University in Prague,
grant No. SGS23/205/OHK3/3T/18.

## References

  * [1]
  * [2] Alkida Balliu, Michele Flammini, Giovanna Melideo & Dennis Olivetti (2017): _Nash Stability in Social Distance Games_.  In Satinder Singh & Shaul Markovitch, editors: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, AAAI ’17, AAAI Press, pp. 342–348, 10.1609/aaai.v31i1.10608.
  * [3] Alkida Balliu, Michele Flammini, Giovanna Melideo & Dennis Olivetti (2019): _On Non-Cooperativeness in Social Distance Games_.  Journal of Artificial Intelligence Research 66, pp. 625–653, 10.1613/jair.1.11808.
  * [4] Alkida Balliu, Michele Flammini, Giovanna Melideo & Dennis Olivetti (2022): _On Pareto optimality in social distance games_.  Artificial Intelligence 312, p. 103768, 10.1016/j.artint.2022.103768.
  * [5] Nathanaël Barrot & Makoto Yokoo (2019): _Stable and Envy-free Partitions in Hedonic Games_.  In Sarit Kraus, editor: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI ’19, ijcai.org, pp. 67–73, 10.24963/ijcai.2019/10.
  * [6] Vittorio Bilò, Angelo Fanelli, Michele Flammini, Gianpiero Monaco & Luca Moscardelli (2018): _Nash Stable Outcomes in Fractional Hedonic Games: Existence, Efficiency and Computation_.  Journal of Artificial Intelligence Research 62, pp. 315–371, 10.1613/jair.1.11211.
  * [7] Vittorio Bilò, Gianpiero Monaco & Luca Moscardelli (2022): _Hedonic Games with Fixed-Size Coalitions_.  In: Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI ’22, AAAI Press, pp. 9287–9295, 10.1609/aaai.v36i9.21156.
  * [8] Hans L. Bodlaender (1996): _A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth_.  SIAM Journal on Computing 25(6), pp. 1305–1317, 10.1137/S0097539793251219.
  * [9] Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi & Tom C. van der Zanden (2020): _Hedonic Seat Arrangement Problems_.  In: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’20, IFAAMAS, Richland, SC, p. 1777–1779.  Available at https://dl.acm.org/doi/10.5555/3398761.3398979.
  * [10] Niclas Boehmer & Edith Elkind (2020): _Individual-Based Stability in Hedonic Diversity Games_.  In: Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI ’20, AAAI Press, pp. 1822–1829, 10.1609/aaai.v34i02.5549.
  * [11] Niclas Boehmer & Edith Elkind (2020): _Stable Roommate Problem With Diversity Preferences_.  In Amal El Fallah Seghrouchni, Gita Sukthankar, Bo An & Neil Yorke-Smith, editors: Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20, IFAAMAS, pp. 1780–1782.  Available at https://dl.acm.org/doi/10.5555/3398761.3398980.
  * [12] Anna Bogomolnaia & Matthew O. Jackson (2002): _The Stability of Hedonic Coalition Structures_.  Games and Economic Behavior 38(2), pp. 201–230, 10.1006/game.2001.0877.
  * [13] Sylvain Bouveret & Jérôme Lang (2008): _Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity_.  Journal of Artificial Intelligence Research 32, pp. 525–564, 10.1613/jair.2467.
  * [14] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang & Ariel D. Procaccia, editors (2016): _Handbook of Computational Social Choice_.  Cambridge University Press, 10.1017/CBO9781107446984.
  * [15] Simina Brânzei & Kate Larson (2011): _Social Distance Games_.  In Toby Walsh, editor: Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI ’11, IJCAI/AAAI, pp. 91–96, 10.5591/978-1-57735-516-8/IJCAI11-027.
  * [16] Martin Bullinger & Warut Suksompong (2023): _Topological Distance Games_.  In: Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI ’23, AAAI Press.
  * [17] Jiehua Chen, Robert Ganian & Thekla Hamm (2020): _Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP_.  In Christian Bessiere, editor: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI ’20, ijcai.org, pp. 146–152, 10.24963/ijcai.2020/21.
  * [18] Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk & Saket Saurabh (2015): _Parameterized Algorithms_.  Springer, 10.1007/978-3-319-21275-3.
  * [19] Reinhard Diestel (2017): _Graph Theory_ , 5th edition.  Graduate Texts in Mathematics, Springer, Berlin, Heidelberg, 10.1007/978-3-662-53622-3.
  * [20] Rodney G. Downey & Michael R. Fellows (2013): _Fundamentals of Parameterized Complexity_.  Texts in Computer Science, Springer, 10.1007/978-1-4471-5559-1.
  * [21] Edith Elkind & Anisse Ismaili (2015): _OWA-Based Extensions of the Chamberlin-Courant Rule_.  In Toby Walsh, editor: Proceedings of the 4th International Conference Algorithmic Decision Theory, ADT ’15, Lecture Notes in Computer Science 9346, Springer, pp. 486–502, 10.1007/978-3-319-23114-3_29.
  * [22] Michele Flammini, Bojana Kodric, Martin Olsen & Giovanna Varricchio (2020): _Distance Hedonic Games_.  In Amal El Fallah Seghrouchni, Gita Sukthankar, Bo An & Neil Yorke-Smith, editors: Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20, IFAAMAS, pp. 1846–1848.  Available at https://dl.acm.org/doi/10.5555/3398761.3399002.
  * [23] Michele Flammini, Bojana Kodric, Martin Olsen & Giovanna Varricchio (2021): _Distance Hedonic Games_.  In Tomás Bures, Riccardo Dondi, Johann Gamper, Giovanna Guerrini, Tomasz Jurdzinski, Claus Pahl, Florian Sikora & Prudence W. H. Wong, editors: Proceedings of the 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM ’21, Lecture Notes in Computer Science 12607, Springer, pp. 159–174, 10.1007/978-3-030-67731-2_12.
  * [24] Robert Ganian, Thekla Hamm, Dušan Knop, Šimon Schierreich & Ondřej Suchý (2022): _Hedonic Diversity Games: A Complexity Picture with More than Two Colors_.  In: Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI ’22, AAAI Press, pp. 5034–5042, 10.1609/aaai.v36i5.20435.
  * [25] Robert Ganian & Viktoriia Korchemna (2021): _The Complexity of Bayesian Network Learning: Revisiting the Superstructure_.  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang & Jennifer Wortman Vaughan, editors: Proceedings of the Thirty-Fifth Conference on Neural Information Processing Systems, NeurIPS ’21, Curran Associates, Inc., pp. 430–442.  Available at https://proceedings.neurips.cc/paper/2021/hash/040a99f23e8960763e680041c601acab-Abstract.html.
  * [26] Tomáš Gavenčiak, Martin Koutecký & Dušan Knop (2022): _Integer programming in parameterized complexity: Five miniatures_.  Discrete Optimization 44(Part 1), p. 100596, 10.1016/j.disopt.2020.100596.
  * [27] Tesshu Hanaka & Michael Lampis (2022): _Hedonic Games and Treewidth Revisited_.  In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg & Grzegorz Herman, editors: Proceedings of the 30th Annual European Symposium on Algorithms, ESA ’22, Leibniz International Proceedings in Informatics 244, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 64:1–64:16, 10.4230/LIPIcs.ESA.2022.64.
  * [28] Matthew O. Jackson (2008): _Social and economic networks_.  Princeton University Press, Princeton, NJ, 10.1515/9781400833993.
  * [29] Christos Kaklamanis, Panagiotis Kanellopoulos & Dimitris Patouchas (2018): _On the Price of Stability of Social Distance Games_.  In Xiaotie Deng, editor: Proceedings of the 11th International Symposium Algorithmic Game Theory, SAGT ’18, Lecture Notes in Computer Science 11059, Springer, pp. 125–136, 10.1007/978-3-319-99660-8_12.
  * [30] Mehmet Karakaya (2011): _Hedonic coalition formation games: A new stability notion_.  Mathematical Social Sciences 61(3), pp. 157–165, 10.1016/j.mathsocsci.2011.03.004.
  * [31] Ton Kloks (1994): _Treewidth: Computations and Approximations_.  Lecture Notes in Computer Science 842, Springer, Berlin, Heidelberg, 10.1007/BFb0045375.
  * [32] Tuukka Korhonen (2021): _A Single-Exponential Time 2-Approximation Algorithm for Treewidth_.  In: Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS ’21, IEEE, pp. 184–192, 10.1109/FOCS52979.2021.00026.
  * [33] Daniel Lokshtanov (2015): _Parameterized Integer Quadratic Programming: Variables and Coefficients_.  CoRR abs/1511.00310, 10.48550/arXiv.1511.00310.  arXiv:https://arxiv.org/abs/1511.00310.
  * [34] Silviu Maniu, Pierre Senellart & Suraj Jog (2019): _An Experimental Study of the Treewidth of Real-World Graph Data_.  In Pablo Barceló & Marco Calautti, editors: Proceedings of the 22nd International Conference on Database Theory, ICDT ’19, Leibniz International Proceedings in Informatics 127, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 12:1–12:18, 10.4230/LIPIcs.ICDT.2019.12.
  * [35] Kazunori Ohta, Nathanaël Barrot, Anisse Ismaili, Yuko Sakurai & Makoto Yokoo (2017): _Core Stability in Hedonic Games among Friends and Enemies: Impact of Neutrals_.  In Carles Sierra, editor: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI ’17, ijcai.org, pp. 359–365, 10.24963/ijcai.2017/51.
  * [36] Masahiro Okubo, Tesshu Hanaka & Hirotaka Ono (2019): _Optimal Partition of a Tree with Social Distance_.  In Gautam K. Das, Partha Sarathi Mandal, Krishnendu Mukhopadhyaya & Shin-Ichi Nakano, editors: Proceedings of the 13th International Conference on Algorithms and Computation, WALCOM ’19, Lecture Notes in Computer Science 11355, Springer, pp. 121–132, 10.1007/978-3-030-10564-8_10.
  * [37] Sebastian Ordyniak & Stefan Szeider (2013): _Parameterized Complexity Results for Exact Bayesian Network Structure Learning_.  Journal of Artificial Intelligence Research 46, pp. 263–302, 10.1613/jair.3744.
  * [38] Christos H. Papadimitriou (1994): _Computational complexity_.  Addison-Wesley.
  * [39] Shao Chin Sung & Dinko Dimitrov (2007): _On Myopic Stability Concepts for Hedonic Games_.  Theory and Decision 62(1), pp. 31–45, 10.1007/s11238-006-9022-2.
  * [40] Kevin Zemmer (2017): _Integer Polynomial Optimization in Fixed Dimension_.  Doctoral thesis, ETH Zurich, Zurich, 10.3929/ethz-b-000241796.