# Investigation of fast-NMPC and deep learning approach in fixed-point-based
hierarchical control.

Xuan-Huy Pham  Mazen Alamir  François Bonne  University of Grenoble Alpes,
Gipsa-lab, (xuan-huy.pham@grenoble-inp.fr).  Univ. Grenoble Alpes,IRIG-DSBT,
F-38000, Grenoble,France

###### Abstract

This paper explores some variations of a hierarchical control framework that
has been recently proposed. The framework is dedicated to control a network of
interconnected subsystems such as the ones describing cryogenic processes or
power plants. Recent investigations showed that handling constraints and
nonlinearities might challenge the real-time feasibility of the approach. This
paper investigates and combine two successful directions, namely, the use of
truncated fast gradient and deep neural networks based controller modeling in
order to reduce the computation time of the most critical subsystem. It is
also shown that by doing so, the control updating period can be drastically
reduced and the closed-loop performances highly improved. The paper can
therefore be seen as a concrete implementation and validation of some key
ideas in real-time distributed NMPC design. All the concepts are validated
using the realistic and challenging example of real-life cryogenic
refrigerator.

###### keywords:

Hierarchical control, NMPC, gradient method, fixed-point iteration, deep
learning, cryogenic station.

##  1 Introduction

In nuclear fusion reactors or particle accelerators, cryogenic refrigerators
play a critical role as they cool down the thermal loads on the
superconducting magnets to maintain the functionality of the overall process
(Henry et al., 2007; Claudet et al., 2000). These facilities are composed of
several highly coupled subsystems forming an interactive network that requires
efficient control design.

In this context, many studies have been conducted in the area of system
modeling and model-based control methodology: In the work of (Bonne et al.,
2014) and references therein, several model-based multi-variable and
constrained control strategies were investigated. Nevertheless, the
aforementioned works are based on centralized frameworks which have some
obvious drawbacks. Indeed, for such large systems where subsystems may be
geographically located in different buildings, operators prefer modular design
in order to facilitate testing, upgrading and maintenance operations. On the
other hand, completely decentralized PID-based schemes fail to achieve an
optimal design while satisfying the operating and safety constraints.

Recently, a fixed-point-based hierarchical control framework has been
suggested and validated for an interacting network of subsystems (Alamir et
al., 2017; Pham et al., 2021a). The proposed hierarchical control architecture
is structured in two distinct layers. In the upper layer, a coordinator
exchanges information with the subsystems located at the lower layer. By using
the information exchanged with the subsystems, the coordinator minimizes a
global cost by computing an optimal vector of set-points to be sent to the
subsystems. On the other hand, each subsystem in the lower layer implements a
local controller in order to regulate a specific output vector. While keeping
the whole structure proposed in (Alamir et al., 2017) unchanged, (Pham et al.,
2021a) have demonstrated the validity of the methodology under constraints on
actuators and nonlinearities in the underlying models. However, it pointed out
that the relating computational burden might become a challenging issue since
the optimization control problems at the local level have to be solved
repeatedly during a fixed-point iteration loop. In order to address this
problem, the authors in (Pham et al., 2021a) proposed to reduce the complexity
of the optimizing set-point vector by performing the distribution of the
optimization process over cyclically changed decision variables, aiming at
limiting the number of iterations per updating period. However, this technique
induces a slight drop in the resulting closed-loop performance.

This paper attempts to address the same issue following the tracks described
hereafter:

(a) First it is shown that using a truncated fast gradient algorithm enables
to reduce the computation time compared to generic available framework (such
as CasADi/IPOPT (Andersson et al., 2019)) even if the maximum number of
iterations of such solver is limited (see Table 3).

(b) Then, in order to further reduce the computation time of the most cpu-
critical local controller, a feed-forward deep neural network is used to
approximate the control law provided by the fast gradient algorithm.

(c) Finally, capitalizing on the resulting reduction of computation time, it
is shown that by adopting a smaller control updating period, one can
significantly improve the closed-loop performance.

This paper is organized as follows: Section 2 recalls the hierarchical control
framework. Section 3 recalls the fast-gradient algorithm. Section 4 describes
the data generation used to train the deep neural network. Finally, section 5
describes the illustrative example and shows numerical results to assess the
effectiveness of proposed approaches.

Notation. Let $\oplus$ denotes the concatenation operator, namely for a
sequence of vectors $q_{i_{1}},q_{i_{2}},\dots$ define:

$\underset{i\in\mathcal{I}}{\oplus}q_{i}:=[q_{i_{1}}^{T},q_{i_{2}}^{T},\dots]^{T},\,\,\text{with}\quad
i_{1}<i_{2}<\dots\in\mathcal{I}$ (1)

Moreover, the bold-faced notation $\bm{p}$ denotes the profile of a vector
variable $p$ over a prediction horizon of length $N$, namely:

$\bm{p}=[p^{T}(k),\dots,p^{T}(k+N-1)]^{T}\in\mathbb{R}^{N\cdot n_{p}}$ (2)

##  2 Recall on fixed-point based hierarchical control framework:

Fig. 1 described the case of interest where a set of interacting subsystems
indexed by $\mathcal{N}:=\\{1,\dots,n_{s}\\}$ is represented. This set is
subdivided into two different subsets:

  * •

A subset of controlled subsystems indexed by
$\mathcal{N}^{ctr}\subset\mathcal{N}$ having each its control input vector and
regulated output vector, denoted for any $s\in\mathcal{N}^{ctr}$ by $u_{s}$
and $y_{s}$ respectively.

  * •

A potential complementary subset of subsystems that includes no control input
denoted by $N^{unc}:=\mathcal{N}-\mathcal{N}^{ctr}$.

The dynamic of each subsystem $S_{s}$ is impacted through the so-called
coupling signal $v_{s^{\prime}\rightarrow s}$ coming from all exogenous
subsystems $\\{S_{s^{\prime}}\\}_{s^{\prime}\in\mathcal{N}_{s}}$ with indices
$s^{\prime}$ belonging to the set of indices $\mathcal{N}_{s}$ (set of indices
of subsystems impacting $S_{s}$).

Figure 1: Example of the hierarchical control architecture and the
interconnection network between the subsystems. The presented sets correspond
to this example are $\mathcal{N}:=\\{1,2,3\\}$;
$\mathcal{N}^{ctr}:=\\{1,3\\}$, $\mathcal{N}_{1}=\\{2,3\\}$,
$\mathcal{N}_{2}=\\{1,3\\}$, $\mathcal{N}_{3}=\\{1,2\\}$.

Let $\bm{v}^{in}_{s}$ and $\bm{v}^{out}_{s}$ be the incoming/outgoing coupling
profiles into and from the subsystem $S_{s}$ respectively. More precisely:

$\bm{v}_{s}^{in}:=\underset{s^{\prime}\in\mathcal{N}_{s}}{\oplus}\bm{v}_{s^{\prime}\rightarrow
s}\quad;\quad\bm{v}_{s}^{out}:=\underset{s^{\prime}|s\in\mathcal{N}_{s^{\prime}}}{\oplus}\bm{v}_{s\rightarrow
s^{\prime}}$ (3)

In (Pham et al., 2021b) the generic formulation of the proposed framework has
been well defined. However, it is essential to recall the overall hierarchical
control framework. Let us begin with the following assumption:

###### Assumption 1

Each subsystem $S_{s}$, when given

  * •

a presumed incoming profile $\bm{v}_{s}^{in}$ and

  * •

a given individual set-point $r_{s}$ (required if $s\in\mathcal{N}^{ctr}$),

can compute what would be:

  * •

Its control profile $\bm{u}_{s}$ (if it has) by solving an nonlinear
optimization problem,

  * •

Its resulting outgoing profile $\bm{v}_{s}^{out}$ and ,

  * •

Its contribution $J_{s}$ to the central cost.

The central cost is assumed to be of the form:

$J_{c}(r,\bm{v}^{in}):=\sum_{s\in\mathcal{N}^{ctr}}J_{s}(r_{s},\bm{v}_{s}^{in})+\sum_{s\in\mathcal{N}^{unc}}J_{s}(\bm{v}_{s}^{in})$
(4)

where $r:=\underset{s\in\mathcal{N}^{ctr}}{\oplus}r_{s}$ and
$\bm{v}^{in}:=\underset{s\in\mathcal{N}}{\oplus}\bm{v}_{s}^{in}$. Note that
typical regulation-based cost $J_{s}$ is defined for $s\in\mathcal{N}^{ctr}$
while $J_{s}$ might represent a constraints violation indicator when
$s\notin\mathcal{N}^{ctr}$.

More precisely, each time the coordinator sends $(r,\bm{v}^{in})$ to the
subsystems, this allows subsystems to compute (in parallel) their
corresponding control profiles $\bm{u}_{s}$ (if $s\in\mathcal{N}^{ctr}$) and
the outgoing coupling signal profiles $\bm{v}_{s}^{out}$ which is represented
by the following form:

$\bm{v}_{s}^{out}=g_{out}(r,\bm{v}^{in})$ (5)

Recall that both $\bm{v}^{in}$ and $\bm{v}^{out}$ are composed of all the
elementary profiles $\bm{v}_{s\rightarrow s^{\prime}}$. Hence, there is a
matrix $G_{in}$ such that:

$\bm{v}^{in}=G_{in}\cdot\bm{v}^{out}$ (6)

By injecting (5) into (6), we obtain:

$\bm{v}^{in}=G_{in}\cdot\bm{g}_{out}(r,\bm{v}^{in})$ (7)

Consequently, the problem that needs to be solved exclusively by the
coordinator can be stated as follows:

$\displaystyle r^{opt}$
$\displaystyle=\operatorname*{argmin}_{r}J_{c}(r,\bm{v}^{in})$ (8)
$\displaystyle\text{subject to:}\,\bm{v}^{in}$
$\displaystyle=G_{in}\cdot\bm{g}_{out}(r,\bm{v}^{in})$ (9)

Since the coordinator does not have any mathematical knowledge of the
subsystems the fixed-point map represented by (9) cannot be analytically known
to the coordinator. That is the reason why the enforcement of (9) for a given
set-point $r$ is done through a round of iterations between the coordinator
and the subsystems as initially suggested in (Alamir et al., 2017) where a
fixed-point-iteration-based algorithm is proposed to evaluate a central cost
associated to a given set-point $r$. Briefly, the algorithm could be
summarized as below:

  1. 1.

The coordinator starts by sending an initial guess
$\bm{v}^{in,(\sigma=0)}_{s}$ regarding the incoming profiles,

  2. 2.

The subsystems compute their control profiles (if any) and the corresponding
in outgoing coupling profiles $\hat{\bm{v}}^{out,(\sigma)}_{s}$ as well as
their local cost $J_{s}$,

  3. 3.

The subsystems send the outgoing coupling profiles
$\hat{\bm{v}}^{out,(\sigma)}_{s}$ to the coordinator from which the
coordinator can constitute the corresponding incoming coupling profiles
$\hat{\bm{v}}^{in,(\sigma)}_{s}$ based on (6).

  4. 4.

To ensure the convergence of the iteration, a stabilizing filter or a
residual-based iterative method is used to update the profile denoted by
$\bm{v}^{in,(\sigma+1)}_{s}$,

  5. 5.

The iterations continue until the termination criteria
$\epsilon:=\text{max}(|\bm{v}^{in,(\sigma+1)}-\bm{v}^{in,(\sigma)}|)\leq$ is
satisfied.

Having the cost associated to a given set-point, any derivative-free
optimization algorithm can be used to solve (8) in the decision variable $r$
(e.g. Genetic algorithm (Thede, 2004), BOBYQA (Powell, 2009), etc.).

##  3 Fast gradient method for solving NMPC problem

Since the solution of the local NMPC problems is processed in parallel, the
real-time feasibility of the framework depends considerably on the critical
subsystem requiring the highest computation time. Although many toolkits for
solving optimization-based control problems, such as ACADO (Houska et al.,
2011) or CasADi (Andersson et al., 2019), it has been shown in (Alamir, 2014)
that when a limited (computation time)/(hardware performance) are present, a
truncated fast gradient might be beneficial to closed-loop performances. That
is why this algorithm is briefly recalled here as it is in the heart of the
forthcoming development.

Recall that each subsystem $S_{s}$, $s\in\mathcal{N}^{ctr}$ solves an
optimization problem upon receiving a pair of $(r_{s},\bm{v}^{in}_{s})$ from
the coordinator:

$\displaystyle\mathcal{P}_{s}:\min_{\bm{u}_{s}\in\mathcal{U}_{s}}J^{loc}_{s}(\bm{u}_{s})$
(10)

where $\mathcal{U}_{s}$ are the admissible set of control profiles
$\bm{u}_{s}$. Note that the cost function $J^{loc}_{s}$ implicitly depends on
the current state, the set-point $r_{s}$ and the incoming coupling profile
$\bm{v}_{s}^{in}$. These variables are considered frozen during the solution
of (10) and are dropped for reasons of compactness.

The implementation of the fast gradient method requires the gradient of the
cost function at $J^{loc}_{s}$ with respect to $\bm{u}_{s}$, which can be
easily obtained by modeling the cost with CasADi and then computing its
gradient $\nabla J^{loc}_{s}$. The algorithm that is used to solve (10) is
given by the following updating rule:

$\displaystyle\bm{z}_{s}^{i+1}$
$\displaystyle=\bm{u}_{s}^{i}-\gamma\cdot\nabla J^{loc}_{s}(\bm{u}_{s}^{i})$
(11) $\displaystyle\bm{u}_{s}^{i+1}$
$\displaystyle=\textbf{Pr}(\bm{z}_{s}^{i+1}+c\cdot(\bm{z}_{s}^{i+1}-\bm{z}_{s}^{i}),\mathcal{U}_{s})$
(12)

where $c\in(0,1)$ is the design variable and $\textbf{Pr}(p,\mathcal{U}_{s})$
is the projection of vector $p$ on the admissible set $\mathcal{U}_{s}$. The
variable $\gamma$ is the step size that is calculated by using Barzilai-
Borwein formula proposed in (Barzilai and Borwein, 1988):

$\gamma^{i+1}=\frac{\|(\bm{u}_{s}^{i+1}-\bm{u}_{s}^{i})\cdot(\nabla
J^{loc}_{s}(\bm{u}_{s}^{i+1})-\nabla J^{loc}_{s}(\bm{u}_{s}^{i}))\|}{\|\nabla
J^{loc}_{s}(\bm{u}_{s}^{i+1})-\nabla J^{loc}_{s}(\bm{u}_{s}^{i})\|^{2}}$ (13)

In (Meyer, 1976), the author shows that the convergence of the algorithm could
be improved when a restart mechanism is included. More precisely, the variable
$\bm{u}_{s}$ is restarted every $n_{rst}$ iteration, but it is noted that the
frequency of restarts should depend on the cost function.

Finally, this method is summarized by Algorithm 1.

Algorithm 1 Fast conjugate gradient method

1:Initialize:

2: $i\leftarrow 0$; $c\in(0,1)$; $\gamma^{i}\in(0,1)$; $n_{rstr}\in\mathbb{N}$
$\bm{u}_{s}^{i}\leftarrow\textbf{0}$; $\bm{z}_{s}^{i}\leftarrow\textbf{0}$

3:

4:for $i\leftarrow 1,\dots,N_{max}$ do

5: $\bm{z}_{s}^{i+1}=\bm{u}_{s}^{i}-\gamma^{i}\cdot\nabla
J^{loc}_{s}(\bm{u}_{s}^{i})$;

6: if $\text{mod}(i,n_{rstr})==0$ then $\triangleright$ check for restart

7: $\bm{u}_{s}^{i+1}=\textbf{Pr}(\bm{z}_{s}^{i+1},\mathcal{U}_{s})$;

8: else

9:
$\bm{u}_{s}^{i+1}=\textbf{Pr}(\bm{z}_{s}^{i+1}+c\cdot(\bm{z}_{s}^{i+1}-\bm{z}_{s}^{i}),\mathcal{U}_{s})$;

10: end if

11: Compute $\gamma^{i+1}$ by (13);

12:end for

##  4 Approximate NMPC by neural network

Recently, deep neural networks (DNNs) have become a popular choice for the
functional form $K_{NN}(z;\theta)$ (with $z$ being the argument of the control
law) because of their universal approximation property. Furthermore, DNNs
could be easily implemented in any programmable logic controllers (PLCs),
whose computational capabilities are not suitable for high-level solver. With
$L$ hidden layers and H nodes per layer, a DNN is given by:

$K_{NN}(z;\theta)=\alpha_{L+1}\circ\beta_{L}\circ\alpha_{L}\circ\dots\circ\beta_{1}\circ\alpha_{1}(z)$
(14)

Each hidden layer involves affine transformation of the output of its previous
layer:

$\alpha_{l}(\epsilon_{l-1})=W_{l}\cdot\epsilon_{l-1}+b_{l}$ (15)

in which $\epsilon_{l-1}\in\mathbb{R}^{H}$ for $l\in\\{2,\dots,L+1\\}$ and
$\epsilon_{0}=z$. The function $\beta_{l}$, for $l\in\\{1,\dots,L\\}$ are
nonlinear activation functions (e.g, rectified linear units (Relu),
sigmoid,…). The parameter vector
$\theta=\\{W_{1},b_{1},\dots,W_{L+1},b_{L+1}\\}$ gathers all weights $W_{l}$
and biases $b_{l}$ in the network with appropriate dimension Once the network
architecture is trained according to , the approximate DNN-based NMPC law
$K_{NN}(z,\theta)$ can be used online to cheaply evaluate the optimal control
input.

###  4.1 Data generation

There are two common data-generation strategies, namely open-loop and closed-
loop. In open-loop data generation, the set
$\mathcal{Z}\subset\mathcal{X}_{s}\times\mathcal{V}^{in}\times\mathcal{R}_{s}\times\mathcal{W}_{s}$
of possible states, incoming coupling profiles, disturbances and set-points
could be created and the corresponding control profile $\bm{u}_{s}$ computed
that will be added together to establish a set of data
$\mathcal{D}=\\{(x^{(i)}_{s},\bm{v}^{in,(i)}_{s},r^{(i)}_{s},\bm{w}^{(i)}_{s},\bm{u}^{(i)}_{s})\\}_{i=1}^{N_{s}}$.
Although very simple, this strategy can result non physically realistic
instances being included in the training data. Closed-loop strategy, on the
contrary, gathers data while running a closed-loop simulation under randomly
drawn physically meaningful initial states. Indeed, the majority of large-
scale cryogenic systems operate under a relatively small number of regimes or
operating scenarios. Each operational scenario is characterized by a few
controlled outputs and a few large magnitude disturbances that may change
frequently, while the set-points are kept unchanged for a long period of time.
Hence, we propose the following data generation procedure that performs off-
line simulation using model to collect the operationally relevant training set
$\mathcal{D}$:

  1. 1.

Determine the operational range of the set-points denoted by
$[\underline{r}_{s},\overline{r}_{s}]$ and the realistic range of the
disturbances denoted by $[\underline{w}_{s},\overline{w}_{s}]$:

  2. 2.

Create pseudo random binary signals (PRBS) of $r_{s}$ and $w_{s}$ in their
operational ranges.

  3. 3.

Run the closed-loop simulations that implement the above discussed
hierarchical design at some chosen initial states with the created PRBS
signals. Note that Data is collected during the fixed-point iterations in
order to capture the relationship between the control profile $\bm{u}_{s}$ and
the triplet $(r_{s},x_{s},\bm{v}^{in}_{s}$).

The network is trained to minimize the mean squared error criteria below:

$J_{NN}(\theta)=\frac{1}{2}\sum_{j=1}^{N_{tr}}[K_{NN}(z_{s}^{(j)},\theta)-\bm{u}_{s}^{(j)}]^{2}$
(16)

where $N_{tr}$ is the number of training observations. The resilient back-
propagation (RPROP) algorithm is used to train the neural network. The
activation function at each node is the sigmoid function. Many configurations
of NN will be examined in the simulation section.

##  5 System description / numerical results

###  5.1 System description

The system under investigation is the cold box of a cryogenic refrigerator
(Fig. 2) composed of a Joule-Thomson cycle and a Brayton cycle. The Brayton
cycle is composed of two heat exchangers, which are NEF2, NEF34 and a
cryogenic turbine T1. The thermal energy from the helium flow is extracted by
using the turbine T1 and by exchanging the heat power between high pressure
pipe line and low pressure pipe line through a series of heat exchangers
(NEFx). When passing the valve CV155 (Joule-Thomson cycle), the isenthalpic
process occurs, resulting in the liquefaction of part of the gaseous helium,
which rests in the helium bath. The remaining gaseous part return to the cycle
through the low pressure line.

Figure 2: Block diagram of the cold box plant.

The Manipulated Inputs: There are three control inputs which are CV155, NCR22
belonging to Joule-Thomson cycle and $\Delta\text{P}_{156}$ which is a part of
the Brayton cycle. These actuators are defined below:

  1. 1.

CV${}_{155}\in[0\%,100\%]$: This valve is situated at the inlet of the helium
bath.

  2. 2.

NCR${}^{(a)}_{22}$: This heating actuator is located inside the helium bath.
The value of $\text{NCR}_{22}^{(a)}$ is in the range of $[0,55]$ W. Note that
the variable NCR22 in Fig. 2 is decomposed into two terms:

$\text{NCR}_{22}:=\text{NCR}_{22}^{(a)}+\text{NCR}_{22}^{(w)}$ (17)

where $\text{NCR}_{22}^{(w)}$ represents the disturbance coming from the heat
source.

  3. 3.

$\Delta\text{P}_{156}\in[0,12]$ bar: The pressure drop between the inlet
pressure and outlet pressure of the valve CV156. Indeed, in order to hide the
nonlinearity, the valve CV156 is controlled through the pressure drop between
its inlet and outlets. Precisely, the required pressure drop is calculated by
an NMPC and sent to the PID controller, which acts on the opening position of
the CV156 valve (Fig. 2).

The Regulated Outputs: There are three regulated outputs and one constrained
output (Figure 2):

  1. 1.

Ltb131: The helium liquid level (%) that must be controlled to ensure that
some thermal loads are always extracted (e.g. used to cool super-critical
helium at liquid helium temperature to be ready for the final customer). The
set-point is chosen by the operator. In the usual operation, it is set at
Ltb${}_{131}^{sp}=60.5\%$.

  2. 2.

Ttb108: The temperature at the inlet of the J-T valve must be tightly
controlled in order to ensure the efficiency of the liquefaction of the
helium.

  3. 3.

Ttb130: Since the cryogenic turbine is a critical component, the temperature
at its outlet must be tightly regulated to avoid the risk of liquid droplet
forming at the outlet, potentially destructive for the turbine.

  4. 4.

$M_{out}$: The exiting flow rate of exchanger NEF34 is constrained to be lower
than an allowed maximum flow rate $\overline{M}_{out}=0.07$ kg/s.

This system could be viewed as a network of four coupled subsystems (Fig. 3).

Figure 3: Block diagram of the cold box plant.

Table 1 summarizes the inputs and outputs of each subsystems in this
decomposition. The notation $T_{C}$, $M_{C}$, and $P_{C}$ ($T_{H}$, $M_{H}$,
and $P_{H}$) are respectively the temperature, flow rate, and pressure of the
cold (hot) branch of the refrigerator.

Table 1: The inputs, outputs and the coupling variables of the 4-subsystems topology. | $u_{s}$ | $y_{s}$ | $v_{s\rightarrow s^{\prime}}$
---|---|---|---
$S_{1}$ |  | NCR${}_{22}^{(a)}$
---
CV155
| Ltb131
---
Ttb108
$v_{1\rightarrow 2}=[M_{H}^{1\rightarrow 2},M_{C}^{1\rightarrow
2},T_{C}^{1\rightarrow 2}]^{T}$
$S_{2}$ | _ | _ |  | $v_{2\rightarrow 1}=[T_{H}^{2\rightarrow 1},P_{H}^{2\rightarrow 1},P_{C}^{2\rightarrow 1}]^{T}$
---
$v_{2\rightarrow 3}=[M_{H}^{2\rightarrow 3},M_{C}^{2\rightarrow
3},T_{C}^{2\rightarrow 3}]^{T}$
$v_{2\rightarrow 4}=[P_{C}^{2^{\prime}\rightarrow 4}]$
$S_{3}$ | _ | $M_{out}$ |  | $v_{3\rightarrow 2}=[T_{H}^{3\rightarrow 2},P_{H}^{3\rightarrow 2},P_{C}^{3\rightarrow 2}]^{T}$
---
$v_{3\rightarrow 4}=[T_{H}^{3\rightarrow 4},P_{H}^{3\rightarrow 4}]^{T}$
$S_{4}$ |  $\Delta$P156 | Ttb130 |  | $v_{4\rightarrow 2}=[M_{C}^{4\rightarrow 2},T_{C}^{4\rightarrow 2}]^{T}$
---
$v_{4\rightarrow 3}=[M_{H}^{4\rightarrow 3}]$

The following local costs of each subsystem are used: For $S_{1}$ and $S_{4}$
that need to track the desired set-point $r^{d}_{s}$:

$J_{s}(r|r^{d}_{s})=\sum_{i=0}^{N-1}\|y_{s}(k+i)-r^{d}_{s}\|^{2}_{Q_{c}^{(s)}}+\|u_{s}(k+i)\|^{2}_{R_{c}^{(s)}}$
(18)

For $S_{3}$ that has output to be constrained

$J_{3}(r|\overline{y}_{3})=\sum_{i=0}^{N-1}\|\max(y_{3}(k+i)-\overline{y}_{3},0)\|^{2}_{Q_{c}^{(3)}}$
(19)

Finally, $S_{2}$ does not have any contribution to the central cost, its cost
is simply defined by $J_{2}(r)=0$. Note however that this subsystem impacts
the fixed-point definition as its outlet $\bm{v}_{s}^{out}$ depend on the
incoming parameters. The weighing matrices appears in (18)-(19) is listed
below:

$\displaystyle Q_{c}^{(1)}$ $\displaystyle=\text{diag}([10^{3},10^{3}])$
$\displaystyle\quad Q_{c}^{(4)}=10^{3}$ $\displaystyle Q_{c}^{(3)}$
$\displaystyle=10^{10}$ (20) $\displaystyle R_{c}^{(1)}$
$\displaystyle=\text{diag}([0,0])$ $\displaystyle\quad R_{c}^{(4)}=0$ (21)

where $\text{diag}()$ denotes a diagonal matrix.

In order to compare the performance of two strategies, the closed-loop
performance $J_{c}^{cl}$ is used that is defined by:

$\displaystyle
J_{c}^{cl}=\frac{1}{N_{sim}}\sum_{i=1}^{N_{sim}}\sum_{s\in\mathcal{N}}J_{s}^{cl}(i)$
(22)

where $N_{sim}$ is the simulation time duration , $J_{s}^{cl}(i)$ is computed
according to the criteria of each subsystem as defined in (18)-(19)

Since the local controller of the Joule-Thomson cycle ($S_{1}$) has the most
critical computation time compared to one of the Brayton cycle, it will be
approximated by the DNN. Concerning the data generation to train the DNN, the
procedure described in section 4 is performed while optimal control profiles
are obtained by using the fast gradient method because the computation time of
CasADi (which is 0.5 secs for resolving problem (10) is highly impractical to
be used in this framework which will be shown in the beginning of subsection
5.

###  5.2 DNN model assessment

The learning performance is evaluated for three different configurations of
DNNs. These configurations are set up so that each DNN has a different number
of hidden layers, ranging from 1 to 3 layers, with each layer having the same
number of nodes, i.e. 25 nodes, denoted by NN-1-25, NN-2-25 and NN-3-25,
respectively. Concretely, each structure is trained for $10000$ epochs, with
$450\times 10^{3}$ samples and validated with $450\times 10^{3}$ in the same
sample pool. Table 2 presents the learning performance for three DNN
structures. The structure NN-2-25 which has the lowest MSE is chosen to
conduct the next simulation.

Table 2: The learning performance of several configuration of DNNs. Structure | NN architecture | MSE | Training time
---|---|---|---
NN-1-25 | [25 25 12] | 0.3192 | 2h47
NN-2-25 | [25 25 25 12] | 0.2726 | 3h15
NN-3-25 | [25 25 23 25 12] | 0.2996 | 3h50

###  5.3 Numerical result

First, we compare the performance of the Ipopt (CasADi) solver and the
truncated gradient solver used to solve the problem (10) of $S_{1}$. This can
be done by evaluating the open-loop performance indicated by
$J_{s}^{loc}(\bm{u}_{s}^{*})$, where $\bm{u}_{s}^{*}$ is the solution of (10).
The evaluation process is described below:

  1. 1.

Create realistic set of state $x_{s}$, set-point $r_{s}$ and $\bm{v}_{s}^{in}$
denoted by
$\mathcal{D}^{\text{solver}}:=\\{(x_{s}^{(i)},r_{s}^{(i)},\bm{v}_{s}^{(i)})\\}_{i=1}^{N_{dta}}$;

  2. 2.

Solve the problem (10) by using solver Ipopt and truncated gradient at
triplets $(x_{s}^{(i)},r_{s}^{(i)},\bm{v}_{s}^{(i)})$ (for
$i=1,\dots,N_{dta}$);

  3. 3.

The open-loop performances $J_{s}^{loc,(i)}(\bm{u}_{s}^{*,\text{Ipopt}})$ and
$J_{s}^{loc,(i)}(\bm{u}_{s}^{*,\text{grd}})$ of the solver Ipopt and truncated
gradient are computed. Then, the average of performance ratio $\overline{J}$
between the two solvers is computed, namely:

$\overline{J}=\frac{1}{N_{dta}}\sum_{i=1}^{N_{dta}}\frac{J_{s}^{loc,(i)}(\bm{u}_{s}^{*,\text{grd}})}{J_{s}^{loc,(i)}(\bm{u}_{s}^{*,\text{Ipopt}})}\times
100\%$ (23)

The maximum number of iterations $N_{\text{iter}}^{\text{max}}$/ the
acceptable tolerance $\epsilon_{\text{tol}}$ of solver Ipopt is set at $5$ and
$10^{-1}$, respectively. For the truncated gradient solver, the maximum number
of iteration is set to $N_{max}=50$ and the update variable is restarted at
every $n_{rstr}=5$ iterations.

Table 3: Performance index of solver Ipopt and truncate gradient. | $N_{max}$ | $\epsilon_{\text{tol}}$ | $\overline{J}$ | $t^{\text{max}}_{\text{cpt}}$
---|---|---|---|---
Truncated gradient | 50 | - | $99.81\%$ | 0.018s
IPOPT | 5 | $10^{-1}$ | $100\%$ | 0.502s

Table 3 shows the average performance ratio $\overline{J}$ and the maximal
computation time $t^{\text{max}}_{\text{cpt}}$ associated to the two solvers.
It can be noted that the truncated gradient solver gives a more far lower time
while achieving in average the same open-loop performance compared to those
given by Ipopt solver.

Second, we compare the performance of the hierarchical control framework with
different set-ups. More precisely, we compare the closed-loop performance
indices $J_{c}^{CL}$s under the disturbance profile (Fig. 4) when using the
exact NMPC of the Joule-Thomson cycle, the approximation NN-2-25 with
$\tau_{u}=2s$ and with $\tau_{u}=0.7s$ (Fig. 5). It can be noted that the DNN
approach allows to update more frequently the control decision, which results
a better performance in closed-loop.

Figure 4: Disturbance profile. Figure 5: Comparison of the system behavior
with different configurations.

Finally, Fig. 6 shows the computation time associated to the Joule-Thomson
cycle within the hierarchical control framework.

Figure 6: Computation time of NN-2-25 and NMPC.

##  6 Conclusion

In this paper, two methods have been proposed to reduce the computation time
of solving the constrained nonlinear optimization problem at the local layer
of the hierarchical control framework. The numerical results have demonstrated
the effectiveness of the two methods. On going work aims to validate the
control structure with a full cryogenic facility.

## References

  * Alamir (2014) Alamir, M. (2014).  Fast nmpc: A reality-steered paradigm: Key properties of fast nmpc algorithms.  In _2014 European Control Conference (ECC)_ , 2472–2477. IEEE.
  * Alamir et al. (2017) Alamir, M., Bonnay, P., Bonne, F., and Trinh, V.V. (2017).  Fixed-point based hierarchical MPC control design for a cryogenic refrigerator.  _Journal of Process Control_ , 58, 117–130.
  * Andersson et al. (2019) Andersson, J., Gillis, J., Horn, G., Rawlings, J., and Diehl, M. (2019).  Casadi: a software framework for nonlinear optimization and optimal control.  _Mathematical Programming Computation_ , 11, 1–36.
  * Barzilai and Borwein (1988) Barzilai, J. and Borwein, J.M. (1988).  Two-point step size gradient methods.  _IMA journal of numerical analysis_ , 8(1), 141–148.
  * Bonne et al. (2014) Bonne, F., Alamir, M., and Bonnay, P. (2014).  Experimental investigation of control updating period monitoring in industrial plc-based fast MPC: Application to the constrained control of a cryogenic refrigerator.  _Control Theory and Technology_ , 15, 92–108.
  * Claudet et al. (2000) Claudet, S., Gayet, P., Lebrun, P., Tavian, L., and Wagner, U. (2000).  Economics of large helium cryogenic systems: experience from recent projects at CERN.  In _Advances in cryogenic engineering_ , 1301–1308. Springer.
  * Henry et al. (2007) Henry, D., Journeaux, J., Roussel, P., Michel, F., Poncet, J., Girard, A., Kalinin, V., and Chesny, P. (2007).  Analysis of the ITER cryoplant operational modes.  _Fusion Engineering and Design_ , 82(5), 1454 – 1459.  Proceedings of the 24th Symposium on Fusion Technology.
  * Houska et al. (2011) Houska, B., Ferreau, H.J., and Diehl, M. (2011).  Acado toolkit—an open-source framework for automatic control and dynamic optimization.  _Optimal Control Applications & Methods_, 32, 298–312.
  * Meyer (1976) Meyer, R.R. (1976).  On the convergence of algorithms with restart.  _SIAM Journal on Numerical Analysis_ , 13(5), 696–704.
  * Pham et al. (2021a) Pham, X.H., Alamir, M., Bonne, F., and Bonnay, P. (2021a).  Revisiting a fixed-point hierarchical control design for cryogenic refrigerators unde constraints, nonlinearities and real-time considerations.  _European Journal of Control_ , under press.
  * Pham et al. (2021b) Pham, X.H., Alamir, M., Bonne, F., and Bonnay, P. (2021b).  A generic fixed-point iteration-based hierarchical control design: Application to a cryogenic process.  _arXiv preprint arXiv:2109.10717_.
  * Powell (2009) Powell, M. (2009).  The BOBYQA algorithm for bound constrained optimization without derivatives.
  * Thede (2004) Thede, S.M. (2004).  An introduction to genetic algorithms.  _Journal of Computing Sciences in Colleges_ , 20(1), 115–123.


# Socially Aware Coalition Formation with Bounded Coalition Size

Chaya Levinger  Amos Azaria and Noam Hazon<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In many situations when people are assigned to coalitions the assignment must
be social aware, i.e, the utility of each person depends on the friends in her
coalition. Additionally, in many situations the size of each coalition should
be bounded. This paper initiates the study of such coalition formation
scenarios in both weighted and unweighted settings. We show that finding a
partition that maximizes the utilitarian social welfare is computationally
hard, and provide a polynomial-time approximation algorithm. We also
investigate the existence and the complexity of finding stable partitions.
Namely, we show that the Contractual Strict Core (CSC) is never empty, but the
Strict Core (SC) of some games is empty. Finding partitions that are in the
CSC is computationally easy, but finding partitions that are in the SC is
hard. The analysis of the core is more involved. For the weighted setting, the
core may be empty. We thus concentrate on the unweighted setting. We show that
when the coalition size is bounded by $3$ the core is never empty, and we
present a polynomial time algorithm for finding a member of the core. When the
coalition size is greater, we provide additive and multiplicative
approximations of the core. In addition, we show in simulation over 100
million games that a simple heuristic always finds a partition that is in the
core.

##  1 Introduction

Suppose that a group of travelers who are located at some origin, would like
to reach the same destination, and later return. Each of the travelers has her
own vehicle; but each traveler has a preference related to whom will be with
her in the vehicle. Namely, each traveler would rather share a vehicle with as
many as possible of her friends during the ride, and thus the utility of each
traveler is the number of friends traveling with her. However, the vehicles
have a limited capacity; this capacity can either be a physical constraint of
the vehicles, or the maximal number of travelers willing to travel together.
How should the travelers be assigned to vehicles in order to maximize the
social welfare (the sum of all travelers’ utilities)? Can the travelers be
organized such that no subgroup of travelers will want to leave their current
group and join together? Similar questions raise when assigning students to
dormitories, colleagues to office-rooms and workers to project teams. In these
settings, it might be that the utility of each person does not depend only on
the number of friends, but also on the intensity of friendship.

This set of problems falls within hedonic games [13], in which a set of agents
are partitioned into coalitions, and the utility for each agent depends only
on the coalition that she is a member of. Additively Separable Hedonic Games
(ASHGs) [9] are a special type of hedonic games, in which each agent has a
value for any other agent, and the utility she assigns to a coalition is the
sum of the values she assigns to its members. In ASHGs there is usually no
restriction on the number of agents that are allowed to belong to a coalition.
However, in our group of travelers example, the vehicles have physical
capacity, and thus, there is an upper bound on the size of each coalition.
Despite this restriction being natural, it is scarcely studied in the domain
of hedonic games.

In this paper, we initiate the study of hedonic games with bounded coalition
size. Specifically, we concentrate on symmetric ASHGs, in which the value an
agent assigns to another agent is non-negative and it is equal to the value
that the other agent assigns to her; we refer to these settings as the
weighted settings. We also study simple symmetric ASHGs, in which the value an
agent assigns to other agents is either $0$ or $1$; we refer to these settings
as the unweighted settings. These models capture many situations, such as
social and friendship relations. We begin by studying the problem of finding a
partition that maximizes the utilitarian social welfare. We show that this
problem is computationally hard for any coalition size bound $k>2$, even in
the unweighted setting. Therefore, we provide a polynomial-time approximation
algorithm. We prove that in the unweighted setting, the algorithm has an
approximation ratio of $\frac{1}{k-1}$, and in the weighted setting it has an
approximation ratio of $\frac{1}{k}$.

We then study stability aspects of the problem. That is, we investigate the
existence and the complexity of finding stable partitions. Namely, we show
that the Contractual Strict Core (CSC) is never empty, but the Strict Core
(SC) of some games is empty. Finding partitions that are in the CSC is
computationally easy, but finding partitions that are in the SC is hard. The
analysis of the core is more involved. For the weighted setting, the core may
be empty; we provide an example for $k=3$. We thus concentrate on the
unweighted setting. We show that for k=$3$ the core is never empty, and we
present a polynomial time algorithm for finding a member of the core. For
$k>3$ it is unclear whether the core can be empty, and how to find a partition
in the core. Therefore, we investigate additive and multiplicative
approximations of the core. In addition, we show in simulation over 100
million games that a simple heuristic always finds a partition that is in the
core.

To summarize, the contribution of this work is being the first systematic
study of additively separable hedonic games with bounded coalition size.
Namely, we provide an approximation algorithm for maximizing the utilitarian
social welfare and study the computational aspects of several stability
concepts.

##  2 Related Work

Dreze and Greenberg [1980] initiated the study of hedonic games, in which the
utility for each agent depends only on the coalition that she is a member of.
Stability concepts of hedonic games were further analyzed in [6] and [10]. For
more details, see the survey of Aziz et al. [2016]. A special case is
Additively Separable Hedonic Games (ASHGs) [9], in which each agent has a
value for any other agent, and the utility she assigns to a coalition is the
sum of the values she assigns to its members. The computational aspects of
ASHGs are analyzed in [12, 5, 21, 24, 1, 4, 7]. None of these works imposed
any restriction on the size of the coalitions.

Indeed, there are few papers that impose a restriction on the size of the
coalitions. Wright and Vorobeychik [2015] study a model of ASHG where there is
an upper bound on the size of each coalition. Within their model, they propose
a strategyproof mechanism that achieves good and fair experimental
performance, despite not having a theoretical guarantee. Flammini et al.
[2021] study the online partition problem. Similar to our work, they also
consider the scenario that the coalitions are bounded by some number. They
consider two cases for the value of a coalition, the sum of the weights of its
edges, which is similar to our work, and the sum of the weights of its edges
divided by its size. However, in both cases they only consider the online
version, i.e., the agents arrive sequentially and must be assigned to a
coalition as they arrive. This assignment cannot be adapted later on, and must
remain. They show that a simple greedy algorithm achieves an approximation
ratio of $\frac{1}{k}$ when the value of the coalition is the sum of the
weights. Cseh et al. [2019] require the partition to be composed of exactly
$k$ coalitions, and also assume a predefined set of size constraints. Each
coalition is required to exactly match its predefined size. They study the
complexity of finding a Pareto optimal partition, as well as the complexity of
deciding whether a given partition is Pareto optimal. Bilò et al. [2022]
consider the same settings as Cseh et al. Since classical stability notions
are infeasible in their setting, they study three different types of swap
stability, and analyze the existence, complexity, and efficiency of stable
outcomes. Note that almost all other works analyzing ASHGs assume that an
agent may assign a negative value to another agent. Otherwise, since they do
not impose any restrictions on the coalition size, the game becomes trivial,
as the grand coalition is always an optimal solution. We found two exceptions
who restrict the value each agent assigns to other agents to be either $0$ or
$1$. Namely, Sless et al. [2018] study the setting in which the agents must be
partitioned into exactly $k$ coalitions, without any restriction on each
coalition’s size. Li et al. [2023] study the setting in which the agents must
be partitioned into exactly $k$ coalitions that are almost equal in their
size.

In our study of the core, we consider additive and multiplicative
approximations for the core. We note that similar approximations were
discussed in other settings [22, 20, 15]. Recent work by Li et al. [2023] has
considered both additive and multiplicative approximations of the core in
ASHGs.

##  3 Preliminaries

Let $V=\\{v_{1},...,v_{n}\\}$ be a set of agents, and let $G(V,E)$ be a
weighted undirected graph representing the social relations between the
agents. For every edge $e\in E$, the weight of the edge, $w(e)$, is positive.
In the unweighted setting, all weights are set to $1$. A $k$-bounded coalition
is a coalition of size at most $k$. A $k$-bounded partition $P$ is a partition
of the agents into disjoint $k$-bounded coalitions. Given a coalition $S\in
P$, and $v\in S$, let $N(v,S)$ be the set of immediate neighbors of $v\in V$
in $S$, i.e., $N(v,S)=\\{u\in S:(v,u)\in E\\}$. Let $W(v,S)$ be the sum of
weights of immediate neighbors of $v\in V$ in $S$, i.e., $W(v,S)=\sum_{u\in
N(v,S)}{w((v,u))}$. Note that in the unweighted setting, $W(v,S)=|N(v,S)|$. An
additively separable hedonic game with bounded coalition size is a tuple
$(G,k)$, where for every $k$-bounded partition $P$, coalition $S\in P$, and
$v\in S$, the agent $v$ gets utility $W(v,S)$. We denote the utility of $v$
given a $k$-bounded partition $P$, by $u(v,P)$. Given a tuple $(G,k)$, the
goal is to find a $k$-bounded partition $P$ that satisfies efficiency or
stability properties.

We consider the following efficiency or stability concepts:

  * •

The utilitarian social welfare of a partition $P$, denoted $u(P)$, is the sum
of the utilities of the agents. That is, $u(P)=\sum\limits_{v\in V}u(v,P)$. A
_MaxUtil_ $k$-bounded partition $P$ is a partition with maximum $u(P)$.

  * •

A $k$-bounded coalition $S$ is said to _strongly block_ a $k$-bounded
partition $P$ if for every $v\in S$, $W(v,S)>u(v,P)$. A $k$-bounded partition
$P$ is in the _Core_ if it does not have any strongly blocking $k$-bounded
coalitions.

  * •

A $k$-bounded coalition $S$ is said to _weakly block_ a $k$-bounded partition
$P$ if for every $v\in S$, $W(v,S)\geq u(v,P)$, and there exists some $v\in S$
such that $W(v,S)>u(v,P)$. A $k$-bounded partition $P$ is in the _Strict Core
(SC)_ if it does not have any weakly blocking $k$-bounded coalitions.

  * •

Given a partition $P$ and a set $S$, let $P^{-S}$ be the partition when $S$
breaks off. That is, $P^{-S}=\\{S\\}\cup\bigcup\limits_{C\in P}\\{C\setminus
S\\}$. A $k$-bounded partition $P$ is in the _Contractual Strict Core (CSC)_
if for any weakly blocking $k$-bounded coalition $S$, there exists at least
one agent $v$ such that $u(v,P^{-S})<u(v,P)$.

Due to space constraints, some proofs are deferred to the appendix.

##  4 Efficiency

We begin with the elementary concept of efficiency, which is to maximize the
utilitarian social welfare.

######  Definition 4.1 (MaxUtil problem).

Given a coalition size limit $k$ and a graph $G$, find a MaxUtil $k$-bounded
partition.

For example, given the unweighted graph in Figure 1(a) and a coalition size
limit $k=3$, let
$P=\\{\\{v_{1},v_{3},v_{6}\\},\allowbreak\\{v_{2},v_{4},v_{7}\\},\\{v_{5},v_{8}\\}\\}$,
shown in Figure 1(b). The utilitarian social welfare of this partition, $u(P)$
equals $14$. Indeed, this is an optimal $3$-bounded partition, since there is
no other $3$-bounded partition with higher social welfare. Clearly, the
decision variant of the MaxUtil problem is to decide whether there exists a
$k$-bounded partition with a utilitarian social welfare of at least
$\upsilon$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$ (a) The graph $G$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$ (b) An optimal
partition in $G$

Figure 1: An example for the MaxUtil problem where $k=3$.

###  4.1 The Hardness of the MaxUtil Problem

The MaxUtil problem when $k=2$ is equivalent to the maximum (weight) matching
problem, and thus it can be computed in polynomial time [14]. However, our
problem becomes intractable when $k\geq 3$ even in the unweighted setting. For
the hardness proof, we define for each $k\in\mathbb{N}$ the $Cliques_{k}$
problem, which is as follows.

######  Definition 4.2 ($Cliques_{k}$).

Given an undirected and unweighted graph $G(V,E)$, decide whether $V$ can be
partitioned into disjoint cliques, such that each clique is composed of
exactly $k$ vertices.

Clearly, $Cliques_{2}$ can be decided in polynomial time by computing a
maximum matching of the graph $G$, $M$, and testing whether
$|M|=\frac{|V|}{2}$. However, $Cliques_{k}$ becomes hard when $k\geq 3$.

######  Lemma 1.

$Cliques_{k}$ is $NP$-Complete for every $k\geq 3$.

######  Theorem 2.

The decision variant of the MaxUtil problem is $NP$-Complete, in the
unweighted and weighted settings.

###  4.2 Approximation of the MaxUtil Problem

Since we showed that the MaxUtil problem is $NP$-Complete, we now provide the
Match and Merge (MnM) algorithm (Algorithm 1), which is a polynomial-time
approximation algorithm for any $k\geq 3$. The algorithm consists of $k-1$
rounds. Each round is composed of a matching phase followed by a merging
phase. Specifically, in round $l$ MnM computes a maximum (weight) matching,
$M_{l}\subseteq E_{l}$, for $G_{l}$ (where $G_{1}=G$). In the merging phase,
MnM creates a graph $G_{l+1}$ that includes a unified node for each pair of
matched nodes. $G_{l+1}$ also includes all unmatched nodes, along with their
edges to the unified nodes (lines 1-1). Clearly, each node in $V_{l}$ is
composed of up-to $l$ nodes from $V_{1}$. Finally, MnM returns the $k$-bounded
partition, $P$, of all the matched sets. For example, given the graph $G_{1}$
in Figure 2(a) and $k=4$, the algorithm finds a maximum matching
$M_{1}=\\{(v_{1},v_{2}),(v_{3},v_{4})\\}$ shown in Figure 2(b). It then
creates the graph $G_{2}$, as shown in Figure 2(c), and finds a maximum
matching for it, $M_{2}=\\{(v_{3,4},v_{5})\\}$ shown in Figure 2(d). It then
creates the graph $G_{3}$, as shown in Figure 2(e), and finds a maximum
matching for it, $M_{3}=\\{(v_{3,4,5},v_{6})\\}$. Finally, MnM created the
graph $G_{4}$, as shown in Figure 2(f), and returns the $4$-bounded partition
$P={\\{v_{1},v_{2}\\},\\{v_{3},v_{4},v_{5},v_{6}\\}}$. We note that by the
algorithm construction, a unified node $v_{i_{1},...,i_{l}}$, is created by
merging nodes $v_{i_{1}}$ and $v_{i_{2}}$, and then by merging
$v_{i_{1},i_{2}}$ and $v_{i_{3}}$, and so on.

1 Input: A graph $G(V,E)$ and a limit $k$

Result: A $k$-bounded partition $P$ of $V$.

2 $G_{1}(V_{1},E_{1})\leftarrow G(V,E)$

3 for  _$l\leftarrow 1$ to $k-1$_ do

4 $M_{l}$ $\leftarrow$ maximum (weight) matching in $G_{l}$

5 $G_{l+1}=(V_{l+1},E_{l+1})\leftarrow$ an empty graph

6 $V_{l+1}\leftarrow V_{l}$

7 for  _every $(v_{i_{1},...,i_{l}},v_{j})\in M_{l}$_ do

8 add vertex $v_{i_{1},...,i_{l},j}$ to $V_{l+1}$

9 remove $v_{i_{1},...,i_{l}},v_{j}$ from $V_{l+1}$

10 for  _every $v_{i_{1},...,i_{l+1}}\in V_{l+1}$_ do

11 for  _every $v_{q}\in V_{l+1}$_ do

12 if  _$(v_{i_{1},...,i_{l}},v_{q})\in E_{l}$ or $(v_{i_{l+1}},v_{q})\in
E_{l}$_ then

13 add $(v_{i_{1},...,i_{l+1}},v_{q})$ to $E_{l+1}$

14

15$P\leftarrow$ an empty partition

16 for  _every $v_{i_{1},...,i_{j}}\in G_{k}$_ do

17 add the set $\\{v_{i_{1}},...,v_{i_{j}}\\}$ to $P$

return P

Algorithm 1 Match and Merge (MnM)

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$ (a) The graph $G_{1}$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$ (b) The Matching $M_{1}$

$v_{1,2}$$v_{3,4}$$v_{5}$$v_{6}$ (c) The graph $G_{2}$

$v_{1,2}$$v_{3,4}$$v_{5}$$v_{6}$ (d) The Matching $M_{2}$

$v_{1,2}$$v_{3,4,5}$$v_{6}$ (e) The graph $G_{3}$

$v_{1,2}$$v_{3,4,5,6}$ (f) The graph $G_{4}$

Figure 2: An example for Algorithm 1 where $k=4$.

###  4.3 Approximation Ratio for Unweighted Setting

We first show that MnM provides an approximation ratio of $\frac{1}{k-1}$ for
the MaxUtil problem in the unweighted setting. For that end, we first prove
the following lemma related to the possible edges in every $G_{l}$, $l>1$.

######  Lemma 3.

Given $\hat{v}=v_{i_{1},...,i_{l}}\in V_{l}$, if there exist $v_{i},v_{j}\in
V_{l}$, $v_{i}\neq v_{j}$ such that $(v_{i},v_{i_{n}}),(v_{j},v_{i_{m}})\in E$
for some $1\leq n\leq m\leq l$, then $n=m$.

###### Proof.

Observe that for every $v_{i},v_{j}\in V_{l}$ where $l>1$,
$(v_{i},v_{j})\notin E$, since $M_{1}$ is a maximum matching in $G_{1}$.
Assume by contradiction and without loss of generality that $n<m$. If $n=1$
and $m=2$, then the path $v_{i}\rightarrow v_{i_{n}}\rightarrow
v_{i_{m}}\rightarrow v_{j}$ is an $M_{1}$-augmenting path in $G_{1}$ ([14]),
contrary to the fact that $M_{1}$ is a maximum matching in $G_{1}$. Therefore,
$m\geq 3$. Consider the graph $G_{2}$, since $v_{i_{m}},v_{j}\in V_{2}$, there
exists an edge $(v_{j},v_{i_{m}})\in E$, contrary to our observation.

∎

We now present a hypothetical procedure (Procedure 2) that is provided with a
solution to the MaxUtil problem, which is a $k$-bounded partition (of $G$)
$Opt$, a graph $G_{l}$ (as defined in Algorithm 1), and a corresponding round
index $l$. Without loss of generality, we assume that every set $S\in Opt$ is
a connected component. Let $O=\\{v_{o}|\\{v_{o}\\}\in Opt$ and $v_{o}\in
V_{2}\\}$. That is, $|O|$ is the number of singletons in the partition $Opt$
that are also not matched in $M_{1}$. We show that Procedure 2 finds a
matching, and we provide a lower bound on the size of this matching (the
number of edges in it). We further show that MnM is guaranteed to perform at
least as well as this procedure, which, as we show, results in an
approximation ratio of $\frac{1}{k-1}$ for every $k\geq 3$.

1 Input:

2 A $k$-bounded partition (of $G$) $Opt$

3 A graph $G_{l}=(V_{l},E_{l})$

4 Result:

5 A matching in $G_{l}$ $R_{l}\leftarrow$ an empty matching

6 for  _each $v_{i}\in V_{l}$ such that $\\{v_{i}\\}\in Opt$_ do

7 remove $v_{i}$ from $V_{l}$

8for  _each $v_{q}\in V_{l}$_ do

9 let $\hat{v}$ be a vertex $v_{i_{1},...,i_{l}}$ such that
$(v_{q},\hat{v})\in E_{l}$ and for some $1\leq j\leq l$, $v_{q}$ and
$v_{i_{j}}$ belong to the same set in $Opt$

10 for  _each $v_{n}\neq v_{q}$_ do

11 if  _$(v_{n},\hat{v})\in E_{l}$ and exists $1\leq m\leq l$, s.t.
$v_{i_{m}}$ and $v_{n}$ belong to the same set in $Opt$_ then

12 remove $v_{n}$ from $V_{l}$

13

14 add $(v_{q},\hat{v})$ to $R_{l}$

return $R_{l}$

Procedure 2 Find matching

######  Lemma 4.

Procedure 2 finds a matching, $R_{l}$, in the graph $G_{l}$, such that
$|R_{l}|\geq(|V|-2|M_{1}|-\sum\limits_{i=2}^{l-1}|M_{i}|-|O|)/(k-1)$, where
$l>1$.

###### Proof.

We first show that Procedure 2 finds a matching, $R_{l}$, in the graph
$G_{l}$. At each iteration of the loop in line 2, we add an edge between a
single node, $v_{q}$, and a unified node, $v_{i_{1},...,i_{l}}$. We consider
each single node only once. Therefore, it is not possible to add a single node
twice to $R_{l}$. Similarly, each time a unified node is added to $R_{l}$,
every single node $v_{n}\neq v_{q}$ such that $v_{i_{m}}$ and $v_{n}$ belong
to the same set in $Opt$, for some $1\leq m\leq l$, is removed from $V_{l}$.
Therefore, a unified node is not added more than once. That is, $R_{l}$ is a
matching in $G_{l}$.

We now show a lower bound on the size of $|R_{l}|$. Let
$V_{l}^{\prime}=\\{v_{i}|v_{i}\in V_{l}\\}$, i.e., the set of all the single
nodes in $G_{l}$. In line 2 we remove nodes only when $m=j$ (according to
Lemma 3). Given $\hat{v}=v_{i_{1},...,i_{l}}$, there are at most $k-1$
different nodes, $v_{j_{1}},...,v_{j_{k-1}}$ that are in the same set with
$\hat{v}$ in $Opt$. Therefore, in each iteration of the loop in line 2, we
remove at most $k-2$ single nodes in line 2 while adding one edge to $R_{l}$
in line 2. Thus, at least $\frac{1}{k-1}$ of the single nodes in $V_{l}$ (who
are not in $O$) are matched to a unified node. Therefore,
$|R_{l}|\geq\frac{|V_{l}^{\prime}|-|O|}{k-1}$. Now,
$|V_{2}^{\prime}|=|V_{1}|-2|M_{1}|$. In addition, at each iteration $l>i>1$,
$|M_{i}|$ single nodes are each added to a unified node. Therefore,
$|V_{l}^{\prime}|=|V_{1}|-2|M_{1}|-\sum\limits_{i=2}^{l-1}|M_{i}|$. In
addition, $V=V_{1}$. Overall,
$|R_{l}|\geq(|V|-2|M_{1}|-\sum\limits_{i=2}^{l-1}|M_{i}|-|O|)/(k-1)$. ∎

######  Theorem 5.

Algorithm 1 provides a solution for the MaxUtil problem with an approximation
ratio of $\frac{1}{k-1}$ for every $k\geq 3$, in the unweighted setting.

###### Proof.

Let $P$ be the $k$-bounded partition returned by Algorithm 1. Clearly,
$u(P)\geq 2\cdot\sum\limits_{i=1}^{k-1}|M_{i}|$. For every $l\geq 1$, $M_{l}$
is a maximum matching and thus $|M_{l}|\geq|R_{l}|$. In addition, according to
Lemma 4,
$|R_{l}|\geq\frac{|V|-2|M_{1}|-\sum\limits_{i=2}^{l-1}|M_{i}|-|O|}{k-1}$.

Therefore,

$u(P)\geq
2\cdot\sum\limits_{i=1}^{k-1}|M_{i}|=2|M_{1}|+2\cdot\sum\limits_{i=2}^{k-1}|M_{i}|.$
$\sum\limits_{i=2}^{k-1}|M_{i}|=|M_{2}|+|M_{3}|+...+|M_{k-1}|\geq$
$|M_{2}|+|M_{3}|+...+|M_{k-2}|+|R_{k-1}|\geq|M_{2}|+|M_{3}|+...+|M_{k-2}|+\frac{|V|-|O|-2|M_{1}|-|M_{2}|-...-|M_{k-2}|}{k-1}=$
$\frac{|V|-|O|-2|M_{1}|}{k-1}+\frac{k-2}{k-1}\sum\limits_{i=2}^{k-2}|M_{i}|\geq(1+\frac{k-2}{k-1})\cdot\frac{|V|-|O|-2|M_{1}|}{k-1}+(\frac{k-2}{k-1})^{2}\sum\limits_{i=2}^{k-3}|M_{i}|\geq...\geq$
$(1+\frac{k-2}{k-1}+(\frac{k-2}{k-1})^{2}+...+(\frac{k-2}{k-1})^{k-3})\cdot\frac{|V|-|O|-2|M_{1}|}{k-1}+(\frac{k-2}{k-1})^{k-2}\sum\limits_{i=2}^{k-1-(k-2)}|M_{i}|=$
$\sum\limits_{i=0}^{k-3}\Big{(}(\frac{k-2}{k-1})^{i}\cdot\frac{|V|-|O|-2|M_{1}|}{k-1}\Big{)}.$

That is,

$u(P)\geq
2|M_{1}|+2\cdot\sum\limits_{i=0}^{k-3}\Big{(}(\frac{k-2}{k-1})^{i}\cdot\frac{|V|-|O|-2|M_{1}|}{k-1}\Big{)}=$
$2|M_{1}|+2\cdot\frac{|V|-|O|-2|M_{1}|}{k-1}\cdot\frac{(\frac{k-2}{k-1})^{(k-2)}-1}{\frac{k-2}{k-1}-1}=$
$2|M_{1}|+2(|V|-|O|-2|M_{1}|)\cdot\frac{(\frac{k-2}{k-1})^{(k-2)}-1}{(k-1)(\frac{k-2}{k-1}-1)}=$
$2|M_{1}|-2(|V|-|O|-2|M_{1}|)((\frac{k-2}{k-1})^{(k-2)}-1)=$
$2(|V|-|O|)(1-(\frac{k-2}{k-1})^{(k-2)})-2|M_{1}|(1-2\cdot(\frac{k-2}{k-1})^{(k-2)}).$

Next, we show that

$(1-2\cdot(\frac{k-2}{k-1})^{(k-2)})\geq 0.$

Let

$f(k)=(\frac{k-2}{k-1})^{k-2}\mbox{, for }k\geq 3.$

Thus

$f^{\prime}(k)=\frac{(k-2)^{k-2}\big{(}ln(\frac{k-2}{k-1})(k-1)+1\big{)}}{(k-1)^{k-1}}.$

Now, $\frac{(k-2)^{k-2}}{(k-1)^{k-1}}>0$. In addition, it is known that
$ln(x)\leq x-1$ [19],
and thus

$ln(\frac{k-2}{k-1})(k-1)+1\leq-\frac{1}{k-1}(k-1)+1=0$

Therefore, for all $k\geq 3$, $f^{\prime}(k)\leq 0$ and $f(k)\leq
f(3)=\frac{1}{2}$.

Overall, since $|M_{1}|\leq\frac{|V|-|O|}{2}$,

$u(P)\geq
2(|V|-|O|)(1-(\frac{k-2}{k-1})^{(k-2)})-2\cdot\frac{|V|-|O|}{2}(1-2\cdot(\frac{k-2}{k-1})^{(k-2)})=|V|-|O|.$

Now, since in $Opt$ there are at least $|O|$ singletons, then $u(Opt)$ is at
most $(|V|-|O|)\cdot(k-1)$, which occurs when all nodes are partitioned into
cliques of size $k$ (except those in $O$). That is,

$u(P)\geq\frac{u(Opt)}{k-1}.$

∎

Since finding a maximum matching in a graph can be computed in
$O(|E|\sqrt{|V|})$, Algorithm 1 runs in $O(kn^{2.5})$ time.

###  4.4 Approximation Ratio for Weighted Setting

We now show that MnM provides an approximation ratio of $\frac{1}{k}$ for the
MaxUtil problem in the weighted setting. Specifically, we show that the first
step of the algorithm, which finds a maximum weight matching, provides an
approximation ratio of $\frac{1}{k}$.

######  Theorem 6.

Algorithm 1 provides a solution for the MaxUtil problem with an approximation
ratio of $\frac{1}{k}$ for every $k\geq 3$, in the weighted setting.

##  5 Stability

When considering a stability concept $c$, we analyze the following two
problems:

  * •

Existence: determine whether for any $(G,k)$ there exists a partition that
satisfies $c$.

  * •

Finding: given $(G,k)$, decide if there exists a partition that satisfies $c$
and if so, find such a partition.

###  5.1 Core

We begin by showing that the core in the weighted setting may be empty.
Specifically, Figure 3 provides an example of such a graph for $k=3$. We use a
computer program that iterates over all possible $3$-bounded partitions, for
verifying that each such $3$-bounded partition has a strongly blocking
$3$-bounded coalition.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$$6$$7$$5$$4$$5$$4$$4$$7$$6$$7$$5$$6$
Figure 3: An example of a weighted graph in which the core is empty, for
$k=3$.

We thus concentrate on the unweighted setting. First, we show that for $k=3$
the core is never empty. We present Algorithm 3, a polynomial time algorithm
that finds a $3$-bounded partition $P$ in the core. The algorithm begins with
all agents in singletons and iteratively considers for each $3$-bounded
coalition whether it strongly blocks the current partition.

1 Input: A graph $G(V,E)$

Result: A $3$-bounded partition $P$ of $V$ in the core.

2 $P\leftarrow\\{\\{v\\}$ for every $v\in V\\}$

3 $V^{\prime}\leftarrow V$

4 outerLoop:

5 for  _$S\subset V^{\prime}$ , such that $|S|=2$ OR $|S|=3$_ do

6

7 if  _$\forall v\in S,W(v,S) >u(v,P)$_ then

8 $P\leftarrow P^{-S}$

9 if  _$S$ is clique of size $3$_ then

10 $V^{\prime}\leftarrow V^{\prime}\setminus S$

11

12 goto outerLoop

return P

Algorithm 3 Finding a $3$-bounded partition in the core

######  Theorem 7.

In the unweighted setting, there always exists a $3$-bounded partition in the
core, and it can be found in polynomial time.

###### Proof.

Consider Algorithm 3. Note that for every $3$-bounded partition $P$, if $S\in
P$ is a clique of size $3$ then every $v\in S$ cannot belong to any strongly
blocking coalition. Therefore, Algorithm 3 removes such vertices from
$V^{\prime}$ (in line 3). Clearly, if Algorithm 3 terminates, the $3$-bounded
partition $P$ is in the core. We now show that Algorithm 3 must always
terminate, and it runs in polynomial time. The algorithm initiates a new
iteration (line 3) whenever the if statement in line 3 is true, which can
happen when the blocking coalition $S$, is one of the following:

  * •

Only singletons (i.e., two or three singletons). Then, $u(P)$ increases by at
least $2$.

  * •

One agent from a coalition in which she has one neighbor, and two singleton
agents. Then, $u(P)$ increases by at least $2$.

  * •

Two agents, each from a coalition with a single neighbor, and one singleton
agent. Then, $S$ must be a clique of size $3$, which increases $u(P)$ by $2$.

  * •

Three agents, each from a coalition with a single neighbor. Then, $S$ must
also be a clique of size $3$; however, $u(P)$ remains the same.

Overall, either $u(P)$ has increased by at least $2$ or $S$ is a clique of
size $3$ and thus its vertices are removed from further consideration (in line
3). Since $u(P)$ is bounded by $2|E|$ and the number of vertices is finite,
the algorithm must terminate after at most $|E|+|V|/3$ iterations. ∎

For $k>3$ it is unclear whether the core can be empty, and how to find a
partition in the core. Therefore, we now investigate additive and
multiplicative approximations of the core, which are defined as follows.

######  Definition 5.1 (Additive approximation).

A $k$-bounded coalition $S$ is said to _$\epsilon_{a}$ -strongly block_ a
$k$-bounded partition $P$ if it improves the utility of each of its members by
more than an additive factor of $\epsilon_{a}$. That is, for every $v\in S$,
$W(v,S)>u(v,P)+\epsilon_{a}$. A $k$-bounded partition $P$ is in the
_$\epsilon_{a}$ -core_ if it does not have any $\epsilon_{a}$-strongly
blocking $k$-bounded coalitions.

The _$\epsilon_{m}$ -core_, which is the multiplicative approximation of the
core is defined similarly. That is, a $k$-bounded coalition $S$ is said to
_$\epsilon_{m}$ -strongly block_ a $k$-bounded partition $P$ if for every
$v\in S$, $W(v,S)>\epsilon_{m}\cdot u(v,P)$.

We now show that for $k>3$ the $\epsilon_{a}$-core, for
$\epsilon_{a}=\lfloor\frac{k}{2}\rfloor-1$, is never empty. We present
Algorithm 4, a polynomial time algorithm that finds a $k$-bounded partition
$P$ in the $\epsilon_{a}$-core. The algorithm begins with all agents in
singletons and iteratively considers for each $k$-bounded coalition whether it
$\epsilon_{a}$-strongly blocks the current partition.

1 Input: A graph $G(V,E)$

2 A limit $k$

3 An additive factor $\epsilon_{a}$

Result: A $k$-bounded partition $P$ of $V$ in the $\epsilon_{a}$-core.

4 $P\leftarrow\\{\\{v\\}$ for every $v\in V\\}$

5 $V^{\prime}\leftarrow V$

6 outerLoop:

7 for  _$S\subset V^{\prime}$ , such that $1<|S|\leq k$_ do

8 if  _$\forall v\in S,W(v,S) >u(v,P)+\epsilon_{a}$_ then

9 $P\leftarrow P^{-S}$

10 if  _$\forall v\in S,W(v,S)\geq k-1-\epsilon_{a}$_ then

11 $V^{\prime}\leftarrow V^{\prime}\setminus S$

12

13 goto outerLoop

return P

Algorithm 4 Finding a $k$-bounded partition in the $\epsilon_{a}$-core

######  Theorem 8.

For $\epsilon_{a}=\lfloor\frac{k}{2}\rfloor-1$, there always exists a
$k$-bounded partition in the $\epsilon_{a}$-core, and it can be found in
polynomial time.

###### Proof.

Consider Algorithm 4. Note that for every $k$-bounded partition $P$, and $S\in
P$, if for every $v\in S$, $W(v,S)\geq k-1-\epsilon_{a}$ then every $v\in S$
cannot belong to any $\epsilon_{a}$-strongly blocking $k$-bounded coalition.
Therefore, Algorithm 4 removes such vertices from $V^{\prime}$ (in line 4).
Clearly, if Algorithm 4 terminates, the $k$-bounded partition $P$ is in the
$\epsilon_{a}$-core. We now show that for
$\epsilon_{a}=\lfloor\frac{k}{2}\rfloor-1$, Algorithm 4 must always terminate,
and it runs in polynomial time.

First, we show that $u(P)$ never decreases. The algorithm initiates a new
iteration (line 4) whenever the if statement in line 4 is true. This can
happen only if for every $v$ in the blocking coalition $S$, $u(v,P)$ is less
than $k-1-\lfloor\frac{k}{2}\rfloor+1$ (since $W(v,S)$ is at most $k-1$).
Therefore, $u(v,P)<k-\frac{k}{2}+\frac{1}{2}=\frac{k}{2}+\frac{1}{2}$. Since
$u(v,P)$ is a natural number, $u(v,P)\leq\frac{k}{2}-\frac{1}{2}$. When $S$
breaks off, the social welfare decreases by at most $2\cdot\sum\limits_{v\in
S}u(v,P)$, and increases by at least $\sum\limits_{v\in
S}(u(v,P)+\lfloor\frac{k}{2}\rfloor)$. Since $\sum\limits_{v\in
S}(u(v,P)+\lfloor\frac{k}{2}\rfloor)\geq\sum\limits_{v\in
S}(u(v,P)+\frac{k}{2}-\frac{1}{2})\geq\sum\limits_{v\in
S}(u(v,P)+u(v,P))=2\cdot\sum\limits_{v\in S}u(v,P)$, then $u(P)$ never
decreases.

Next, we show that if $u(P)$ remains the same, then vertices are removed from
further consideration (in line 4). Observe that $u(P)$ remaining the same
entails that $2\cdot\sum\limits_{v\in S}u(v,P)=\sum\limits_{v\in
S}(u(v,P)+\lfloor\frac{k}{2}\rfloor)$. That is, $\sum\limits_{v\in
S}u(v,P)=\sum\limits_{v\in S}\lfloor\frac{k}{2}\rfloor$. Recall that for every
$v\in S$, $u(v,P)\leq\frac{k}{2}-\frac{1}{2}$ and note that
$\frac{k}{2}-\frac{1}{2}\leq\lfloor\frac{k}{2}\rfloor$. Therefore, if $u(P)$
remains the same, then for every $v\in S$, $u(v,P)=\frac{k}{2}-\frac{1}{2}$.
Now, since for every $v\in S$, $W(v,S)>u(v,P)+\lfloor\frac{k}{2}\rfloor-1$ and
$\epsilon_{a}\geq 1$, then
$W(v,S)>\frac{k}{2}-\frac{1}{2}+\frac{k}{2}-\frac{1}{2}-1=k-2\geq
k-1-\epsilon_{a}$. Therefore, all $v\in S$ are removed from further
consideration.

Overall, either $u(P)$ has increased by at least $2$ or vertices are removed
from further consideration. Since $u(P)$ is bounded by $2|E|$ and the number
of vertices is finite, the algorithm must terminate after at most
$|E|+\frac{|V|}{k}$ iterations. ∎

Next, we show that for $k>3$ the $\epsilon_{m}$-core, for $\epsilon_{m}=2$, is
never empty. We use Algorithm 4, with the following changes:

  * •

The input of the algorithm is $\epsilon_{m}$ instead of $\epsilon_{a}$ (in
line $3$).

  * •

In line $8$, we check if for every $v$ in $S$,
$W(v,S)>\frac{u(v,P)}{\epsilon_{m}}$.

  * •

In line $10$, we check if for every $v$ in $S$,
$W(v,S)\geq\frac{k-1}{\epsilon_{m}}$.

We show that this algorithm finds a $k$-bounded partition $P$ in the
$\epsilon_{m}$-core in polynomial time.

######  Theorem 9.

For $\epsilon_{m}=2$, there always exists a $k$-bounded partition in the
$\epsilon_{m}$-core, and it can be found in polynomial time.

Finally, we show in simulation that a simple heuristic always finds a
partition that is in the core. Our heuristic function works as follows:

  1. 1.

Start with a $k$-bounded partition $P$, where all the agents are singletons.

  2. 2.

Iterate randomly over all the $k$-bounded coalitions until a coalition $S$ is
found, which strongly blocks the partition $P$.

  3. 3.

Update $P$ to be $P^{-S}$, and return to step $(2)$.

The heuristic terminates when either there is no strongly blocking coalition
for the partition $P$ (i.e., $P$ is in the core), or when in $100$ consecutive
iterations all of the partitions have already been seen. In the later case, we
restart the heuristic.

We test our heuristic function for $k=5$ over more than $100$ million random
graphs of different types:

  * •

Random graphs of size $30$ with probability of $0.5$ for rewiring each edge.

  * •

Random trees of size $30$.

  * •

Random connected Watts–Strogatz small-world graphs of size $30$, where each
node is joined with its $5$ nearest neighbors in a ring topology and with a
probability of $0.5$ for rewiring each edge.

Our heuristic always found a $k$-bounded partition that is in the core.
Moreover, we had to restart the heuristic in only $33$ instances, and then a
$k$-bounded partition in the core was found.

###  5.2 Strict Core (SC)

We first show that for every size limit, $k$, there is at least one graph
where there is no $k$-bounded partition in the strict core. Indeed, given a
size limit $k$, we build the graph $G(V,E)$, which is a clique of size $k+1$.
For every partition $P$ of $V$, let $S$ be a coalition in $P$ such that
$|S|<k$. Now, any set of agents of size $k$ that also contains some $v\in S$
is a weakly blocking $k$-bounded coalition for $P$. Furthermore, even
verifying the existence of the strict core is a hard problem.

######  Definition 5.2 ($SC$ existence problem).

Given a coalition size limit $k$ and a graph $G$, decide whether a $k$-bounded
partition exists that is in the strict core.

######  Theorem 10.

The $SC$ existence problem is $NP$-hard.

###  5.3 Contractual Strict Core (CSC)

We show that the CSC is never empty. Indeed, given any $(G,k)$, the following
algorithm finds a $k$-bounded partition in the CSC:

  1. 1.

Start with a $k$-bounded partition $P$, where all the agents are singletons.

  2. 2.

Iterate over all the coalitions in $P$ until two coalitions, $S_{1},S_{2}$,
are found, such that $|S_{1}|+|S_{2}|\leq k$ and $u(P)<u(P^{-S_{1}\cup
S_{2}})$.

  3. 3.

Update $P$ to be $P^{-S_{1}\cup S_{2}}$, and return to step $(2)$.

The algorithm terminates when step $2$ does not find two coalitions that meet
the required conditions.

######  Theorem 11.

There always exists a $k$-bounded partition in the CSC, and it can be found in
polynomial time.

###### Proof.

At each iteration, the number of the coalitions in $P$ decreases and thus the
algorithm must terminate after at most $k-1$ iterations. Consider the
$k$-bounded partition $P$ when the algorithm terminates. Clearly, there are no
two coalitions in $P$ that can benefit from breaking off and joining together.
In addition, observe that every coalition $S\in P$ is a connected component.
Thus, no coalition $S^{\prime}\subsetneq S$ can break off without decreasing
the utility of at least one agent from $S\setminus S^{\prime}$. Therefore, $P$
is in the CSC. ∎

##  6 Conclusions and Future Work

In this paper, we initiate the study of ASHGs with a bounded coalition size.
We provide MnM, an approximation algorithm for maximizing the utilitarian
social welfare and study the computational aspects of the core, the SC, and
the CSC. We note that MnM can be improved such that it finds a partition that
is in the CSC while maintaining its approximation ratio. This is done by
running MnM and iteratively joining together any two coalitions that improve
the social welfare (without violating the size constraint).

There are several interesting directions for future work. Since we show that
the MaxUtil problem cannot be computed in polynomial time (unless $P=NP$), it
will be interesting to investigate some variants. For example, the problem of
finding a $k$-bounded partition such that each agent will be matched with at
least one friend in its coalition. Another interesting research direction is
to incorporate skills in our model, motivated by coalitional skill games [3].
That is, each agent has a set of skills, and each coalition is required to
have at least one agent that acquires each of the skills.

## Acknowledgments

This research has been partly supported by the Ministry of Science, Technology
& Space (MOST), Israel.

## References

  * Aziz et al. [2013] Haris Aziz, Felix Brandt, and Hans Georg Seedig.  Computing desirable partitions in additively separable hedonic games.  _Artificial Intelligence_ , 195:316–334, 2013.
  * Aziz et al. [2016] Haris Aziz, Rahul Savani, and Hervé Moulin.  Hedonic games.  In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, _Handbook of Computational Social Choice_ , pages 356–376. Cambridge University Press, 2016.
  * Bachrach and Rosenschein [2008] Yoram Bachrach and Jeffrey S Rosenschein.  Coalitional skill games.  In _Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems_ , pages 1023–1030, 2008.
  * Bachrach et al. [2013] Yoram Bachrach, Pushmeet Kohli, Vladimir Kolmogorov, and Morteza Zadimoghaddam.  Optimal coalition structure generation in cooperative graph games.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 27(1):81–87, Jun. 2013.  10.1609/aaai.v27i1.8653.  URL https://ojs.aaai.org/index.php/AAAI/article/view/8653.
  * Ballester [2004] Coralio Ballester.  Np-completeness in hedonic games.  _Games and Economic Behavior_ , 49(1):1–30, 2004\.
  * Banerjee et al. [2001] Suryapratim Banerjee, Hideo Konishi, and Tayfun Sönmez.  Core in a simple coalition formation game.  _Social Choice and Welfare_ , 18(1):135–153, 2001\.
  * Bilò et al. [2019] Vittorio Bilò, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, and Luca Moscardelli.  Optimality and nash stability in additively separable generalized group activity selection problems.  In _Proceedings of the 28th International Joint Conference on Artificial Intelligence_ , pages 102–108, 2019.
  * Bilò et al. [2022] Vittorio Bilò, Gianpiero Monaco, and Luca Moscardelli.  Hedonic games with fixed-size coalitions.  In _Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence_ , volume 36, pages 9287–9295, 2022.
  * Bogomolnaia and Jackson [2002] Anna Bogomolnaia and Matthew O Jackson.  The stability of hedonic coalition structures.  _Games and Economic Behavior_ , 38(2):201–230, 2002.
  * Cechlárová et al. [2001] Katarı Cechlárová, Antonio Romero-Medina, et al.  Stability in coalition formation games.  _International Journal of Game Theory_ , 29(4):487–494, 2001.
  * Cseh et al. [2019] Ágnes Cseh, Tamás Fleiner, and Petra Harján.  Pareto optimal coalitions of fixed size.  _arXiv preprint arXiv:1901.06737_ , 2019.
  * Deng and Papadimitriou [1994] Xiaotie Deng and Christos H Papadimitriou.  On the complexity of cooperative solution concepts.  _Mathematics of operations research_ , 19(2):257–266, 1994.
  * Dreze and Greenberg [1980] Jacques H Dreze and Joseph Greenberg.  Hedonic coalitions: Optimality and stability.  _Econometrica: Journal of the Econometric Society_ , pages 987–1003, 1980.
  * Edmonds [1965] Jack Edmonds.  Paths, trees, and flowers.  _Canadian Journal of Mathematics_ , 17:449–467, 1965.  10.4153/CJM-1965-045-4.
  * Fanelli et al. [2021] Angelo Fanelli, Gianpiero Monaco, and Luca Moscardelli.  Relaxed core stability in fractional hedonic games.  In _Thirtieth International Joint Conference on Artificial Intelligence $\\{$IJCAI-21$\\}$_, pages 182–188. International Joint Conferences on Artificial Intelligence Organization …, 2021.
  * Flammini et al. [2021] Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Mordechai Shalom, and Shmuel Zaks.  On the online coalition structure generation problem.  _Journal of Artificial Intelligence Research_ , 72:1215–1250, 2021.
  * Garey and Johnson [1979] Michael R Garey and David S Johnson.  _Computers and intractability_ , volume 174.  freeman San Francisco, 1979.
  * Li et al. [2023] Lily Li, Evi Micha, Aleksandar Nikolov, and Nisarg Shah.  Partitioning friends fairly.  In _Proceedings of the 37th AAAI conference on Artificial Intelligence_ , 2023.
  * Love [1980] E. R. Love.  64.4 some logarithm inequalities.  _The Mathematical Gazette_ , 64(427):55–57, 1980\.  ISSN 00255572.  URL http://www.jstor.org/stable/3615890.
  * Maschler et al. [1979] Michael Maschler, Bezalel Peleg, and Lloyd S Shapley.  Geometric properties of the kernel, nucleolus, and related solution concepts.  _Mathematics of operations research_ , 4(4):303–338, 1979.
  * Olsen [2009] Martin Olsen.  Nash stability in additively separable hedonic games and community structures.  _Theory of Computing Systems_ , 45(4):917–925, 2009.
  * Shapley and Shubik [1966] Lloyd S Shapley and Martin Shubik.  Quasi-cores in a monetary economy with nonconvex preferences.  _Econometrica: Journal of the Econometric Society_ , pages 805–827, 1966.
  * Sless et al. [2018] Liat Sless, Noam Hazon, Sarit Kraus, and Michael Wooldridge.  Forming k coalitions and facilitating relationships in social networks.  _Artificial Intelligence_ , 259:217–245, 2018.
  * Sung and Dimitrov [2010] Shao-Chin Sung and Dinko Dimitrov.  Computational complexity in additive hedonic games.  _European Journal of Operational Research_ , 203(3):635–639, 2010.
  * Wright and Vorobeychik [2015] Mason Wright and Yevgeniy Vorobeychik.  Mechanism design for team formation.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 29(1):1050–1056, Feb. 2015.  URL https://ojs.aaai.org/index.php/AAAI/article/view/9326.

Chaya Levinger
Ariel University
Ariel, Israel

Amos Azaria
Ariel University
Ariel, Israel

Noam Hazon
Ariel University
Ariel, Israel

##  Appendix A Deferred Proofs

###  A.1 Proof of Lemma 1

###### Proof.

Clearly, $Cliques_{k}$ is $NP$ for every $k$. We use induction to show that
any $Cliques_{k}$ is $NP$-Hard for every $k\geq 3$. $Cliques_{3}$ is known as
the ‘partition into triangles’ problem, which was shown to be $NP$-Complete
[17]. Given that $Cliques_{k}$ is $NP$-Hard we show that $Cliques_{k+1}$ is
also $NP$-Hard. Given an instance of the $Cliques_{k}$ on a graph $G(V,E)$, we
construct the following instance. We build a graph
$G^{\prime}(V^{\prime},E^{\prime})$, in which we add a set of nodes
$\hat{V}={\hat{v}_{1},...,\hat{v}_{\frac{|V|}{k}}}$, i.e.,
$V^{\prime}=V\cup\hat{V}$. If $e\in E$ then $e\in E^{\prime}$, and for every
$v\in V,\hat{v}\in\hat{V}$ we add $(v,\hat{v})$ to $E^{\prime}$. Clearly, $V$
can be partitioned into disjoint cliques with exactly $k$ vertices if and only
if $V^{\prime}$ can be partitioned into disjoint cliques with exactly $k+1$
vertices. ∎

###  A.2 Proof of Theorem 2

###### Proof.

Clearly the problem is $NP$, since if we are given a partition $P$, a limit
$k$, and the value $\upsilon$, we can easily check that $\forall S\in P$,
$|S|\leq k$ and that $u(P)\geq\upsilon$ in polynomial time. For the hardness
proof, we use the $Cliques_{k}$ problem. Given an instance of $Cliques_{k}$ on
an unweighted graph $G(V,E)$, we use the same graph with the same $k$ and
$\upsilon=|V|(k-1)$ as an instance to the MaxUtil problem. Clearly, $V$ can be
partitioned into disjoint cliques with exactly $k$ vertices if and only if
there exist a $k$-bounded partition $P$ such that $u(P)=\upsilon$. ∎

###  A.3 Proof of Theorem 6

In order to prove Theorem 6, we must first prove a number of lemmas.
Specifically, in Lemma 12 we characterize all the parallel lines in regular
polygons with an odd number of sides, and in Lemma 13 we characterize all the
parallel lines in regular polygons with an even number of sides.

(a)

(b)

Figure 4: An example for a polygon with $7$ vertices

######  Lemma 12.

Let $P=(v_{1},...,v_{n})$ be a regular polygon, $n$ is odd and $n>3$, such
that $v_{1},...,v_{n}$ are its vertices. For each side of $P$ there are
$\frac{n-1}{2}$ parallel lines that connect two vertices.

###### Proof.

Let $(v_{1},v_{2}),(v_{2},v_{3}),...,(v_{n},v_{1})$ be the sides of the
polygon $P$, and let $v_{i}v_{j}$ be the line that connects $v_{i}$ to
$v_{j}$. We denote by $d(p,p^{\prime})$ the Euclidean distance between the
points $p$ and $p^{\prime}$. We first show that $v_{1}v_{n}$ is parallel to
$v_{2}v_{n-1}$. Since the sides $(v_{1},v_{2})$ and $(v_{n-1},v_{n})$ are not
parallel, there exists a point, denoted by $x$, in which their corresponding
lines intersect. Let $\alpha_{1}=\sphericalangle v_{1}v_{2}v_{n-1}$,
$\alpha_{2}=\sphericalangle v_{n}v_{n-1}v_{2}$, $\alpha_{3}=\sphericalangle
v_{n}v_{1}v_{2}$, $\alpha_{4}=\sphericalangle v_{1}v_{n}v_{n-1}$,
$\alpha_{5}=\sphericalangle xv_{1}v_{n}$, $\alpha_{6}=\sphericalangle
xv_{n}v_{1}$, $\alpha_{7}=\sphericalangle v_{1}xv_{n}$ (Figure 4(a)
demonstrates our notation of the angles for a polygon with $7$ vertices). $P$
is a regular polygon, and thus $\alpha_{3}=\alpha_{4}$. Next,
$\alpha_{5}=\alpha_{6}=180^{\circ}-\alpha_{3}$. Thus, $d(v_{1},x)=d(v_{n},x)$
and $\alpha_{5}=\frac{180^{\circ}-\alpha_{7}}{2}$. Now, since
$d(v_{2},v_{1})$= $d(v_{n-1},v_{n})$, it holds that $d(v_{2},x)=d(v_{n-1},x)$.
Therefore,
$\alpha_{1}=\alpha_{2}=\frac{180^{\circ}-\alpha_{7}}{2}=\alpha_{5}$. Finally,
since $\alpha_{1}$ and $\alpha_{5}$ are corresponding angles and
$\alpha_{1}=\alpha_{5}$, the lines $v_{1}v_{n}$ and $v_{2}v_{n-1}$ are
parallel.

Note that since $\alpha_{1}=\alpha_{2}$, also $\sphericalangle
v_{3}v_{2}v_{n-1}=\sphericalangle v_{n-2}v_{n-1}v_{2}$. Now, if $n\geq 9$, a
similar argument can show that $v_{3}v_{n-2}$ is parallel to $v_{2}v_{n-1}$.
More generally, depending on $n$, this argument repeats $t$ times,
$t=\lfloor\frac{n}{4}\rfloor$. Namely, for any $i\in{1,2,...,t}$ we show that
the lines $v_{i}v_{n-i+1},v_{i+1}v_{n-i}$ are parallel.

We now show that if $n\geq 7$, the lines $v_{t+1}v_{n-t},v_{t+2}v_{n-t-1}$ are
parallel. Since the sides $(v_{t+1},v_{t+2})$ and $(v_{n-t},v_{n-t-1})$ are
not parallel, there exists a point, denoted by $x^{\prime}$, in which their
corresponding lines intersect. Let $\alpha_{1}^{\prime}=\sphericalangle
v_{t+2}v_{t+1}v_{n-t}$, $\alpha_{2}^{\prime}=\sphericalangle
v_{t+1}v_{n-t}v_{n-t-1}$, $\alpha_{3}^{\prime}=\sphericalangle
v_{t+1}v_{t+2}v_{n-t-1}$, $\alpha_{4}^{\prime}=\sphericalangle
v_{n-t}v_{n-t-1}v_{t+2}$, $\alpha_{5}^{\prime}=\sphericalangle
x^{\prime}v_{t+2}v_{n-t-1}$, $\alpha_{6}^{\prime}=\sphericalangle
x^{\prime}v_{n-t-1}v_{t+2}$, $\alpha_{7}^{\prime}=\sphericalangle
v_{t+2}x^{\prime}v_{n-t-1}$ (Figure 4(b) demonstrates our notation of the
angles for a polygon with $7$ vertices. Note that for $n=7$, $t$ equals $1$.).
Since $P$ is a regular polygon and $\alpha_{1}=\alpha_{2}$, then
$\alpha_{1}^{\prime}=\alpha_{2}^{\prime}$. Next, since
$\alpha_{1}^{\prime}=\alpha_{2}^{\prime}$, then
$d(v_{t+1},x^{\prime})=d(v_{n-t},x^{\prime})$ and
$\alpha_{1}^{\prime}=\frac{180^{\circ}-\alpha_{7}^{\prime}}{2}$. Now, since
$d(v_{t+1},v_{t+2})$= $d(v_{n-t},v_{n-t-1})$, it holds that
$d(v_{t+2},x^{\prime})=d(v_{n-t-1},x^{\prime})$. Therefore,
$\alpha_{5}^{\prime}=\alpha_{6}^{\prime}=\frac{180^{\circ}-\alpha_{7}^{\prime}}{2}=\alpha_{1}^{\prime}$.
Finally, since $\alpha_{1}^{\prime}$ and $\alpha_{5}^{\prime}$ are
corresponding angles and $\alpha_{1}^{\prime}=\alpha_{5}^{\prime}$, the lines
$v_{t+1}v_{n-t}$ and $v_{t+2}v_{n-t-1}$ are parallel.

Now, if $n\geq 11$, a similar argument can show that $v_{t+2}v_{n-t-1}$ is
parallel to $v_{t+3}v_{n-t-2}$. More generally, depending on $n$, this
argument repeats $t^{\prime}$ times,
$t^{\prime}=\lfloor\frac{n+1}{4}\rfloor-1$. Namely, for any
$i^{\prime}\in{1,2,...,t^{\prime}}$ we show that the lines
$v_{t+i^{\prime}}v_{n-t-i^{\prime}+1},v_{t+i^{\prime}+1}v_{n-t-i^{\prime}}$
are parallel.

Finally, using the same arguments for all sides, we obtain that for each side
of $P$ there are $\frac{n-1}{2}$ parallel lines that connect two vertices.

∎

######  Lemma 13.

Let $P=(v_{1},...,v_{n})$ be a regular polygon, $n$ is even and $n>3$, such
that $v_{1},...,v_{n}$ are its vertices. For each side of $P$ there are
$\frac{n}{2}-1$ parallel lines that connect two vertices. In addition, for
each line $v_{i}v_{((i+2)\mod n)}$ there are $\frac{n}{2}-2$ parallel lines
that connect two vertices.

###### Proof.

Obviously, every side of the polygon is parallel to another side. Now, using a
similar argument to the one used in Lemma 12 we can show that $(v_{1},v_{n})$
is parallel to $v_{2}v_{n-1}$. This argument can be repeated
$\lfloor\frac{n-2}{4}\rfloor$ times. In addition, the same argument shows that
$v_{\frac{n}{2}}v_{\frac{n}{2}+1}$ is parallel to
$v_{\frac{n}{2}-1}v_{\frac{n}{2}+2}$, and can be repeated
$\lfloor\frac{n}{4}\rfloor-1$ times. Since $(v_{1},v_{n})$ is parallel to
$v_{\frac{n}{2}}v_{\frac{n}{2}+1}$, all said lines are parallel. Clearly, the
same arguments can be used for all sides. Overall, for each side there are
$\frac{n}{2}-1$ parallel lines that connect two vertices. Similar arguments
can be used to show that for each line $v_{i}v_{((i+2)\mod n)}$ there are
$\frac{n}{2}-2$ parallel lines that connect two vertices. ∎

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$ Figure 5: Division of all
the edges in a graph with $7$ vertices into $7$ disjoint groups, using
parallel lines.

We can deduce from Lemmas 12 and 13, that given a complete graph, the set of
edges can be partitioned into $n$ subsets, such that each subset is a
matching.

######  Lemma 14.

Let $G(V,E)$ be a complete graph with $n$ vertices, $n\geq 3$. $E$ can be
partition into $n$ matchings.

###### Proof.

Note that $G$ can be represented as a regular polygon $P=(v_{1},...,v_{n})$.
We first consider the case in which $n$ is odd. The set
$\\{(v_{1},v_{n}),(v_{2},v_{n-1}),...,(v_{\frac{n-1}{2}},v_{\frac{n-1}{2}+2})\\}$
is a valid matching, since all the edges are parallel to each other by Lemma
12. Therefore, for each side of $P$, we obtain a matching of size
$\frac{n-1}{2}$. Since $n$ is odd, there are no two parallel sides in $P$.
Therefore, we obtain $n$ disjoint matchings of size $\frac{n-1}{2}$ each,
which totals at $\frac{n(n-1)}{2}=|E|$. An example for this partition for
$n=7$ is shown in Figure 5.

Next, we consider the case in which $n$ is even. The set
$\\{(v_{1},v_{n}),(v_{2},v_{n-1}),...,(v_{\frac{n}{2}},v_{\frac{n}{2}+1})\\}$
is a valid matching, since all the edges are parallel to each other by Lemma
13. Therefore, for each side of $P$ we obtain a matching of size
$\frac{n}{2}$. Now, since $n$ is even, for every side of $P$ there is exactly
one other parallel side. Thus, we obtain $\frac{n}{2}$ disjoint matchings of
size $\frac{n}{2}$. In addition, the set
$\\{(v_{n-1},v_{1}),(v_{n-2},v_{2}),...,(v_{\frac{n}{2}+1},v_{\frac{n}{2}-1})\\}$
is a valid matching since all the edges are parallel to each other (by Lemma
13). Note that this matching does not include an edge in which $v_{n}$ or
$v_{\frac{n}{2}}$ is an endpoint. Thus, we obtain $\frac{n}{2}$ disjoint
matchings of size $\frac{n-2}{2}$. Overall, we obtain
$\frac{n}{2}\cdot\frac{n}{2}+\frac{n}{2}\cdot\frac{n-2}{2}=\frac{n}{2}\cdot(\frac{n}{2}+\frac{n-2}{2})=\frac{n(n-1)}{2}=|E|$.
An example for this partition for $n=8$ is shown in Figure 6.

∎

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$ Figure 6: A partition
of all the edges in a graph with $8$ vertices into $8$ disjoint groups, using
parallel lines.

We are now ready to prove Theorem 6.

###### Proof.

let $Opt=\\{S_{1},S_{2},...\\}$ be an optimal $k$-bounded partition, and let
$M_{i}$ be a maximum weight matching for coalition $S_{i}$. Lemma 14 shows
that each coalition $S_{i}$ can be partitioned into $|S_{i}|$ disjoint
matchings. In addition, for each $i$, $|S_{i}|\leq k$. Therefore, for each
$i$, $\sum_{e\in M_{i}}w(e)\geq\frac{\sum_{v\in S_{i}}{W(v,S_{i})}}{k}$. Let
$M$ be the maximum weight matching for $G$ found by Algorithm 1 in its first
step. Clearly, $\sum_{e\in M}w(e)\geq\sum_{i}\sum_{e\in M_{i}}w(e)$. In
addition, for the $k$-bounded partition $P$ that MnM returns,
$u(P)\geq\sum_{e\in M}w(e)$. Therefore, Algorithm 1 provides a solution for
the MaxUtil problem with an approximation ratio of $\frac{1}{k}$ for every
$k\geq 3$, in the weighted setting.

∎

###  A.4 Proof of Theorem 9

###### Proof.

Clearly, if the algorithm terminates, the $k$-bounded partition $P$ is in the
$\epsilon_{m}$-core. We show that $u(P)$ always increases. The algorithm
initiates a new iteration whenever $\forall v\in
S,W(v,S)>\frac{u(v,P)}{\epsilon_{m}}$, which can happen only if $S$ breaks
off. When $S$ breaks off, the social welfare decreases by at most
$2\cdot\sum\limits_{v\in S}u(v,P)$, and increases by at least
$\sum\limits_{v\in S}(2\cdot u(v,P)+1)$. Since $\sum\limits_{v\in S}(2\cdot
u(v,P)+1)>2\cdot\sum\limits_{v\in S}u(v,P)$, then $u(P)$ always increases. ∎

###  A.5 Proof of Theorem 10

###### Proof.

We use a reduction from $Cliques_{k}$ for the hardness proof. Given an
instance of the $Cliques_{k}$ on a graph $G(V,E)$, we construct the following
instance. We build a graph $G^{\prime}(V^{\prime},E^{\prime})$ such that
$V^{\prime}$ contains all the nodes from $V$. In addition, for every $v_{x}\in
V$ we add the nodes $\hat{v}_{x}$ and $v_{x}^{1},\ldots,v_{x}^{k-1}$ to
$V^{\prime}$. Now, $E^{\prime}$ contains all the edges of $E$, and for every
$v_{x}\in V$ and $1\leq i\leq k-1$ we add
$(v_{x},v_{x}^{i}),(v_{x}^{i},\hat{v}_{x})$ to $E^{\prime}$. Finally, for
every $v_{x}\in V$ and $1\leq i,j\leq k-1$, $i\neq j$ we add
$(v_{x}^{i},v_{x}^{j})$ to $E^{\prime}$. Figure 7 shows this construction for
a specific $v_{x}$ when $k=4$. We first show that if $G$ cannot be partitioned
into disjoint cliques of size $k$, then the strict core is empty. Indeed,
assume that $G$ cannot be partitioned into disjoint cliques of size $k$, and
let $P$ be a $k$-bounded partition of $V^{\prime}$. Then, there is at least
one vertex $v_{x}\in V$ that belongs to a coalition $S\in P$, such that
either:

  1. 1.

$W(v_{x},S)<k-1$, or

  2. 2.

$v_{x}^{i}\in S$ for some $i$ between $1$ and $k-1$.

In case $1$, the coalition $\\{v_{x},v_{x}^{1},\ldots,v_{x}^{k-1}\\}$ is a
weakly blocking $k$-bounded coalition. In case $2$, the coalition
$\\{\hat{v}_{x},v_{x}^{1},\ldots,v_{x}^{k-1}\\}$ is a weakly blocking
$k$-bounded coalition. Therefore, if the strict core is not empty, then $G$
can be partitioned into disjoint cliques of size $k$.

We now show that if $G$ can be partitioned into disjoint cliques of size $k$,
then the strict core is not empty. Clearly, in this case $G^{\prime}$ can be
partitioned into disjoint cliques of size $k$, and this partition is in the
strict core. Therefore, if the strict core is empty, then $G$ cannot be
partitioned into disjoint cliques of size $k$. ∎

$v_{x}^{1}$$v_{x}^{2}$$v_{x}^{3}$$\hat{v}_{x}$$v_{x}$ Figure 7: The reduction
construction for a specific $v_{x}$, when $k=4$.

##  Appendix B Additional Results

###  B.1 Tightness of the Approximation Ratio of the MnM Algorithm in the
Unweighted Setting

We show that our approximation ratio in the unweighted setting is tight.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$$v_{10}$ Figure
8: An example of a graph in which $k=5$, and MnM achieves an approximation
ratio of exactly $\frac{1}{4}$.

######  Theorem 15.

The approximation ratio of MnM for the MaxUtil problem in the unweighted
setting is tight.

###### Proof.

Given $k>2$, consider a complete graph of size $2k$. In this case, MnM finds a
perfect matching in $M_{1}$, and thus the partition $P$ returned by MnM
contains $k$ groups of $2$ nodes. That is, $u(P)=2k$. On the other hand, an
optimal $k$-bounded partition $Opt$ consists of $2$ Cliques of size $k$, and
thus $u(Opt)=2k(k-1)$. That is, MnM provides an approximation of exactly
$\frac{1}{k-1}$. ∎

Figure 8 presents a case where $k=5$, and $G$ is a complete graph with $10$
nodes. Here,
$P=\\{\\{v_{1},v_{2}\\},\\{v_{3},v_{4}\\},\\{v_{5},v_{6}\\},\\{v_{7},v_{8}\\},\\{v_{9},v_{10}\\}\\}$,
as shown in the dotted lines, and thus $u(P)=10$ . However,
$Opt=\\{\\{v_{1},v_{2},v_{3},v_{4},v_{5}\\},\\{v_{6},v_{7},v_{8},v_{9},v_{10}\\}\\}$,
as shown in the blue lines, and $u(Opt)=40$.

###  B.2 MaxUtil with Distributed Partition in Unweighted Setting

We analyze a procedure that attempts to model the behavior of the agents when
there is no central mechanism that determines the partition. Assume that the
agents are split up arbitrarily but maximally, i.e., in a way that no two
coalitions can joint together such that the social welfare will be higher. We
call this procedure $Arbmax$. Without loss of generality, we assume that every
set $S\in Arbmax$ is a connected component. We show that $\frac{1}{k}$ is an
upper bound on the approximation ratio that $Arbmax$ may guarantee.

######  Theorem 16.

For any $k$, $Arbmax$ cannot guarantee an approximation ratio better than
$\frac{1}{k}$

###### Proof.

Given $k$, consider the following graph $G$. There are $k$ distinguished
nodes, $v_{1},\ldots,v_{k}$, with the edges $(v_{i},v_{i+1})\in E$ for
$i=1,\ldots,k-1$. Each distinguished node $v_{i}$ has $k-1$ additional
neighbors that are connected only to $v_{i}$, i.e., $v_{i}$ is the internal
node of a star graph with $k-1$ leaves. Clearly, $Opt$ consists of $k$
coalitions, where each coalition consists of a star graph. Thus,
$u(Opt)=2k(k-1)$. On the other hand, $Arbmax$ may partition the graph such
that the distinguished nodes $v_{1},\ldots,v_{k}$ are in the same coalition.
Since there are no edges between two undistinguished nodes, the social welfare
of this partition is $2(k-1)$. Therefore, $Arbmax$ cannot guarantee an
approximation ratio better than $\frac{1}{k}$. ∎

Figure 9 presents a case where $k=5$, and $Arbmax$ may provide only a
$\frac{1}{5}$ of the social welfare provided by an optimal solution. Here,
$Arbmax$ may return the partition
$P^{\prime}=\\{\\{v_{1},v_{2},v_{3},v_{4},v_{5}\\},\\{v_{6}\\},\\{v_{7}\\},$
$\\{v_{8}\\},\\{v_{9}\\},\\{v_{10}\\},\\{v_{11}\\},\\{v_{12}\\},\\{v_{13}\\},\\{v_{14}\\},\\{v_{15}\\},\\{v_{16}\\},$
$\\{v_{17}\\},\\{v_{18}\\},$
$\\{v_{19}\\},\\{v_{20}\\},\\{v_{21}\\},\\{v_{22}\\},\\{v_{23}\\},\\{v_{24}\\},\\{v_{25}\\}\\}$
and thus $u(P^{\prime})=8$, while
$Opt=\\{\\{v_{1},v_{6},v_{7},v_{8},v_{9}\\},\\{v_{2},v_{10},v_{11},v_{12},v_{13}\\},\\{v_{3},v_{14},v_{15},$
$v_{16},v_{17}\\},\\{v_{4},v_{18},v_{19},v_{20},v_{21}\\},\\{v_{5},v_{22},v_{23},v_{24},v_{25}\\}\\}$
and therefore $u(Opt)=40$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$$v_{10}$$v_{11}$$v_{12}$$v_{13}$$v_{14}$$v_{15}$$v_{16}$$v_{17}$$v_{18}$$v_{19}$$v_{20}$$v_{21}$$v_{22}$$v_{23}$$v_{24}$$v_{25}$
Figure 9: A case where $k=5$, and $Arbmax$ may provide only a $\frac{1}{5}$ of
the social welfare provided by an optimal solution.

###  B.3 Worst Case Example for the MnM Algorithm in the Weighted Setting

We show that in the weighted setting, MnM cannot guarantee a better
approximation ratio. Indeed, Figure 10 shows an example where $k=3$ and MnM
$=\\{\\{v_{1},v_{2}\\},\\{v_{3},v_{4}\\},\\{v_{5},v_{6}\\}\\}$. In this case,
the outcome of MnM provides only a $\frac{2+\epsilon}{6}$ of the social
welfare provided by the optimal solution
$\\{\\{v_{1},v_{2},v_{3}\\},\\{v_{4},v_{5},v_{6}\\}\\}$. Therefore, for any
$\epsilon>0$, when $k=3$, MnM cannot provide an approximation that is better
than $\frac{1}{k}+\epsilon$.

$v_{1}$$v_{3}$$v_{2}$$v_{4}$$v_{5}$$v_{6}$$1$$1$$1$$1$$1$$1$$\epsilon$ Figure
10: A case where $k=3$, and MnM provides only a $\frac{2+\epsilon}{6}$ of the
social welfare provided by an optimal solution.

###  B.4 Nash Stablity

Due to [9], for any $(G,k)$ a Nash stable $k$-bounded partition exists. In
this section, we present Algorithm 5, a polynomial time algorithm that finds
such a partition in the unweighted setting. The algorithm begins with all
agents in singletons and iteratively considers for each agent whether it may
benefit from leaving her coalition and joining a coalition of size of at most
$k-1$.

1 Input: A graph $G(V,E)$ and a limit $k$

Result: A $k$-bounded Nash Stable partition $P$ of $V$.

2 $P\leftarrow\\{\\{v\\}$ for every $v\in V\\}$

3

4outerLoop:

5 for  _$v\in V$_ do

6 for  _$S\in P$_ do

7 if  _$W(v,S\cup\\{v\\}) >u(v,P)$ AND $|S|\leq k-1$_ then

8 $P\leftarrow P^{-S\cup\\{v\\}}$

9 goto outerLoop

return P

Algorithm 5 Finding a Nash stable $k$-bounded partition

######  Theorem 17.

There always exists a $k$-bounded Nash stable partition, and it can be found
in polynomial time.

###### Proof.

Consider Algorithm 5. Clearly, when Algorithm 5 terminates, the partition $P$
is a $k$-bounded Nash Stable partition. We now show that Algorithm 5 must
always terminate, and it runs in polynomial time. Returning to line 5 occurs
only when the if statement in line 5 is true, which entails that $u(P)$ has
increased. Since any increase in $u(P)$ must be by multiples of $2$, and since
$u(P)$ is bounded by $2|E|$, the algorithm must terminate after at most $|E|$
iterations. ∎