A new biomimetic assay reveals the temporal role of matrix stiffening in cancer cell invasion ABSTRACT Tumor initiation and growth is associated with significant changes in the surrounding tissue. During carcinoma progression, a global stiffening of the extracellular matrix is observed and is interpreted as a signature of aggressive invasive tumors. However, it is still unknown whether this increase in matrix rigidity promotes invasion and whether this effect is constant along the course of invasion. Here we have developed a biomimetic in vitro assay that enabled us to address the question of the importance of tissue rigidity in the chronology of tumor invasion. Using low concentrations of the sugar threose, we can effectively stiffen reconstituted collagen I matrices and control the stiffening in time with no direct effect on residing cells. Our findings demonstrate that, depending on the timing of its stiffening, the extracellular matrix could either inhibit or promote cancer cell invasion and subsequent metastasis: while matrix stiffening after the onset of invasion promotes cancer cell migration and tumor spreading, stiff matrices encapsulate the tumor at an early stage and prevent cancer cell invasion. Our study suggests that adding a temporal dimension in in vitro models to analyze biological processes in four dimensions is necessary to fully capture their complexity.

INTRODUCTION

The tumor microenvironment is characterized by an abnormal synthesis of extracellular matrix (ECM) components and an overall increase of matrix stiffness [START_REF] Paszek | Tensional homeostasis and the malignant phenotype[END_REF][START_REF] Levental | Matrix crosslinking forces tumor progression by enhancing integrin signaling[END_REF][START_REF] Attieh | The hallmarks of CAFs in cancer invasion[END_REF]. Such severe changes in the microenvironment are integrated at the cellular level. As a result, the transition from a benign to a malignant tumor is not induced by tumor internal signaling alone but results from a dynamic crosstalk between the tumor and its microenvironment [START_REF] Attieh | The hallmarks of CAFs in cancer invasion[END_REF].

In vivo, massive deposition of collagen and enzymatic collagen cross-linking by lysyl oxidase (LOX) are responsible for tumor matrix stiffening [START_REF] Levental | Matrix crosslinking forces tumor progression by enhancing integrin signaling[END_REF][START_REF] Barker | The rationale for targeting the LOX family in cancer[END_REF]. However, their impact on tumor progression is not restricted to a mechanical effect. The increase in collagen density also correlates with a higher number of binding sites available and therefore modifies tumor cell adhesion and migration, while LOX also acts as an intracellular factor regulating genes responsible for epithelial-mesenchymal transition [START_REF] Levental | Matrix crosslinking forces tumor progression by enhancing integrin signaling[END_REF][START_REF] Barker | The rationale for targeting the LOX family in cancer[END_REF][START_REF] Attieh | The hallmarks of CAFs in cancer invasion[END_REF].

Although stiff matrices are a signature of aggressive tumors, the causal connection between matrix stiffness and tumor aggressiveness has never been tested. Does matrix stiffening induce cancer cell invasion or is it a consequence of tumor spreading? And is the effect of matrix stiffness on cancer cell invasion constant in time or do cells respond differently to mechanical changes in their environment depending on whether these happen during early or advanced stages of invasion?

Ralitza Staneva a,b, † , Federica Burla c, † , Gijsje H. Koenderink c , Stéphanie Descroix d , Danijela Matic Vignjevic a , Youmna Attieh a,e, ‡, *, and Marine Verhulsel

BRIEF REPORT

To address these questions, in vitro models are valuable tools, as they are less complex than the in vivo microenvironment and offer the ability to decouple the different parameters at play in cancer invasion. Here we show a new approach by which we can modify matrix stiffness alone at different time points during tumor invasion. We use threose, a sugar and natural collagen crosslinker [START_REF] Kinnunen | Nondestructive fluorescence-based quantification of threose-induced collagen cross-linking in bovine articular cartilage[END_REF] that is more effective than the traditional cross-linking agent ribose. As threose does not affect cell autonomous adhesion, migration, and force generation, we can modulate the stiffness of collagen gels without affecting cancer cells embedded in the gel. Our results expose the importance of the temporal dimensions of biological processes and reveal that matrix stiffening inhibits invasion at an early stage but enhances it at later stage.

RESULTS AND DISCUSSION

Threose stiffens collagen more efficiently than ribose

In vitro models of tumor-matrix interactions ideally need to recapitulate the fibrillar structure, rheological properties, and the nature and spatial distribution of ligands of the in vivo ECM to provide biologically relevant insights [START_REF] Verhulsel | A review of microfabrication and hydrogel engineering for micro-organs on chips[END_REF]. We therefore chose collagen I for our artificial matrix, as it supports the growth of cells in three dimensions while closely mimicking in vivo fibrillar ECMs and reproducing cell-matrix interactions specific to tumors [START_REF] Wolf | Collagen-based cell migration models in vitro and in vivo[END_REF][START_REF] Geraldo | Do cancer cells have distinct adhesions in 3D collagen matrices and in vivo?[END_REF][START_REF] Wolf | Physical limits of cell migration: control by ECM space and nuclear deformation and tuning by proteolysis and traction force[END_REF]. Among the different options published in the literature to stiffen collagen [START_REF] Tanaka | Glycation induces expansion of the molecular packing of collagen[END_REF][START_REF] Paszek | Tensional homeostasis and the malignant phenotype[END_REF][START_REF] Levental | Matrix crosslinking forces tumor progression by enhancing integrin signaling[END_REF], glycation and LOX cross-linking are the only ones also occurring spontaneously in vivo. As LOX activity is known to modulate gene expression, glycation occurring between glucose and collagen better meets our needs for a physiological environment [START_REF] Tanaka | Glycation induces expansion of the molecular packing of collagen[END_REF]. Ribose is mostly used as a glucose substitute in vitro, but the high concentrations and long incubation time required to significantly stiffen the collagen matrix are presumed to induce a diabetic phenotype in cells [START_REF] Han | D-ribose induces cellular protein glycation and impairs mouse spatial cognition[END_REF].

To overcome this limitation, we tested an alternative collagen cross-linker, threose, which efficiently forms cross-links in bovine articular cartilage [START_REF] Kinnunen | Nondestructive fluorescence-based quantification of threose-induced collagen cross-linking in bovine articular cartilage[END_REF]. We incubated collagen gels with threose after polymerization to avoid any interference with fibrillogenesis and minimize potential changes in network architecture. To test whether threose is a more effective cross-linker than ribose, we compared the rheological properties of 2 mg/ml collagen gels alone or supplemented for 48 h either with 1 mM of threose or with 1 or 10 mM of ribose. At concentrations of 1 mM, the elastic modulus of collagen treated with ribose was similar to control, whereas threose treatment induced a 1.8-fold increase in stiffness (Figure 1A). At a concentration of 10 mM, ribose stiffened collagen to the same extent as 1 mM threose (Figure 1A).

These results suggest that threose is effective at lower concentrations than ribose, which is advantageous, as lower sugar concentrations diminish the likelihood to induce a diabetic phenotype or cause a hypertonic stress to cells.

In addition, monitoring the development of the elastic modulus of collagen gels in time revealed that ribose treatment had a delayed impact on collagen cross-linking compared with threose (Figure 1B). Measurements of the mesh size of the networks by reflectance microscopy validated that the architecture of collagen networks was not affected by threose (Figure 1C). This was confirmed by fluorescence microscopy imaging, although this yielded overall smaller mesh sizes than reflectance imaging because fluorescence microscopy, unlike reflectance imaging, visualizes also fibers orthogonal to the plane of imaging (Figure 1C). Whether in control or threose-treated gels, mesh sizes similarly varied between 2 and 5 µm, indicating that threose did not induce heterogeneous changes in ECM architecture (Figure 1D). Furthermore, we confirmed that the addition of threose did not affect fiber structure by using turbidimetry to compare fiber radii in the absence and presence of threose, which were, respectively, 90 ± 7 and 88 ± 7 nm. Altogether, this characterization shows that a low concentration of threose is effective in changing the stiffness of collagen gels without altering network architecture.

Collagen stiffening before the onset of invasion inhibits cancer cell invasion

We first considered the influence of matrix stiffening at an early stage, when cancer cell invasion has not yet started. To model tumor invasion in vitro, we mixed spheroids of CT26 intestinal adenocarcinoma invasive cells with 2 mg/ml collagen solutions. Once collagen polymerized, gels containing spheroids were incubated in 1 mM of threose for a 24-or 48-h treatment (Figure 2A, Thr_24 h and Thr_48 h). Invasion was quantified 3 d after embedding. The number of cells that invaded out of the spheroid was counted using a three-dimensional automated software. This quantification method generates an invasion index that represents the number of invading cancer cells normalized to the surface area of the spheroid contour. Therefore, we only scored active cell migration and did not discriminate spheroids based on their size [START_REF] Attieh | Cancer-associated fibroblasts lead tumor invasion through integrin-beta3-dependent fibronectin assembly[END_REF].

Matrix stiffening before the onset of invasion dramatically inhibited cell invasion when collagen was treated with threose compared with control (Figure 2, B andC). Treating collagen with threose for an additional day did not further impede the invasion capacity of cancer cells, as it was already almost completely blocked on a 24 h treatment (Figure 2, B andC). Consistent with these findings, CT26 cancer cells invaded collagen gels with slower speed in the presence of threose when embedded as single cells (Figure 2D). Cell persistence was similar in both conditions, indicating that it was the cells' capacity to move rather than the directional persistence of their movement that was compromised in a stiffer matrix (Figure 2D).

Inhibition of invasion could be due to an increase in matrix stiffness or to a direct effect of threose on cells. To check whether threose impeded the invasive phenotype of cells, CT26 were preincubated in 1 mM threose for 3 d while spheroids were forming (Figure 2A, Thr_incubation). Invasion was similar for preincubated and control spheroids, indicating that threose did not alter the invasive phenotype of cancer cells (Figure 2, B andC).

We further verified whether threose could alter the molecular machinery driving cell migration by plating cancer cells on glass as an inert substrate that cannot be glycated and treated with increasing concentrations of threose (Figure 2E). Cells migrated with equivalent speed and persistence regardless of threose concentration, suggesting that threose did not affect the migratory phenotype of cancer cells.

Alternatively, threose could decrease adhesion of cells to collagen. We tested the latter hypothesis by plating cells on two-dimensional collagen matrices for increment time points and measuring the percentage of adhered cells after wash (Figure 2F). We found that cell adhesion was unaffected whether collagen (Coll_thr), cells (Cells_Thr), or both (Cells_Thr + Coll_Thr) were treated with threose compared with control, suggesting that threose modified neither collagen adhesion sites nor the adhesion capacity of cancer cells (Figure 2F). We thus concluded that the inhibition of invasion at an early stage was due only to matrix stiffening.

Collagen stiffening before the onset of invasion prevents fiber alignment by cancer cells

Previous reports have shown that prior to invasion, cancer cells contract and align collagen fibers in the direction of their movement [START_REF] Provenzano | Matrix density-induced mechanoregulation of breast cell phenotype, signaling and gene expression through a FAK-ERK linkage[END_REF][START_REF] Riching | 3D collagen alignment limits protrusions to enhance breast cancer cell persistence[END_REF][START_REF] Kopanska | Tensile forces originating from cancer spheroids facilitate tumor invasion[END_REF]. Once collagen is aligned, cancer cells migrate in a fast and persistent manner, promoting tumor spread [START_REF] Riching | 3D collagen alignment limits protrusions to enhance breast cancer cell persistence[END_REF]. In in vitro models, collagen fibers are initially aligned parallel to the edge of the tumor [START_REF] Kopanska | Tensile forces originating from cancer spheroids facilitate tumor invasion[END_REF]. To evaluate whether cells remodeled the matrix, we imaged collagen I fibers surrounding spheroids 3 d postpolymerization and quantified fiber orientation of control and threose-treated gels. Imaging of collagen I revealed that noncross-linked collagen fibers were not parallel to the edge of the tumor and were randomly organized, while fiber alignment parallel to the spheroid was maintained in threose-treated samples (Figure 3A). This observation was validated by the quantification of the orientation of collagen fibers with respect to the spheroid edge (Figure 3B). In threose-treated collagen gels, fibers were mainly Measurements were performed during threose treatment and after wash. Migration persistence was defined as the final cell displacement divided by the length of the trajectory. Results are represented as a histogram with mean + SD for three independent experiments. The p values were calculated using Newman-Keuls multiple comparison test and showed no statistical difference. (F) Quantification of the capacity of control cells to adhere to collagen (control, gray) or to threose-treated collagen (Coll_thr, green) and of threose-treated cells to adhere to control collagen (Cells_thr, blue) or to threose-treated collagen (Cells_thr + coll_thr, red). Measurements were performed at 0, 15 min, 30 min, 1 h, and 2 h. Results are expressed as an XY coordinate with mean ± SD with data representing an average over three independent measurements. The p values are compared with control condition using Dunnett's multiple comparison test and showed no statistical difference. parallel to the spheroid, whereas this tendency was less pronounced in control matrices as the proportion of fibers oriented between 0 and 30° was 20% lower (Figure 3B). We thus concluded that 3 d after spheroid embedding, cells started remodeling collagen fibers in control gels but not in threose-treated samples.

Impaired matrix remodeling observed in threose-treated hydrogels could be either due to a stiffer matrix or to a direct effect of threose on cell mechanisms regulating contractile forces. To test the latter hypothesis, we performed traction force microscopy on cells plated on polyacrylamide gels containing fluorescent beads. Both control and threose-treated cells exerted comparable traction forces, indicating that threose does not affect traction force generation and that matrix stiffening alone prevented matrix remodeling (Figure 3C).

Altogether these results suggest that matrix remodeling is necessary for cancer cells to migrate out of the spheroid and that a stiffer matrix inhibits this process.

Collagen stiffening after the onset of invasion favors cancer cell invasion

The reduced invasion we observed in a stiffer environment is surprising, as aggressive tumors are typically characterized by high tissue rigidity. However, it is still not known whether the matrix gets stiffer before or after cancer cell invasion [START_REF] Attieh | The hallmarks of CAFs in cancer invasion[END_REF]. Matrix stiffening after the onset of invasion might favor cell invasion, as the critical step of matrix remodeling and fiber alignment is then already complete. To test this hypothesis, we embedded spheroids in collagen and monitored how the invasion rate would change when threose was added after invasion started (i.e., from day 3 to day 5 after embedding spheroids in collagen) (Figure 4A,Thr_d3d5). Stiffening after the onset of invasion was compared with early stiffening (Thr_d0d2) and control. Experiments were extended to 7 d after embedding spheroids in collagen to allow for cells to properly invade out of the spheroid. Similarly to the shorter-term experiments, preincubating cancer cells in threose (Figure 4A, Thr_incubation) did not affect their invasion index compared with control, confirming that threose at a concentration of 1 mM does not alter cancer cells' invasive phenotype even at longer times (Figure 4, B andC).

Surprisingly, cancer cell invasion was increased twofold when the matrix was stiffened after the onset of invasion compared with control (Figure 4, B and C, Thr_d3d5). Moreover, we observed that the decrease of cell invasion observed at day 3 on threose treatment, before the onset of invasion (Figure 2, B and C), vanished when cancer cells were examined at day 7 (Figure 4, B and C, Thr_d0d2): cells showed the same final invasion state as cells invading control gels after 7 d of culture in collagen droplets. This observation indicates that, although matrix stiffening slows down the initiation stage, it enhances cell migration once cells invade the matrix. Given that threose does not interfere with the autonomous migratory phenotype of cancer cells (Figure 2E), we concluded that matrix stiffening enhances cell migration, resulting in extensive invasion at later stages of tumor development.

Altogether, these experiments highlight the importance of the chronology of events in cancer cell invasion. Depending on the stage of the tumor, the changes in the mechanical properties of its microenvironment could differentially influence its aggressiveness. Matrix stiffening before invasion is initiated slows down the transition from noninvasive to invasive tumor stage. On the contrary, stiffening of the matrix after the onset of tumor invasion intensifies tumor invasion. We propose here a model in which, within the chronology of cancer development, cancer cells migrate out of the tumor site, followed by a stiffening of the matrix (Figure 4D).

We have thus uncovered a novel phenotype of invading tumor cells by effectively modulating matrix stiffness in time without altering cancer cells' autonomous phenotype. We have developed a physiological tumor model composed of spheroids embedded in three-dimensional collagen matrices and selected a natural crosslinker to stiffen collagen. This in vitro model allowed us to directly test the correlation between matrix stiffness and tumor aggressiveness observed in patients [START_REF] Cox | Remodeling and homeostasis of the extracellular matrix: implications for fibrotic diseases and cancer[END_REF][START_REF] Pickup | The extracellular matrix modulates the hallmarks of cancer[END_REF][START_REF] Acerbi | Human breast cancer invasion and aggression correlates with ECM stiffening and immune cell infiltration[END_REF].

As opposed to other cross-linkers commonly used in the field, threose presents the advantage of effectively stiffening collagen at low concentrations. As proven by our experiments, a strong advantage of using threose is that it does not induce changes in the network architecture in terms of mesh size and fibril diameter, while being effective in changing the stiffness of the matrix. This increase in stiffness is most likely due to a stabilization and an increase in cross-linking of already existing contact points.

Using threose at low concentrations allowed us to modify matrix stiffness while tumor cells were embedded in their physiological three-dimensional matrix, as opposed to studies exposing cancer cells to previously treated and already stiff gels or collagen gels of varying densities that cannot be modulated in time [START_REF] Paszek | Tensional homeostasis and the malignant phenotype[END_REF][START_REF] Levental | Matrix crosslinking forces tumor progression by enhancing integrin signaling[END_REF][START_REF] Provenzano | Matrix density-induced mechanoregulation of breast cell phenotype, signaling and gene expression through a FAK-ERK linkage[END_REF][START_REF] Krndija | Substrate stiffness and the receptor-type tyrosineprotein phosphatase alpha regulate spreading of colon cancer cells through cytoskeletal contractility[END_REF]. We were thus able to control the temporal onset of matrix stiffening. Although we worked at lower collagen concentration and thereby at lower stiffness than analogous studies using ribose, cells were highly responsive, suggesting that cells are more sensitive to relative changes in matrix rigidity than to its intrinsic value [START_REF] Bordeleau | Matrix stiffening promotes a tumor vasculature phenotype[END_REF][START_REF] Carey | Three-dimensional collagen matrix induces a mechanosensitive invasive epithelial phenotype[END_REF].

At an early stage of invasion, cells first remodel the matrix to effectively migrate out of the tumor niche. Contractile forces of cancer cells are required to deform the ECM and lead to tensile radial forces within the matrix that orient the collagen fibers perpendicular to the surface of the tumor [START_REF] Provenzano | Matrix density-induced mechanoregulation of breast cell phenotype, signaling and gene expression through a FAK-ERK linkage[END_REF][START_REF] Riching | 3D collagen alignment limits protrusions to enhance breast cancer cell persistence[END_REF][START_REF] Kopanska | Tensile forces originating from cancer spheroids facilitate tumor invasion[END_REF]. As there is a mechanical relation between the tensile state of the ECM and invasion, collagen organization at the onset of invasion plays a critical role in the outcome of tumor development. Our results support this hypothesis, as threose-treated matrices are stiffer and therefore more difficult to remodel than control matrices. This is evidenced by the high proportion of collagen fibers oriented parallel to the edge of the tumor 3 d after embedding and the consequent inhibition of cancer cell invasion.

Stiffer matrices are also known to favor a migratory phenotype in cancer cells [START_REF] Paszek | Tensional homeostasis and the malignant phenotype[END_REF][START_REF] Levental | Matrix crosslinking forces tumor progression by enhancing integrin signaling[END_REF]. This biomechanical process is consistent with the cell response observed when we added threose after the onset of invasion, which led to a twofold increase in invasion. This antagonistic influence of matrix stiffening in the early and late stages of invasion is clearly illustrated by the behavior of cancer cells when collagen is exposed to threose in the early stage: although the transition from noninvasive to invasive phenotype is delayed compared with control, once invasion is initiated, migration is enhanced as cancer cells catch up with control conditions within 4 d of invasion. As CT26 are invasive cancer cells with a mesenchymal-like phenotype, this result is consistent with new findings suggesting that only malignant cancer cells have the ability to adjust to collagen matrices of different densities [START_REF] Wullkopf | Cancer cell ability to mechanically adjust to extracellular matrix stiffness correlates with their invasive potential[END_REF].

In conclusion, our in vitro three-dimensional culture model provides a physiologically relevant microenvironment to study the effect of matrix stiffness per se on the transition from benign to malignant tumor. We report here the first data on in vitro collagen cross-linking using threose, which allows us to significantly stiffen collagen matrices without interfering with the phenotype of cancer cells. Furthermore, this study highlights the need to introduce a fourth dimension into cell biological models. Indeed, a static assay where all factors are initially set and remain unchanged could fail to capture the complexity of cancer invasion. The flexibility of our system allowed us to tackle the question of the dynamics of matrix stiffening during tumorigenesis. Our study illustrates that within the chronology of tumor development, neither matrix stiffening nor softening is the most favorable but rather an interchanging state that is used by cancer cells to efficiently invade.

MATERIALS AND METHODS

Rheological measurements

Rheology tests were performed on an Anton Paar Physica MCR 501 rheometer, with a stainless steel 30-mm-diameter and 1° truncation angle cone-plate geometry (CP30-1). The plates were heated to 37° before loading the sample. Water was added to the solvent trap to maintain a moist environment. Twenty minutes after loading the sample, a solution of either pure DMEM or DMEM supplemented with 1-10 mM ribose or 1 mM threose was placed around the geometry and allowed to diffuse in the sample for 48 h. To prevent evaporation during the measurement, a layer of mineral oil was further added around the measuring geometry. During the whole 48 h, the elastic and viscous moduli of the network were probed by applying an oscillatory deformation with 0.5% strain amplitude and a frequency of 0.5 Hz. Results show the values of elastic and viscous moduli after 48 h, averaged over at least three different independent repeats, while the error reported is the standard error of the mean.

Sample preparation

The samples were prepared on ice to prevent early polymerization of collagen. First, collagen was pipetted into an Eppendorf tube and weighed to determine the volume of the final solution. Samples were prepared to have a final collagen concentration of 2 mg/ml, in phosphate buffer saline (PBS) and pH set to 7 with addition of NaOH and topped up to the final volume with DMEM.

Imaging three-dimensional collagen networks

The pure and threose-supplemented collagen networks were imaged in confocal reflectance and confocal fluorescence mode using an inverted Eclipse Ti microscope (Nikon, Tokyo, Japan), a 488-nm Argon laser (Melles Griot, Albuquerque, NM) for illumination, and a 100× objective (Nikon, N.A. 1.49). Z-stacks were acquired 10 µm above the coverslip to avoid surface effects, over a depth of 10 µm, with a step of 0.2 µm and shown as a maximum projection. The networks were allowed to polymerize for 48 h at 37°C with controlled humidity. To visualize fluorescent collagen, we added the collagen binding protein CNA35 [START_REF] Aper | Colorful protein-based fluorescent probes for collagen imaging[END_REF] tagged with green fluorescent protein (pET28a-EGFP-CNA35 was a gift from Maarten Merkx, TU Eindhoven [Addgene plasmid # 61603]) to collagen prior to polymerization in a molar ratio of 20:1.

Mesh size analysis

The mesh size of the networks was determined using an algorithm described in [START_REF] Kaufman | Glioma expansion in collagen I matrices: analyzing collagen concentration-dependent growth and motility patterns[END_REF]. Images were background subtracted and binarized with an Otsu threshold using ImageJ. The resulting image was then analyzed in a custom-written Python routine, which counted the distance between on and off pixels along the rows and columns. The distances obtained were then fitted with an exponential probability distribution, and the mean value (converted from pixels to µm) was taken as the average mesh size. For each condition, we analyzed at least eight randomly sampled images.

Fiber diameter analysis

To analyze the average diameters of the collagen fibers, we performed turbidity measurements with a Lambda 35 dual-beam spectrophotometer (PerkinElmer, Waltham, MA). Samples were polymerized inside a plastic cuvette (UV-Cuvette micro; Plastibrand, Germany) or a quartz cuvette for 48 h before measuring. Subsequently, the optical density of the sample was measured in the wavelength range 650-900 nm. The measured optical density I 0 was converted into turbidity τ using the formula

I L ln 10 0 τ ( ) =
where L represents the optical path length. To extract fiber radii and mass-length ratios, we employed the following relation [START_REF] Yeromonahos | Nanostructure of the fibrin clot[END_REF]:

A B a 5 2 2 τ λ µ λ ( ) = -
where A and B are constants corresponding respectively to (88/15)c p π 3 n s (dn/dc p ) 2 /N A and (184/154)π 2 n 2 s . Here c p represents the collagen concentration, n s the refractive index of the solvent, dn/dc p is the refractive index increment, N A is the Avogadro constant, µ is the mass per length ratio, and a is the fiber radius.

Cell lines

Mouse intestinal cancer cells CT26 were obtained from the American Type Culture Collection. Cells were cultured in DMEM (Life Technologies) supplemented with 10% fetal bovine serum (FBS) (Invitrogen) and 5% CO 2 . Mycoplasma testing was performed every 2 wk to verify that cells were clear of infections.

Invasion assay

Agarose (Invitrogen) was dissolved in water to a concentration of 0.01 g/ml and boiled. Of the solution, 150 µl was added to wells of a 48-well plate, and agarose was left to polymerize for at least 10 min at room temperature (RT). A solution of 10 4 cells/ml CT26 cancer cells was made, and 75-100 µl of the solution was added to the wells. The wells were subsequently filled with DMEM supplemented with 10% FBS ± threose (1 mM, T7642, Sigma), and spheroids were left to form for 3-4 d.

Tissue culture plates (30 mm 2 ) were specifically fashioned for the invasion assay: three holes of ∼3-4 mm in diameter were drilled in a plate and widened around the edges using a scalpel.

Rat tail collagen I (2 mg/ml; Corning) was prepared in DMEM, 10X PBS, and 1 M NaOH, to pH = 7, as described under Sample preparation. The solution was kept on ice to avoid collagen polymerization. Spheroids were embedded in 15-µl collagen drops, positioned in the hole of the culture plate. After filling all three holes, the plate was flipped every 30 s for 5 min for the cells to stay in the middle of the collagen drop (preventing sedimentation of spheroids to the glass or to collagen/air interface). Collagen was left to polymerize for an additional 15 min at RT before 3 ml of DMEM supplemented with 5% FBS, 1% antibiotic antimycotic (AA) was added ± 1 mM of threose.

Three-dimensional immunofluorescence

Spheroids embedded in collagen were fixed using 4% paraformaldehyde in PBS for 30 min at RT. Spheroids were then washed with PBS and permeabilized with 0.1% Triton X-100 in PBS for 30 min at RT. DNA and F-actin were stained using 4′,6-diamidino-2-phenylindole (DAPI) and phalloidin, respectively (Life Technologies). Collagen was imaged using confocal reflection microscopy.

Imaging three-dimensional spheroids

Images were acquired with an inverted AOBS two-photon laser scanning confocal microscope SP8 (Leica) coupled to femtosecond laser Chameleon Vision II (Coherent Inc) using a 25×/1.0NA waterimmersion objective. The microscope is equipped with two nondescanned hybrid detectors: NDD1 (500-550 nm) and NDD2 (≥590 nm). Fluorescence channels were recorded simultaneously using the excitation wavelength 980 nm. Collagen was visualized by confocal reflectance microscopy using light at a wavelength of 488 nm and a standard photomultiplier tube detector at a low gain (500 V). Threedimensional stacks were obtained at a step size of 2-µm intervals. The images were processed with Leica Application Suite (LAS), ImageJ (National Institutes of Health) and Imaris (Bitplane).

Invasion counter software

Quantification of cell invasion from spheroids was performed as already described using a custom semiautomated image analysis program written in Python [START_REF] Attieh | Cancer-associated fibroblasts lead tumor invasion through integrin-beta3-dependent fibronectin assembly[END_REF].

Cell adhesion assay

CT26 cells were pretreated for 2 d with 1 mM of threose or no threose in DMEM supplemented with 10% FBS and 1% AA. Collagen (50 µl) (2 mg/ml) was polymerized in 96-well plates and pretreated for 2 d with 1 mM of threose or no threose in DMEM and 1% AA. After 2 d, CT26 cells were stained with CellTracker Red CMTPX Dye (ThermoFisher) and 2 × 10 5 cells were seeded per well in the 96-well plate. Cells were then incubated at 37°C for 5 min, 15 min, 30 min, 1 h, or 2 h and washed three times to remove nonadherent cells. Fluorescence intensity was measured using a FluoStar fluorescence plate reader (BMG Labtech). Adhesion was represented as the percentage of adherent cells per condition.

Collagen topography measurements

Fibers alignment and their angles with respect to the spheroid edge were measured on images acquired using reflection microscopy with the available software CurveAlign (UW-Madison; http:// loci.wisc.edu/software/curvealign) in MatLab. The angles of collagen fibers compared with the spheroid edge were determined for seven to eight slices per condition.

Traction force microscopy

Traction force microscopy was conducted as previously described [START_REF] Elkhatib | Fascin plays a role in stress fiber organization and focal adhesion disassembly[END_REF].

Glass-bottom cell culture dishes (35 mm; FluoroDish, World Precision Instruments) were silanized with (3-aminopropyl)trimethoxysilane (Sigma-Aldrich) for 15 min and extensively washed with water. The glass surface of the dishes was treated with 0.5% glutaraldehyde (Electron Microscopy sciences) for 30 min and extensively washed with water. Acrylamide 40% (93.3 µl) and 2% bisacrylamide (11 µl) were mixed in PBS solution to a final volume of 500 µl to achieve a Young's modulus of 5 kPa. For traction force measurements, FluoSphere bead solution (0.2 µm, 580/605 nm; Invitrogen) was added at 2% volume. Polymerization was initiated by addition of 2.5 µl ammonium persulfate (10% wt/vol solution) and 0.25 µl of N,N,N',N'-tetramethylethane-1,2-diamine. Polyacrylamide solution (12 µl) was rapidly deposited onto the glass-bottom dish and covered with a 18-mm coverslip. After 1 h, PBS was added to the dishes for 10 min, and the coverslips were gently removed under PBS. To allow for collagen coating, the gel surface was activated using Sulfo-SANPAH (1 mg/ml; ThermoFisher) that was photoactivated by ultraviolet (365 nm) for 10 min. After three washes with HEPES and PBS, the gels were coated with monomeric collagen (100 µg/ml) overnight at 4°C. The next day gels were washed three times with PBS. CT26 cells were pretreated for 1 d ± 1 mM threose prior to seeding on the gels. CT26 cells (1 × 10 4 ) were plated per gel in DMEM supplemented with 10% FBS, 2% AA, and ± 1 mM threose and cultured on the gels one additional day, thus allowing for a total 2-d incubation ± threose.

To image traction force experiments, we used an Inverted Nikon Ti-E microscope equipped with a scientific complementary metal-oxide semiconductor (sCMOS) 2048 ORCA Flash4.0 V2 camera (Hamamatsu) and a 40× Plan Fluor dry objective (0.75 NA; Nikon). A fluorescent image of the FluoSphere beads and a phase contrast image of the cells were acquired. At the end of the acquisition, cells were detached from the gels using 0.5% Trypsin-EDTA (Life Technologies), and a reference image without cells was recorded. We used a previously described correlation algorithm to extract the bead displacement fields. Traction force was determined using the Fourier transform traction force algorithm, as introduced by [START_REF] Butler | Traction fields, moments, and strain energy that cells exert on their surroundings[END_REF]. To quantify the force applied by a cell, we measured the strain energy that corresponds to the energy the cell exerts to deform the substrate, which is proportional to the average force applied by a cell.

Two-dimensional migration

CT26 cells were incubated for 2 d with the following concentrations of threose: 0, 0.5, 1, and 2 mM in DMEM supplemented with 10% FBS and 1% AA. After 2 d, CT26 cells were resuspended and 2500 cells were seeded on uncoated glass-bottom wells of a 96-well plate. After overnight imaging, all the wells were washed and DMEM 10% FBS 1% AA was added, and cell migration was imaged for 8 more hours.

Three-dimensional migration of single cells

Rat tail collagen I (2 mg/ml; Corning) was prepared in DMEM, 10X PBS, and 1 M NaOH, to pH = 7 as described under Sample preparation. The solution was kept on ice to avoid collagen polymerization. Glass-bottom cell culture dishes (FluoroDish, World Precision Instruments) were coated with poly-l-lysine (Sigma-Aldrich) for 5 min and washed three times with PBS. CT26 cells were resuspended, and 5000 cells were embedded in 40 µl collagen drops that were deposited on the bottom of the culture dishes. Dishes were flipped for 1.5 min for the cells to stay in the center of the collagen drop. Collagen was left to polymerize for an additional 30 min at RT before 2 ml of DMEM supplemented with 10% FBS, 1% AA was added ± 1 mM of threose. Dishes were maintained for 2 d at 37°C, 5% CO 2 .

Microscopy of CT26 migration and image analysis

Two-and three-dimensional cultures were imaged using an Inverted Nikon Ti-E microscope equipped with a sCMOS 2048 ORCA Flash4.0 V2 camera (Hamamatsu) using the following objectives: Plan Fluor 10x Ph1 DL and Plan Apo VC 20x DIC N2. Images were acquired every 10-20 min for 8-12 h.

A random population of cells was selected and manually tracked in two-dimensional using the MTrackJ plugin [START_REF] Meijering | Methods for cell and particle tracking[END_REF] in ImageJ (Bitplane). Following tracking of cells, the trajectories were analyzed using custom software written in Python. Migration persistence was defined as the final cell displacement divided by the length of the trajectory.

Statistical analysis

All experiments were performed in a minimum of three independent experiments. All statistical analysis and graphic representations were performed using Prism software.

  d,e, ‡, * a Institut Curie, PSL Research University, CNRS, UMR 144 and d UMR 168, F-75005 Paris, France; b Université Paris Descartes, 75006 Paris, France; c Department of Living Matter, AMOLF, 1098 XG Amsterdam, The Netherlands; e Sorbonne Universités, UPMC Univ Paris 06, IFD, 75252 Paris cedex 05, France

FIGURE 1 :

 1 FIGURE 1: Threose stiffens collagen more efficiently than ribose. (A) Elastic moduli obtained with small-amplitude oscillatory rheology for untreated collagen gels, gels treated with 1 or 10 mM of ribose or with 1 mM threose, 48 h after polymerization. Data represent an average over at least three independent measurements. The p values are compared with control condition using Dunnett's multiple comparison test (*p < 0.05). (B) Measurements of elastic moduli as a function of time over a period of 48 h obtained with small amplitude oscillatory rheology on untreated collagen gels, gels treated with 1 or 10 mM of ribose, or with 1 mM threose. Results are expressed as mean ± SEM obtained as an average over at least three independent measurements. The p values are compared with control condition using Dunnett's multiple comparison test (****p < 0.0001). (C) Left, maximum intensity projections of reflectance and fluorescence images of collagen networks with or without 1 mM of threose added during 48 h. Scale bar = 10 µm. Right, mesh size measurements of collagen networks. Results are represented as a histogram with mean + SEM for n = 8 positions over n = 3 independent samples. The p values were calculated using an unpaired t test for each separate condition and showed no statistical difference. The mesh size measured with fluorescence microscopy is smaller because confocal reflectance does not allow for visualization of fibers perpendicular to the imaging plane. (D) Mesh size distribution within collagen networks acquired by fluorescence. Results are represented as box and whiskers (minimum to maximum), where each point represents a different region within the matrix, with n > 20 positions over n = 3 independent samples. The p values were calculated using an unpaired t test for each separate condition and showed no statistical difference.

FIGURE 2 :

 2 FIGURE 2: Collagen stiffening before the onset of invasion inhibits cancer cell invasion. (A) Timeline representing the chronology of the experiment. Cancer cell were plated in agarose-coated wells for 3 d to form spheroids in the absence (Control) or presence of threose (Thr_incubation). Spheroids were then embedded in collagen droplets with or without threose. Threose was washed out 24 h (Thr_24 h) and 48 h (Thr_48 h) later. All spheroids were fixed at day 3 postembedding. (B) Maximum intensity projections of cancer cell spheroids at day 3. F-actin (red) and DNA (cyan) were respectively stained with phalloidin-rhodamin and DAPI. Scale bar indicates 100 µm. (C) Quantification of cancer cell invasion. Invasion index is defined as the ratio between the number of invading nuclei of cancer cells and the area of the spheroid contour. Data are expressed as box and whiskers (minimum to maximum) of at least N = 3 separate experiments. The p values are compared with control condition using Newman-Keuls multiple comparison test (*p < 0.05). (D) Quantification of single-cell invasion/migration in three-dimensional collagen gels (left: speed; right: persistence) ± 1 mM of threose, after a 48 h incubation in threose. Persistence was defined as the final cell displacement divided by the length of the trajectory. Results are represented as box and whiskers (minimum to maximum) where each point represents an individual cell. The p value was calculated using Mann-Whitney test for n = 107 cells for control and n = 105 cells for threose over n = 3 separate experiments (***p < 0.001). (E) Quantification of migration (left: speed; right: persistence) of CT26 cancer cells with increasing concentrations of threose treatment plated on glass.Measurements were performed during threose treatment and after wash. Migration persistence was defined as the final cell displacement divided by the length of the trajectory. Results are represented as a histogram with mean + SD for three independent experiments. The p values were calculated using Newman-Keuls multiple comparison test and showed no statistical difference. (F) Quantification of the capacity of control cells to adhere to collagen (control, gray) or to threose-treated collagen (Coll_thr, green) and of threose-treated cells to adhere to control collagen (Cells_thr, blue) or to threose-treated collagen (Cells_thr + coll_thr, red). Measurements were performed at 0, 15 min, 30 min, 1 h, and 2 h. Results are expressed as an XY coordinate with mean ± SD with data representing an average over three independent measurements. The p values are compared with control condition using Dunnett's multiple comparison test and showed no statistical difference.

FIGURE 3 :

 3 FIGURE 3: Collagen stiffening before the onset of invasion prevents fiber alignment by cancer cells. (A) Twodimensional slices of cancer cell spheroids in collagen I at day 3. F-actin (red) was stained with phalloidin-rhodamine and collagen was imaged using reflectance (cyan). Right panel, overlaid images of collagen I matrices containing cancer cell spheroids generated using the software CurveAlign (UW-Madison; http://loci.wisc.edu/software/curvealign). Yellow line indicates the edge of the spheroid, and green lines indicate fibers orientation with respect to the closest point on the spheroid edge. Scale bar = 100 µm. (B) Rose plots representing the frequency of distribution of the absolute angles of collagen fibers within the range of 0°-90° with respect to the closest point on the spheroid edge. Data represent the average of 7 < n < 8 spheroids. Fibers parallel to the tumor edge lie in the 0°-30° angles. (C) Left, representative traction force map of a control and a threose-treated cell on collagen-coated polyacrylamide gels with Young's modulus of 5 kPa. White dotted line represents the cell's edge. Color code gives the magnitude of traction stress in Pa, which corresponds to forces of pN/µm 2 . Scale bar = 20 µm. Right, corresponding mean force (strain energy) exerted by CT26 cancer cells. Results are represented as box and whiskers (minimum to maximum), where each point represents an individual cell. The p value was calculated using Mann-Whitney test for n = 27 cells for control and n = 25 cells for threose over three separate experiments and showed no statistical difference.

FIGURE 4 :

 4 FIGURE 4: Collagen stiffening after the onset of invasion favors cancer cell invasion. (A) Timeline representing the chronology of the experiment. Cancer cell spheroids were left to form in agarose-coated wells for 3 d with (Thr_ incubation) or without (Control) threose. Spheroids were then embedded in collagen droplets with (Thr_d0d2) or without (Control) threose for 48 h. Three days postembedding, threose was added in the media for 48 h (Thr_d3d5). All spheroids were fixed at day 7 postembedding. (B) Maximum intensity projections of cancer cell spheroids at day 7. F-actin (red) and DNA (cyan) were respectively stained with phalloidin-rhodamin and DAPI. Scale bar indicates 100 µm. (C) Quantification of cancer cell invasion. Invasion index is defined as the ratio between the number of invading nuclei of cancer cells and the area of the spheroid contour. Quantification results are expressed as box and whiskers (minimum to maximum) of N = 3 separate experiments. The p values are compared with control condition using Newman-Keuls multiple comparison test (**p < 0.01). (D) Model, tumor cells are surrounded by the ECM (a). Cancer cells start invading the ECM before the matrix gets remodeled (b) rather than the matrix being remodeled beforehand (b′). As cancer cells invade the matrix, collagen fibers get aligned (c), which sets up positive feedback to enhance invasion.

ACKNOWLEDGMENTS

We thank Andrew G. Clark for designing the three-dimensional quantification software, Carlos Perez-Gonzalez for help with the generation of roseplots, Marko Matic for help with quantification of two-dimensional migration data, and Nadia Elkhatib and Jorge Barbazan for help with TFM and cell adhesion. We acknowledge Nikon Imaging Center@CNRS-Institut Curie, PICT-IBiSA@Lhomond supported by the Fondation pour la Recherche Médicale (FRM No. DGE20111123020), the Cancérôple-IdF (No. 2012-2-EML-04-IC-1), and InCA (Cancer National Institute, No. 2011-1-LABEL-IC-4). We also thank La ligue contre le cancer (Y.A. and M.V.), Fondation pour la Recherche Médicale (FRM FDT20170437130), and Ecole Doctorale Frontières du Vivant (F.d.V.)-Programme Bettencourt (R.S.). The work of F.B. and G.H.K. is part of the Industrial Partnership Programme Hybrid Soft Materials that is carried out under an agreement between Unilever Research and Development B.V. and the Netherlands Organisation for Scientific Research (NWO). This work was supported by Labex CelTisBioPhy (Y.A. and M.V.). This article is dedicated to the memory of Maxime Dahan, director of the UMR 168, who recently passed away. As a member of the Labex CelTisPhyBio steering committee, he supported this study through grant funding.


Vittorio Bilò
email: vittorio.bilo@unisalento.it

Laurent Gourvès
email: laurent.gourves@dauphine.fr

Jérôme Monnot
email: jerome.monnot@dauphine.fr

On a Simple Hedonic Game with Graph-Restricted Communication

Keywords: Hedonic Games, Price of Anarchy/Stability, Graphs

We study a hedonic game for which the feasible coalitions are prescribed by a graph representing the agents' social relations. A group of agents can form a feasible coalition if and only if their corresponding vertices can be spanned with a star. This requirement guarantees that agents are connected, close to each other, and one central agent can coordinate the actions of the group. In our game everyone strives to join the largest feasible coalition. We study the existence and computational complexity of both Nash stable and core stable partitions. Then, we provide tight or asymptotically tight bounds on their quality, with respect to both the price of anarchy and stability, under two natural social functions, namely, the number of agents who are not in a singleton coalition, and the number of coalitions. We also derive refined bounds for games in which the social graph is restricted to be claw-free. Finally, we investigate the complexity of computing socially optimal partitions as well as extreme Nash stable ones.

Introduction

Coalition formation, that is the process by which agents gather into groups, is a fervent research topic at the intersection of Multi-Agent Systems, Computational Social Choice and Algorithmic Game Theory. One of the most studied models of coalition formation is that of hedonic games [START_REF] Banerjee | Core in a simple coalition formation game[END_REF][START_REF] Bogomolnaia | The stability of hedonic coalition structures[END_REF][START_REF] Drèze | Hedonic coalitions: Optimality and stability[END_REF][START_REF] Hoefer | Dynamics in matching and coalition formation games with structural constraints[END_REF], where agents have preferences over all possible coalitions they can belong to. As agents are usually assumed to be self-interested, an acceptable outcome for a hedonic game, that is a partition of agents into coalitions, needs to be resistant to agents' deviations. Several notions of stability have been investigated in the literature, such as, individual stability, Nash stability, core stability (see, for instance, [START_REF] Aziz | Hedonic games[END_REF]).

In a recent paper, Igarashi and Elkind [START_REF] Igarashi | Hedonic games with graph-restricted communication[END_REF] add a further constraint to the definition of acceptable outcomes for hedonic games, by introducing the notion of feasible coalition: a coalition is feasible if and only if it complies with some prescribed properties. For instance, they assume that the set of agents corresponds to the vertex set V (G) of a social graph G and require a coalition to induce a connected subgraph of G.

In this work, we restrict the feasibility constraint of [START_REF] Igarashi | Hedonic games with graph-restricted communication[END_REF] to coalitions inducing a subgraph of G admitting a spanning star. This requirement guarantees that agents are connected, close to each other, and one central agent can coordinate the actions of the group. We apply this framework within a basic model, falling within the class of additive separable symmetric hedonic games, in which an agent's utility is defined by the cardinality of the coalition she belongs to.

Game Model, Definitions and Notation

Given an unweighted and undirected graph G = (V, E), a coalition is any non-empty subset of V . A partition of V is a set of pairwise disjoint coalitions whose union equals V . We denote by F ⊆ 2 V the set of feasible coalitions. We shall consider F = {C ∈ 2 V | G[C] can be spanned with a star}, where G[C] is the subgraph of G induced by C and a star is a tree of depth at most 1. A star on one vertex is called trivial.

Given an undirected, unweighted and connected graph G, game (G, F) is defined as follows. Each vertex of G is associated with an agent in the game. Let Π be the set of partitions of V . For a partition π ∈ Π and a vertex i ∈ V , denote as π(i) the coalition in π containing i. The utility of i in π is defined as

u i (π) = |π(i)| if π(i) ∈ F, 0 otherwise. ( 1
)
We say that agent i has a profitable deviation in π if either π(i) / ∈ F, or there exists a coalition C ∈ π such that C ∪ {i} ∈ F and |C| ≥ |π(i)|. In the first case agent i can form the singleton coalition {i} which is feasible because it is spanned by a trivial star and yields a utility equal to 1 > u i (π) = 0. In the second case, agent i increases her utility by joining C. More generally, a set of agents S has a joint profitable deviation in π if there exists a partition π , obtained from π by letting every agent i ∈ S leave coalition π(i) and either join another coalition in π or form a new one, such that u i (π ) > u i (π) for each i ∈ S.

A partition π is Nash stable (resp. Strong Nash stable) if no agent (resp. no set of agents) has a profitable deviation (resp. a joint profitable deviation) in π. Nash and strong Nash stable partitions correspond to (pure) Nash and Strong equilibria respectively. We say that a partition is feasible if each of its coalitions belongs to F. It is easy to see that, by definition, any Nash stable partition is feasible. In a core stable partition π, there is no coalition C for which all its members are better off by forming C. The set of core stable partitions (simply called the core) is a subset of the set of Nash stable ones. Strong Nash stability implies core stability but the converse is not always true. Nevertheless, because every agent only cares about the size of its coalition if it is feasible, like in anonymous hedonic games [START_REF] Banerjee | Core in a simple coalition formation game[END_REF], strong Nash stability and core stability coincide in our game. We will use the word core instead of strong Nash for the rest of this article.

A social function is a function, defined from Π to R ≥0 , measuring the social value of a partition. A social optimum is a partition π * ∈ F optimizing a given social function. We consider the following two social functions: sociality, defined as soc(π) = |{i ∈ V : |π(i)| > 1}|, and fragmentation, defined as f rag(π) = |π|. Sociality needs to be maximized, while fragmentation needs to be minimized.

We evaluate the efficiency of stable partitions by means of the well established notions of price of anarchy (PoA), price of stability (PoS) and their strong versions (SPoA and SPoS). The PoA (resp. PoS) of game (G, F) with respect to sociality is defined as soc(π * ) soc(π) , where π * is a social optimum and π is a Nash stable partition of minimum (resp. maximum) sociality. The PoA (resp. PoS) of game (G, F) with respect to fragmentation is defined as f rag (π) f rag(π * ) , where π * is a social optimum and π is a Nash stable partition of maximum (resp. minimum) fragmentation. By substituting the notion of Nash stable partition with that of core stable one, we obtain the definition of both the SPoA and SPoS. Observe that, for a given game (G, F) and independently of the chosen social function, PoS(G,

F) ≤ SPoS(G, F) ≤ SPoA(G, F) ≤ PoA(G, F).

Some Motivations

Requiring subgraphs spanned by a star can be interpreted as restricting the model of [START_REF] Igarashi | Hedonic games with graph-restricted communication[END_REF] to communication patterns of small length. In comparison, unbounded multi-hop communication may be costlier, slower, and prone to errors or misunderstandings. Therefore, distant communication should be avoided. These observations provide both theoretical and practical motivations for the constraint considered in this work. Moreover, our game, complemented with a suitable social function, naturally models several interesting scenarios, some of which are outlined in the following.

Unions. Assume that V (G) models a set of workers of a given company, the edge set E(G) the ideological acquaintance, and that the power of a union is measured by its size. Thus, workers want to join the largest unions. However, a union can survive only if it has a leader who is ideologically close to its partners. For this model, it makes sense considering the fragmentation social function that aims at minimizing the number of unions representing the workers and augmenting their negotiation power.

Group Buying. Assume that V (G) models a set of buyers, all interested in the same product, and E(G) their knowledge/trust relationships. Buyers enjoy flowing into large buying groups, as the larger the group, the better the purchasing conditions they can fetch. However, negotiation with the seller is carried out by one group member only, who then gets also in charge of redistributing what is bought to the others. Thus, this agent needs to be trusted by everybody. If one considers the case in which the product has a fixed price and the share each agent pays is equal to the price divided by the cardinality of her buying group, fragmentation becomes equal to the sum of the costs of all players, i.e., to the utilitarian social function.

Sport Tournaments. Assume that V (G) models a set of teams and there is an edge between two teams if they are close enough to meet and practice a given sport (e.g. football). The participants gather into groups in such a way that a central member can host all teams of its group and organize a tournament. Teams will prefer larger tournaments to small ones in order to maximize the number of opponents against which they can play a match. Sociality, here, aims at involving as many teams as possible into the organization of local tournaments, no matter how big those events are.

Contribution

We focus on the complexity and efficiency of both Nash stable and core stable partitions. Some proofs are omitted due to space constraints.

As to complexity results, we provide two constructive evidences showing existence of core stable partitions, and so also of Nash stable ones. In particular, any sequence of joint profitable deviations converges to a core stable partition, while Theorem 1 characterizes the core as the set of all possible outputs of a polynomial time greedy algorithm. These two facts complement each other, as the first does not need any coordination among the agents, but provides no guarantees of fast convergence, whereas the second, while requiring centralized coordination (dictated by the greedy choices of the proposed algorithm), guarantees efficient computation. We then provide bounds on the PoA, PoS, SPoA and SPoS under social functions sociality and fragmentation. In particular, we consider games induced by general (unrestricted) graphs and games induced by claw-free graphs. These results are summarized in Figure 1.

Efficiency of

General graphs Claw-free graphs stable partitions Sociality Fragmentation Sociality Fragmentation

PoA

n 3 n-2 2 n n- n-1 2 2k k+1 , 2 SPoA n 1+ √ n-1 n/2 2 , n 4 + 11 20 n n- n-1 2 2k k+1 , 2 SPoS n 2+ √ n-2 , n 1+ √ n-1 n/2 2 , n 4 + 11 20 n n- n-1 2 2k k+1 , 2 PoS n 2 √ n-1 , n 1+ √ n-1 n/2 2 , n 4 + 11 20 n n- n-1 2 1
Fig. 1. Bounds on the efficiency of both Nash stable and core stable partitions with respect to social functions sociality and fragmentation. In the last column

k = √ n + 4 -2.
It turns out that the presence of claws in the social graph defining the game is a provable source of inefficiency that has to be taken into account, for instance, whenever mechanisms for coping with selfish behavior can be designed and applied.

Finally, we also address the problem of computing outcomes with prescribed welfare guarantees. In particular, we consider the computation of social optima and extreme (i.e., either best or worst) Nash stable partitions under both social functions. We design a polynomial time algorithm to compute a social optimum for sociality and prove that all other problems are NP-hard, except for that of computing a worst Nash stable partition under fragmentation whose complexity remains open.

Related Work

The language for describing which coalitions are feasible, and how agents value them, is a critical feature in hedonic games. Like in [START_REF] Deng | On the complexity of cooperative solution concepts[END_REF][START_REF] Brânzei | Coalitional Affinity Games and the Stability Gap[END_REF], feasible coalitions and their values can be described with the help of a (directed) graph. Igarashi and Elkind [START_REF] Igarashi | Hedonic games with graph-restricted communication[END_REF] and Peters [START_REF] Peters | Graphical hedonic games of bounded treewidth[END_REF] have considered hedonic games defined over graphs: agents are the vertices and feasible coalitions satisfy a given graph property. Regarding the worth of a coalition, a simple and compact representation is given by additively separable functions [START_REF] Banerjee | Core in a simple coalition formation game[END_REF]: each agent i assigns a value ν ij to agent j and agent i's worth for a coalition C is j∈C ν ij . See, for example, [START_REF] Olsen | On non-trivial Nash stable partitions in additive hedonic games with symmetric 0/1-utilities[END_REF] for a simple hedonic game where ν ij ∈ {0, 1}. Our work falls in this framework, as everybody wants to be part of the largest coalition (ν ij is always Algorithm 1 Greedy Core

Input: Game (G, F) where G = (V, E) is a graph. Output: A core stable partition π. 1: while V = ∅ do 2: take i ∈ V maximizing the degree dG(i) 3: π(i) ← NG[i] *NG[i] is the closed neighbourhood of i* 4: G ← G[V \ NG[i]] 5: end while 6: return π 1)
, and a coalition is feasible if and only if the vertices representing the agents can be covered with a star.

Regarding existing games defined over graphs, Panagopoulou and Spirakis [START_REF] Panagopoulou | A game theoretic approach for efficient graph coloring[END_REF] and Escoffier et al. [START_REF] Escoffier | Strategic coloring of a graph[END_REF] studied a game where the vertices of a graph have to select a color (each color corresponds to a coalition), and a vertex's payoff is the number of agents with the same color, provided that it constitutes an independent set.

In many works including the famous stable marriage problem, the coalitions form a matching of a graph (see for example [START_REF] Hoefer | Dynamics in matching and coalition formation games with structural constraints[END_REF]).

For bounds on the price of anarchy and the price of stability in some classes of hedonic games, one can see [START_REF] Balliu | Nash stability in social distance games[END_REF][START_REF] Bilò | Nash stable outcomes in fractional hedonic games: Existence, efficiency and computation[END_REF][START_REF] Feldman | Hedonic clustering games[END_REF][START_REF] Monaco | Stable outcomes in modified fractional hedonic games[END_REF][START_REF] Monaco | On the performance of stable outcomes in modified fractional hedonic games with egalitarian social welfare[END_REF]. The computation of socially optimal partitions in hedonic games, according to different social functions, has been treated in [START_REF] Balliu | On Pareto optimality in social distance games[END_REF][START_REF] Charikar | Clustering with qualitative information[END_REF][START_REF] Demaine | Correlation clustering in general weighted graphs[END_REF][START_REF] Flammini | Online coalition structure generation in graph games[END_REF][START_REF] Brânzei | Coalitional Affinity Games and the Stability Gap[END_REF]. Finally, we refer the reader to [START_REF] Aziz | Stable partitions in additively separable hedonic games[END_REF][START_REF] Ballester | NP-completeness in hedonic games[END_REF][START_REF] Olsen | Nash stability in additively separable hedonic games and community structures[END_REF][START_REF] Peters | Simple causes of complexity in hedonic games[END_REF] for an extensive treatment of the computational complexity of both decision and search problems related to stable partitions in hedonic games.

On Core Stable Partitions

Given a partition π, a strong Nash dynamics of length starting from π is a sequence of partitions π = π 0 , π 1 , . . . , π such that, for each j ≥ 1, π j is obtained as a result of a joint profitable deviation of some set of agents in π j-1 .

A game has the lexicographical improvement property (LIP) [START_REF] Harks | Strong equilibria in games with the lexicographical improvement property[END_REF], if every joint profitable deviation strictly decreases the lexicographical order of a certain function defined on Π. It is not difficult to see that for any graph G, game (G, F) has the LIP property if one considers the n-dimensional vector consisting of the values u i (π) for each i ∈ V , sorted in non-increasing order. Thus, a core stable partition always exists as the length of every strong Nash dynamics is finite.

We now prove that, if centralized coordination is allowed, a core stable partition can be computed in polynomial time. This is done by proving that the core is completely characterized by the set of all possible outputs of Algorithm 1. Theorem 1. A partition is core stable if and only if it is the output of Algorithm 1 (according to some specific tie breaking rule).

Proof. The algorithm outputs a feasible partition π. First we show that π is core stable. Assume, by way of contradiction, that π is not core stable. Then, there exists a joint profitable deviation in π for a coalition S such that |S| ≥ 1. Let i be the agent getting the highest utility in π among the ones belonging to S. As i improves, she will end up in a coalition C ∈ F such that |C| > |π(i)|. If C is created by the algorithm before π(i), then i should belong to C in π: a contradiction to the greedy choice. Hence, either C is created by the algorithm after π(i) or it is a new coalition created by the joint deviation. As i gets the highest utility in S, C only contains vertices belonging to coalitions created by the algorithm at the step π(i) is created or after. This implies that, at the step in which π(i) is created, C could have been created too, thus contradicting the greedy choice. Now, we show that any core stable partition π can be the output of the above algorithm. List the coalitions in π by non-increasing cardinality and define a tie breaking rule R that gives priority to the coalitions in π according to the given ordering, and gives higher priority to a coalition in π with respect to any coalition not in π. Run the algorithm according to rule R to obtain a partition π . Assume, by way of contradiction, that π = π . List the coalitions in π by non-increasing cardinality, breaking ties according to R. Let j be the first index at which the two sequences become different and denote as C and C the j-th coalition in the ordering defined on π and π , respectively. By the definition of R, it must be |C | > |C| which implies that all vertices in C can perform a joint profitable deviation in π. This contradicts the assumption that π is a core stable partition.

Efficiency of Core/Nash Stable Partitions

In this section, we focus on the efficiency of Nash or core stable partitions with respect to both social functions sociality and fragmentation. Before characterizing the price of anarchy, we prove some preliminary lemmas.

Lemma 1. If G admits a spanning star, then any Nash stable partition for game (G, F) is formed by a unique coalition V (G).

Lemma 2. If G is connected with n ≥ 3, then any Nash stable partition for game (G, F) contains either 2 coalitions of size at least 2 or a coalition of size at least 3.

We are now ready to characterize the PoA. As it is equal to 1 for any game with three players (by Lemma 1), in the remaining of the section we shall assume n ≥ 4.

Theorem 2. For any game with n players, the price of anarchy is n/3 with respect to sociality and (n -2)/2 with respect to fragmentation. Both bounds are tight.

Proof. Fix a Nash stable partition π. By Lemma 2, soc(π) ≥ 3. As the sociality of any partition is upper bounded by n, we obtain an upper bound of n/3 on the price of anarchy. By Lemma 1, if the fragmentation of the social optimum is 1, then the price of anarchy is 1, hence assume that its fragmentation is at least 2. By Lemma 2, f rag(π) ≤ n -2 which yields the desired upper bound on the price of anarchy.

A matching lower bound for both social functions can be obtained by considering the game induced by the graph G depicted in Figure 2. The partition π such that π(v 1 ) = {v 1 , v 2 , v 3 } and π(v i ) = {v i } for i > 3 is Nash stable and has soc(π) = 3 and f rag(π) = n -2. On the other hand, the partition π * such that π * (v 1 ) = {v 1 , v 2 } and π * (v 3 ) = {v 3 , . . . , v n } has a sociality of n and a fragmentation of 2. Comparing the two partitions yields the desired lower bounds. It is also possible to give an upper bound on the price of anarchy with respect to both social functions which depends on the stability number α(G) of graph G, where α(G) is the largest size of an independent set. Proof. Fix a Nash stable partition π. As the set of centres of the stars spanning the subgraph induced by each coalition in π forms an independent set in G, it follows that f rag(π) ≤ α(G). Thus, by Lemma 2, it follows that the price of anarchy with respect to fragmentation is at most α(G)

2 . Moreover, as G has at least one edge, the number of singleton coalitions in π can be at most f rag(π) -

1 ≤ α(G) -1. So, soc(π) ≥ n -α(G) + 1.
For the efficiency of core stable outcomes, we have the following results. For the lower bound on the strong price of anarchy, consider the game induced by a tree G rooted at vertex x 0 which has children denoted as x 1 , . . . , x . For each i ∈ [ ],

x i has -1 children, so that G has n = 2 + 1 vertices. By using the characterization of core stable partitions given in Theorem 1, it follows that the partition π whose unique non-singleton coalition is {x 0 , x 1 , . . . , x } is a core stable partition for game (G, F). As soc(π) = +1 and there is a partition with sociality n, we get that the strong price of anarchy is lower bounded by n +1 . By using

n = 2 + 1, it follows that n +1 = n 1+ √ n-1
and this provides the desired lower bound.

For the lower bound on the strong price of stability, add a vertex y to the previous instance which is solely connected to x 0 , so that G now has n = 2 + 2 vertices. In this case, the partition π whose unique non-singleton coalition is {x 0 , x 1 , . . . , x , y} is the unique core stable partition for game (G, F). As soc(π) = + 2, we get that the strong price of stability is lower bounded by n +2 . By using n = 2 + 2, it follows that

n +2 = n 2+ √
n-2 and this provides the desired lower bound. Theorem 5. For any instance (G, F) of the game with n players and the fragmentation function, it holds that n/2 /2 ≤ P oS(G, F) ≤ SP oA(G, F) ≤ n/4 + 11/20.

Proof. Let π be a core stable partition and set k = ∆(G) + 1, where ∆(G) is the maximum degree of G. It follows that the fragmentation of the social optimum is at least n/k . From Theorem 1, we know that there is a coalition of size k in π. Thus 11 20 , where the last inequality is due to the hypothesis n ≥ 4 (the smallest odd n is 5). To show the lower bound when n is even, consider the game induced by the graph depicted in Figure 3. We have a social optimum π * such that π * (x 1 ) = {x 1 , . . . , x n/2 } and π * (y 1 ) = V \ π * (x 1 ) and yielding f rag(π * ) = 2. There are only two Nash stable partitions, namely π 1 and π 2 , both having fragmentation equal to n/2 . In particular, π 1 is such that π 1 (x 1 ) = {x 1 , . . . , x n/2 , y 1 } and π 1 (y i ) = {y i } for i > 1, while π 2 flips the roles of x and y. When n is odd, take the same instance and add a new vertex solely connected to x 1 to get the lower bound of n/2 /2.

f rag(π) ≤ 1 + n -k, and SP oA(G, F) ≤ k(1+n-k) n . If n is even then k(1+n-k) n ≤ n/4 + 1/2, otherwise k(1+n-k) n ≤ (n+1) 2 4n = n 4 + 1 2 + 1 4n ≤ n 4 +
x1 y1 x2 x n/2 y2 y n/2
Fig. 3. A graph yielding a game with worst-case price of stability with respect to fragmentation.

We conclude the section with a lower bound on the price of stability for the sociality social function showing that the quality of the best Nash stable partition cannot be better than twice that of the worst core stable one. Theorem 6. For any game with n players, the price of stability with respect to sociality is at least n 2 √ n-1 .

Proof. Consider the game yielded by the graph G = (V, E) such that V = X ∪ Y 1 ∪ . . . ∪ Y , with X = {x 1 , . . . , x } and, for each i ∈ [ ], Y i = {y i,1 , . . . , y i, -1 }. The set of edges E is such that G[X] = K (i.e. complete graph on vertices) and, for each i ∈ [ ] each vertex in Y i is connected to x i only. Note that, by setting = √ n, we obtain |V | = n. We shall prove that, in any Nash stable partition, the sociality is at most

2 √ n -1.
Given that there is a partition of sociality n, this will yield the corresponding lower bound. Fix a Nash stable partition π. We claim that π contains a unique nonsingleton coalition containing X. This easily follows from the fact that X defines a clique and that, by the topology of G, in any feasible coalition C containing a vertex of x ∈ X, C induces a subgraph of G admitting a spanning star centred at x. Moreover, as π is Nash stable, we shall have that the unique non-singleton coalition in π will also contain all vertices in Y i for a certain i ∈ [ ]. No other vertices of G can be added to the coalition without violating the feasibility constraint and no other non-singleton coalition can be constructed as the remaining vertices yield an independent set of G. Hence, the sociality of π is 2 √ n -1.

Claw-Free Graphs

In this subsection, we consider the case in which the graph G is claw-free, i.e., it does not contain an induced K 1,3 (i.e. complete bipartite graph with 1 and 3 vertices on the respective sides). It will turn out that the presence of claws in graph G is a provable source of inefficiency as the price of anarchy with respect to both social functions (and so also all the other metrics) for games played on claw-free graphs drops to a value which never exceeds 2. Claws (and more generally induced stars with a large number of leaves) are problematic for our social functions when the center c of a claw belongs to a partition π(c) which does not admit a spanning star of center c. In this case some leaves of the claw are isolated: they cannot join π(c) or group themselves because they are disconnected. For the social function sociality, the following two theorems provide an asymptotically tight characterization.

Theorem 7. For any game with n players, the price of anarchy with respect to sociality is at most

n n-n-1 2
, that is 2n n+2 and 2n n+1 when n is even and odd, respectively.

Proof. Fix a Nash stable partition π and let i be a vertex belonging to a singleton coalition in π. Clearly, i cannot be adjacent to a vertex being a center of a spanning star of any subgraph induced by a coalition in π. So, i can only be adjacent to leaves of spanning stars of any subgraph induced by coalitions in π. Assume that there exists a vertex j also belonging to a singleton coalition in π and sharing a neighbour k with i. Let c be the center of a star spanning G[π(k)]. As {i, j, c} is independent, we find that the set of vertices {i, j, k, c} induces a claw in G: a contradiction. Two vertices forming a singleton coalition cannot share the same leaf of a star spanning a non-singleton coalition. Thus, denote by α the number of vertices that are centres of a star spanning the subgraph induced by a non-singleton coalition in π, we get that the number of vertices forming singleton coalitions in π, which is integral, is upper bounded by n-α 2 ≤ n-1

2

. This implies that soc(π) ≥ n -n-1 2 , which yields the desired upper bound because the optimal sociality soc(π * ) is n. Theorem 8. For any game with n players, the price of stability with respect to sociality is at least

n n-n-1 2 .
Proof. Suppose n = 2p and consider the graph

G 2p = (V 2p , E 2p ) such that V 2p = X p ∪ Y p ,
where X p = {x 1 , . . . , x p }, Y p = {y 1 , . . . , y p }, X p forms a clique, and each vertex y i is adjacent to vertex x i . One can see that G 2p is claw-free, and X p ⊆ π(x i ) for any Nash stable partition π. Moreover, to have feasibility, a coalition C can contain at most one vertex from Y p . It follows that the sociality of any Nash stable partition is at most p + 1. As there exists a partition with sociality 2p, the claimed lower bound follows. For n = 2p + 1, use the same construction with Y p = {y 1 , . . . , y p-1 }.

For the fragmentation social function, a slightly different situation occurs. Theorem 9. For any game with n players, the price of anarchy with respect to fragmentation is at most 2.

Proof. Fix a Nash stable partition π.

If f rag(π) ≤ 2, we are done. If f rag(π) ≥ 3, consider three distinct coalitions C 1 , C 2 , C 3 ∈ π and let c 1 , c 2 and c 3 be the centres of the spanning stars of G[C 1 ], G[C 2 ] and G[C 3 ],
respectively. As π is Nash stable, the set of vertices U = {c 1 , c 2 , c 3 } induces an independent set of G. We claim that these vertices cannot belong to a same cluster in some social optimum π * . Assume, by way of contradiction, that there exists a cluster C * ∈ π * containing U . As U induces an independent set of G no vertex in U can be the center of the star spanning G[C * ]. So, there exists c * ∈ C * which is adjacent to all vertices in U . But U ∪ {c * } induces a claw: a contradiction. Hence, for every two coalitions in π, there must exist a distinct coalition in π * which yields the desired upper bound.

Theorem 10. For any positive integer k, there exists a game whose strong price of stability with respect to fragmentation is at least 2k k+1 . Proof. For an integer k ≥ 1, define the following graph G k . The set of vertices is

V = X 1 ∪ . . . ∪ X k ∪ Y ∪ Z, with Y = {y 1 , . . . , y k } and Z = {z a 1 , z b 1 , . . . , z a k , z b k } so that |Z| = 2k. As to sets X i for i ∈ [k], we have that |X i | = 2i, G k (X i ) induces
a clique and X i contains two special vertices, namely x i and x i , which are the only vertices adjacent to vertices in V \ X i . In particular, x i is adjacent to both z a i and z b i , while x i is adjacent to y i and, for i < k, to both z a i+1 and z b i+1 . Finally, for each i ∈ [k], z a i and z b i are adjacent and, for i > 1, they are both adjacent to y i-1 . Again, we show two fundamental properties:

Property 1. (i) G k is claw-free, (ii) (X i ∪ {z a i , z b i }, {y i } | i ∈ [k]
) is a core stable partition.

Consider the feasible partition π * containing the following coalitions:

X k ∪ {y k }, X i ∪ {y i } ∪ {z a i+1 , z b i+1 } for each i ∈ [k -1] and {z a 1 , z b 1 }. As f rag(π) = k + 1, the claimed lower bound follows.
Theorem 11. For any game with n players, the price of stability with respect to fragmentation is 1.

Proof. Our aim is to show that, given a partition π, it is possible to schedule profitable deviations so as to obtain a Nash dynamics starting from π and ending up to a Nash stable partition π such that f rag(π ) ≤ f rag(π). Choosing a social optimum as starting partition will yield the claim. Our scheduling algorithm is defined as follows: given a partition π, if more than one player have a profitable deviation in π, break ties in favour of a player who does not constitute a center for any spanning star of the subgraph induced by the coalition she belongs to. By the LIP property, we are guaranteed that the Nash dynamics defined by this scheduling algorithm always ends to a Nash stable partition π for any starting partition π.

Assume, by way of contradiction, that f rag(π ) > f rag(π). This implies that there are two partitions π, π ∈ Π and a player i such that π is obtained as a result of a profitable deviation of i in π and f rag(π) < f rag(π ). The latter condition can happen only if G[π(i) \ {i}] does not admit a spanning star, which implies that G[π(i)] admits only one spanning star centred at i. So, there are at least two distinct vertices u and v other than i belonging to π(i). Let C ∈ π be the coalition joined by i and let j = i be the center of a spanning star for G

[C ∪ {i}]. Clearly it must be {i, j} ∈ E. If {u, j} ∈ E, then C ∪ {u} ∈ F. But as u u (π) = u i (π) = |π(i)| < u i (π ) = |C ∪ {i}| = |C ∪ {u}|,
it follows that u has a profitable deviation in π and, by the definition of the scheduling algorithm, i should have not been chosen. The same argument holds for v. Thus, we have detected a set of vertices {i, j, u, v} inducing a claw in G: a contradiction.

Computing Partitions with Prescribed Properties

In this section, we address the complexity of computing partitions with some prescribed properties, such as, for example, being a social optimum or being a Nash stable partition either maximizing or minimizing a given social function.

Computing a Social Optimum

Proposition 1. Computing a social optimum with respect to fragmentation is NP-hard, even for claw-free graphs.

The following result relies on the efficient computation of a minimum edge-cover. Proposition 2. For connected graphs on n vertices, computing a social optimum π * with respect to sociality is polynomial and soc(π * ) = n.

Computing an Extreme Stable Partition

Using Theorem 11 and Proposition 1, we deduce that computing a best Nash stable partition with respect to fragmentation is NP-hard, even for claw-free graphs. We now show that hardness holds also for the sociality social function.

Theorem 12. Computing the best Nash stable partition with respect to sociality is NPhard when the input graph G has maximum degree equal to 5.

Proof. We propose a reduction from 3-DIMENSIONAL MATCHING (3-DM in short). An instance of 3-DM consists of a collection C = {s 1 , . . . , s m } ⊆ X × Y × Z of m triples, where X = {x 1 , . . . , x n }, Y = {y 1 , . . . , y n } and Z = {z 1 , . . . , z n } are 3 pairwise disjoint sets of size n. A matching is a subset M ⊆ C such that no two elements in M agree in any coordinate, and the purpose of 3-DM is to answer the question: does there exist a perfect matching M on C, that is, a matching of size n? This problem is known to be NP-complete (problem [SP1] page 221 in [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]), even if each element t ∈ X ∪ Y ∪ Z appears in at most 3 triples. We start from such an instance I = (C, X ∪ Y ∪ Z) of 3-DM and we build a game (G, F), where G = (V, E) is as follows. Vertex set contains L ∪ R where L = {l 1 , . . . , l m } corresponds to the different triples of C and R = R x ∪ R y ∪ R z where R t = {r t 1 , . . . , r t n } for t = x, y, z, corresponds to elements of X ∪ Y ∪ Z. Moreover for t = x, y, z, l i r t j ∈ E if and only if t j is an element of triplet s i . This particular bipartite graph is usually called representative bipartite graph. We use gadget H(l i ) for each l i ∈ L to characterize triplets of C. This gadget is illustrated in Figure 4 (on the left of the drawing).

The construction of G is complete and its maximum degree is 5. We claim that I admits a perfect matching if and only if there exists a Nash stable partition π of (G, F) with soc(π) ≥ 5m + n. Actually, we will prove that 5m + n is the best value reachable by any Nash stable partition π.

Clearly, if C ⊆ C is a set of n triples forming a perfect matching, then consider the following partition π. For s i = (x i1 , y i2 , z i3 ) ∈ C , set π(d i ) = {d i }, π(e i ) = {e i } and π(l i ) = {b i , c i , l i , r x i1 , r y i2 , r z i3 }; an illustration of these 3 coalitions is proposed in Figure 4 (on the right of the drawing). Otherwise, for s i / ∈ C , set π(l i ) = {l i , b i , c i , d i , e i }. It is easy to see that π is a Nash stable partition with soc(π) = 6n + 5(m -n) = 5m + n. Conversely, let π be a Nash stable partition. If {l i , r t j } ⊆ π(r t j ) for some j ∈ [n] and t = x, y, z, then: Property 2. (i) ∀i = i, l i / ∈ π(r t j ), (ii) {b i , c i } ⊆ π(r t j ) and {d i , e i } ∩ π(r t j ) = ∅.

Let Cov = {l i ∈ L : |π(l i )| = 6} and p = |Cov|. By Property 2, for every l i ∈ Cov, it must be π(e i ) = {e i } and π(d i ) = {d i } (see right picture of Figure 4 for an illustration); actually, these collations correspond to a (3-dimensional) matching of size p. Using Property 2, we know that we also loose in the sociality function, as many trivial stars as the number of vertices of R \ (∪ li∈Cov π(l i )). Hence, soc(π) ≤ 5m + 3n -(2p + 3n -3p) = 5m + p ≤ 5m + n and the last inequality is tight only when |Cov| = n or equivalently when C = {s i | l i ∈ Cov} is a perfect matching.

Corollary 1. Computing the best Nash stable partition with respect to either sociality or fragmentation is NP-hard even for planar graphs.

As to the problem of computing a worst Nash stable partition, we give a hardness result with respect to sociality, while the case of the fragmentation social function remains open.

Theorem 13. Computing the worst Nash stable partition with respect to sociality is NP-hard when the input graph G has maximum degree equal to 11.

Conclusion

Two problems are left open: closing the gap between upper and lower bounds on the PoS with respect to sociality for games played on general graphs, and determining the complexity of computing a worst Nash stable partition with respect to fragmentation. Addressing the problem of computing extreme core stable partition is also worth to be investigated.

Applying our feasibility constraint (i.e. imposing a spanning star) to hedonic games having agents' preferences other than the ones considered in this paper is clearly an interesting research direction. Other graph patterns are appealing in our opinion: the largest distance between any pair of agents, or the distance to some agent of the coalition can be upper bounded by a given number (for the latter the distance to some agent is 1 in this paper).

Fig. 2 .

 2 Fig.2. A graph yielding a game with worst-case price of anarchy.

Theorem 3 .

 3 The price of anarchy of game (G, F) is at most n n-α(G)+1 with respect to sociality and at most α(G) 2 with respect to fragmentation.

Theorem 4 .and

 4 For any game (G, F) with n players SP oS(G, F) ∈ SP oA(G, F) = n 1+ √ n-1 hold for the sociality function. Proof. For the upper bound, consider a coalition C in a core stable partition π with |C| = k > 2 and let c be the center of the spanning star of G[C]. No vertex i belonging to a singleton coalition can be adjacent to c, otherwise i would have a profitable deviation in π. Any vertex i ∈ C, with i = c can be adjacent to at most k -2 vertices belonging to a singleton coalition, otherwise these vertices, together with i and c would have a joint profitable deviation in π. It follows that for any coalition in π with k > 2 vertices, there can be at most (k -1)(k -2) singleton coalitions in π. Let s k be the number of coalitions in π with k vertices for k ≥ 1. We deduce n k=3 s k (k 2 -3k + 2) ≥ s 1 which gives n k=2 s k (k 2 -2k + 2) ≥ n by adding n k=2 ks k on both sides. As the sociality in a social optimum is upper bounded by n and soc(π) = n k=2 (s k k), we obtain that the strong price of anarchy is at most n n k=2 (s k k) ≤ k 2 -2k+2 k , where k = max{k : s k > 0}. Moreover, as soc(π) ≥ k, the strong price of anarchy is trivially upper bounded by n/k. It follows that the minimum of the two derived bounds is maximized for k 2 -2k + 2 = n ⇔ k = 1 + √ n -1, which yields the desired upper bound on both SP oA(G, F) and SP oS(G, F).

1 Fig. 4 .

 14 Fig.[START_REF] Balliu | Nash stability in social distance games[END_REF]. On the left: Gadget H(li). On the right: a possible Nash stable partition for agents in H(li).