Bouchra Amaury

Davide Pilet

François Frey

Taïani

Germinal

AUCCCR: Agent Utility

Keywords:

come   L'archive ouverte pluridisciplinaire

I Introduction

In this work, we aim to provide an algorithmic solution for people or organizations who wish to collaborate towards some task (buying, machine-learning...) but do not want to cooperate with members whose individual objectives are too different from their own. This problem can be modeled as a set of rational agents that may or may not form coalitions depending on the utility they might derive from such coalitions, a formalism based on economics and prescriptive decision theory [vM44]. While descriptive decision theory has shifter to the more exact Prospect theory [START_REF] Kahneman | Prospect Theory: An Analysis of Decision under Risk[END_REF], this work is about automated decision support and, thus, based on expected utility [Ran+07]. The utility an agent obtains from belonging to a group is positively correlated to the group's size (larger is better), but negatively correlated with its distance from the group's barycenter (closer is better). Such a model can capture various practical problems: in collaborative machine learning, for instance, learners with similar but different tasks may or may not collaborate with each other, depending on the effect of this collaboration on the efficiency of their learning process; in grouped purchases, potential buyers will search for other people with similar buying habits to save money by placing grouped orders, but will not benefit if the products bought deviates too much from their preferred options; when planing organized vacations, most people want to save money with group rates, but not at the cost of visiting too many places they are not interested in. We also consider the case where people want to be in large enough groups but not too large.

An algorithm that solves this problem should provide collaboration recommendations (e.g. with whom each agent should perform a grouped order) that agents find acceptable and from which they do not deviate. Since, in this context, the relative utility of different options for an agent depends on the choices of other agents, it is crucial to prevent situations where a few agents reject the recommendation, as this could lead to a complete collapse of the solution. The departure of a dissatisfied agent can decrease the group's value for other agents, which may in turn leave the group, etc.

In economic terms, this problem can be modeled as a hedonic game [START_REF] Drèze | Hedonic Coalitions: Optimality and Stability[END_REF], but this formalization tends unfortunately to be too general to allow for effective algorithmic solutions. Existing algorithms that solve generic hedonic games, summarized in [START_REF] Aziz | Hedonic Games[END_REF], need to constrain them by requiring the existence of some kind of equilibrium (Nash equilibrium or a similar definition), which is not guaranteed by the generic definition of hedonic games and may not exist in practice. In our work, we instead consider a more restricted class of games, and we provide a solution that also works in cases where no kind of equilibrium exists.

Hedonic games designed for specific problems have been proposed in the past, for example in [START_REF] Saad | Coalition Formation Games for Distributed Cooperation Among Roadside Units in Vehicular Networks[END_REF], but the practical problems they consider do not apply to our context. In particular, these works tend to adopt a formalization that ensures the existence of some kind of equilibrium, while we want solutions for cases where no equilibrium exists.

Our insight is that the hedonic games corresponding to our coalition-formation problem can be interpreted as a clustering problem. We want to identify groups of close and numerous agents, which is essentially a clustering task. However, commonly used clustering algorithms, while technically applicable, are not adapted to this particular task. To address this gap, this paper proposes a novel clustering algorithm, that is specifically designed to address the task we want to solve.

We begin this paper with a formal definition of the class of hedonic games we use to model collaboration. We then propose AUCCCR (pronounced "okr", IPA: [okʁ]), a clustering algorithm able to provide solutions to the considered problem. We present a theoretical and experimental evaluation of our algorithm on both synthetic and real data. From this evaluation, we conclude that our algorithm respects individual agents interests better than other clustering algorithms.

II Our approach II.1 Problem statement and formalization

We consider a set of agents 𝑎 0 , ..., 𝑎 𝑚 ∈ 𝐴 that seek to form groups so that every agent in a group effectively benefits from belonging to this group. We represent agents' preferences using an ℓ-dimensional real vector given by a projector function, 𝑝 ∶ 𝐴 → ℝ ℓ , which allows us to measure similarity between agents as a distance. In our model, the benefit from being in a group depends on two factors: the size of the group (the larger the better), and the similarity between an agent and the (average of) the group (the more similar the better).

More concretely, we define a utility function 𝑈 𝑝 (𝑎, 𝑔) that expresses the interest of an agent, 𝑎, in a group, 𝑔, using a projector, 𝑝, as the product of two factors: (i) the value of the group (function 𝑣), which grows with the group's size; and (ii) a decreasing function (𝑛(...)) of the distance between an agent and the group's barycenter (as measured by a distance function 𝑑(...)). This is formally captured by the following formula:

𝑈 𝑝 (𝑎, 𝑔) ∶ 𝐴 × 𝒫(𝐴) → ℝ + = 𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦 𝑝 (𝑔))) × 𝑣(#𝑔),
where 𝒫(𝐴) is the power set of 𝐴, #𝑔 is the size of group 𝑔, bary 𝑝 (𝑔) is the barycenter of group 𝑔 with projector 𝑝, and the functions 𝑑, 𝑣, and 𝑛 are defined as follows: 𝑑(𝑥, 𝑦) ∶ ℝ 𝑘 × ℝ 𝑘 → ℝ is the distance between 𝑥 and 𝑦; 𝑣(𝑛) ∶ ℕ → [1, +∞[ is the value of a group of size 𝑛 (increasing, 𝑣(1) = 1); and 𝑛(𝑑) ∶ ℝ + → [0, 1] is the normalizer for an agent at distance 𝑑 from its group's barycenter (decreasing, 𝑛(0) = 1). In the following we will also use 𝑔(𝑎) to denote the group of agent 𝑎. These definitions associate a utility value of 1 with an agent that remains alone (since the interest of joining a group with a barycenter at distance 0 and consisting of 1 element (itself) is 𝑛(0) × 𝑣(1) = 1 × 1).

Given 𝐴, 𝑝(), 𝑑(), 𝑛() and 𝑣(), the group formation problem we seek to solve consists in finding a partition of 𝐴 (representing the groups), that maximizes the sum of every agent's utility, while minimizing (or even eliminating) the benefit individual agents could gain by either changing group or

II.2 Algorithm

In this section, we present our algorithm's and define them precisely.

In the following algorithms, the member function * .𝑖𝑛𝑣𝑒𝑟𝑡𝑘𝑣() inverts keys and values of an associative container (data structure), the member function * .𝑔𝑟𝑜𝑢𝑝(𝑥) returns the set of all elements in the container associated with the same key as 𝑥, singleton 𝑥 if 𝑥 is not in the container.

Algorithm 1 presents the control function (loop) of our group recommendation algorithm. It loops over the parameter 𝑘 (number of groups), increasing it until no significant global utility (sum of all agents utility) gains have been achieved. To reduce the randomness of the process (our clustering algorithm being randomized) each 𝑘 value is tried several times and the loop will only terminate if no gain happen for several 𝑘 increments (momentum).

Algorithm 2 is based on k-means [START_REF] Stuart | Least squares quantization in PCM[END_REF]. The first step is the initialization of groups, which is a k-means++ [START_REF] Arthur | K-means++: The Advantages of Careful Seeding[END_REF] initialization (each group is given one single random member sequentially, with probability increasing with the distance to existing groups). After initialization, the process consists of two nested loops (inner and outer). Since, unlike k-means, we take group size into account, we need two loops, one for distance changes (as k-means) and one for group size changes (the inner loop). In the inner loop, at initialization, each group, has a fixed barycenter and is given a potential size of #𝐴. At each turn, agents compute their utility for each group with the potential sizes and choose their group accordingly. After that, the potential size of each group is set to the number of agents choosing this group, the barycenters are not updated. The process is repeated until no change append in one turn. In the outer loop, at each turn, the inner loop is executed and the barycenters are updated. The loop terminates if no change append in one turn.

Compared with k-means, the interesting part of our algorithm is the inner loop. Since, unlike k-means, our algorithm take the size of groups into account, we need this inner loop. It allows us to compute agents' utility with bigger groups. For agents to join groups, these groups have to be big enough and for groups to be big, agents have to join them. Our inner loop, with its over-evaluated groups' initial potential sizes, breaks this circle. The main limitation of this algorithm is that we do not have a theoretical termination proof for it. It could potentially, in very rare cases, get stuck in an infinite loop. So, we propose variation with guaranteed termination in Algorithm 3.

Algorithm 3 terminates the inner loop if the total number of agents member of any group does not change in one turn and the outer loop if the global utility of the affectation does not increase in one turn. This way, the algorithm is guaranteed to converge.

Both algorithms include a somewhat complex formula to compute agent's interest. For large instances, with very big clusters, individual agents influence on a cluster can be considered negligible. We call this situation "agents' atomicity" (agents are "atoms", too small relatively to the whole system to have significant influence individually). Thus, we can make an agents' atomicity hypothesis to simplify the formulas. 𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦(𝑔𝑟𝑝[𝑖] ∪ 𝑎))) × 𝑣(𝑠𝑖𝑧𝑒[𝑖] + 𝟙 𝑎∉𝑔𝑟𝑝[𝑖] ) can be replaced by

𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦(𝑔𝑟𝑝[𝑖]))) × 𝑣(𝑠𝑖𝑧𝑒[𝑖]

). This possibility may be used for a production implementation.

III Theoretical analysis

Here we prove the essential property of the clustering algorithm presented in Algorithm 2. Property (Nash equilibrium). If we consider a game where each agent's (player) possible choices are 𝑘 different groups to join, or not choosing any group, and each agent's 𝑎 payoff for choosing group 𝑔 is given by 𝑈 𝑝 (𝑎, 𝑔) as defined before and 1 for no choosing any group, the affectation outputed by Algorithm 2, if it exists, is a (weak) Nash equilibrium for this game.

Proof (Nash equilibrium). We assume that our algorithm as converged, we consider the last iteration of the loop guarded by 𝑛𝑔𝑟𝑝 = 𝑔𝑟𝑝 (line 11) and, in this iteration, the last iteration of the loop guarded by 𝑛𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 (line 15). ), we can affirm that, in this loop iteration, a different group would have been selected for at least one 𝑎. Now, either that changes the size of at least one group, implying 𝑛𝑠𝑖𝑧𝑒 ≠ 𝑠𝑖𝑧𝑒 at the end of the loop, which is a contradiction. Or, if the sizes remains identical (exchange of members), then, the loop guarded by 𝑛𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 exists, and we get 𝑛𝑔𝑟𝑝 ≠ 𝑔𝑟𝑝, which also is a contradiction.

Since the existence of a Nash equilibrium for this game is not guaranteed, it is possible that Algorithm 2 does not terminate. Now, we prove that Algorithm 3, for which we do not have an equilibrium proof, will always terminate.

Property (Convergence). Algorithm 3 always terminates.

Proof (Convergence). Among the control structures used in Algorithm 3, the two repeat…until loops are the only that do not trivially terminate (for loops terminate trivially). For the inner loop, we replaced 𝑛𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 by 𝑛𝑠𝑖𝑧𝑒.𝑠𝑢𝑚() ⩾ 𝑠𝑖𝑧𝑒.𝑠𝑢𝑚() as termination condition. This implies that, during the loop, 𝑠𝑖𝑧𝑒.𝑠𝑢𝑚()'s values are a strictly decreasing natural (ℕ) sequence. Such a sequence can not be infinite, thus, the inner loop terminates. For the outer loop, we replaced 𝑛𝑔𝑟𝑝 = 𝑔𝑟𝑝 by 𝑛𝑣𝑎𝑙 ⩽ 𝑣𝑎𝑙 as termination condition. This implies that, during the loop, 𝑣𝑎𝑙's values are a strictly increasing real sequence. Moreover, those values are given by a formula taking as parameter an affectation of a finite number of agents in a finite number of groups. The possible inputs for this formula for a given execution of the algorithm (fixed parameters) are a finite set. This implies that the possible values for 𝑣𝑎𝑙 (output of this formula) are also a finite set (for a given execution of the algorithm). Thus, 𝑣𝑎𝑙's values are a strictly increasing sequence of elements of a finite set (the order is given by the classical order for real number). Such a sequence can not be infinite, thus, the outer loop terminates. We can now conclude that our algorithm will always terminate.

We note that Algorithm 3 is not guaranteed to give a Nash equilibrium. Such an equilibrium may simply not exist, but even if it exists, the algorithm is not guaranteed to find it. Due to the end condition of its outer loop, Algorithm 3, while still based on agents' self-interest, is more centered on attaining general optimality (maximizing the sum of all agents utilities) than Algorithm 2.

An important thing that differentiates our algorithm from generic approaches to solve hedonic games presented in [START_REF] Aziz | Hedonic Games[END_REF] is the inner loop of our algorithm, which allows groups to grow to a point that is better for every agent even in situations where individual rational decisions could not.

Let's examine this simple example : We have four agents, 𝐴, 𝐵, 𝐶 and 𝐷. 𝑛

(𝑥) = 1 1+𝑥 , 𝑣(𝑥) = 𝑥, 𝑝's values in ℝ 2 , 𝑝(𝐴) = [0, 0], 𝑝(𝐵) = [0, 2.5], 𝑝(𝐶) = [2.5, 0] and 𝑝(𝐷) = [2.5, 2.5] (a square).
In this example, having all agents in a single group, 𝒢, is the best solution. ∀ 𝑎∈{𝐴,𝐵,𝐶,𝐷} 𝑈 𝑝 (𝑎, 𝒢) = 4 1+2.5 √ 2/2 > 1. But this situation could not be reached from groups consisting of a single agent by individual rational decisions, since the best interest one single agent could get from grouping with another agent would be 2 2.25 < 1, so no agent would want to group with any other. With our algorithm, if we start with a group 𝒢 = {𝐴}, due to making computations based on the potential maximum size of the group rather than its actual size, individual interest of 𝐵 and 𝐶 for join the group would be estimated at 4 3.5 > 1 with an atomic variant (even more with a non-atomic variant) and the group 𝒢 will be updated 𝒢 = {𝐴, 𝐵, 𝐶}. On the second run of the inner loop, with the bary center of 𝒢 being at [ 2.5 /3, 2.5 /3], the atomic-estimated interest for 𝐷 to join 𝒢 would be 4 1+ 5 /3 √ 2 > 1. We end up with 𝒢 = {𝐴, 𝐵, 𝐶, 𝐷}.

IV Experimentation

In this section, we evaluate Algorithm 3, in normal an atomic agents variants and see how much, in practice, it deviates from Algorithm 2's Nash equilibrium property. We compare our algorithm with two reference clustering algorithms: OPTICS [Ank+99] and k-means [START_REF] Stuart | Least squares quantization in PCM[END_REF] with k-means++ [START_REF] Arthur | K-means++: The Advantages of Careful Seeding[END_REF] initialization. All algorithms evaluated have guaranteed termination. We perform this evaluation on four kinds of datasets: synthetic data and three real data applications: leisure travel, buying and machine-learning.1

IV.1 Synthetic Data

We first evaluate our algorithm on ℝ 2 data generated using a combination of Gaussian distributions. We choose Gaussians because those distributions are usually considered good models of characteristics distribution in real populations. A fixed number of points is generated, the distribution used to generate each vector is chosen randomly according to a predetermined ratio. Parameters of these laws will be detailed in each specific tests. We used the usual euclidean distance for 𝑑, 𝑛(𝑥) = 1 1+𝑥 and Example results, based on a single run (same data for all algorithms), are also given. In these, a color identify a cluster, gray points are alone (or in a cluster of size 1). "AUCCCR-C" is Algorithm 3 in its normal variant, "AUCCCR-CA" is the atomic variant.

(a) AUCCCR-C (b) AUCCCR-CA (c) k-means (d) OPTICS

IV.1.a Bi-Gaussian

For this test, we used two (0, 0)-centered Gaussian distributions with 1 and 8 as standard deviations and a 0.5 -0.5 ratio (same probability for each distribution). The number of point is 100.

Figure 1 presents a sample output of the four algorithms. In these, a color identify a cluster, gray points are alone (or in a cluster of size 1). Figure 2c shows the global utility, as a sum of all agents' utility, for each algorithm. Figure 2a shows the sum of the losses of agents, which is the difference between the utility an agent gets from the present cluster affectation and the maximum utility the agent could get if the agent chooses its cluster (or being alone) following its own interest. Figure 2b shows the share of agents experiencing losses.

In this test, we see that AUCCCR-C(A) yields a lower global utility but also that its output is very close to a Nash equilibrium (near 0 losses), while k-means and OPTICS have more than 25% of agents experiencing losses. Looking at individual runs, we see that k-mean and OPTICS just produce a single giant cluster, maximizing its value for all agent but causing losses for agents that lie far away from the barycenter, while our algorithm, because it allows agent to stay on their own, took more care of their individual interest.

IV.1.b 3 Gaussians

For this test, we used three Gaussian distributions, (-6, 0), (0, 0) and (0, 6)-centered with 1.5 as standard deviations and a 0.33-0.33-0.33 ratio (same probability for each distribution). The number of point is 200.

Figure 3 presents a sample output of the four algorithms. In these, a color identify a cluster, gray points are alone (or in a cluster of size 1). Figure 4c shows the global utility, as a sum of all agents' utility, for each algorithm. Figure 4a shows the sum of the losses of agents, which is the difference between the utility an agent gets from the present cluster affectation and the maximum utility the agent could get if the agent chooses its cluster (or being alone) following its own interest. Figure 4b shows the share of agents experiencing losses.

In this test, we see that AUCCCR-C(A) and k-means both perform well it terms of global utility, better than OPTICS, likely due to OPTICS density-centered design being ineffective for this kind of pattern ; OPTICS has difficulties in distinguishing close but clearly distinct distributions. Losses were limited but AUCCCR clearly outperformed k-mean and, even more, OPTICS.

IV.1.c Gaussians Star

For this test, we used five Gaussian distributions, (0, 0), (-10, -10), (-10, 10), (10, -10) and (10, 10)-centered with 5 for the (0, 0) and 2 for others as standard deviations and a 0.5 -0.125 -0.125 -0.125 -0.125 ratio. The number of point is 300.

Figure 5 presents a sample output of the four algorithms. In these, a color identify a cluster, gray points are alone (or in a cluster of size 1). Figure 6c shows the global utility, as a sum of all agents' utility, for each algorithm. Figure 6a shows the sum of the losses of agents, which is the difference between the utility an agent gets from the present cluster affectation and the maximum utility the agent could get if the agent chose its cluster (or being alone) following its own interest. Figure 6b shows the share of agents experiencing losses.

In this test, all algorithms gave similar results in terms of global utility (slightly lower for AUCCCR on average). The gap much higher on losses, with AUCCCR clearly leading. Looking at samples, it seems that AUCCCR performed pretty well for identifying the five Gaussians mixed in the input data compared to k-means and OPTICS.

IV.1.d Effect of the number of agents

In this test we reused our Gaussians Star setup, but we tested different numbers of agents.

Figure 7c shows the global utility, as an average of all agents' utility, for each algorithm. Figure 7a shows the average of the losses of agents, which is the difference between the utility an agent gets from the present cluster affectation and the maximum utility the agent could get if the agent chooses its cluster (or being alone) following its own interest. Figure 7b shows the share of agents experiencing We see here that all algorithms have similar performances in terms of global utility; AUCCCR being slightly better for a high number of agents. In terms of losses, however, OPTICS and k-means seems to perform better for low numbers of agents. This is likely due to the fact that AUCCCR is used with an algorithm to find optimal 𝑘 which optimizes global utility rather than loss. For k-mean and OPTICS, both simply put all agents in one cluster, which, for this number of agents, is a Nash equilibrium, but not necessarily an optimal affectation. Used with this 𝑘 researcher, AUCCCR ended up being better for global utility and not for losses, while it is designed to minimize losses, in this specific case were a trivial (one cluster) affectation is a Nash equilibrium. Note that the losses are still very low compared to what k-means and OPTICS did for lower numbers of agents.

IV.1.e Effect of the standard deviations

In this test we reused our Gaussians Star setup, but we tested different standard deviations.

Figure 8c shows the global utility, as an average of all agents' utility, for each algorithm. Figure 8a shows the average of the losses of agents, which is the difference between the utility an agent gets from the present cluster affectation and the maximum utility the agent could get if the agent chooses its cluster (or being alone) following its own interest. Figure 8b shows the share of agents experiencing losses.

The value used in the "Standard deviations" axis is the (0, 0)-centered distribution's standard deviations. Others were modified by the same factor, as well as the distances between distributions' centers.

With a high standard deviation, the optimal solution becomes essentially to have nearly as many clusters as agents. k-means performs much worse than other algorithms (nearly all agents have losses, while nearly none have for other algorithms) because it is not designed to find this kind of affectation. AUCCCR and OPTICS have similar performance overall, except for 10. In losses, AUCCCR is the only algorithm to always remain at very low values. For the value 10, while AUCCCR was slightly lower for global utility, it is by far the best for losses.

IV.1.f Effect of scale

In this test we reused our Gaussians Star setup and combined the two previous tests, modifying at the same time, standard deviations, number of agents and mean values separations by the same scale factor (for geometrical reasons, this implies that the distances were increased by the square root of this factor).

Figure 9c shows the global utility, as an average of all agents' utility, for each algorithm. Figure 9a shows the average of the losses of agents, which is the difference between the utility an agent gets from the present cluster affectation and the maximum utility the agent could get if the agent chooses its cluster (or being alone) following its own interest. Figure 9b shows the share of agents experiencing losses.

Here we observe that AUCCCR can have difficulties with certain scale values, around 2 or 4, in terms of global utility, while being more competitive for a higher value of 8. This is probably due to such scales offering more opportunity for AUCCCR to deviate from the global optimum in favor of reducing individual losses. In terms of losses, however, AUCCCR remains extremely low for all value, while other algorithms get much worse results.

IV.1.g Size constraint

To evaluate the ability of our algorithm to manage cases where too large clusters are not wanted (agents want to be in a sufficiently large group but not too large) we take a simple case, with a single Gaussian, in which our usual 𝑣(𝑥) = √ 𝑥 function would make a single cluster (with all agents in it) optimal. We then change 𝑣(𝑥) so that too large clusters are not optimal.

We test two different functions, both = √ 𝑥 for 𝑥 ⩽ 20, but for 𝑥 > 20 the first function is constant √ 20 while the second is decreasing √ 20 1+ |20-𝑥| 20 (both functions are continuous). The number 20 is an arbitrary choice and can be considered as a target size for clusters. See Figure 10 for a plot. decreasing 𝑣(𝑥) functions and we see that we get (too) small clusters in that case, but this does not prevent the algorithm from working correctly. AUCCCR performs quite well in terms of size of cluster (close to the target size). AUCCCR clusters tends to be large, some times a bit larger than wanted, compared to k-means and, even more, OPTICS, which produce too small clusters. With the metrics, we see that our algorithm continues to outperform others in the same way as with other experiments with √ 20, with √ 20 1+ |20-𝑥| 20 however, k-means' results are very close to AUCCCR's.

IV.2 The BuddyMove dataset

The BuddyMove [START_REF] Renjith | A personalized mobile travel recommender system using hybrid algorithm[END_REF] dataset consists of statistics from users of a travel review website. For each user, the dataset gives the number of review wrote for each of 6 classes of destination (e.g. religious site, park, etc). From these data, we derived for each user the share of reviews written for each destination class. This can be interpreted as the relative interest of a user for each kind of destination. This could allow providing recommendation to users on whom they should go with for group travels, based on the similarity of their preferences.

IV.2.a Hyperparameters

Our clustering algorithms used Euclidean distance for 𝑑, 𝑛(𝑥) = 1 1+𝑥 and 𝑣(𝑥) = √ 𝑥. 𝑝𝑟𝑐 = 20, 𝑚𝑚𝑡 = 5. Results are average over 10 runs, error bars indicates standard deviation. Sample examples, based on a single run, are also given. In these, a color identify a cluster, gray points are alone (or in a cluster of size 1). "AUCCCR-C" is Algorithm 3 in its normal variant, "AUCCCR-CA" is the atomic variant. An additional Hyperparameter is used: scale. The scale describes how "far" a given distance is considered by the algorithm (the distances naturally present in the dataset must be given an absolute cardial signification for the algorithm or its formalization make no sens). For example, if the scale is 10, a distance of 1 will be computed as 10 for computation. If the scale is bigger, distance between points will be considered longer by the algorithm.

IV.2.b Metrics

The graphs in Figure 18 presents the 3 following metrics : the average utility of agents (Figure 18c), the average losses of agents (Figure 18a) and the share of agents having losses (Figure 18b) for a range of scale values. The range of scale is selected to cover all the range of cases from a situation where everyone alone is optimal to a situation were a universal cluster is optimal.

We note that, is those graphs, the lines for the two variants of AUCCCR are largely superposed, and k-means and OPTICS are identical. For a low scale, users are considered close and all algorithms will detect a single cluster but, as the scale increases, the results become very different. AUCCCR, contrary to the reference algorithms, will prevent individual losses ; as we can see, losses are very low for AUCCCR, especially for large scales, while, for other algorithms, losses increase dramatically. For a scale of 130, AUCCCR has nearly 0 agents losses while k-mean and OPTICS have 30%. This comes at the cost of a reduced global utility, which slowly drops until it nearly hits 1 (equivalent to everyone alone) at 130. For midrange values, we see that AUCCCR has nearly no losses with a still high global utility (1.5, 1.7 for reference algorithms; this lower value being due to the small size of clusters possible with minimal individual losses) while reference algorithms have 15% to 20% of losses.

IV.2.c Clusters size

The graphs in Figure 19 gives the obtained clusters sizes for the different algorithms with a scale of 115. We see that, for this midrange scale, k-means and OPTICS identified only a universal cluster, while both AUCCCR variants identified 3 and let numerous users alone.

IV.2.d Clusters visualisation

Since the dataset has a large dimension (6), we provide views in reduced dimensions, 2 and 3. We propose two different kinds of dimension reduction methods. The first simply presents the dimensions were the original dataset has higher standard deviation. See Figure 20 for 2D and Figure 21 for 3D. The second uses the scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF] Python library, which implements various algorithms that can perform non-linear dimension reduction. The specific algorithm we used is MDS (Multi-Dimensional Scaling) [START_REF] Borg | Modern Multidimensional Scaling -Theory and Applications[END_REF]. See Figure 22 for 2D and Figure 23 for 3D.

IV.3 The Wholesale dataset

The Wholesale [START_REF] Gonçalo | Análise do perfil do cliente Recheio e desenvolvimento de um sistema promocional[END_REF] dataset consists of statistics from customers of a wholesale vendor. For each customer, the dataset indicates the annual spending for each of 6 classes of products (e.g. fresh, frozen, etc). From these data, we derive for each customer the share of reviews written for each product class. This result could for instance be used to provide recommendations to customers on whom they should collaborate with to make grouped orders more directly, removing the wholesale distributor from the

IV.3.a Hyperparameters

We configure our clustering algorithms to use the Euclidean distance for 𝑑, 𝑛(𝑥) = 1 1+𝑥 and 𝑣(𝑥) = √ 𝑥. 𝑝𝑟𝑐 = 20, 𝑚𝑚𝑡 = 5. Results are average over 10 runs, error bars indicate standard deviation. Sample examples, based on a single run, are also given. In these, a color identify a cluster, gray points are alone (or in a cluster of size 1). "AUCCCR-C" is Algorithm 3 in its normal variant, 'AUCCCR-CA" is the atomic variant. An additional Hyperparameter is used: scale. The scale describes how "far" a given distance is considered by the algorithm (the distances naturally present in the dataset must be given an absolute cardial signification for the algorithm or its formalization make no sens). For example, if the scale is 10, a distance of 1 will be computed as 10 for computation. If the scale is bigger, distance between point will be considered longer by the algorithm.

IV.3.b Metrics

The graphs in Figure 24 presents the 3 following metrics : the average utility of agents (Figure 24c), the average losses of agents (Figure 24a) and the share of agents having losses (Figure 24b) for a range of scale values. The range of scale is selected to cover all the range of cases from a situation where everyone alone is optimal to a situation were a universal cluster is optimal.

We note that, is those graphs, the lines for the two variants of AUCCCR are largely superposed. For a low scale, users are considered close and all algorithms will detect a single cluster but, as the scale increases, the results become very different. AUCCCR, contrary to the reference algorithms, will prevent individual losses ; as we can see, losses are close to 0 for AUCCCR, especially for large scales, while, for other algorithms, losses increase dramatically. For a scale of 60, AUCCCR has nearly 0 agents losses while k-mean has > 30% and OPTICS has > 40%. The global utility remains similar to k-means and greater than OPTICS for the lower half of scales, only higher values have a utility lower than OPTICS but still very close from both, OPTICS and k-means. For midrange values, we see that AUCCCR has nearly no losses with a global utility close to k-means and higher than OPTICS, while reference algorithms have around 10% of losses.

IV.3.c Clusters size

The graphs in Figure 25 gives the obtained clusters sizes for the different algorithms with a scale of 45. We see that, for this midrange scale, k-means and OPTICS identified only a universal cluster, while both AUCCCR variants identified 3 and let numerous users alone.

IV.3.d Clusters visualisation

Since the dataset has a large dimension (6), we provide views in reduced dimensions, 2 and 3. We propose two different kinds of dimension reduction methods. The first simply presents the dimensions were the original dataset has higher standard deviation. See Figure 26 for 2D and Figure 27 for 3D. The second uses the scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF] Python library, which implements various algorithms that can perform non-linear dimension reduction. The specific algorithm we used is MDS (Multi-Dimensional Scaling) [START_REF] Borg | Modern Multidimensional Scaling -Theory and Applications[END_REF]. See Figure 28

IV.4 Machine-learning Data -MNIST

As a more concrete application, we evaluate our program on machine-learning data. We use here classical multi-layer perceptrons (MLP) on the well-known MNIST dataset.

The task associated with the MNIST dataset is handwritten digits recognition. From this task, we want to obtain a cooperation recommendation task. There are various distributed machine-leaning methods, as the one presented in [START_REF] Bouchra | Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Networks[END_REF]. These methods imply cooperation between different MLPs. Now, we want our MLPs to have more or less similar tasks. To this aim, we simply modified the MNIST task for some of those MLPs: part of our MLPs have to perform the standard digit recognition task, while others have to perform a modified task where two digits are exchanged, so a [9] would be classified as a eight and vis versa. The clustering task would be to assign to the same cluster MLPs with the same task and different clusters MLPs with different tasks.

Since our clustering algorithms takes real vectors as inputs, we need to make real vectors from our MLPs. The most straightforward way would be to directly take the MLPs learned parameters, which are real values, but this is not a good way. Due to the nature of neural networks, similar learned tasks absolutely do not imply similar learned parameters. For this reason, we used a different method. After a reasonable amount of training, we made each MLP work on the test part of the MNIST dataset. For each different digit tested (from 0 to 9), we took the average of the outputs of each MLP (10 real values, which are the MLPs estimated likeliness of the input image to be each of the digits from 0 to 9) and concatenated them in one ℝ 100 vector. These vectors will be used as input for our clustering algorithms.

We use two metrics to evaluate the quality of the outputted affectation: the Identification rate, which is the share of the pairs of MLPs with identical task being in the same cluster, and the Differentiation rate, which is the share of the pairs of MLPs with different tasks being in different clusters. We want both value to be as close to 1 as possible.

We trained 16 MLPs, 9 of them performing a standard classification task and 7 of them have 8 and 9 permuted. They were trained each on a different part of the MNIST dataset training part of size 3500. The MLPs had a 784=300=100=10 configuration with 𝜆 = 1 sigmoid activation functions and a 0.1 learning rate. The ℝ 100 vectors where built from the 1000 first values of the MNIST dataset test part.

Our clustering algorithms used euclidean distance for 𝑑, 𝑛(𝑥) = 1 1+15𝑥 and 𝑣(𝑥) = √ 𝑥. 𝑝𝑟𝑐 = 20, 𝑚𝑚𝑡 = 5. Results are average over 10 runs, error bars indicates standard deviation. Sample examples, based on a single run, are also given. In these, a color identify a cluster, gray points are alone (or in a cluster of size 1). "AUCCCR-C" is Algorithm 3 in its normal variant, 'AUCCCR-CA" is the atomic variant. Figure 30a presents the identification rate for various numbers of mini-batches and Figure 30b the differentiation rate.

We essentially observe that all algorithms remains close to perfect for all tests. While those tests on a very simple case do not allow determining which algorithm would be the best, they prove the validity of the idea of using clustering algorithms to provide cooperation recommendations for distributed machine-learning.

Figure 31 gives examples of cluster affectation outputted by AUCCCR-C. Since we used vectors from a space of dimension 100, we selected to relevant dimensions, 89 and 99 (corresponding to permuted digits), to make these 2D plots.

IV.5 Machine-learning Data -VSN

To go farer than our previous experiment with MNIST, we use a different task: vehicle recognition from sensors. We use a dataset from [START_REF] Duarte | Vehicle classification in distributed sensor networks[END_REF]. This dataset contains data from sensors (notably seismic and acoustic sensors) produced while some (military) vehicle passes near the sensor. In that case, no obvious group affectation is possible without relying on clustering, allowing us to evaluate how our approach allows to effectively get better performance than a reference. The task proposed is to recognize the class of vehicle (assault amphibious or dragon wagon) from each sensor's data (binary classification). To allow a MLP to perform this task, the data from each set of sensors (node) is first transformed into 50 seismic and 50 acoustic features (100 total inputs). This process (based on Fast Fourier Transform) is described in the original paper [START_REF] Duarte | Vehicle classification in distributed sensor networks[END_REF]).

As for MNIST, we rely on the approach of distributed multi-task machine learning presented in [START_REF] Bouchra | Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Networks[END_REF] For our distributed multi-task setup, we consider each node as a peer. The tasks are similar, since all peer what to classify the same kinds of vehicles from the same kind of data, but different due to the location of sensors influencing their output.

To get real vectors for our clustering algorithms, as we do with MNIST, we take locally pre-trained networks (one for each peer) and test them on a standard set inputs. From the obtained output, we construct ℝ 2 vectors from the average output of networks on each type of vehicle.

For this experiment we use 16 peers, each with a training set of 50 samples. The mini-batch size is 25. We use an MLP with a 100=50=20=1 layout, trained with stochastic gradient descent, 𝜆 = 1 sigmoid activation functions and a 0.1 learning rate.Our clustering algorithms used euclidean distance for 𝑑, 𝑛(𝑥) = 1 1+15𝑥 and 𝑣(𝑥) = √ 𝑥. 𝑝𝑟𝑐 = 20, 𝑚𝑚𝑡 = 5. Results are average over 10 runs. We start with a local pre-training phase of 400 mini-batches. Then, we use the output of the pre-trained networks on a (identical for all peers) test set of 1000 samples to get inputs for clustering. With the output of our clustering algorithm, we define partial models (see [START_REF] Bouchra | Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Networks[END_REF] for details) to use for the real training phase of 400 mini-batches (we restart from 0 for a fair comparaison with reference results) and perform tests on 200 samples (specific to each peer). Here, the performance Figure 32 gives examples of cluster affectation outputted by different algorithms. Figure 33 compares the performance of the reference from [START_REF] Bouchra | Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Networks[END_REF] to what can be achieved using affectations obtained from our clustering algorithms (k-means and OPTICS both failed to provide meaningful affectations).

While no obvious cluster affectation is visible, AUCCCR manages to find some clusters (differences between samples from the two variants of AUCCCR are more likely due to randomness than real difference between the two algorithms). k-means and OPTICS however both fail in this difficult case.

k-means and OPTICS fail to provide meaningful clustering information, not allowing any gain over reference (all logical affectations derivable from their outputs are in reference). With AUCCCR, however, we get two cluster affectations, from each of which can be derived several averaging schemes (see [START_REF] Bouchra | Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Networks[END_REF] for details).

We present results of three different schemes, which can be considered the most obvious possibilities:

• per class: A 100-50-20-1 (full network) model for each cluster (out of clusters peers are trained locally).

• semi-local: A 100-35-14-1 for all peers and a 0-15-6-0 (dependent on the previous one) for each cluster (leaving nothing local for peers in clusters).

• semi-local+local: A 100-35-14-1 for all peers and a 0-7-3-0 (dependent on the previous one) Notice that those are only there of the numerous possibilities offered in our case by [START_REF] Bouchra | Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Networks[END_REF]'s approach. We chose those because they are the most consistent with results from [BFT21] but further optimization is possible and may lead to better results, even through [START_REF] Bouchra | Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Networks[END_REF] concluded that the solution we used in semi-local+local was the best in their experiments.

As we see in results, per class does not beat reference, likely due to lots of peers being out of classes (the performance is slightly higher than local learning). Semi-local achieve reference-like performance, likely because the gain from clusters is cancelled by the loss from lack of intra-cluster differentiation. Semi-local+local, however, manages to obtain (slightly) better than reference results. The gain is limited but similar to what reference achieved with partial averaging compared to global.

IV.6 General analysis of results

On our synthetic data tests, we showed that our algorithm is more efficient for cluster identification than classical clustering algorithms. It also appeared that, as intended, our algorithm causes much lower individual losses to agent than other algorithms. While it is not possible to completely remove losses in the absence of a Nash (or similar) equilibrium for mathematical reasons, our algorithm Our algorithm also exhibited good performance on the two real datasets, Buddymove and Wholesale, proving its applicability to real use cases.

We also proved that our idea of using clustering algorithms to identify good collaboration opportunities in distributed machine learning is valid, with our MLP-MNIST example, and that in could lead to performance improvement in cases where no manual affectation is possible, with our MLP-VSN example.

V Related work

Hedonic games as a theoretical model were originally proposed in the economic community by [START_REF] Drèze | Hedonic Coalitions: Optimality and Stability[END_REF]. More recently, this field has been studied by the algorithmic community. The authors of [START_REF] Aziz | Hedonic Games[END_REF] summarize algorithmic studies of these games. Existing algorithmic solutions all relies on some kind of equilibrium (similar to Nash equilibrium) which may not exist in real applications.

In addition to those general researches on hedonic games, some researchers considered using hedonic games to solve practical problems. For example, [START_REF] Saad | Coalition Formation Games for Distributed Cooperation Among Roadside Units in Vehicular Networks[END_REF] worked on collaboration between roadside units in Intelligent Transportation Systems. [START_REF] Anglano | A game-theoretic approach to coalition formation in fog provider federations[END_REF] considered hedonic games in the context of Fog Computing. Application of these games to edge computing is also proposed in [START_REF] Zhang | Data offloading in mobile edge computing: A coalitional game based pricing approach[END_REF]. These games can also be applied to energy networks, as suggested by [START_REF] Mei | Coalitional Game Theory Based Local Power Exchange Algorithm for Networked Microgrids[END_REF]. Each of these articles presents its own model and algorithm, to solve the specific problem they are considering.

The most known clustering algorithm is k-means [START_REF] Stuart | Least squares quantization in PCM[END_REF]. A lot of variants have been proposed, notably k-means++ [START_REF] Arthur | K-means++: The Advantages of Careful Seeding[END_REF], which improves its initialization. There are also variants of k-means with size constraints [START_REF] Ganganath | Data Clustering with Cluster Size Constraints Using a Modified K-Means Algorithm[END_REF][START_REF] Tang | Size Constrained Clustering With MILP Formulation[END_REF] or density [START_REF] Davidson | Agglomerative Hierarchical Clustering with Constraints: Theoretical and Empirical Results[END_REF] but such variants can only find clusters with similar characteristics (size/density) leading to results unwanted for our application (the graphs in [START_REF] Ganganath | Data Clustering with Cluster Size Constraints Using a Modified K-Means Algorithm[END_REF] show this clearly). Another well-known clustering algorithm is OPTICS [START_REF] Ankerst | OPTICS: Ordering Points To Identify the Clustering Structure[END_REF], which can be seen as an improved DBSCAN [START_REF] Ester | A Density-based Algorithm for Discovering Clusters a Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[END_REF]; both OPTICS and DBSCAN are density-based (k-means is distance-based). Through they did not formalized the problem as an hedonic game, the authors of [SvW19] also propose to use a clustering algorithm for coalition formation in the specific context of machine learning. This work did not proposed a novel algorithm and simply used a variant of DBSCAN. OPTICS, which we tested and proved limited in our experiments, being an improved DBSCAN, we can affirm that the solution proposed in [START_REF] Strezoski | Learning Task Relatedness in Multi-Task Learning for Images in Context[END_REF] would not exhibit good results compared to ours.

VI Conclusion

In this work, we defined a new class of hedonic games on which we based a algorithm for providing cooperation recommendation. We compared our algorithm to classical clustering algorithm that could have also been used for the same recommendation problem. We proved that our algorithm yields results that exhibit close to no losses and are thus much to a Nash equilibrium (which does not exist in the general case) than other algorithms.

Figure 1 :

 1 Figure 1: Clusters found in Bi-Gaussian

Figure 2 :

 2 Figure 2: Metrics in Bi-Gaussian for all algorithms

Figure 3 :

 3 Figure 3: Clusters found in 3 Gaussians

Figure 4 :

 4 Figure 4: Metrics in 3 Gaussians for all algorithms

Figure 5 :

 5 Figure 5: Clusters found in Gaussians Star

Figure 7 :

 7 Figure 6: Metrics in Gaussians Star for all algorithms

Figure 8 :Figure 9 :

 89 Figure 8: Metrics in Gaussians Star for different standard deviations by different algorithms

Figure 10 :

 10 Figure 10: Group value functions

Figure 11 :

 11 Figure 11: Clusters with various algorithms and different 𝑣(𝑥)

Figure 12 :

 12 Figure 12: Clusters size with √ 𝑥 by different algorithms

Figure 13 :

 13 Figure 13: Clusters size with √ 20 by different algorithms

Figure 14 :

 14 Figure 14: Clusters size with √ 20 1+ |20-𝑥| 20

  Figure 15: Metrics with √ 𝑥 for all algorithms

Figure 18 :

 18 Figure 17: Metrics with √ 20 1+ |20-𝑥| 20

Figure 19 :

 19 Figure 19: Clusters size in Buddymove for scale 115 by different algorithms

Figure 20 :

 20 Figure 20: Clusters found in Buddymove@115

Figure 21 :

 21 Figure 21: Clusters found in Buddymove@115

Figure 25 : 2 𝑟𝑎Figure 26 :(Figure 28 :Figure 33 :

 252262833 Figure 25: Clusters size in Wholesale for scale 45 by different algorithms

Table 1 :

 1

Symbols used in algorithm remaining alone (to ensure the solution's stability). Table

1

summarizes these notations and defines the variables and parameters appearing in algorithms.

  𝐴 set of agents, 𝑝 projector, 𝑝𝑟𝑐 is the number of (random) initial values to try, 𝑚𝑚𝑡 momentum effect Result: A pair of a group affectations of agents and its value

	1 𝑣𝑎𝑙 ← #𝐴
	2 𝑘 ← 1
	3 𝑝𝑚𝑚 ← 𝑚𝑚𝑡
	4 repeat
	5	𝑝𝑣𝑎𝑙 ← 𝑣𝑎𝑙
	6	𝑣𝑎𝑙 ← #𝐴
	7	repeat
	8	𝑎𝑓𝑒𝑐𝑡 ← CLUSTER(𝐴, 𝑝, 𝑘)
	9	𝑛𝑣𝑎𝑙 ← ∑ 𝑎∈𝐴 𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦(𝑎𝑓𝑒𝑐𝑡.𝑔𝑟𝑜𝑢𝑝(𝑎)))) × 𝑣(#𝑎𝑓𝑒𝑐𝑡.𝑔𝑟𝑜𝑢𝑝(𝑎))
	10	if 𝑛𝑣𝑎𝑙 > 𝑣𝑎𝑙 then
	11	if 𝑛𝑣𝑎𝑙 > 𝑝𝑣𝑎𝑙 then
	12	𝑠𝑜𝑙 = 𝑎𝑓𝑒𝑐𝑡
	13	𝑣𝑎𝑙 ← 𝑛𝑣𝑎𝑙
	14	until 𝑝𝑟𝑐 times
	15	𝑘 + +
	16	if 𝑣𝑎𝑙 > 𝑝𝑣𝑎𝑙 then
	17	𝑝𝑚𝑚 ← 𝑚𝑚𝑡

Algorithm 1: Recommendation algorithm

Data:

Algorithm 2: Clustering algorithm

	1 function CLUSTER(𝐴, 𝑝, 𝑘) is
			/* k-means++ initialization */
	2	𝑟𝑎 ← 𝑟𝑎𝑛𝑑(𝐴)
	3	𝑛𝑔𝑟𝑝[0] ← {𝑟𝑎}
	4	foreach 𝑎 ∈ 𝐴 do
	5	𝑑𝑚𝑖𝑛2[𝑎] ← 𝑑(𝑝(𝑎), 𝑝(𝑟𝑎)) 2
	6	for 1 ⩽ 𝑖 < 𝑘 do
	7	𝑛𝑎 ← 𝑟𝑎𝑛𝑑(𝐴, 𝑑𝑚𝑖𝑛2)
		/* random element from 𝐴, relatives probabilities given by 𝑑𝑚𝑖𝑛2 */
	8	𝑛𝑔𝑟𝑝[𝑖] ← {𝑛𝑎}	// appends {𝑛𝑎} to ngrp
	9	foreach 𝑎 ∈ 𝐴 do
	10	𝑑𝑚𝑖𝑛2[𝑎] ← min(𝑑(𝑝(𝑎), 𝑝(𝑛𝑎)) 2 , 𝑑𝑚𝑖𝑛2[𝑎])
			/* main loop */
	11	repeat
	12	𝑔𝑟𝑝 ← 𝑛𝑔𝑟𝑝
	13	𝑛𝑔𝑟𝑝.𝑐𝑙𝑒𝑎𝑟()
	14	𝑛𝑠𝑖𝑧𝑒 ← [#𝐴…#𝐴]
	15	repeat
	16	𝑠𝑖𝑧𝑒 ← 𝑛𝑠𝑖𝑧𝑒
	17	𝑛𝑠𝑖𝑧𝑒 ← [0…0]
	18	foreach 𝑎 ∈ 𝐴 do
	19	𝑏𝑔𝑟𝑝[𝑎] ← argmax 𝑖∈⊥∪⟦0,𝑘-1⟧ (𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦(𝑔𝑟𝑝[𝑖] ∪ 𝑎))) × 𝑣(𝑠𝑖𝑧𝑒[𝑖] + 𝟙 𝑎∉𝑔𝑟𝑝[𝑖] ))
		/* assuming 𝑔𝑟𝑝[⊥] = ∅ and 𝑠𝑖𝑧𝑒[⊥] = 0 */
	20	𝑛𝑠𝑖𝑧𝑒[𝑏𝑔𝑟𝑝[𝑎]] + +	// does nothing if 𝑏𝑔𝑟𝑝[𝑎] = ⊥
	21	until 𝑛𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒
	22	𝑛𝑔𝑟𝑝 ← 𝑏𝑔𝑟𝑝.𝑖𝑛𝑣𝑒𝑟𝑡𝑘𝑣()	// key-value inversion
	23	until 𝑛𝑔𝑟𝑝 = 𝑔𝑟𝑝
	24	return 𝑛𝑔𝑟𝑝
	Let's assume that the output of the function, 𝑛𝑔𝑟𝑝 = 𝑔𝑟𝑝, is not a (weak) Nash equilibrium. Then
	∃𝑎 ∈ 𝐴, 𝑔 ∈ ⊥ ∪ ⟦0, 𝑘 -1⟧(𝑈 𝑝 (𝑎, 𝑔) > 𝑈 𝑝 (𝑎, 𝑔𝑟𝑝.𝑔𝑟𝑜𝑢𝑝(𝑎))).
	Since at the end of the loop iteration 𝑛𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 and 𝑛𝑠𝑖𝑧𝑒 is, by design, the vector of the sizes of
	the groups given by 𝑛𝑔𝑟𝑝, we can affirm that, during the considered loop iteration (assimilating 𝑖 with
	a group), 𝑈 𝑝 (𝑎, 𝑔𝑟𝑝[𝑖]) = 𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦(𝑔𝑟𝑝[𝑖] ∪ 𝑎))) × 𝑣(𝑠𝑖𝑧𝑒[𝑖] + 𝟙 𝑎∉𝑔𝑟𝑝[𝑖] ).
	Since, by design, our algorithm selects 𝑖 to maximize 𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦(𝑔𝑟𝑝[𝑖]∪𝑎)))×𝑣(𝑠𝑖𝑧𝑒[𝑖]+𝟙 𝑎∉𝑔𝑟𝑝[𝑖]

Our code is available at https://gitlab.inria.fr/abouchra/distributed_neural_networks


domain: chim phys.cond.cm-scm phys

text:
Aicha Jani

Benjamin Malfait

Denis Morineau
email: denis.morineau@univ-rennes1.fr

On the Coupling between Ionic Conduction and Dipolar Relaxation in Deep Eutectic Solvents: Influence of Hydration and Glassy Dynamics

We have studied the ionic conductivity and the dipolar reorientational dynamics of aqueous solutions of a prototypical deep eutectic solvent (DES), ethaline, by using dielectric spectroscopy on a broad range of frequency (MHz-Hz) and for temperatures ranging from 128 to 283 K. The fraction of water in the DES was varied systematically to cover different regimes, starting from pure DES and its water-in-DES mixtures to the diluted electrolyte solutions. Depending on these parameters, different physical states were examined, including low viscosity liquid, supercooled viscous liquid, amorphous solid and freeze-concentrated solution. The ionic conductivity and the reorientational relaxation both exhibited characteristic features of glassy dynamics that could be quantified from the deviation from Arrhenius temperature dependence and non-exponential decay of the relaxation function. A transition occurred between the water-in-DES regime, (< 40 wt %), where the dipolar relaxation and ionic conductivity remained inversely proportional to each other, and the DES-in-water regime, (> 40 wt %), where a clear rotation-translation decoupling was observed. This suggests that for low water content, on the timescale covered by this study (~10 -6 s to 1 s), the rotational and transport properties of ethaline aqueous solutions obey classical hydrodynamic scaling despite these systems being presumably spatially microheterogeneous. A fractional scaling is observed in the DES-in-water regime, due to the formation of a maximally freeze-concentrated DES aqueous solution coexisting with frozen water domains at sub-ambient temperature.

Introduction

Recently, deep eutectic solvents (DESs) have received increased attention as an emerging class of solvents. [1][2][3][4][5][6] A majority of DESs are obtained by mixing of an H-bond donor (HBD) (typically an organic molecular component such as an amide, carboxylic acid, or polyol) with an H-bond acceptor (HBA) or with a molecular ionic species. 6 In most frequently studied systems, i.e. type III DESs, the latter consists of a quaternary ammonium salt. For compositions approaching the eutectic point a large decrease of the melting point is obtained, so that DESs form a liquid phase at room temperature. 7,8 This phenomenon can be amplified by non-ideal mixing effects, which are favored by ionic and H-bonding interactions, and specific spatial correlations between the DES constituents. 9,10 Nowadays, DESs are contemplated as cost-effective and sustainable alternatives to classical organic solvents. [3][4][5][6] They present many performant properties, such as low volatility, and high solvating and extracting properties. DESs have been considered for practical applications in a growing number of industrial processes, including extraction, (bio)synthesis, catalysis, electrochemistry, and carbon dioxide capture. 6 The ionic conductivity of DESs makes them good candidates as alternative electrolytes for applications related to energy harvesting and storage. 6,[11][12][13][14][15] Recently, choline chloride-based DESs (i.e. ethaline, reline and aqueous solution of glyceline) have been studied as electrolytes for electrochemical applications, 11,12 redox flow batteries, 13 lithium-ions batteries, 14 and dyesensitized solar cells. 15 From a fundamental point of view, it is striking that the ionic and molecular mobilities of DESs question classical theories. The rotational and translational dynamics of fluorescent dyes have been studied in reline, 16 ethaline, 17 and acetamide-urea DESs. 18 They exhibit fractional viscosity dependence and deviations from the hydrodynamic predictions based on Stokes-Einstein and Stokes-Einstein-Debye theories. These results suggest that the molecular motions of the fluorescent dyes are sensitive to the existence of dynamic heterogeneity in DESs. High frequency (GHz) dielectric relaxation (DR) have also concluded on the deviation from the hydrodynamic predictions for molecular rotation, indicating the critical role of collective reorientation relaxation and H-bond fluctuations in regulating the DR dynamics. 19,20 From the combination of molecular dynamics (MD) simulation and neutron scattering (NS), a microscopic relation was made between transport properties and liquid structure of ethaline. 21 Different translational diffusion and rotational relaxation depending on the DES constituent were observed, and evidence for longlasting dynamic heterogeneity (> 10 ns at 298 K) was inferred from the non-Gaussian character of the van Hove function related to self-diffusion of Chloride anion. Interestingly, dynamic heterogeneities were found to result from the complex interplay of solvation structure and H-bond dynamics. 21 Aiming at a better understanding of the dynamics of DESs, it is worth noting that only a few studies have addressed longer time relaxation processes (i.e. longer than a few ns), so far. [22][23][24] Dielectric spectroscopy (DS) is a perfectly well-suited method because it allows independent measurements of the ionic conductivity and the orientation dipolar dynamics on an extended frequency range. [START_REF] Kremer | Broadband Dielectric Spectroscopy Springer[END_REF] This provides a complementary view on the translation and rotational motions of DES species. 24 Moreover, it bridges the gap from short (~10 -9 to 10 -6 s) to ultra-long timescale (~10 2 s), which are typical for the dynamical range going from a low-viscosity liquid to an amorphous solid. Due to the large depression of the eutectic melting point, DESs are usually liquid on a wide range of temperatures, and in frequent cases, eutectic crystallization can be avoided. This further extends the slowing down of the DES dynamics in the supercooled and glassy states, implying that their dynamics should be studied over many decades. 24,[START_REF] Jani | [END_REF] For ethaline, a comprehensive DS study has shown that the ionic transport and the reorientation dipolar motions were strongly influenced by the glassy dynamics. 24 In addition, it was demonstrated that both dynamics obeyed the same temperature dependence. The origin of this unique scaling has not been clarified yet. It might arise from a direct translational-rotational coupling, such as revolving-door mechanism or be due to the coupling of both dynamics to viscosity. The latter case would imply that hydrodynamics predictions from Stoke-Einstein and Stoke-Einstein-Debye models are fulfilled, thus minimizing the influence of dynamic heterogeneity.

In order to better understand the role of dynamic heterogeneity, an attractive approach would consist in varying gradually the solvation properties and H-bond interactions. Although conceivable in molecular models, this goal is more challenging in experiments. In the present study, we propose to use different hydration levels of DES as control parameters. In fact, water addition is recognized as a way to formulate DES-based solvents with tailored properties. 10,[START_REF] Jani | [END_REF][27][28][29][30][31][32][33][34][35][36][37] More specifically, the structure of DESs is greatly influenced by water in several ways. 10,27,28,36,38,39 Although supramolecular ionic clusters formed by the association of the initial DES components seem resistant to moderate hydration levels in the so-called 'water-in-DES' regime, water molecules often participate in the H-bond complexes of the original DESs as an additional HBD. 38,[40][41][42] The preferential solvation of chloride by water was also reported in choline chloride based DESs. 27,33,43,44 Dielectric relaxation study of aqueous solution of glyceline and reline performed at room temperature and high (microwave) frequencies (0.05 to 89 GHz) indicates that a structural transition occurs for water mole fraction about 0.8, from the homogeneous electrolyte solution to a micro-heterogeneous structure with water-rich and DES-rich pools. 45 The micro-segregation of species into regions of different composition can result in co-continuous structures and mesoscopic length scale heterogeneities. 10,35,36,39,46 In the present study, we have addressed the relative impact of these structural reorganizations on transport properties, dipolar relaxation and glassy behavior. We have performed a dielectric spectroscopy study of the prototypical ethaline DES (choline chloride/ethylene glycol 1:2) and nine different aqueous mixtures thereof, which were recently studied by differential scanning calorimetry (DSC) and neutron scattering. [START_REF] Jani | [END_REF]39 The ionic conductivity and reorientation dynamics were shown to vary by more than 6 decades on the entire studied temperature range 128 -283 K.

In the 'DES-in-water' region, (> 40 wt %), according to the designation introduced by Roldán-Ruiz et al. 36 , an abrupt decoupling between transport properties and dipolar relaxation was observed. This was attributed to phase separation and the formation of a maximally freeze concentrated DES solution during cooling. In the 'water-in-DES' regime, (< 40 wt %), the solution obviously formed a macroscopically homogeneous liquid phase and presented characteristic features of a glassy dynamics, i.e. non-Arrhenius temperature dependence and non-exponential relaxation functions. In this range of composition, temperature, and timescale, this study indicates that only a marginal decoupling between ionic transport and dipolar dynamics is observed.

Methods

Samples.

Choline chloride (>99%) and ethylene glycol (anhydrous, 99.8%) were purchased from Sigma-Aldrich. DES was prepared by weighting and adding ethylene glycol and choline chloride in a molar ratio of 2:1, which is the accepted composition of the eutectic mixture. 47,48 The DES were mixed by mechanical agitation at about 60°C for 30 min until a clear homogeneous liquid phase was obtained and served as stock solutions. Series of 10 working solutions were prepared by pipetting and addition of deionized water, corresponding to regularly spaced values of the mass fraction of water W from 0 to 90 (%wt).

Dielectric Spectroscopy Experiments.

The sample was prepared in parallel plate geometry between two gold-plated electrodes with a diameter of 20 mm and a spacing of 260 m maintained by Teflon spacers. It was placed in the cryostat and maintained under a dry nitrogen atmosphere. The complex impedance of the asprepared capacitor was measured from 1 Hz to 10 6 Hz with a Novocontrol high resolution dielectric Alpha analyzer with an active sample cell. The measurements were performed at thermal equilibrium with a temperature step of 5 K, and covering the temperature range from 283 K to 128 K (10 °C to -145 °C). The temperature of the sample was controlled by a Quatro temperature controller (Novocontrol) with nitrogen as a heating/cooling agent providing a temperature stability within 0.1 K.

Results and discussion

Dielectric permittivity spectra.

The complex dielectric function of the sample 𝜀 * (𝑓) = 𝜀 ′ (𝑓) -𝑖𝜀 ′′ (𝑓) was evaluated for the ten DES samples with different hydration levels, where f denotes the frequency of the electric field, ´ and ´´ the real and loss part of the complex dielectric function and i symbolizes the imaginary unit. The two components are presented in Fig. 1(a) and (b) for a mixture of ethaline with W = 10 wt% of water. Qualitatively comparable spectra were obtained for all the samples. Depending on the temperature and the frequency ranges, different contributions were observed in the instrumental frequency window. At high temperature, the complex dielectric function was dominated by ionic conductivity. This was revealed by a power law term (-1/f) in the intensity of the dielectric loss (cf. blue dashed line with slope -1 in log-log scale in Fig. 1(b)). This ionic conductivity ultimately led to a huge increase of both ´ and ´´ at lower frequency, with deviation of ´´ from the (-1/f) scaling. These phenomena were attributed to polarizations effects due to the blocking electrodes, as usually observed for conducting liquids. They do not hold any useful physical information on the samples and have been excluded from the discussion. In the low temperature range, typically below 210 K, a main peak appeared in the dielectric loss. It was also associated to a jump in the real permittivity ´, as indicated by solid lines and red filled areas in Fig. 1(a) and (b). This was attributed to the dipolar -relaxation process, in agreement with the interpretation made for anhydrous ethaline. The dielectric measurements were analyzed quantitatively by fitting the complex dielectric function by a model including a Havriliak and Negami functions (HN-model), 49 and a conductivity term according to eq. 1.

𝜀 * (𝜔) = 𝜀 ∞ + ∆𝜀 (1+(𝑖𝜔𝜏 𝐻𝑁 ) 𝛼 ) 𝛽 -𝑖 𝜎 𝜔𝜀 0 (1)
where 𝜀 ∞ is the sample permittivity in the limit of high frequency, ∆𝜀 and  are the dielectric strength and the HN-relaxation time of the mode. According to the formalism of the HN-model, the exponent parameters  and  account for the symmetric and the asymmetric broadening of the complex dielectric function with respect to the Debye one.  stands for the DC conductivity of the sample and 𝜀 0 the permittivity of vacuum. The application of this model provided fits of good quality in the temperature and frequency regions where electrode polarization was not significant, as illustrated in Fig. 1. The average relaxation time corresponding to the maximum frequency of the relaxation peak was computed according to

𝜏 = 𝜏 𝐻𝑁 sin ( 𝜋𝑎 2+2𝛽 ) -1 𝛼 ⁄ sin ( 𝜋𝑎𝛽 2+2𝛽 ) 1 𝛼 ⁄ (2)

Ionic conductivity around room temperature

The ionic conductivities measured by fitting the complex dielectric function were found in good agreement with recent measurements reported in the complementary region above room temperature by Lapena et al. 34 These measurements were however limited to pure ethaline and one ethaline-water mixture (8 wt%) as illustrated in Fig. 2a. On increasing the amount of water at a constant temperature (T = 283 K), the conductivity gradually increased until it reached a maximum value for W > 40% as illustrated in Fig. 2b. This non-monotonous behavior has been also observed by molecular dynamics simulations of aqueous reline and ethaline solutions by Celebi et al. 50 The initial increase of conductivities with adding water was attributed to the destabilization of the Hbonds associations between DESs species that resulted in a smaller viscosity and faster transport properties. For W > 40%, DESs constituents were found fully dissolved into a DES-in-water aqueous solution, which implied that the ionic conductivity eventually decreased due to dilution effects. A clear explanation of this dependence on the water dilution can be found in the phase diagram of the ethaline-water system, which was recently determined by calorimetry (cf. Fig. 4). [START_REF] Jani | [END_REF] For W < Wg', the conductivity monotonously increases with the fraction of water. This behavior follows the observations made previously around room temperature, and confirms the plasticizing effect of water. For W > Wg', the opposite dependence of the conductivity with the fraction of water is observed Tc. This is due to the formation of a spatially heterogeneous phase separated system, where the ionic diffusion process that persists in the freeze-concentrated electrolyte is restricted by the coexisting ice matrix. Although the composition of the conducting freeze-concentrated electrolyte (Wg') does not depend on the initial composition W, the overall conductivity of the heterogeneous system decreases as a function of the relative fraction of ice formed.

Reorientational dynamics

The dielectric relaxation times are illustrated in Arrhenius representation in Fig. 5. As for the transport properties, two different behaviors were observed depending on the regime of hydration.

For low hydration levels (W < Wg'), the dipolar relaxation became faster with the addition of water (cf. Fig. 5a). It was accelerated by up to a factor of 100 for the hydration level W = 30 %, with respect to the neat DES. The acceleration of the reorientational dynamics at low hydration level resembles the observation made for the conductivity. As general trends, these observations confirm that the addition of water to DES reduces viscosity and enhances molecular mobility. For high hydration levels (W > Wg'), the dipolar dynamics depended only marginally on the amount of water. Indeed, the relaxation times measured for 6 different compositions essentially felt on a single curve, which extended over 7 decades in time (cf. Fig. 5b). This behavior differs from the ionic conductivity that decreases with W. This apparently contradictory observation finds a clear explanation. The dipolar relaxation probes the reorientational dynamics of the DES solution on a local scale. For W > Wg', the co-existence of ice with the phase forming the maximally freezeconcentrated solution of DES does not affect the rotational dynamics of the DES molecules. This implies that the size of the DES domains is large enough to limit the influence of interfacial effects and to prevent that the molecules can diffuse across a DES domain on the typical timescale of the rotational dynamics. On the contrary, these conditions may not be fulfilled for ionic conduction, which proceeds through translational diffusion of the ionic species.

Glassy dynamics

We now analyze in more details the functional temperature dependence of both dynamics. In all cases, a strong deviation from an Arrhenius behavior was observed. This is demonstrated by the curvature in the Arrhenius plots of the conductivity and the relaxation time shown in Fig. 3 and Fig. 5. This increase of the apparent activation energy during cooling is typical for glassforming liquids and it has been already discussed for neat ethaline. 24 For all the water-ethaline mixture studied, the existence of a glass transition has been actually by demonstrated by DSC. [START_REF] Jani | [END_REF] A complementary estimation of the glass transition temperature has been also evaluated from the present dielectric measurements by extrapolation of the relaxation time to 10 2 s as illustrated in Fig. 5.

The deviations of the dipolar relaxation and conductivity from the Arrhenius behavior were described by the empirical Vogel-Fulcher-Tammann (VFT) law. For the relaxation time, the classical VFT equation is given by Eq. 3, while the modified version corresponding to Eq. 4 is classically adopted for the ionic transport. 24 𝜏 = 𝜏 0 𝑒𝑥𝑝 (

𝐷 𝜏 𝑇 0𝜏 𝑇-𝑇 0𝜏 ) (3)
𝜎 = 𝜎 0 𝑒𝑥𝑝 ( -𝐷 𝜎 𝑇 0𝜎 𝑇-𝑇 0𝜎 ) (4)
In these two equations, 0 and  0 are the pre-exponential factors, Dx and T0x (x = , ) are the strength parameters and the Vogel-Fulcher temperatures associated to the dipolar relaxation and conductivity, respectively. Large deviation from an Arrhenius behavior is characterized by small values of Dx, while an Arrhenius behavior is recovered for large Dx and T0x  0. Satisfactory fits of the experimental relaxation times and conductivities were obtained for the studied range of temperature and water mass fraction as illustrated by solid lines in Fig. 3 and Fig. 5. The deviation of the relaxation time from an Arrhenius behavior has been considered for many decades as a salient feature of most of the glassforming systems in their liquid and supercooled states. It has been recognized as an evidence for the cooperative nature of the structural relaxation. 51 The non-Arrhenian character has been used to define a parameter, named the fragility index m, that categorizes series of glass-forming liquids according to the nature of their dynamics in terms of fragile or strong systems. 52 For ethaline, we found values of the fragility index around m = 48, which corresponds to the type of intermediate system according to this classification. For pure ethaline, Reuter et al. found a slightly larger value of the fragility index (m = 60), which might be attributed to the larger frequency range adopted in that study (10 9 -10 -1 Hz). Interestingly, we observed that the fragility of ethaline decreased with the addition of water, as illustrated in Fig. 6, and then reached a plateau value (m = 40) for water mass fraction larger than W = 40%. The invariance of m in the DES-in-water regime, i.e. for W > 40%, agrees well with the formation on cooling of a maximally freeze-concentrated solution with fixed composition Wg' and dipolar dynamics. In the water-in-DES regime, the possible reduction of fragility of a DES with adding water has never been reported so far, though it can be seen as moderate, if one considers that the entire fragility scale extends from m = 16 for strong liquids to m = 170 for extremely fragile systems.

FIG. 6. Dependence on the water amount of the fragility index (circle) and the stretching exponent of the dipolar relaxation (square).

Another salient observation concerns the deviation of the relaxation function from a simple Debye process. In the time domain, the non-exponential character of the relaxation function of liquids is often expressed by a stretched exponential function, also denoted Kohlrausch-William-Watts function. To conform with this representation, we applied the numerical ansatz that connects the stretching exponent KWW with the HN parameters obtained in the frequency domain i.e.

𝛽 𝐾𝑊𝑊 = (𝛼𝛽) 1 1.23 . 53 The found values of KWW increased from 0.6 to 0.7 with the addition of water, and saturated for mass fraction larger than W = 40%, as illustrated in Fig. 6. In glass forming liquids, the non-exponential character of the structural relaxation is classically attributed to the presence of a distribution of relaxation times. There is a growing number of evidences that this distribution actually reflects the presence of spatially heterogeneous dynamics. 53 Accordingly, it seems counterintuitive, that the addtion of water to DES resulted in apparently more homogeneous reorientational dynamics. From a structural point of view, the addition of water as a competing HBD and solvating agent with respect to the initial DES constituents rather point to the formation of a broader distribution of local environments. 10,27,35,39,46 Therefore, one would have expect a decrease of KWW with increasing W. A possible rationalization is suggested by the concomitant reduction of fragility of the DES with the addition of water. As shown in Fig. 6, the increase of KWW seems correlated to the decrease in the fragility index m. A relationship between fragility and non-exponentiality has been established for numerous very different glass-forming systems. 52 It appears that ethaline and water-ethaline mixtures also obey with this relationship between KWW and m. Their dynamics compare well with other H-bonded liquids, such as polyalcohols, that fall in the category of intermediate and moderately non-Debye liquids (cf. Fig. 3 in ref. 52). Moreover, when adding water the increase of KWW with decreasing m is in qualitative agreement with the linearly decreasing dependence, which was proposed for molecular glassfomers in that study. 52 Supporting pioneering ideas about the concept of cooperativity dynamics, 51 many studies indicate that the glassy slowdown is accompanied by the growing length scale of transient domains. 54,55 In this context, one may speculate that the nanosegregation of DES components with the addition of water, while favoring structural heterogeneity with the formation of domains having distinct composition, would restrict the growth of dynamic cooperativity to values bounded by the domains typical size. 35,39 A microscopic description of cooperative character of the molecular dynamics in DESs would be desirable to test this idea, which shares similarity with the concept cut-off on cooperativity length introduced for nanoconfined liquids. [56][57][58]

Rotation-Translation decoupling

In order to address the (de)coupling of the ionic transport and the reorientation dipolar motions we have compared in Fig. 7 the strength parameter evaluated from VTF fits of both dynamical processes. Same values are obtained for neat ethaline, which is in agreement with the recent study concluded that both dynamics obeyed the same temperature dependence. 24 To overcome the question, we have also represented the conductivity as a function of the relaxation time for a limited selection of temperatures where both processes are measurable simultaneously in the DS spectra, as illustrated in Fig. 8a. It confirms that for W < 40 %, and in this temperature range, both quantities are essentially inversely proportional. This relationship is indicated by a solid line in Fig. 8a. For neat ethaline, this inverse proportionality has been already demonstrated. 24 In this study, the authors concluded that the question remained opened, however, whether the two processes were actually coupled to viscosity, implying that the Stokes-Einstein and Stokes-Einstein-Debye relationships were fulfilled, or that both processes were directly coupled to each other. The latter case was illustrated by the revolving-door or paddle-wheel mechanism, which was also considered for ionic liquids where paths for ions diffusion are opened by the rotation of other dipolar ions. 59 The addition of water to choline based DES is known to modify significantly the hydration shell of chloride anions, which are preferentially solvated by water. 27,33,43,44 The Hbond interactions within the original DESs supramolecular complexes are also affected by water acting as an additional HBD. 38,[40][41][42] For these reasons, it seems unlikely that a persistent revolving- For large water mass fraction (W > 40%), a completely different situation is observed, with a large decoupling between both dynamics. This is illustrated by a sudden jump of the strength parameter of the ionic conductivity from about D = 15 to 60 at W = 40%, which is consistent by the close to Arrhenian behavior of the conductivity shown in Fig. 4b. Likewise, a breakdown of the inverse proportionality is observed, indicating a fractional translational-rotational coupling with 𝜎 ∝ 𝜏 -0.9 , as illustrated in Fig. 8b. This phenomenon provides a clear illustration of the possible effects of strong spatial heterogeneities, the latter being due to the coexistence of domains formed by maximally freeze-concentrated DES aqueous solutions and by solid water.

Conclusion

The existence of dynamic heterogeneity in DESs has been indicated by clear deviations of the rotational-translational dynamics of dye molecules from the Stokes-Einstein-Debye hydrodynamic predictions. The dielectric spectroscopy is a unique method to determine simultaneously the reorientational dynamics of dipolar molecules and the transport properties of ionic species on an extended range of frequency. So far, this method has been barely used for DESs, although a recent study has pointed to the existence of a coupling between both processes for ethaline.

In the present study, we have used the fraction of water in ethaline DES aqueous mixtures, as a varying control parameter of the solvation and H-bond interactions. The reorientational dynamics and the ionic conductivity of ten ethaline solutions were studied in the temperature range 128 - Interestingly, it can be concluded that in this range of composition, temperature, and timescale, the dipolar relaxation and ionic conductivity remained inversely proportional to each other. The persistence of a direct coupling mechanism, where paths for ions diffusion are opened by the rotation of other dipolar ions is improbable. Although such paddle-wheel mechanism was indicted for ionic liquids, and also invoked as a possible process for neat ethaline, it seems unlikely that it remains unaffected despite the important modifications in ion solvation and H-bond interaction induced by the water addition to the DES components. The applicability of the Stokes-Einstein-Debye relation rather indicates that both dynamics are equally coupled to viscosity. This conclusion also implies that the dynamic heterogeneity plays a secondary role in the present experiment situation.

In the DES-in-Water regime, (> 40 wt %), a clear rotation-translation decoupling is observed, including a transition towards a nearly Arrhenius dependence of the ionic transport, and a fractional relation between conductivity and dipolar relaxation with 𝜎 ∝ 𝜏 -0.9 . This behavior is

24

 24

FIG. 1 .

 1 FIG. 1. (a) Real and (b) loss part of the complex dielectric function of a mixture of ethaline with

FIG. 2 . 50 3. 3 . 36 FIG. 3 .

 2503363 FIG. 2. (a) Comparison of the conductivity measured in the present study from the fit of the

FIG. 4 .

 4 FIG. 4. Phase diagram of the DES aqueous mixtures as a function of the water mass fraction.

FIG. 5 .

 5 FIG. 5. Temperature dependence of the relaxation time of aqueous mixtures of ethaline in

FIG. 7 .

 7 FIG. 7. Dependence on the water mass fraction of the strength parameter of the dipolar

FIG. 8 .

 8 FIG. 8. Dependence of the ionic conductivities on their reorientational relaxation times of

  283 K and the MHz-Hz frequency range. Two different regimes were observed depending on the water mass fraction W, which agrees with the published phase diagram of ethaline aqueous solutions. In the water-in-DES regime, (< 40 wt %), the DES aqueous mixtures did not formed classically phase separated systems. The relaxation time and the conductivity presented characteristic features of glassforming systems, including a deviation from Arrhenius temperature dependence and a nonexponential decay of the relaxation function. The addition of water resulted in an acceleration of both dynamics, by up to a factor of 100, indicating a plasticizing effect of water on the DES. Moreover, according to the dipolar relaxation, the addition of water concomitantly reduced the fragility index m and increased the stretching exponent KWW. According to the values of both parameters, ethaline and ethaline-water mixtures fall in the category of intermediate glassforming liquids. The values of KWW and m fulfills the relationship made for intermediate molecular glassforming liquids such as polyalcohols.

Acknowledgments

Support from Rennes Metropole and Europe (FEDER Fund -CPER PRINT2TAN), and the ANR (Project NanoLiquids N° ANR-18-CE92-0011-01) is expressly acknowledged. This work is part of the PhD thesis of A.J. who benefits from a grant from the French Ministry of Higher Education, Research, and Innovation. The authors are grateful to the CNRSnetwork SolVATE (GDR 2035) for financial support and fruitful discussions.

Data Availability

Derived data supporting the findings of this study are available from the corresponding author upon reasonable request.

attributed to the spatially heterogeneous nature of the phase-separated sample, where domains formed by maximally freeze-concentrated DES aqueous solutions coexist with frozen water.