Thomas Ranvier
email: thomas.ranvier@univ-lyon1.fr

Haytham Elgazel
email: haytham.elghazel@univ-lyon1.fr

Emmanuel Coquery
email: emmanuel.coquery@liris.cnrs.fr

Khalid Benabdeslem
email: khalid.benabdeslem@univ-lyon1.fr

Autoencoder-based Attribute Noise Handling Method for Medical Data

Keywords: Data Denoising, Data Imputation, Attribute Noise, Machine Learning, Deep Learning

Medical datasets are particularly subject to attribute noise, that is, missing and erroneous values. Attribute noise is known to be largely detrimental to learning performances. To maximize future learning performances it is primordial to deal with attribute noise before any inference. We propose a simple autoencoder-based preprocessing method that can correct mixed-type tabular data corrupted by attribute noise. No other method currently exists to handle attribute noise in tabular data. We experimentally demonstrate that our method outperforms both state-of-the-art imputation methods and noise correction methods on several real-world medical datasets.

Introduction

Medical studies are particularly subject to outliers, erroneous, meaningless, or missing values. In most real-life studies, not solely limited to the medical field, the problem of incomplete data and erroneous data is unavoidable. Those corruptions can occur at any data collection step. They can be a natural part of the data (patient noncompliance, irrelevant measurement, etc.) or appear from corruption during a later data manipulation phase [START_REF] Yang | Dealing with Predictive-but-Unpredictable Attributes in Noisy Data Sources[END_REF]. Regardless of their origin, those corruptions are referred as "noise" in the following work. Noise negatively impacts the interpretation of the data, be it for a manual data analysis or training an inference model on the data. The goal of a machine learning model is to learn inferences and generalizations from training data and use the acquired knowledge to perform predictions on unseen test data later on. Thus, the quality of training data on which a model is based is of critical importance, the less noisy the data is, the better results we can expect from the model.

Noise can be divided into two categories, namely class noise and attribute noise [START_REF] Zhu | Class Noise vs. Attribute Noise: A Quantitative Study[END_REF]. Class noise corresponds to noise in the labels, e.g. when data points are labeled with the wrong class, etc. Attribute noise on the other hand corresponds to erroneous and missing values in the attribute data, that is, the features of the instances. Attribute noise tends to occur more often than class noise in realworld data [START_REF] Yang | Dealing with Predictive-but-Unpredictable Attributes in Noisy Data Sources[END_REF][17] [START_REF] Van Hulse | The Pairwise Attribute Noise Detection Algorithm[END_REF]. Despite this fact, compared to class noise, very limited attention has been given to attribute noise [START_REF] Zhu | Class Noise vs. Attribute Noise: A Quantitative Study[END_REF]. In real-world medical data, the probability of mislabeled data in a survival outcome context is quite low, we focused our work on attribute noise to maximize prediction performance while trying to compensate for a lack of appropriate methods within the literature.

The problem of imputing missing values has been vastly addressed in the literature, one can choose from many imputation methods to complete its data depending on its specific needs [START_REF] Stef | Flexible Imputation of missing Data[END_REF]. Imputation methods only address part of the attribute noise problem, they can handle missing values but do not handle erroneous values, which can be highly detrimental to imputation results. Those methods have been widely researched, but methods able to deal with erroneous values have been less researched and can be considered incomplete at the moment [START_REF] Yang | Dealing with Predictive-but-Unpredictable Attributes in Noisy Data Sources[END_REF].

Handling erroneous values can be done in three main ways: using robust learners that can learn directly from noisy data and naturally compensate or partially ignore the noise, filtering methods that remove data points that are classified as noisy, and polishing methods that aim to correct noisy instances. Robust learners are models that are less sensitive to noise in the data than classic models but they present several disadvantages [START_REF] Van Hulse | The Pairwise Attribute Noise Detection Algorithm[END_REF]. They usually have limited learning potential compared to other learners. Using robust learners is not useful if we aim to perform anything else than the task the learner will solve. Filtering methods aim to detect which instances are noisy to delete them from the training set [START_REF] Zhu | Class Noise vs. Attribute Noise: A Quantitative Study[END_REF] [START_REF] Van Hulse | The Pairwise Attribute Noise Detection Algorithm[END_REF]. By training a learner on this cleaned set it can learn inferences without being disturbed by erroneous values and outliers which eventually leads to better prediction performances on test data. The third way to deal with erroneous values is the polishing method [START_REF] Teng | Polishing Blemishes: Issues in Data Correction[END_REF], which corrects instances detected as noisy. Such a method can correct erroneous values on small datasets but lacks scalability for larger datasets containing more features [START_REF] Van Hulse | The Pairwise Attribute Noise Detection Algorithm[END_REF]. Those three methods are able to deal with erroneous values and outliers but are not able to deal with incomplete data, they only address part of the attribute noise problem.

At the moment the only way to handle attribute noise in its entirety is to use a combination of an imputation method followed by a noise correction method, to the best of our knowledge the literature lacks a method that would be able to perform both those tasks at once. Real-world data and especially medical data are subject to attribute noise in its entirety, it is important to conceive an approach able to handle the totality of attribute noise and not just subpart of it.

In this paper, we propose a preprocessing method based on autoencoders that deals with attribute noise in its entirety in real-world tabular and mixedtype medical data. Our method is able to learn from incomplete and noisy data to produce a corrected version of the dataset. It does not require any complete instance in the dataset and can truly handle attribute noise by performing both missing values completion and correction of erroneous values at the same time. We conduct extensive experiments on an imputation task on real-world medical data to compare our method to other state-of-the-art methods and obtain competitive and even significantly better results on classification tasks performed on the corrected data. We extend our experiments to show that our method can both complete missing data while correcting erroneous values, which further improves the obtained results.

The complete source code used to conduct the experiments is available at the following github repository 6 .

The rest of the paper is organized as follows: we first present related work of data imputation and noise correction in both tabular and image data, especially in the medical field, in section 2. Then, we present and explain our proposed approach in section 3. Section 4 shows our experimental results compared to both data imputation and noise correction state-of-the-art methods. Finally, we conclude with a summary of our contributions.

Related work

Denoising is vastly researched in the image field, in the image medical domain it is easy to find recent reviews and methods to correct medical images [START_REF] Sagheer | A review on medical image denoising algorithms[END_REF]. Correction of tabular data on the other hand is less researched, only the imputation part seems to attract lots of attention. In this paper, we are especially focused on methods that can be applied to mixed-type tabular data.

Recently lots of autoencoder-based imputation methods have been researched [START_REF] Pereira | Reviewing Autoencoders for Missing Data Imputation: Technical Trends, Applications and Outcomes[END_REF]. An autoencoder is a machine learning algorithm that takes an input x ∈ R d with d the number of features and learns an intermediate representation of the data noted z ∈ R h with h the size of the newly constructed latent space. Then, from the intermediate representation z the model reconstructs the original data x, we note the model output x. During its training, the reconstruction error between x and x is minimized.

One of those autoencoder-based imputation methods is MIDA: Multiple Imputation using Denoising Autoencoders, introduced in 2018 [START_REF] Gondara | MIDA: Multiple Imputation Using Denoising Autoencoders[END_REF]. Unlike most autoencoder-based methods which are usually applied to images, MIDA has been successfully applied to tabular data. This imputation method learns from a complete training dataset and can then be applied to unseen incomplete test data to impute the missing values. The authors assume that in order to learn how to impute missing values MIDA must learn from complete data. However, in this paper our experimental protocol does not provide a clean dataset to train on, therefore we show that MIDA obtains satisfactory results when properly parameterized, even when learning on incomplete data.

We want to show that autoencoders can not only be used to impute missing values, but also to correct erroneous values that are part of the observed values. It is easier to correct erroneous values in an image than in tabular data, since in images pixels in a close neighborhood are related to each other, which might not be true for arbitrarily ordered features in tabular data. As stated earlier correction of images is a very active research domain. Recently, Ulyanov et al. introduced a new approach called "Deep Image Prior [START_REF] Ulyanov | Deep Image Prior[END_REF]." That innovative approach uses autoencoders to restore images but does not use the original data X as model input, instead, the autoencoder is given pure noise as input and is trained to reconstruct the original corrupted data X from the noise. In that way, the model is no longer considered an autoencoder but a generative model, however, in practice the model keeps the same architecture. Therefore, the only information required to correct the input image is already contained in the image itself. By stopping the training before complete convergence it is possible to obtain a cleaner image than the original corrupted image. Ulyanov et al. showed that their approach outperforms other state-of-the-art methods on a large span of different tasks.

In this paper, we aim to conceive a method that would be able to correct mixed-type tabular data, we aim to use the lessons from [START_REF] Gondara | MIDA: Multiple Imputation Using Denoising Autoencoders[END_REF] and [START_REF] Ulyanov | Deep Image Prior[END_REF] to conceive a method able to handle attribute noise as a whole as a preprocessing method.

A Method to Truly Handle Attribute Noise

Our method is based on a deep neural architecture that is trained to reconstruct the original data from a random noise input. We note the original data with its attribute noise X ∈ R n×d with n the number of instances in the dataset and d the number of features. We note the deep generative model X = f Θ (•) with Θ the model parameters that are learned during training and X is the model output, in our case the model output is a reconstruction of X. The input of the model is noted Z ∈ R n×d and has the same dimension as X, which keeps our model a kind of autoencoder. The model is trained to reconstruct X using the following loss term: L(X, X) = ||( X -X) ⊙ M || 2 , where ⊙ is the Hadamard product and M ∈ R n×d is a binary mask that stores the locations of missing values in X, M ij = 1 if X ij is observed and M ij = 0 if X ij is missing. By applying the mask M to the loss ensure that the loss is only computed on observed values, in this way the reconstruction X will fit the observed values in X, while missing values will naturally converge to values that are statistically consistent given the learned data distribution. Figure 1 shows how the model is fitted to the original data X with the application of the binary mask M during training.

To determine the right step at which to stop training we define a stopping condition based on the evolution of a given metric. In a supervised setting, for example, we regularly compute the AUC on a prediction task performed on the reconstructed data X, which gives us the evolution of the quality of the reconstruction. We stop the training when the AUC degrades for a set number of iterations, then we obtain a reconstruction with consistent imputations and noise correction, which provides better data quality than the original data. If no supervision is possible the only metric that can be used to determine when to stop training is the loss value, which gives correct results but is quite limited since it is harder to determine when overfitting starts.

In practice, we set the input of the model either as random noise or as the original data depending on the obtained results. We note that on datasets containing large amounts of features, using 1D convolutions instead of classic fully-connected layers tends to give better results, it helps our method to scale on datasets with large amounts of data and features.

What makes this method different from most other autoencoder-based methods and able to handle attribute noise as a whole is that we determine an earlystop condition to stop training at the proper moment. Stopping at the right moment allows the method to reach a point where the reconstructed data X contains less noise than the original data X while containing all important information from X.

Experimental Results

Used Datasets

We ran our experiments on three real-life medical mixed-type tabular datasets naturally containing missing values. We evaluated our method and compared our results to other state-of-the-art methods on those medical datasets.

-NHANES, US National Health and Nutrition Examination Surveys: Those are surveys conducted periodically by the US NHCS to assess the health and nutritional status of the US population [START_REF] Barnard | Applications of multiple imputation in medical studies: from AIDS to NHANES[END_REF]. We used data from studies spanning from 2000 to 2008, with 95 features and about 33% missing values. We selected the "diabete" feature as a class and randomly selected 1000 samples from both outcomes to evaluate the quality of the data correction on a classification task on this class. -COVID19: This dataset was publicly released with the paper [START_REF] Yan | An interpretable mortality prediction model for COVID-19 patients[END_REF], it contains medical information collected between in early 2020 on pregnant and breastfeeding women. We based our data preprocessing on the one realized in the original paper, we selected only the measurements from the last medical appointment for each patient. After preprocessing, we obtain a dataset composed of 361 patients with 76 features, with about 20% missing data.

We evaluate the quality of the data correction on a classification task on the survival outcome, 195 patients have survived and 166 are deceased. -Myocardial infarction complications: This medical dataset is available on the UCI machine learning repository, it was publicly released with the paper [START_REF] Golovenkin | Trajectories, bifurcations, and pseudo-time in large clinical datasets: applications to myocardial infarction and diabetes data[END_REF].

It is composed of 1700 patients with 107 features, with about 5% missing values. We evaluate the quality of the data correction on a classification task on the survival outcome, 1429 patients have survived and 271 are deceased.

Used Metrics

We evaluate the quality of the obtained correction on classification tasks. As can be seen from the previous section, the medical datasets we used are not all balanced, the Myocardial dataset is especially imbalanced. In such a context it is important to choose metrics that are not sensitive to imbalance. In a medical context where we aim to predict the outcome between sane and sick, it is extremely important not to classify sick patients as sane since it would be very detrimental for them not to get an appropriate medical response. In machine learning terms we are in cases where false positives on the negative class would be less detrimental than false negatives, therefore we should aim to minimize false negatives.

Appropriate metrics, in this case, are the AUC: Area Under the Receiver Operating Characteristic (ROC) Curve, and the balanced accuracy. The AUC corresponds to the area under the ROC curve obtained by plotting the true positive rate (recall) against the false positive rate (1-specificity). An AUC score of 1 would mean that the classifier gives true positives 100% of the time, whereas a value of 0.5 means that the classifier is no better than a random prediction. The balanced accuracy is defined as the average of recall obtained on each class, which is simply the average of the true positive rate between all the classes.

Experimental Protocol

Our experiments aim to compare our method to other state-of-the-art methods for both imputation and noise correction tasks. All our experiments are evaluated using the balanced accuracy and the AUC metrics. We repeated each experiment 10 times with 10 different stochastic seeds to set up the random state of nondeterministic methods. For each experiment we compare the performances of each method to ours using t-tests. We use the results from those statistical tests to determine if our method is significantly better, even, or significantly worse than each other method, based on a p-value set at 0.05.

We first evaluate our method on an imputation task on the three medical datasets previously described. Each of those datasets is missing part of its data, we compare the quality of the data imputation by training a decision tree on a classification task on each dataset after imputation.

The capacity of our method to impute missing values on incomplete and noisy data is assessed by introducing artificial noise in the datasets. Noise is artificially added to the data by randomly replacing attribute values with a random number at a certain rate, as described by Zhu et al. [START_REF] Zhu | Class Noise vs. Attribute Noise: A Quantitative Study[END_REF]. We compare the results at the following noise rates: 0/5/10/15/20/40/60%.

Finally, to assess the effectiveness of our method to both complete missing values while correcting erroneous values, we introduce artificial noise in the naturally incomplete datasets. We apply our method and compare its results to those obtained by a sequential execution (i.e. pipeline) of an imputation method followed by a noise correction method.

The results from our method are compared to those of other state-of-the-art imputation methods:

-MEAN, MEDIAN and KNN: We used the "SimpleImputer" and "KNNImputer" classes from the python library "scikit-learn" 7 . -MICE: Multivariate Imputation by Chained Equations has been introduced in 2011 in [START_REF] Buuren | mice: Multivariate Imputation by Chained Equations in R[END_REF]. This is a very popular method of imputation because it provides fast, robust, and good results in most cases. We used the implementation from the experimental "IterativeImputer" class from "scikit-learn". -GAIN: Generative Adversarial Imputation Nets, introduced recently in [START_REF] Yoon | GAIN: Missing Data Imputation using Generative Adversarial Nets[END_REF],

two models are trained in an adversarial manner to achieve good imputation. We used the implementation from the original authors 8 . -SINKHORN: An optimal transport based method for data imputation introduced in [START_REF] Muzellec | Missing Data Imputation using Optimal Transport[END_REF] We used the implementation from the original authors 9 . -SOFTIMPUTE: The SOFTIMPUTE algorithm has been proposed in 2010

[5], it iteratively imputes missing values using an SVD. We used the public re-implementation by Travis Brady of the Mazumder and Hastie's package 10 . -MISSFOREST: An iterative imputation method based on random forests introduced in 2012 in [START_REF] Stekhoven | MissForest-Non-Parametric Missing Value Imputation for Mixed-Type Data[END_REF]. We used the "MissForest" class from the python library "missingpy" 11 . -MIDA: Multiple Imputation Using Denoising Autoencoders has been recently proposed in [START_REF] Gondara | MIDA: Multiple Imputation Using Denoising Autoencoders[END_REF]. We implemented MIDA using the author description from the original paper and the code template supplied in this public gist 12 The following noise correction methods are used as comparison:

-SFIL: Standard Filtering, which we implemented such as described in [START_REF] Teng | Polishing Blemishes: Issues in Data Correction[END_REF].

-SPOL: Standard Polishing, which we also implemented such as described in [START_REF] Teng | Polishing Blemishes: Issues in Data Correction[END_REF]. -PFIL, PPOL: Improved versions of SFIL and SPOL where the noisy instances to filter or polish are identified using the noise detection method Panda [START_REF] Van Hulse | The Pairwise Attribute Noise Detection Algorithm[END_REF].

Results

In this subsection, we present and analyze the most important comparative results between our proposed method and state-of-the-art methods. The entire experimental results with statistical significance can be found in our code.

Imputation on Incomplete Medical Data With our first experiment, we show that our method can impute missing values in real-world medical datasets.

Table 1 shows the results on the three real-world medical datasets. We can see that our method obtains very competitive results on all datasets. We obtain significantly better results than other state-of-the-art methods in most cases for both metrics. The only cases in which our method performs significantly worse are against KNN and MICE on COVID data on the balanced accuracy metric. This shows that our method is able to impute missing values on incomplete real-world medical mixed-type tabular data with results as good as other stateof-the-art imputation methods and even better in most cases.

Imputation on Incomplete and Noisy Medical Data Our second experiment shows that our method can impute missing values in real-world medical datasets in a noisy context. We artificially add noise to the data at various rates: 0/5/10/15/20/40/60%, and evaluate each imputation method at each noise level. Figure 2 shows AUC results obtained on NHANES and MYOCARDIAL data at each noise rate against several imputation methods. In both cases, we note that our method globally obtains significantly better results than other methods. The performance of all methods drops when the noise level increases, which is expected. On NHANES data our method performs largely better than others until a noise rate of 60% where the MEDIAN imputation gets similar results to ours. This can probably be explained by the fact that with a noise level that high Table 1. Comparative study between our method and other methods. BalACC corresponds to the balanced accuracy, AUC is the area under the ROC curve. Our method is compared to each other using t-tests with a p-value of 0.05, when our method is significantly better it is indicated by •, even by ≡, and significantly worse by •. it is nearly impossible to impute coherent values other than the median or mean value for each feature. We can observe the same pattern on MYOCARDIAL data, with the difference that GAIN seems to have learned how to adapt to such an amount of noise in this case. Those results show that on low to high noise rates, our method can impute missing values while correcting erroneous values.

Model

It provides better data correction than most other methods. At extreme noise rates naive methods might provide better results.

Comparison with the Combination of Imputation and Noise Correction Methods The last experiment compares our method results to those obtained from the combination of an imputation method followed by a noise correction method. We chose MICE as the state-of-the-art imputation method since it obtains competitive results against ours in a not noisy context. We then apply the four noise correction methods SFIL, PFIL, SPOL, and PPOL. Figure 3 show AUC results obtained on COVID and MYOCARDIAL data at each noise rate. We note that SFIL and SPOL perform worse than the Panda alternative of both those methods at all noise rates. We also note that for both datasets the other state-of-the-art noise correction methods give very poor results as soon as the noise level reaches more than 5%, at higher noise rates the data quality is better before noise correction than before. For COVID data all methods yield similar results at low noise levels, with our method on top with a very slight advantage. At high rates, however, our method gives very significantly better results than all other methods. For MYOCARDIAL data the opposite pattern can be observed, our method gives significantly better results up until a noise rate of 40%, after which MICE imputation is slightly better. This experiment completes the conclusions drawn from the second experiment, our method provides very good data correction, up until the noise rate becomes too extreme, at that point, simpler methods achieve slightly better results. The fact that the opposite is observed on COVID data is probably due to a remarkable original data quality, which would explain why our method becomes significantly better only at higher noise levels.

Conclusion

Handling attribute noise means imputing missing values while correcting erroneous values and outliers. This phenomenon is of critical importance in medical data, where attribute noise is especially present and detrimental to analysis and learning tasks on the data. No method in the literature is capable of handling attribute noise in its entirety in mixed-type tabular data. Many methods exist to impute missing values while other methods can correct erroneous values.

In this paper, we propose an autoencoder-based preprocessing approach to truly handle attribute noise. Our method imputes missing values while correcting erroneous values without requiring any complete or clean instance in the dataset to correct. Our experiments show that our method competes against and even outperforms other imputation methods on real-world medical mixed-type tabular data. Our method is less sensitive to noise on an imputation task.

Finally, as autoencoder approaches are amenable to an empirical tuning phase, we plan to implement in the future an algorithm able to automatically define an adapted architecture depending on the dataset dimensions.

Fig. 1 .

 1 Fig.1. The model parameters are trained so that the model learns to reconstruct the original data. The training must be stopped at the right moment for the reconstruction X to be cleaner than the original data X.

Fig. 2 .

 2 Fig. 2. AUC results on imputation on incomplete and noisy medical data

Fig. 3 .

 3 Fig. 3. AUC results on combination of imputation and noise correction

https://github.com/ThomasRanvier/Autoencoder-based Attribute Noise Handling Method for Medical Data

Acknowledgments

This research is supported by the European Union's Horizon 2020 research and innovation program under grant agreement No 875171, project QUALI-TOP (Monitoring multidimensional aspects of QUAlity of Life after cancer Im-munoTherapy -an Open smart digital Platform for personalized prevention and patient management).


Augustin Chaintreau

Guillaume Ducoffe

Dorian Mazauric

Non-existence of stable social groups in information-driven networks

We study a group-formation game on an undirected complete graph G with all edge-weights in a set W ⊆ R ∪ {-∞}. This work is motivated by a recent information-sharing model for social networks (Kleinberg and Ligett, GEB, 2013). Specifically, we consider partitions of the vertex-set of G into groups. The individual utility of any vertex v is the sum of the weights on the edges uv between v and the other vertices u in her group. -Informally, u and v represent social users, and the weight of uv quantifies the extent to which u and v (dis)agree on some fixed topic. -For a fixed integer k ≥ 1, a k-stable partition is a partition in which no coalition of at most k vertices would increase their respective utilities by leaving their groups to join or create another common group. Before our work, it was known that such a partition always exists if k = 1 (Burani and Zwicker, Math. Soc. Sci., 2003). We focus on the regime k ≥ 2.

• Our first result is that when all the social users are either friends, enemies or indifferent to each other (i.e., W = {-∞, 0, 1}), a partition as above always exists if k ≤ 2, but it may not exist if k ≥ 3. This is in sharp contrast with (Kleinberg and Ligett, GEB, 2013) who proved that k-stable partitions always exist, for any k, if W = {-∞, 1}.

• We further study the intriguing relationship between the existence of k-stable partitions and the allowed set of edge-weights W. Specifically, we give sufficient conditions for the existence or the non existence of such partitions based on tools from Graph Theory. Doing so, we obtain for most sets W the largest k(W) such that all graphs with edge-weights in W admit a k(W)-stable partition.

• From the computational point of view, we prove that for any W containing -∞, the problem of deciding whether a k-stable partition exists is NP-complete for any k > k(W).

Our work hints that the emergence of stable communities in a social network requires a trade-off between the level of collusion between social users, and the diversity of their opinions.

Introduction

In the line of [START_REF] Kleinberg | Information-sharing in social networks[END_REF][START_REF] Bermond | How long does it take for all users in a social network to choose their communities[END_REF][START_REF] Ducoffe | The parallel complexity of coloring games[END_REF], we continue the study of a simplified model of group formation within Online Social Networks (OSNs). The combinatorics behind this model is surprisingly intricate, and, we think, interesting to study on its own. As a starter, let us sketch the motivations behind the original model of Kleinberg and Ligett, from [START_REF] Kleinberg | Information-sharing in social networks[END_REF]. Users' behaviour in OSNs is driven by two conflicting objectives, namely: sharing with the other users while enforcing privacy of their personal information. Information is commonly shared between users within a same social group, also known as a community. However, communities are dynamic. As a user leaves one community for another, she may reveal the information learnt from her previous community to the new one, which results in privacy leakage. The model from [START_REF] Kleinberg | Information-sharing in social networks[END_REF] helps for understanding how strategic users can best choose their community in this context. We study the existence of stable outcomes in this model.

Specifically, a generalized coloring game is played on an edge-weighted graph G = (V, E, w), with each vertex being an agent. Throughout this paper, the set of edge-weights is denoted by W (i.e., W = w(E)). We partition agents into groups. Then, the individual goal of each agent is to maximize the sum of the weights of the edges between herself and the other agents in her group. -Alternatively, we may see a partition as a graph coloring, and each group as a color class, hence the name of generalized "coloring game". -We refer to Figure 1 for an illustration (see also Section 2 for a formal definition of the game, and for any undefined terminology). Our main focus is on the existence, and the computation, of k-stable partitions for generalized coloring games. Roughly, these are partitions such that no k-subset of agents have an incentive to deviate from their current strategy, i.e., from leaving their respective groups to join another (possibly, new) one. See Figure 3 for an illustration. Note that 1-stable partitions are exactly the Nash equilibria of the game. On a social network point of view, stable partitions ensure that no small coalition of users have an incentive to leave their current community for another one, thus preventing information leakage from a community to another. Related work. Kleinberg and Ligett studied a uniform version of the game: where G must be a complete graph, and all edge-weights must be taken in W = {-∞, 1} (the latter representing enmity and friendship between two users, respectively) [START_REF] Kleinberg | Information-sharing in social networks[END_REF]. Amongst many results, they proved that a k-stable partition always exists, for any k, but that it is NP-hard to compute one if k is part of the input. In two follow-up papers [START_REF] Bermond | How long does it take for all users in a social network to choose their communities[END_REF][START_REF] Ducoffe | Propriétés métriques des grands graphes[END_REF], we further studied the complexity of computing k-stable partitions, for small values of k, using parallel algorithms or better-response dynamics. In particular, better-response dynamics do not converge in polynomial time for any fixed k ≥ 4 [START_REF] Bermond | How long does it take for all users in a social network to choose their communities[END_REF]. On the way, we uncovered an equivalence between the model of Kleinberg The generalized coloring games that we study are equivalent to the so called additively separable symmetric Hedonic games [START_REF] Flammini | Strategyproof mechanisms for additively separable hedonic games and fractional hedonic games[END_REF]. We note that there have been several subclasses of Hedonic games proposed in the literature as a solution concept for group formation dynamics [DBHS06, BZ03, Bal04, SD10, HJ17, FMZ17, OBI + 17]. Additively separable symmetric Hedonic games are quite appealing in this context, as they always admit a Nash equilibrium [START_REF] Burani | Coalition formation games with separable preferences[END_REF]. Equivalently with our terminology, every generalized coloring game admits a 1-stable partition. We focus in this paper on the existence of k-stable partitions, for k ≥ 2. The particular case k = 2 can be seen as a variation of the well-known concept of pairwise stability [START_REF] Jackson | A strategic model of social and economic networks[END_REF], while larger values of k correspond to larger subsets of people coordinating their actions.

Finally, as noted by Kleinberg and Ligett, their model is also distantly related to the well-known stable marriage problem [START_REF] Gale | College admissions and the stability of marriage[END_REF]. Recall that there always exists a solution for the stable marriage problem, which can be computed in polynomial time. In contrast, even for slight variations of this original problem (e.g., stable roommates), solutions may not always exist, and this is sometimes NP-complete to decide [START_REF] Mnich | Stable marriage with covering constraints-a complete computational trichotomy[END_REF][START_REF] Chen | Stable marriage with multi-modal preferences[END_REF][START_REF] Ronn | NP-complete stable matching problems[END_REF]. This brings us with two close questions, namely: can we find generalized coloring games for which no k-stable partition exists? and if so, what is the complexity to decide whether, given a generalized coloring game, there exists a k-stable partition? In what follows, we almost completely answer these two questions.

Our contributions. We give the first known relationships between the existence of k-stable partitions and the properties of G and its subgraphs. For instance, we prove that a k-stable partition always exists if k is less than the girth in the "friendship" subgraph G + that is induced by all edges with positive weights (Theorem 1). Doing so, we establish several positive and negative results on the existence of k-stable partitions:

• In Section 3, we study the case of a graph G with all edge-weights in W = {-∞, 0, 1}. We prove that, while a modest generalization of the uniform version of the game Kleinberg and Ligett studied in [START_REF] Kleinberg | Information-sharing in social networks[END_REF], the situation is quite different from the latter, as k-stable partitions may not always exist! Specifically, we prove on the positive side that a 2-stable partition always exists (Corollary 1). However, on the negative side, we found a surprising counter-example with only four null-weight edges for which no 3-stable partition can exist (Theorem 2). The latter result shows that the existence of neutral relationships between users can strongly impact the outcome of the game1 . It also makes of pairwise stability (a.k.a., 2-stable partition) the best stability result that one can hope for.

• Our counter-example for k = 3 and W = {-∞, 0, 1} is derived from a larger class of very symmetric instances, all of which do not admit a k-stable partition for some small value of k (typically, k = 2). We use this larger class of counter-examples in order to obtain, for almost any possible edge-weight set W, the largest value k(W) such that any graph G with edge-weights in W admits a k(W)-stable partition (Table 1). We see our result as evidence of the tension between the collusion level between users (parameter k) and the diversity of their opinions (edge-weight set W) in the existence of stable outcomes.

• We end up studying in Section 4.2 the complexity of the recognition of generalized coloring games with a k-stable partition. Our main result in this part is an amusing dichotomy result that we obtain for every edge-weight set W ⊃ {-∞}. Specifically, for the graphs G with all edge-weights in W, the problem of deciding whether G has a k-stable partition is: trivial if k ≤ k(W), and NP-complete if k > k(W). We stress that any known G 0 with no k-stable partition can be used as a black-box in our hardness reduction. Therefore, the mere existence of any single counter-example to k-stability is sufficient in order to make the problem intractable.

Definitions

Preliminaries. The following notations and terminology are from [START_REF] Ducoffe | Propriétés métriques des grands graphes[END_REF]. For standard terminology of Game Theory, see [START_REF] Osborne | A course in game theory[END_REF][START_REF] Myerson | Game theory[END_REF]. For standard terminology of Graph Theory, see [START_REF] Bondy | Graph theory[END_REF].

Let G = (V, E, w) be an edge-weighted graph with w : E → R ∪ {-∞} be its weight function. Here, the symbol -∞ represents an arbitrarily small quantity which stays unaffected when added to any other quantity. Up to replacing the nonedges by null-weight edges, for the remainder of the paper, we assume the graph G to be a clique. In particular, we may omit the edge-set E and write G = (V, w). Let W = def w(E) be the set of all edge-weights.

Partitions and Utilities.

A coloring c : V → {1, 2, . . . , |V |} of G is a partition of its vertex-set with each class (or group) being assigned a distinct integer. For every vertex v ∈ V we denote by c(v) the integer corresponding to her group, also known as her color. Then, in the generalized coloring game that is played on G, the vertices of G are the agents of the game, and the strategy of an agent is her color. The group of all the vertices of color i is denoted by

X (c) i , or X i if c is clear from the context. For every v ∈ V , the utility of v is defined as f c (v) = u∈X c(v)
w uv (by convention, we assume that w vv = 0). Every agent aims at maximizing her utility function. We define the global utility of a coloring as

U (c) = v∈V f c (v).
Deviations, Stability. We call a subset S ⊆ V , with |S| ≤ k, a k-deviation w.r.t. c, if it satisfies the following property: there exists some color i ∈ N so that, for every v ∈ S, we have c(v) ̸ = i and:

f c (v) < u∈X i ∪S w uv .
We call a coloring c a k-stable partition if there is no k-deviation w.r.t. c. In particular, note that k-stability implies j-stability for every j ∈ {1, 2, . . . , k}. We further have an equivalence between |V |-stability and k-stability for every k ≥ |V |. The following better-response dynamics (see also Algorithm 1) are a classical approach in order to compute stable partitions. Specifically, we start from a trivial configuration where each agent has a different color. Then, as long as there exists a k-deviation, we pick any existing k-deviation S and we assign a same color i to all the agents in S so that they increase their respective utilities. Let us point out that i can be either a new color (we make of S a new group) or a color already assigned to some other agents not in S (i.e., we add the agents in S to an existing group). Furthermore, if this above dynamics converges then it stops on a k-stable partition.

Better-Response Dynamics (Algorithm 1)

Input: a positive integer k ≥ 1, and a graph G = (V, w).

1: Let c 0 be s.t. all the vertices of V have a different color. 2: Set i = 0. 3: while there exists a k-deviation w.r.t. c i do

4:

Choose one k-deviation S and let j be s.

t. ∀v ∈ S, f c i (v) < u∈X (c i ) j ∪S w uv .

5:

Define c i+1 as the coloring s.t.:

c i+1 (v) = j if v ∈ S c i (v) otherwise.

6:

Set i = i + 1.

Friendship and conflict graphs. For any set of weights W ′ , the subgraph G⟨W ′ ⟩ is the one induced by all the edges of G whose weight is in W ′ . In particular:

• The set W + contains all positive weights, and it induces the friendship graph G + := G⟨W + ⟩.

• Similarly, the set W -contains all negative weights, and it induces the conflict graph G -:= G⟨W -⟩. In particular, if W -= {-∞} (that was the case in [START_REF] Kleinberg | Information-sharing in social networks[END_REF]), then any stable partition must be a proper coloring of G -.

As an example, in Figure 1, the friendship graph is a disjoint union of two triangles 2K 3 , and the conflict graph is a complete bipartite graph K 3,3 . 3 Games with a unique positive weight

Positive results

We relate some structural properties of the underlying graph G with the existence of stable partitions.

In particular, we relate the existence of stable partitions with the girth (size of a smallest cycle) in the friendship graph. Throughout the paper, the notation -N stands for the set of negative integers.

Theorem 1. Let G = (V, w) has all its edge-weights in {-∞, 0, 1} ∪ -N. If G + has girth at least k + 1, then there exists a k-stable partition for the generalized coloring game that is played on G. Furthermore, better-response dynamics converge in O(|V | 2 ) steps to a k-stable partition.

Before proving Theorem 1, we need to introduce a (very generic) potential function argument:

Lemma 1. Let c be a coloring of G = (V, w), let S be a k-deviation w.r.t. c, and let i be a color such that, for every v ∈ S, we have

f c (v) < u∈X i ∪S w uv . If c ′ is the coloring obtained from c by
assigning color i to all the vertices in S, then we have:

U (c ′ ) -U (c) ≥ 2 •   |S| - v,v ′ ∈S w vv ′ + v,v ′ ∈S|c(v)=c(v ′ ) w vv ′   .
Proof. By the hypothesis, the utility of each vertex in S increases by at least 1. So, we get as the variation of the utility for the whole k-set:

v∈S [ f c ′ (v) -f c (v) ] ≥ |S|. For every v ∈ S, we then define δ v = u / ∈S|c(u)=c(v) w uv and σ v = u∈S|c(u)=c(v) w uv . We define δ ′ v = u / ∈S|c(u)=i w uv and σ ′ v = u∈S w uv in a similar fashion. Then, f c (v) = δ v + σ v , while f c ′ (v) = δ ′ v + σ ′ v .
So, we get by summation that:

v∈S f c (v) = v∈S δ v + 2 • v,v ′ ∈S|c(v)=c(v ′ ) w vv ′ , v∈S f c ′ (v) = v∈S δ ′ v + 2 • v,v ′ ∈S w vv ′ .
Note that for any v, v ′ ∈ S, we count w vv ′ twice: once for v, and another time for v ′ . Furthermore, the variation of the global utility includes that of the nodes of S, that of the nodes of

X (c) i , plus that of the nodes in X (c) c(v) , ∀v ∈ S.
In other words, we get by symmetry that:

U (c ′ ) -U (c) = v∈S [ f c ′ (v) -f c (v) ] + v∈S [ δ ′ v -δ v ] = 2 • v∈S [ f c ′ (v) -f c (v) ] + 2 • v,v ′ ∈S|c(v)=c(v ′ ) w vv ′ -2 • v,v ′ ∈S w vv ′ ≥ 2|S| + 2 • v,v ′ ∈S|c(v)=c(v ′ ) w vv ′ -2 • v,v ′ ∈S w vv ′ .
We are now ready to prove the main result of this subsection:

U (c ′ ) -U (c) ≥ 2 •   |S| - v,v ′ ∈S|c(v)̸ =c(v ′ ) w vv ′   ≥ 2 • (|S| -e).
Furthermore, since the girth of G + is at least k + 1, S induces a forest in G + , and so, e ≤ |S| -1. Hence, U (c ′ ) -U (c) ≥ 2, and as a result the global utility increases at each step of the dynamics. The latter concludes the proof, because the global utility is upper bounded by an O(|V | 2 ).

In particular, since any friendship graph has girth at least three, we obtain the following corollary:

Corollary 1. Let G = (V, w) has all its edge-weights in {-∞, 0, 1} ∪ -N.
Then, there exists a 2-stable partition for the generalized coloring game that is played on G. Furthermore, better-response dynamics converge in O(|V | 2 ) steps to a 2-stable partition.

We remark that Theorem 1 (and so, Corollary 1) still holds true if one replaces 1 by any positive integer a. However, it is unclear to us whether Theorem 1 still holds true if one replaces -N by the larger set of all negative real numbers. Indeed, it is no more true that each vertex in a k-deviation increases her utility by at least 1 (we only have that each such vertex increases her utility by a positive real value, that can be made arbitrarily small by including some suitable subset of negative real edge-weights).

A counter-example for k = 3

As we prove next, the result of Corollary 1 cannot be improved, already for W = {-∞, 0, 1}.

Theorem 2. There is a graph G = (V, w) whose edge-weights are in W = {-∞, 0, 1} and such that there does not exist a 3-stable partition for the generalized coloring game that is played on G.

The proof of Theorem 2 relies on another structural result which we state as follows. Given an edge-weighted graph G = (V, w), we say that u and u ′ are quasi-twins if w uu ′ > 0 and for all nodes v ∈ V \ {u, u ′ }, w uv = w u ′ v except maybe for one v 0 for which

|w uv 0 -w u ′ v 0 | ≤ w uu ′ .
Lemma 2. Let G = (V, w) be a graph, and let c be a 1-stable partition. Then, for all quasi-twin vertices u, u ′ in G, we have c(u) = c(u ′ ).

Proof. Without loss of generality we have that for all vertices

v ∈ V \ {u, u ′ }, w uv ≥ w u ′ v . In particular, either w uv = w u ′ v for all v ∈ V \ {u, u ′ }, or there is a unique v 0 such that 0 < w uv 0 -w u ′ v 0 ≤ w uu ′ and w uv = w u ′ v for all v ∈ V \ {u, u ′ , v 0 }. Suppose by contradiction c(u) ̸ = c(u ′ ).
There are two cases to be considered.

• Case f c (u) > f c (u ′ ). If u ′ changes her color for c(u), then we get a new coloring c ′ such that f c ′ (u ′ ) ≥ (f c (u) -w uu ′ ) + w uu ′ =f c (u) > f c (u ′ ). • Case f c (u) ≤ f c (u ′ ). If u changes her color for c(u ′ ), then we get a new coloring c ′ such that f c ′ (u) ≥ f c (u ′ ) + w uu ′ > f c (u ′ ) ≥ f c (u).
In both cases, there is a 1-deviation, that is contradiction, hence c(u) = c(u ′ ).

Proof of Theorem 2. The set of vertices consists of four sets A i , 0 ≤ i ≤ 3, each of equal size h ≥ 2 and each with a special vertex a i , plus four vertices b i , 0 ≤ i ≤ 3, and two vertices c 0 and c 1 . In what follows, indices are taken modulo 2 for c j , j ∈ {0, 1}, and they are taken modulo 4 everywhere else. Figure 2 represents the example with h = 3. The friendship graph G + here consists of all the edges with weight 1; it contains:

1. all the edges between nodes in A i (0 ≤ i ≤ 3);

edges between b i and A

i (0 ≤ i ≤ 3); 3. edges between b i and A i+1 \ {a i+1 } (0 ≤ i ≤ 3); 4. edges between b i and b i-1 and b i+1 (0 ≤ i ≤ 3);
5. edges between c 0 and all the b i , and edges between c 1 and all the b i ;

6. edges between c 0 and A 0 ∪ A 2 , and edges between c 1 and A 1 ∪ A 3 .

Moreover, there are four edges with weight 0, namely the edges {b i , a i+1 }. All the other pairs of agents represent "enemies" (they are pairwise connected by an edge with negative weight -∞).

That is two nodes in different A i , A i ′ are enemies; a user b i is enemy of b i+2 and of the nodes in A i+2 and A i+3 ; c 0 and c 1 are enemies; c 0 is enemy of the nodes in A 1 and A 3 , and c 1 is enemy of the nodes in A 0 and A 2 . We now assume by contradiction there exists a 3-stable partition c for the generalized coloring game which is played on G = (V, w).

A 1 Proof. Since the vertices of A i are pairwise quasi-twins, this is a direct corollary of Lemma 2.

A 2 A 3 A 0 a 0 a 1 a 2 a 3 b 0 b 1 b 2 b 3 c 0 c 1

Claim 2. b i picks the same color as the agents in A i or the agents in

A i+1 .
Proof. Suppose that it is not the case. Then X c(b i ) contains at most two other nodes: one of b i-1 and b i+1 (together enemies), and one of c 0 and c 1 (enemies). In particular,

|X c(b i ) | ≤ 3. If |X c(b i ) | ≤ 2
or the group X j containing A i has size at least 3, then b i can increase her utility by choosing color j. Therefore, since c is 1-stable, we assume from now on |X c(b i ) | = 3, h = 2 and A i = X j . There are two cases.

• If c(b i ) = c(c i ) then, S = {b i , c i } is a 2-deviation.
Indeed, both vertices can increase their respective utilities by choosing color j.

• Else, c(b i ) = c(c i-1 ). Recall that X c(b i ) ∩ {b i-1 , b i+1 } ̸ = ∅. In particular, if b i-1 ∈ X c(b i ) , then S = {c i-1 , b i-1 } is a 2-deviation.
Indeed, all the vertices of S can increase their respective utilities by choosing the same color j ′ as all the vertices of A

i-1 . Similarly, if b i+1 ∈ X c(b i ) , then S = {c i-1 , b i+1 } is a 2-deviation.
Indeed, all the vertices of S can increase their respective utilities by choosing the same color j ′ as all the vertices of A i+1 .

In both cases, we derive a contradiction, because c is 2-stable. Claim 3. There is an i such that agents in A i , b i and b i-1 pick the same color.

Proof. We show the claim by contradiction. For that, we distinguish two cases:

• Case 1: b i-1 is with A i , but not b i . So, as the claim is supposed to be false, b i is with A i+1 , b i+1 is with A i+2 , and b i+2 is with A i+3 . If c(b i-1 ) = c(c i )
, then b i would increase her utility by choosing color c(b i-1 ). Else, c(b i-1 ) ̸ = c(c i ), but then S = {b i , c i } is a 2-deviation. Indeed, both vertices can increase their respective utilities by choosing color c(b i-1 ).

• Case 2: b i is with A i , but not b i-1 . So, as the claim is supposed to be false, b i-1 is with In both cases, we derive a contradiction, because c is 2-stable.

A i-1 , b i+1 is with A i+1 ,
Let i be s.t. the agents in A i , i , b i-1 , c i all pick the same color. Such an i exists by Claim 3, and it is necessarily unique. By symmetry, we assume i = 0, and we now consider the group X c(a 0 ) = {b 0 , b 3 , c 0 } ∪ A 0 . There are several cases to distinguish.

• Case 1: c(a 2 ) = c(b 1 ) = c(b 2 ). In particular, by Claims 1 and 2, X c(a 2 ) = A 2 ∪ {b 1 , b 2 }.
Then, there are two subcases. Suppose that c(a 1 ) = c(c 1 ), in which case we have X c(c 1 ) = A 1 ∪{c 1 }. In this situation, the agent b 1 would increase her utility from 1+(|A 2 |-1) = |A 2 | = h to 1+|A 1 | = h+1 by choosing the same color as a 1 and c 1 . So, there is a 1-deviation. Otherwise, c(a 1 ) ̸ = c(c 1 ), and so, X c(a 1 ) = A 1 , while X c(c 1 ) is equal to either {c 1 } or A 3 ∪ {c 1 }. But then, the agents b 1 and c 1 would increase their respective utilities from 1 + (|A 2 | -1) = |A 2 | = h and ≤ |A 3 | = h to 1 + |A 1 | = h + 1, by choosing the same color as a 1 . So, there is a 2-deviation.

• Case 2: c(a 2 ) = c(b 2 ) ̸ = c(b 1 ). In particular, by Claims 1 and 2, X c(a 2 ) = A 2 ∪ {b 2 }, and

X c(b 1 ) is equal to either A 1 ∪ {b 1 } or A 1 ∪ {b 1 , c 1 }.
Then, there are two subcases. Suppose that c(a 3 ) = c(c 1 ), in which case we have X c(c 1 ) = A 3 ∪ {c 1 }. Then, if b 2 and b 3 pick the color of a 3 , they would increase their respective utilities from

|A 2 | = h and 2+(|A 0 |-1) = 1+|A 0 | = h+1 to, respectively, 2+(|A 3 |-1) = |A 3 |+1 = h+1 and 2 + |A 3 | = h + 2. Otherwise, c(a 3 ) ̸ = c(c 1 ), in which case X c(c 1 ) is equal to either {c 1 } or A 1 ∪ {b 1 , c 1 }.
But then, if the three of b 2 , b 3 , c 1 pick the same color as a 3 , they would increase their respective utilities from

|A 2 | = h, 2+(|A 0 |-1) = 1+|A 0 | = h+1, and ≤ 1+|A 1 | = h+1 to, respectively, 2 + (|A 3 | -1) = 1 + |A 3 | = h + 1, 2 + |A 3 | = h + 2, and 2 + |A 3 | = h + 2. • Case 3: c(a 2 ) = c(b 1 ) ̸ = c(b 2 ). In particular, by Claim 2, X c(a 2 ) = A 2 ∪ {b 1 }, and X c(b 2 ) is equal to either A 3 ∪ {b 2 } or A 3 ∪ {b 2 , c 1 }. In that case, b 1 would increase her utility from |A 2 | -1 = h -1 to ≥|A 1 | = h
by choosing the color of a 1 . Therefore, there is a 1-deviation.

• Case 4: c(a 2 ) / ∈ {c(b 1 ), c(b 2 )}. In particular, c(a 2 ), c(b 1 ) and c(b 2 ) are pairwise different, and we have:

X c(a 2 ) = A 2 ; X c(b 1 ) is equal to either A 1 ∪ {b 1 } or A 1 ∪ {b 1 , c 1 }; X c(b 2 ) is equal to either A 3 ∪ {b 2 } or A 3 ∪ {b 2 , c 1 }. We observe that in this case, c(b 2 ) = c(a 3 ).
Then, there are two subcases. Suppose that c(c 1 ) = c(a 3 ). In this situation, we have X c(a 3 ) = A 3 ∪{b 2 , c 1 }. But then, the agent b 3 would increase her utility from 2+(|A 0 |-1) = h+1 to 2+|A 3 | = h+2 by choosing this color, so, there is a 1-deviation. Otherwise, c(c 1 ) ̸ = c(a 3 ), in which situation we have: X c(c 1 ) is equal to either {c 1 } or A 1 ∪ {b 1 , c 1 }; and X c(a 3 ) = A 3 ∪ {b 2 }. But then, both b 3 and c 1 would increase their respective utilities from ≤ h + 1 to h + 2 by choosing the color of a 3 . Finally, since in all cases there is a 3-deviation, there does not exist a 3-stable partition for the generalized coloring game that is played on G.

The general case

The threshold for stability

Let us define, for every fixed set W, k(W) to be the largest k such that, for every graph with edge-weights in W, there exists a k-stable partition. We prove sharp bounds on k(W) for almost all sets W (see Table 1). Note that the two first lines of Table 1 were only proved for a = 1. However, it follows from the definition of k-stability that scaling all edge-weights by some positive value a has no impact on the (non)existence of a k-stable partition. As for the third line of Table 1, see our brief discussion at the end of Sec. 3.1. The constructions of our counter-examples are presented next. Remarkably, our results show that, along with the trivial cases where all the weights are either non negative or non positive, the uniform version of the game Kleinberg and Ligett studied in [START_REF] Kleinberg | Information-sharing in social networks[END_REF] is the only set W s.t. we have k

(W) = ∞. W k(W) {-∞, a}, a > 0 ∞ [KL13] {-∞, 0, a}, a > 0 2 Theorem 2, Corollary 1 {-∞, 0, a} ∪ -N, a ∈ N \ {0} 2 Theorem 2, Corollary 1 {-∞, a, b}, b > a > 0 1 Lemma 3 {-a, b}, a > 0, b > 0 ≤ 2 • ⌈ a+1 b ⌉ + 1 Lemma 4 Table 1: Values of k(W) for different W.
Starters. Consider the graph G of Figure 3. There are three non negative weights, namely: All the other edges have weight -∞. Moreover, if w 1 < w 2 < w 3 and w 1 + w 2 > w 3 , then we claim that there does not exist a 2-stable partition. Indeed, the partition with groups {v 1 , v 2 , v 3 }, {u 1 }, {u 2 }, {u 3 } is 1-stable but not 2-stable. All the other 1-stable partitions for the generalized coloring game that is played on G are isomorphic to the one we drew in Figure 3. Therefore, none of them is 2-stable. Next, we generalize this construction.

• The edges v 1 v 2 , v 2 v 3 , v 3 v
Lemma 3. Let a, b be two positive integers such that a < b. There exists a graph G = (V, w) s.t. all the edge-weights are in W = {-∞, a, b}, and there does not exist a 2-stable partition. Proof. Users are partitioned into four sets

U 1 = {x 1 , x 2 , x 3 }, U 2 = {y 1 , y 2 , y 3 }, U 3 = {z 1 , z 2 , z 3 } and {v 1 , v 2 , v 3 }.
Each of these sets induces a triangle whose three edges are weighted b. In addition:

• each edge between a node in U i and another node in

U i ′ , i ̸ = i ′ has negative weight -∞.
• the edges between v 1 and U 2 are weighted b, whereas the edges between v 1 and U 1 have negative weight -∞. Similarly, the edges between v 2 and U 3 (resp., between v 3 and U 1 ) are weighted b, whereas the edges between v 2 and U 2 (resp., between v 3 and U 3 ) have negative weight -∞.

• Finally, we set:

• w v 1 z 1 = w v 1 z 2 = b, w v 1 z 3 = a; • w v 2 x 1 = w v 2 x 2 = b, w v 2 x 3 = a; • w v 3 y 1 = w v 3 y 2 = b, w v 3 y 3 = a.
Let us assume by contradiction that there exists a 2-stable partition c.

Claim 4. For any 1 ≤ i ≤ 3, the nodes in U i pick the same color.

Proof. By symmetry, it suffices to show the claim for U 1 . First, since the nodes x 1 , x 2 are quasi-twins, they pick the same color by Lemma 2. Furthermore, by construction all the edges between a node of X c(x 1 ) and x 3 have a positive weight (i.e., because the nodes of U 1 are twins in the conflict graph G -). Suppose for the sake of contradiction x 3 / ∈ X c(x 1 ) . Then, the utility of x 3 is at most w v 2 x 3 + w v 1 x 3 = a + b < 2b. However, this implies that by choosing color c(x 1 ), the node x 3 would increase her utility to at least 2b. By replacing each subset U i by a single node u i , we get the counter-example of Figure 3 for the choices of weights w 1 = b, w 2 = 2b + a and w 3 = 3b. In particular, by Claim 4, we may associate to any 1-stable partition c of G a partition c ′ of the graph of Figure 3. Suppose by contradiction that c ′ is not 1-stable. We can check that there always exists a 1-deviation whose node is taken from {v 1 , v 2 , v 3 }. Therefore, c is not a 1-stable partition of G, that is a contradiction. From now on, we assume that c ′ is 1-stable. However, in any 1-stable partition c ′ , there exists a 2-deviation which only contains nodes amongst {v 1 , v 2 , v 3 }. In particular, this is also a 2-deviation w.r.t. c. Lemma 4. Let a, b be positive integers (not necessarily distinct). There exists a graph G = (V, w) s.t. all the edge-weights are in W = {-a, b}, and there does not exist a 2 • 1 + ⌈ a+1 b ⌉ -stable partition.

Proof. Let x, y be non negative integers such that bx -ay = gcd{a, b}

= d. The vertex-set is partitioned in nine subsets V 1 , V 2 , V 3 , U + 1 , U + 2 , U + 3 , U - 1 , U - 2 , U - 3 plus three vertices u = 1 , u = 2 , u = 3 .
In particular, there exist large enough constants k 1 , k 2 , k 3 s.t.:

• The subsets V i have respective size 1 + ⌈ a+1 b ⌉; • The subsets U + i have respective size 1+b•(1+⌈ a+1 b ⌉) d • x + k i • a. • The subsets U - i have respective size 1+b•(1+⌈ a+1 b ⌉) d • y + k i • b -1.
The edge-set is as follows:

• V 1 ∪ V 2 ∪ V 3 induces a clique in the friendship graph G + (i.
e., all the edges between these vertices are weighted b).

• The subsets

U i = U + i ∪ U - i ∪ {u = i } induce cliques in the friendship graph G + .
• For every i ̸ = j, the edges between V i and U + j have weight b (i.e., they induce a complete bipartite subgraph in G + ).

• Finally, all the edges between u = 1 and V 3 have weight b, and in the same way all the edges between u = 2 and V 1 (resp., between u = 3 and V 2 ) have weight b.

Every remaining edge has weight -a.

Suppose by contradiction that there exists a 2 1

+ ⌈ a+1 b ⌉ -stable partition c. By construction, V 1 , V 2 , V 3 , U + 1 , U + 2 , U + 3 , U - 1 , U - 2 , U - 3 are quasi-twin sets.
In particular, by Lemma 2, all the nodes in any one of these sets pick the same color. For simplicity, let us write p = 1 + a+1 b , and

q = 1+b•p d . W.l.o.g., let us assume k 1 ≤ k 2 ≤ k 3 . If a vertex v ∈ V 3
picks the same color as those nodes in U + 3 , then her maximum utility would be:

f c (v) = b • |V 1 | + |V 2 | + (|V 3 | -1) + |U + 1 | + |U + 2 | + 1 -a • |U + 3 | = b • [3p + 2qx + (k 1 + k 2 ) • a] -a • (qx + k 3 • a)
that is negative for large enough k 3 (with respect to k 1 , k 2 ). Therefore, the vertices of V 3 pick a different color than those in U + 3 (otherwise, the partition is not 1-stable). Similarly, if a vertex u ∈ U 1 ∪ U 2 picks the same color as those nodes in U + 3 , then her maximum utility would be:

f c (v) = b • [|V 1 | + |V 2 | + |U 2 | -1] -a • |U + 3 | = b • [2p + qx + k 2 • a -1] -a • (qx + k 3 • a) < 0.
As a result, the vertices of U 1 ∪ U 2 pick different colors than those of U + 3 . We can prove in the exact same way that the vertices of

V 3 ∪ U 1 ∪ U 2 pick different colors than those of U - 3 . Then, the group of U + 3 , resp. of U - 3 , is a subset of U 3 ∪ V 1 ∪ V 2 . In particular, since |U + 3 |, |U - 3 | ≫ |V 1 | + |V 2 | = 2p
, we obtain that all the vertices of U 3 must pick the same color (otherwise, there would exist 1-deviations).

By similar arguments as above, we may choose k 1 , k 2 large enough so that all the vertices of U 2 (resp., of U 1 ) pick the same color. Moreover, the vertices of V i pick a different color than those of U i , and for any i ̸ = j the vertices of U j pick a different color than those of U i . Let us replace the subsets V i , U i by fresh new vertices v i , u i . Doing so, we get an isomorphic copy of the counter-example of Figure 3. In order to fix the weights w 1 , w 2 , w 3 , we fix a subset V j , and then we consider the contribution of any other subset to the utility of the nodes of V j . We obtain that:

• w 1 = b • |V i | = b • p = b • 1 + a+1 b ≥ b + a + 1; • w 2 = b • |U + i | -a • |U - i ∪ {u = i }| = bqx + bk i a -aqy -ak i b = (bx -ay)q = d • q ≥ 1 + b • p; • w 3 = b • |U + i ∪ {u = i }| -a • |U - i | = bqx + bk i a + b -aqy -ak i b + a = d • q + (b + a).
In particular, w 1 < w 2 < w 3 < w 1 + w 2 . This implies that we can map c to a 1-stable partition c ′ of the graph of Figure 3. For the latter, there exists a 2-deviation whose nodes are taken amongst v 1 , v 2 , v 3 . In turn, there exists a 2p-deviation w.r.t. c, that is a contradiction.

Hardness results

Surprisingly, under the additional assumption -∞ ∈ W, the threshold k(W) fully characterizes the complexity of recognizing generalized coloring games with a k-stable partition. Specifically, we prove the following dichotomy result:

Theorem 3. Let W contain -∞, and let k ≥ 1 be fixed. Then, the problem of deciding whether a given generalized coloring game, played on a graph with edge-weights in W, admits a k-stable partition is either:

• trivial if k ≤ k(W); • or NP-complete if k > k(W).
Under the assumption -∞ ∈ W, our results from Sections 3.2 and 4.1 show that in most cases k(W) ≤ 2. Then, we observe that whenever k ≤ k(W), we can also compute a k-stable partition in polynomial time, e.g., by using better-response dynamics. This approach does not work anymore for the uniform case [START_REF] Kleinberg | Information-sharing in social networks[END_REF], thereby reinforcing the specificity of the latter compared to the other possible sets of weights.

The remaining of this subsection is devoted to the proof of Theorem 3. The problem is clearly in NP because, for any fixed k, we can decide whether a k-deviation exists in polynomial-time n O(k) . Informally, in order to prove the NP-hardness we will assume the existence of a counter-example, and we will build a supergraph of it that is arbitrarily large. We will characterize the k-stable partitions for the generalized coloring game that is played on this supergraph. In particular, we will prove that a necessary and sufficient condition for having a k-stable partition is that one user from the counter-example picks the same color as a large independent set from the supergraph. By doing so, we will be able to reduce the well-known Maximum Independent Set to our problem.

Intermediate reductions.

For technical reasons, we need a constant lower bound on the utility of a user. Intuitively, we use this lower bound in order to ensure that if there exists a k-stable partition, then there is some user from the counter-example that picks the same color as a large independent set from the supergraph. In what follows, we introduce two reductions for enforcing this constant lower bound.

Reduction 1. Let t be a positive integer, and let W be a finite set such that W + ̸ = ∅. We set w p = max W. For a given graph G = (V, w) whose weight in W, and n ′ ≥ |V |, we construct a new graph G t,n ′ as follows:

• We create n ′ distinct copies of the complete graph K t , whose edges are all weighted w p .

• Then, we add an edge of weight -∞ between any two nodes in two distinct copies of K t .

• Finally, we add an edge of weight w p between any node in V and any node belonging to some copy of K t .

Intuitively, Reduction 1 increases the minimum utility of the nodes to w p t.

Reduction 2. Let α be a positive integer, and let W be a finite set such that W + ̸ = ∅. We set w p = max W. For a given graph G = (V, w) whose weight in W, we construct KG α as follows:

• We replace every node u ∈ V with a clique of α nodes K α (u) ⊆ V (KG α ).

• For every u i , u j ∈ K α (u), the edge u i u j has weight w p .

• For every u i ∈ K α (u) and v j ∈ K α (v), the edge u i v j has weight w uv .

Overall, our reductions ensure the following properties: Lemma 5. Let W be a finite set such that W + ̸ = ∅, and let G = (V, w) have all its edge-weights restricted to W. Then, for any n ′ ≥ |V | and t > |V |, there exists a k-stable partition for the game played on G if, and only if, there exists a k-stable partition for the game played on G t,n ′ . Proof. We remind that one obtains G t,n ′ from G by adding n ′ distinct copies of the complete graph K t , that we will denote by K 1 t , . . . , K n ′ t .

First, let c be a k-stable partition for the game played on G. W.l.o.g., the colors used in c are {1, 2, . . . , p}, for some p ≤ |V |. Let c ′ be the coloring G t,n ′ s.t.:

c ′ (v) = c(v) if v ∈ V c ′ (v) = j if v ∈ K j t .
We claim that c ′ is a k-stable partition for the game played on G t,n

k • w p ≤ (|V | -1) • w p < (t -1) • w p . Since ∀v ∈ K i t , f c ′ (v) ≥ (t -1)
• w p , this is impossible. Therefore, we must have S ′ = S ∩ V ̸ = ∅. However, this implies:

∀v ∈ S ′ , f c ′ (v) = f c (v) + w p • t < u∈X (c ′ ) j ∪S w uv ≤     u∈(X (c ′ ) j ∩V )∪S ′ w uv     + w p • t.
In particular, S ′ is a k-deviation w.r.t. c. Conversely, let c ′ be a k-stable partition for the game played on G t,n ′ . By Lemma 2, for any i, the nodes in K i t pick the same color. Furthermore, we claim that every node of V must pick the same color as some clique K i t . Indeed, suppose that it is not the case for u ∈ V . Since n ′ ≥ n, there exists an i such that no vertex of V picks the same color as K i t . In particular, K i t is a group of the partition. But then, f c (u) < v∈V w uv < w p • t, and so, there would exist a 1-deviation. Therefore, we proved as claimed that every node of V picks the same color as some clique K i t . Now, let c be such that, ∀v ∈ V, c(v) = c ′ (v). We claim that c is a k-stable partition for the coloring game played on G. Indeed, suppose by contradiction that there exists a k-subset S ⊆ V , and a color j such that:

∀v ∈ S, f c (v) < u∈X (c) j ∪S w uv .
Again, since n ′ ≥ n, we may assume w.l.o.g. that X

(c ′ ) j ̸ = ∅. Furthermore, ∀v ∈ S, f c ′ (v) = f c (v) + w p • t < u∈X (c) j ∪S w uv + w p • t = u∈X (c ′ ) j ∪S w uv . A contradiction.
We are now able to prove Theorem 3: Proof of Theorem 3. Let G 0 = (V 0 , w 0 ) be restricted to W and such that the game which is played on it does not admit a k-stable partition. W.l.o.g., there exists some x 0 ∈ V 0 whose removal makes the existence of a k-stable partition for the gotten subgraph. Indeed, otherwise, we remove nodes sequentially until obtaining this property. Moreover, we may substitute W by the subset of all the weights on the edges of G 0 , that is finite. Since there is no k-stable partition, we have W + ̸ = ∅. In what follows, let w p = max W. Let c 0 be a k-stable partition for the coloring game that is played on G 0 -x 0 . Let c ′ 0 be obtained from c 0 by adding a new group equal to the singleton {x 0 }. By the hypothesis, c ′ 0 is not k-stable.

Amongst all the k-deviations S w.r.t. c ′ 0 , and all the colors j s.

t. ∀v ∈ S, f c ′ 0 (v) < u∈X (c ′ 0 ) j ∪S w uv ,
we choose one such a pair (S, j) such that, in the new coloring obtained from c ′ 0 by assigning color j to all the nodes in S, the utility of x 0 is maximized. Denote by f 0 this maximum value of the utility function for x 0 . Up to replacing G 0 with (G 0 ) t ′ ,n ′ 0 for some large enough constants t ′ , n ′ 0 (that can be done w.l.o.g. by Lemma 5), we may assume f 0 > 0. We also define the two constants α = ⌈ f 0 wp ⌉ and β 0 = 2n 0 + 1, with n 0 = |V 0 |.

We can now prove the NP-hardness of our problem by using a polynomial reduction for Maximum Independent Set. Specifically, let G = (V, E) be an undirected unweighted graph, and let β ≥ β 0 be an integer. We define

D G = (V, w G ) such that ∀uv ∈ E, w uv = -∞ and ∀uv / ∈ E, w uv = w p (note that the conflict graph D - G is equal to G). Furthermore: let t = α • (β -1) + 1; let G 1 = (G 0 ) t,n 0 ; and let G 2 = K(D G ) α .
Here, it is important to observe that we have t > αβ -f 0 wp -1 ≥ αβ -n 0 -1 ≥ β -n 0 -1 ≥ n 0 , because f 0 ≤ n 0 w p . Finally, we build the graph H G from G 1 and G 2 as follows:

• For every edge between G 1 -x 0 and G 2 , we assign a negative weight -∞.

• For every edge between x 0 and G 2 , we assign a positive weight w p . This above transformation is illustrated in Figure 4. In what follows, we prove that there exists a k-stable partition for the game played on H G if and only if there exists a maximum independent set of size at least β in G. For that, let us first assume that every independent set of G has a size less than β. Suppose for the sake of contradiction that there exists a k-stable partition for the coloring game played on H G . By construction, no group can intersect both V (G 1 ) \ {x 0 } and V (G 2 ). In particular, the group of x 0 is either fully contained in G 1 , or in G 2 + x 0 . Furthermore, there can be no group with more than α • (β -1) vertices of V (G 2 ). But then, since α • (β -1) < t, the group of x 0 must be in V (G 1 ) (otherwise, we could increase the utility of x 0 from ≤ α • (β -1) • w p to, at least t • w p , by joining some group in V (G 1 )). As a result, we can bipartition the k-stable partition in, respectively, a k-stable partition for G 1 , and a k-stable partition for G 2 . By Lemma 5, the fact that there does not exist a k-stable partition for the game played on G 0 implies the same for the game played on G 1 . A contradiction. Therefore, there is no k-stable partition for H G .

Conversely, let us assume that there exists an independent set of G with size at least β. We observe that, up to replacing w p by 1 in G 2 +x 0 , we fall in the uniform version of the game studied by Kleinberg and Ligett in [START_REF] Kleinberg | Information-sharing in social networks[END_REF]. In particular, by [START_REF] Kleinberg | Information-sharing in social networks[END_REF], there exists a k-stable partition c ′ whose largest group X (c ′ ) j is a maximum independent set of the conflict graph G + x 0 . Then, c ′ (x 0 ) = j because it is an isolated vertex in G + x 0 . Also, recall that there exists a k-stable partition c 0 for G 0 -x 0 . Therefore, by Lemma 5, there exists a k-stable partition c 1 for G 1 -x 0 . Let c be s.t.:

c(v) = c ′ (v) if v ∈ V (G 2 ) ∪ {x 0 } c(v) = c 1 (v) if v ∈ V (G 1 ) \ {x 0 }.
We claim that c is a k-stable partition for the gamed played on H G . Indeed, suppose for the sake of contradiction that there exists a k-deviation S. By definition of c ′ , c 0 , we must have S ∩ (V (G 1 ) \ {x 0 }) ̸ = ∅, and in the same way S ∩ (V (G 2 ) ∪ {x 0 }) ̸ = ∅. This implies x 0 ∈ S ⊆ V (G 1 ). But then, let us choose a color j ′ s.t. ∀v ∈ S, f c (v) < u∈X (c ′ ) j ′ ∪S w uv . We must have X (c ′ ) j ′ ∪ S ⊆ V (G 1 ), and therefore, by assigning color j ′ to all the vertices in S the utility of x 0 becomes at most f 0 +w p •t. However, the former utility of x 0 was at least w p •α•β = w p •(t+α) ≥ w p •(t+ f 0 wp ) = w p •t+f 0 . In particular, the utility of x 0 has not increased, that is a contradiction because x 0 ∈ S. This concludes the NP-hardness proof, as our transformation is polynomial, and Maximum Independent Set is NP-complete [START_REF] Dailey | Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete[END_REF].

Conclusion

We have obtained several new results on the (non)existence of k-stable partitions, by identifying some relevant structural properties of the subgraphs induced by some subsets of weights, e.g.: girth, quasi-twin sets, and the (non)existence of some highly symmetric patterns. It would be interesting to study these problems in a different setting, where we allow any set of weights but we restrict ourselves to some well-structured class of graphs. Also, we would find it interesting to study whether our techniques could apply to the model of Angel et

  and Ligett and the earlier introduced coloring games [PS08, CKPS10, MW13, EGM12]. Angel et al. studied the sequential (non game-theoretic) complexity of a more general model where, informally speaking, there are different categories of information considered [ABK + 16]. We here propose a deeper study of the original model of Kleinberg and Ligett for arbitrary edge-weight sets W.

Figure 1 :

 1 Figure 1: A bicoloring of a graph G = (V, w). Agents that are represented by a circle (resp., by a square) have the same color. Red dashed edges have negative weight -∞, while green continuous edges are labeled with their (positive) weight. Furthermore, each agent is labeled with her (positive) utility with respect to this bicoloring.

Proof of Theorem 1 .

 1 Let us consider any one phase of the better-response dynamics. That is, we have a color c, a k-deviation S w.r.t. c, and a color i s.t. ∀v ∈ S, f c (v) < u∈X i ∪S w uv . Then, during this phase, we assign color i to all the vertices in S, and in doing so we get a new coloring c ′ . Let e = |E(G + [S])| be the number of edges in the friendship subgraph induced by S. Since the only positive weight is 1, we get by Lemma 1:

Figure 2 :

 2 Figure 2: A graph G = (V, w) with edge-weights in W = {-∞, 0, 1}. The coloring game played on G does not admit a 3-stable partition. To keep the graph readable, we use conventions. (1) Some sets of nodes are grouped within a circle; an edge from another node to that circle denotes an edge to all elements of this set. (2) Edges of the conflict graph are not represented. In particular, all nodes that are not connected by an edge on the figure are connected by an edge with negative weight -∞. (3) Green solid edges represent edges with weight 1, whereas blue dashed edges represent edges with weight 0.

  and b i+2 is with A i+2 . We observe that either c(c i ) = c(b i ) or c(c i ) = c(b i+2 ). W.l.o.g., suppose c(c i ) = c(b i+2 ). If c(b i+1 ) = c(c i+1 ),then b i would increase her utility by choosing color c(b i+1 ). Else, c(b i+1 ) ̸ = c(c i+1 ), but then S = {b i , c i+1 } is a 2-deviation. Indeed, both vertices would increase their respective utilities by choosing color c(b i+1 ).

••

  1 have the same weight w 1 (on the Figure, w 1 = 2); The edges v 1 u 3 , v 2 u 1 , v 3 u 2 have the same weight w 2 (on the Figure, w 2 = 3); The edges v 1 u 2 , v 2 u 3 , v 3 u 1 have the same weight w 3 (on the Figure, w 3 = 4).

Figure 3 :

 3 Figure3: A coloring game that does not admit a 2-stable partition: edges in green have the positive weight indicated, whereas the red edges have negative weight -∞. The partition on the right is not 2-stable. As an example, nodes v 1 and v 2 can decide to simultaneously move into the group containing u 3 , which effectively "rotates" the groups in the partition.

Figure 4 :

 4 Figure 4: The NP-hardness reduction of Theorem 3.

  ′ . By contradiction, let S be a k-deviation w.r.t. c ′ , and let a color j s.t., ∀v ∈ S, f c ′ (v) <

	u∈X j (c ′ )	∪S	w uv . If S ⊆ K i t then the only
	possibility for the vertices of S is to create a new group. However, that would result in their utility
	being

  al. [ABK + 16].

See also[OBI + 17], where similar results are proved for another Hedonic game (that is related to the one we study in this paper), but for a stronger notion of (core) stability.