Online Learning of Partitions in Additively Separable Hedonic Games

1 Introduction

A set of computer science students initiates their Bachelor's degree, eager to enhance their learning experience and academic successes by forming study groups during the semester. Initially, with limited information about other students' skills and work habits, the students change their preferences through interactions, making informed decisions to join study groups aligned with their working styles and academic goals. This adaptive process enables them to optimize collaborative learning, leveraging the strengths of diverse groups. The composition of study groups may also evolve over time as students' preferences adapt and factors like schedules and health-related issues affect physical attendance at the university. Such situations and many other real-life scenarios noticed in our social, economic, and politic life, fall within the phenomenon of coalition formation, where agents perform activities in coalitions rather than on their own.

A popular framework for studying coalition formation is that of hedonic games [Dr`eze and Greenberg, 1980], which disregards externalities, i.e., agents' utilities solely depend on the coalition they are part of. The outcome of such games is a set of disjoint coalitions (hereafter, partition). Most of the hedonic games literature considers an offline setting, where a single game is fully available upfront. Yet, in many realistic cases as our study groups example (see, e.g., [Cohen and Agmon, 2023a]), not all agents are initially present, but different subsets of them arrive over time, while their preferences toward other agents are initially unknown and may change.

In this paper, we present and study a new model capturing such real-world scenarios in coalition formation from the perspective of online learning. At each round, a possibly different subset of a given set of agents arrives, that a learner then partitions into coalitions. Only afterwards, the agents' preferences, which possibly alter across time, are revealed. For performance evaluation, we focus on the classic metric of regret [Shalev-Shwartz, 2012]. Prior works on online learning typically consider the static regret [Hazan, 2016], evaluating the learner's decisions against an optimal fixed offline decision. Yet, it is not a suitable measure in dynamic settings such as ours, where the best decision may change frequently. As a remedy, recent studies focus on dynamic regret [Yang et al., 2016], comparing the learner's decisions against the decisions optimal for individual time steps. In our model, the learner's goal is thus minimizing (static or dynamic) regret.

Our study aims to characterize what the learner can attain in terms of static and dynamic regret. First, we prove that nostatic regret is hard to approximate. We show that, if we have an efficient learner, then we can devise an efficient algorithm that approximately solves an offline variant of our problem, proven to be hard to approximate due to Bil`o et al. [2022]. Our result also indicates constant approximation to no-static regret is unattainable in polynomial time. Surprisingly, this result does not apply to the more stringent dynamic regret. To overcome our hardness result, we consider a fractional relaxation of our problem, where agents are fractionally assigned to multiple coalitions. We prove that such a relaxation allows us to obtain a best of both (regret) worlds algorithm that concurrently attains the optimal static and dynamic regret. Our algorithm is derived from a primal-dual formulation for our problem's fractional relaxation. Finally, we provide our main technical contribution: we supply a randomized rounding scheme proven to have an optimal dynamic regret, which converts the fractional solution produced by our above algorithm into an integral one. All omitted proofs can be found in the supplementary materials [Cohen and Agmon, 2024].

2 RelatedWork

Hedonic games have been introduced by Dr`eze and Greenberg [1980], and later expanded to the study of various solution concepts such as stability, fairness, and optimality (see, e.g., [Aziz and Savani, 2016; Woeginger, 2013]). One major concern is designing computationally manageable classes of hedonic games, which led to an abundance of game representations. Some are ordinal and can fully express any preference over coalitions [Bouveret et al., 2010; Elkind and Wooldridge, 2009], yet may require exponential space. In contrast, cardinal hedonic games, based on weighted graphs [Aziz et al., 2019; Bogomolnaia and Jackson, 2002], are not fully expressive, but only require polynomial space for reasonable weights. Our work focuses on additively separable hedonic games [Bogomolnaia and Jackson, 2002], wherein a large body of research considers stability notions [Banerjee et al., 2001; Bogomolnaia and Jackson, 2002; Aziz et al., 2011; Ballester, 2004], while we regard economic efficiency [Aziz et al., 2015; Bullinger, 2020; Elkind et al., 2020].

Our work is closely related to the online version of hedonic games introduced by Flammini et al. [2021], where agents arrive one at a time and should be immediately and irrevocably assigned to coalitions with the goal of maximizing social cost. This problem was then studied by Bullinger and Romen [2023], for which they also recently considered various stability concepts [2024]. Notably, requiring that algorithms exactly know the agents' preferences before making decisions limits practicality as agents may lack enough information to assess their preferences before interacting with others as in our study groups example. In fact, social interactions are complex and relationships often require time to develop. Those works also make a single, immediate and irrevocable assignment for each agent, while assuming that agents' preferences do not change. In contrast, we consider realistic scenarios where preferences dynamically evolve based on interactions, allowing agents to adapt to changing situations. Our repeated game nature allows agents to learn the coalitions proven most relevant and effective for them.

We offer a novel framework that mitigates those issues by studying coalition formation from the viewpoint of online learning. Our study contributes to the research trend on online learning in combinatorial domains such as online task allocation [Cohen and Agmon, 2023b], submodular optimization [Hazan and Kale, 2012; Krause and Golovin, 2014], matching markets [Zhang et al., 2022; Maheshwari et al., 2022], clustering [Christou et al., 2024; Fotakis et al., 2021], bandits [Tekin and Van Der Schaar, 2015], online inventory problems [Hihat et al., 2023] and many more. Our fractional relaxation technique is a common approach for handling impossibilities, proven fruitful for combinatorial online learning problems (see, e.g., [Gergatsouli and Tzamos, 2022]), and many other problems such as matchings [Aziz and Klaus, 2019] and fair division [Amanatidis et al., 2023]. Our algorithm for this relaxation is also related to online learning primal-dual methods, which were applied in, e.g., bandits

[Li et al., 2021; Tirinzoni et al., 2020]. Note that primaldual analysis is also used in many other (online) domains beyond online learning (e.g., online matchings [Ekbatani et al., 2023]). Yet, as far as we know, we are the first to study online learning in hedonic games, providing algorithms proven to have optimal regret.

In this context, most related to our work are matching markets, which can be seen as a constrained variant of hedonic games where coalitions are restricted to be of size at most 2. Unlike our work, the input instances are also limited to be bipartite, while either only one side must have preferences over the other one [Maheshwari et al., 2022], or both sides have preferences over each other [Jagadeesan et al., 2021; Zhang et al., 2022]. Some works study learning matchings with monetary transfers [Liu et al., 2020; Sankararaman et al., 2021]. Yet, our setting is more challenging as it is not limited to matchings and monetary transfers are not available.

Those studies and ours are also connected to online convex optimization (see [Shalev-Shwartz, 2012; Hazan, 2016] for surveys). Its classic performance measure is the static regret, evaluating the learner's decisions against a single optimal decision in hindsight. Over the past decades, various algorithms, such as online gradient descent (OGD) [Zinkevich, 2003; Hazan et al., 2007], have been proposed to yield (optimal) sub-linear regret under different scenarios. However, in real-life scenarios such as our dynamic context the optimal decision drifts over time. Hence, algorithms that guarantee decisions close to a static one may perform poorly in dynamic settings. As a remedy, the dynamic regret has recently become a popular metric [Zinkevich, 2003; Besbes et al., 2015; Zhang et al., 2017], comparing the learner's overall loss against a comparator sequence of solutions optimal for individual time steps. Due to the arbitrary fluctuation in the loss functions, it is well-known that the worst-case dynamic regret scales linearly in the number of rounds T [Yang et al., 2016], unless some restrictions are imposed [Jadbabaie et al., 2015].

Yet, the dynamic regret can be bounded by certain regularities of the comparator or function sequences. A natural regularity is the path-length [Zinkevich, 2003], denoted as S T ⋆ , reflecting the fluctuation of online optimal decisions. When known in advance, Zinkevich [2003] shows OGD has a dynamic regret of O(√T(1+S T ⋆ )) for convex functions, that can be improved to O(S T ⋆ ) for smooth functions that are either strongly convex [Mokhtari et al., 2016], or convex with minimizers lying in the decision set's interior [Yang et al., 2016]. For the latter, Yang et al. [2016] prove that O(S T ⋆ ) dynamic regret is optimal. Another regularity is the temporal variability [Besbes et al., 2015; Baby and Wang, 2019], capturing the function values' variation.

In our work, we present the interaction term, a novel regularity measuring the variation in agents' interactions, which holds the potential of expanding the research on online learning within computational social choice in general. Further, our problem falls under the learning from expert advice problem, wherein the well-known multiplicative weights update (MWU) method is no-regret [Hazan, 2016]. However, MWU cannot be applied to our setting due to its demanding time and space requirements: MWU maintains different weights for all possible partitions, which form a space exponential in the number of agents. This required us to devise new methods that can solve our problem efficiently.

3 Online Learning in Hedonic Games

We consider an online learning variant of additively separable hedonic games (ASHGs), where different subsets of a given agents set dynamically arrive across T rounds, while possibly changing their preferences over time. We study the most general setting, where an online learning algorithm (hereafter, learner) maintains a partition of the agents into disjoint subsets (i.e, coalitions) over time, while interacting with an adversary that controls both the agents' composition and their preferences across time without posing any restrictions on their behaviour. Formally, the input to our problem is given by a finite set N = {1, . . . , n} of n agents. For x ∈ N, we hereafter denote [x] := {1, . . . , x} and [0] = {0}. At each time t ∈ [T ], the learner and the adversary interact according to the following protocol. The adversary first picks a subset N t ⊆ N of nt := |N t | agents that are present in the game at time t, capturing (worst-case) adversarial arrivals. Without loss of generality, we assume that N t ̸= ∅ at any time t.

Afterwards, the learner selects a partition πt of the agents in N t , where we denote |πt | as the number of its coalitions and πt (i) as the coalition C ∈ πt such that i ∈ C. We focus on real-life scenarios where the number of coalitions and the size of each coalition are bounded. Fixing positive integers α ≤ n and k ≤ n before any agent arrives, we assume that the learner chooses an (α, k)-partition πt at each time t, i.e., |πt | ≤ k and |C| ≤ α for each coalition C ∈ πt . We denote the collection of all (α, k)-partitions at time t as Πtα,k .

Only after the learner picks a partition, the adversary reports the preferences of each agent i ∈ N t . While her preferences are usually given as her utility from others, for the sake of the analysis we represent them by an analogous cardinal disutility dti : N t → R with dti (i) = 0, specifying that agent i assigns a disutility of dti (j) ∈ R to any agent i ̸= j ∈ N t which indicates the degree of her dislike for agent j. Essentially, it is the negation of agent i's utility. We denote the agents' joint disutility at time t as dt = (dti )i∈N t .

Remark 1. (Valuations' Evolution) For any pair of agents i, j ∈ N t that were also present during some time t′ < t (i.e., i, j ∈ N t′ ), note that dti (j) may not be equal to dt′ i (j). This models scenarios where the agents' social interactions at different time instants may yield an (adversarial) alteration in their preferences. However, an agent's valuations may remain unchanged over time, i.e., each agent i ∈ N may have a fixed disutility di : N → R with di(i) = 0 such that her utility at time t for any agent j ∈ N t is simply dti (j) = di(j).

For obtaining (cardinal) preferences over coalitions, individual disutilities are aggregated via their summation. That is, we denote by N t i the set of coalitions agent i ∈ N t belongs to, i.e., N t i = {C ⊆ N t : i ∈ C}. Agent i's disutility can be then additively aggregated to preferences over each coalition C ∈ N t i via dti (C) = ∑j∈C dti (j). We further denote by dti (πt ) = dti (πt (i)) the disutility agent i receives from the partition πt chosen by the learner, which induces the partition πt 's disutility profile dt (πt ) := (dti (πt ))i∈N t .

After the agents' valuations are revealed, the learner incurs the social cost of the partition πt , which is defined by the sum of all agents' disutilities for that partition. Intuitively, the social cost indicates the agents' overall dissatisfaction with the partition. Formally, for a coalition C ⊆ N t , we let sc(C, dt ) = ∑i∈C dti (C) be the social cost of C w.r.t. dt . The social cost of the partition πt w.r.t. dt is sc(πt , dt ) = ∑C∈πt sc(C, dt ) = ∑i∈N t dti (πt ). Hence, a partition π of the agents in N t is cost-minimal if it minimizes the social cost amongst all possible partitions, i.e., π ∈ argminπ′∈Πtα,k sc(π′ , dt ). We can thus summarize the learner-adversary interaction protocol as follows:

1. At each time t, the adversary picks the subset of agents N t ⊆ N that are present in the game at time t.
2. The learner then selects an (α, k)-partition πt of N t .
3. Afterwards, the adversary reports the joint disutility profile dt = (dti )i∈N t for the agents in N t .
4. The learner incurs a social cost of sc(πt , dt ).

We study an online learning problem, termed as (α, k)- Online Partitions ((α, k)-OP), which is defined as follows. At each time t, based on the agents' past joint disutilities {dτ }τ∈[t-1], the learner's goal is choosing an (α, k)-partition πt at time t such that the learner's cumulative social cost over time is close to the overall social cost of the cost-minimal partitions. The standard metric for online learning algorithms is the static regret [Shalev-Shwartz, 2012], which compares the learner's decisions against the optimal decision in hindsight. In our context, the optimal decision is a single partition of all n agents minimizing the learner's cumulative social cost over time. Formally, we denote the set of all (α, k)-partitions of the agents in N as Π. Given a partition π ∈ Π, we can obtain an (α, k)-partition π ∩N t := (C ∩N t )C∈π:C∩N t ̸=∅ of the agents present at time t (i.e., N t ). Note that π ∩N t is not necessarily cost-minimal at time t. Further, if the bounds on the number of coalitions and their size are bounded such that α · k < n, then not all the agents in N are assigned to a coalition in π. In this case, if the partition π ∩ N t contains any empty coalition at time t, we use the convention that dti (∅) = 0 for each agent i ∈ N t . As such, the learner's single optimal decision in hindsight is any partition π ∈ arg minπ′∈Π ∑Tt=1 sc(π′ ∩ N t , dt ).

Next, we present the formal definition of static regret. First, we denote the absolute maximum value of a non-zero singleagent disutility as W := maxt∈[T],i,j∈N t :dti (j)̸=0 |dti (j)|. If the learner's overall social cost is at most c > 0 times the total social cost of a single optimal (offline) partition up to an additive term that is sublinear in T, then the learner is said to be no-c-regret. Formally, the learner is no-c-regret (c > 0) if and only if, for any sequence of agent sets {N t }t∈[T] and joint disutility profiles {dt }t∈[T ] that are chosen by the adversary, the partitions {πt }t∈[T] selected by the learner satisfy:

where δ < 1. If c = 1, then the learner is called no-regret. However, since the static regret benchmarks the learner with a single fixed partition, it fails to accurately assess the quality of decisions in our dynamic setting. Namely, the minimum social cost is not static, but it changes dynamically as both the agents' composition and their preferences evolve over time. The stronger notion of dynamic regret naturally reflects this concept, allowing us to measure the performance difference between the learner and a set of partitions optimal for individual time instants in hindsight [Jadbabaie et al., 2015]. Formally, for c > 0, the learner's c-dynamic regret for his selected partitions {πt }t∈[T] is given by:

where πt⋆ is a cost-minimal partition w.r.t. dt . For c = 1, we obtain the standard dynamic regret RT := RT1 . No-cdynamic regret is defined similarly to (1).

4 Hardness of Being No-c-Regret

Though certain domains admit no-static regret algorithms (see, e.g., [Zinkevich, 2003]), we begin with proving that it is hard to approximate in our context, despite that it is weaker than dynamic regret. The key idea is that if we have a good efficient learner, then we can obtain an efficient algorithm that approximately solves an offline variant of our problem, proven to be hard to approximate due to Bil`o et al. [2022]. Formally, our strong negative result holds even for a restricted version of (α, k)-OP termed as (α, k)-OP=, where, at any time t, there are exactly nt = α · k agents and a partition must contain exactly k coalitions, each containing exactly α agents. We also consider the following offline variant, where the subsets of agents and their valuations are available upfront:

Definition 1. (Offline (α, k)-OP=) Given a sequence of B agent sets {N b }b∈[B] with |N b | = αk for any b ∈ [B] and corresponding joint disutility profiles {db }b∈[B], select an (α, k)-partition π of N = ∪b∈[B]N b with exactly k coalitions, each containing exactly α agents, such that ∑Bb=1 sc(π ∩ N b , db ) is minimized. For any b ∈ [B], note that π ∩ N b is an (α, k)-partition, but it is not required to contain exactly k coalitions, each with exactly α agents. Denoting π⋆ as the optimal partition minimizing this objective, a c-approximation algorithm for offline (α, k)-OP= returns an (α, k)-partition π such that ∑Bb=1 sc(π ∩N b , db ) ≤ c · ∑Bb=1 sc(π⋆ ∩ N b , db ) in polynomial time.

To go from our learning problem to the combinatorial offline (α, k)-OP= problem, we perform the following approximation preserving reduction from (α, k)-OP= to offline (α, k)-OP= that will imply our main result:

Lemma 1. Any (randomized or deterministic) no-c-regret algorithm for (α, k)-OP= yields a (c+1)-approximation algorithm for offline (α, k)-OP=.

Proof. As deterministic algorithms are a special case of randomized ones, we focus on the latter. Consider any randomized no-c-regret algorithm A for (α, k)-OP=. For an instance of offline (α, k)-OP= given by a sequence of agent sets N := {N b }b∈[B] and their joint disutilities D := {db }b∈[B], we devise the algorithm A′ that simulates this instance online over some T > 0 rounds using algorithm A as follows. First, A′ picks τ ∈ [T] uniformly at random. Then, it runs an adversary that, at each time t ∈ [T], selects uniformly at random a set of agents N t and its corresponding joint disutility dt . Let πt and π ∈ Π be the random partition returned by A at time t and the random offline optimal solution (resp.). The algorithm A′ returns the partition πτ . Since A is no-c-regret: ∑Tt=1 1B ∑Bb=1 E[sc(πt , db )] ≤ c · TB ∑Bb=1 E[sc(π ∩ N b , db )] + Θ(poly(n,W) · T δ ), where δ < 1 and the expectation is over the randomness of A and the adversary. Thus, the expected social cost of A′ is at most: 1 T ∑Tt=1 ∑Bb=1 E[sc(πt , dt )] = BT ∑Tt=1 1B ∑Bb=1 E[sc(πt , dt )] ≤ cB T · TB ∑Bb=1 E[sc(π ∩ N b , dt )] +Θ(poly(n,W) · T δ-1 ). As T was arbitrary, setting T = Θ(poly(n,W)1/(1-δ) ) yields that A′ is a (c + 1)- approximation algorithm for offline (α, k)-OP=.

We can now obtain our computational hardness results. We remark that they hold even for simple games, where, at any time t, the disutility of each agent i ∈ N t for any other agent i ̸= j ∈ N t satisfies dti (j) ∈ {0, -1}.

Theorem 1. When k is not constant, assuming the Exponential Time Hypothesis (ETH), there does not exist a no(n1/ log logβ n - 1)-regret algorithm for (α, k)-OP=, where β > 0 is a universal constant independent of n. Further, assuming that there is a constant ε > 0 s.t. no subexponentialtime algorithm can distinguish between a satisfiable 3SAT formula and one which is only (1-ε)-satisfiable (also known as Gap-ETH), there does not exist a no-(nf(n) - 1)-regret algorithm for (α, k)-OP= for any function f ∈ o(1). Both results hold even for simple games.

Proof. (Sketch) The proof readily follows via combining Lemma 1 with Theorem 11 by Bil`o et al. [2022], and is thus deferred to Appendix A. First, we show that Theorem 11 by Bil`o et al. [2022] can be applied to offline (α, k)-OP= with B = 1 by proving that it is a variant of the problem considered by Bil`o et al. [2022]. Combining this observation with Lemma 1 establishes our hardness results. We also note that Theorem 11 by Bil`o et al. [2022] is obtained by reduction from the Densest β-Subgraph (DβS) problem, known to be hard to approximate [Manurangsi, 2017]. For completeness, in Appendix A we supply our reduction from DβS to offline (α, k)-OP= that, combined with Lemma 1 and [Manurangsi, 2017, Corollary 1.3], gives an alternative proof.

Remark 2. As (α, k)-OP= is a subproblem of (α, k)-OP, Theorem 1 also holds for the latter. As it is well-known that the worst-case dynamic regret scales linearly in T, we show in Appendix B that a no-c-dynamic regret algorithm is unattainable for any c > 0. Hence, Theorem 1 does not apply to dynamic regret. Since we posed no restriction on the agents' disutilities, our result also holds when they remain unchanged over time (see Remark 1).

This establishes the possible regret bounds and indicates that constant approximation to no-static regret cannot be attained in polynomial time for (α, k)-OP when α is bounded

(i.e., α < nt at each time t). Thus, our result motivates us to assume the following most general setting:

Assumption 1. The coalition size bound α is unbounded at each time t (i.e., α = n), in which case we term the (α, k)-OP problem as k-OP for short. We also assume that k ≥ 2 since the case of k = 1 is trivial.

Next, we devise online learning schemes that attain nontrivial regret bounds in polynomial time. Initially, we consider a fractional relaxation of our problem, where agents are fractionally assigned to multiple coalitions (Section 5), for which we devise a no-static regret learner that simultaneously has low dynamic regret (Section 5.1). In fact, our algorithm is best of both (regret) worlds: it is optimal in terms of both static and dynamic regret. We then give an efficient randomized rounding scheme with optimal dynamic regret that converts the fractional partitions produced by our algorithm into integral ones (Section 6).

5 Fractional Online Partitions

In this section, we consider fractional k-OP, the fractional relaxation of our problem where agents are allowed to be part of several coalitions by being fractionally assigned to multiple coalitions. This approach is common in numerous related problems (e.g., matchings [Aziz and Klaus, 2019] and fair division [Amanatidis et al., 2023]), and has been proven fruitful for overcoming impossibilities as the one in Theorem 1. This setting also has many real-life applications. For instance, a company manager may assign his employees to several project teams, where a fractional assignment models the amount of time an employee spends working on each project. Later, we show that such relaxation leads to a no-regret algorithm, proven to attain optimal static and dynamic regret.

Fractional k-OP (k-FOP) is defined as follows. First, we denote the k-dimensional simplex as ∆k = {y ∈ Rk≥0 : ∑ℓ∈[k] yi,ℓ = 1}. At each time t, after the adversary picks the subset of agents N t , the learner selects a vector yt i = (yt i,ℓ )ℓ∈[k] ∈ ∆k for any agent i (i.e., a agent i's fractional assignment), where yt i,ℓ stands for the fraction of agent i assigned to the ℓ-th (possible) coalition for each ℓ ∈ [k]. We term yt = (yt i )i∈N t as the fractional partition. Afterwards, the adversary reports the joint disutility profile dt = (dti )i∈N t for the agents in N t . Let 1xti,ℓ>0 be equal to 1 if xti,ℓ > 0, and 0 otherwise. The learner then incurs the fractional social cost fsc(yt , dt ), which is the optimal value of the following convex linear program:

where the minimum is over the fractional partition xt = ((xti,ℓ )ℓ∈[k])i∈N t . The intuition behind problem (3)'s objective is that, if agent i is fractionally assigned to the ℓ-th coalition (i.e., xti,ℓ > 0), then she receives a disutility of xtj,ℓdti (j) from each agent i ̸= j ∈ N t . Thus, given the fractional partition yt selected by the learner of the agents in N t with the joint disutility dt chosen by the adversary, problem (3) picks xt for minimizing its objective such that xti,ℓ ≤ yt i,ℓ for any agent i ∈ N t and ℓ ∈ [k]. Since the learner chooses the fractional partition before observing the agents' valuations, he can solve (3) for obtaining the agents' fractional assignments only after the disutilities are revealed.

Once the agents' assignment vectors are integral (i.e., xti,ℓ ∈ {0, 1}), each agent can be assigned to at most one coalition. This reduces k-FOP to the original k-OP problem, in which case the fractional social cost equals to the original social cost. Thus, we infer the following relation:

Lemma 2. For any sequence of agent sets {N t }t∈[T] and joint disutility profiles {dt }t∈[T], the social cost of a costminimal partition πt⋆ for k-OP at each time t is lower bounded by the fractional social cost of the optimal fractional partition yt⋆ for the corresponding k-FOP problem, i.e., sc(πt⋆ , dt ) ≥ fsc(yt⋆ , dt ).

Commonly used methods for solving problems such as kFOP are based on online gradient descent (OGD) [Hazan, 2016]. Such algorithms use the subgradients of the problem's objective function, which are defined as follows:

Definition 2. (Subgradients) For a function g : Rm → R, a vector z ∈ Rm is a subgradient of g at point y ∈ Rm if and only if g(y′ ) ≥ g(y) + z⊤(y′ -y) for any y′ ∈ Rm. The set of g's subgradients at point y ∈ Rm is denoted as ∂g(y).

Generally, calculating subgradients is computationally challenging. However, we show that they can be easily attained for our problem (3) by solving a new primal-dual program, which we obtain in Lemma 3 by following the common approach for solving constrained optimization problems via their Lagrangian relaxed form.

Lemma 3. Given the set N t of nt agents, their valuations dt , the fractional partition yt and the fractional assignment xti of each agent i ∈ N t , the Lagrangian relaxation of (3) at time t gives the primal-dual optimization problem given by the following convex linear program:

where the minimum is over the Lagrangian multipliers λt ∈ Rnt ≥0 , µt ∈ Rnt×k ≥0 and γ t ∈ Rnt×k ≥0 .

Proof. (Sketch) In Appendix C, we consider the Lagrangian function L(xt , yt , λt , γ t , µt ) of (3) and the Lagrangian dual function g(λt , γ t , µt ) = infxt L(xt , yt , λt , γ t , µt ). We find the supremum by computing the gradient ∇xtL(xt , yt , λt , γ t , µt ) w.r.t. yt and solving ∇xtL(xt , yt , λt , γ t , µt ) = 0. The latter gives us the constraints in (4), whose substitution to the Lagrangian function yields that the objective of our primal-dual problem is g(λt , γ t , µt ) = ∑i∈N t λti - ∑i∈N t ∑ℓ∈[k] µti,ℓ · yt i,ℓ .

Next, we show how the subgradients in ∂ fsc(yt , dt ) can be easily computed using the optimal solution to the optimization problem in (4). We also supply an upper bound on the subgradients, which depends on m := maxt∈[T] |N t | (i.e.,

Algorithm 1 : Online Gradient Descent for k-FOP

Input: A constant step size η > 0

• 1: The learner initializes z1i as z1 i,ℓ = 1/k ∀i ∈ N, ℓ ∈ [k].
• 2: for each time t ∈ [T] do
• 3: The adversary picks the agents N t arriving at time t.
• 4: The learner picks yt i,ℓ = zt i,ℓ ∀i ∈ N t , ℓ ∈ [k].
• 5: The adversary reports the agents' disutilities dt .
• 6: The learner incurs fsc(yt , dt ).
• 7: The learner solves (3) and obtains xt⋆,i ∀i ∈ N t .
• 8: Given xt⋆,i and yt , the learner solves (4) to attain µt⋆ .
• 9: The learner sets gt = ((-µt⋆,i,ℓ )ℓ∈[k])i∈N t .
• 10: The learner picks yt+1 = P∆k (yt - ηgt ).
• 11: The learner sets zt+1 i as yt+1 i if i ∈ N t , and yt i o.w.

the maximum number of agents that are present at a single time instant), and the absolute maximum value W of a nonzero single-agent disutility (as defined before (2)).

Lemma 4. Given a set N t of nt agents and their valuations dt at time t, let λt⋆ , µt⋆ , γ t⋆ be the optimal solution of the problem (5) with respect to a fractional partition yt and a fractional assignment xt . Then, for any fractional partition ˆyt and fractional assignment ˆxt : fsc(ˆyt , dt ) ≥ fsc(yt , dt ) + ∑ℓ∈[k] ∑i∈N t (-µt⋆,i,ℓ ) · (ˆ yt i,ℓ - yt i,ℓ ). Further, the subgradients are upper bounded by: | - µt⋆,i,ℓ | ≤ (m- 1)W.

5.1 A Best of Both (Regret) Worlds Algorithm

We are now ready to present our algorithm for k-FOP (Algorithm 1), which is no-regret while also providing low dynamic regret. Our algorithm provides the best of both (regret) worlds: it simultaneously achieves optimal static and dynamic regret. Algorithm 1 uses a modified variant of online gradient descent (OGD) [Zinkevich, 2003], and is parameterized by a constant η > 0. We will later provide the suitable selections of η that yields low regret. Algorithm 1 runs as follows. The learner first initializes a fractional partition z1 = ((z1 i,ℓ )ℓ∈[k])i∈N that splits each agent equally among the k possible coalitions (i.e., z1 i,ℓ = 1/k for each agent i ∈ N and ℓ ∈ [k]). At each time t, the adversary first selects the arriving agents N t and the learner responds with yt = ((zt i,ℓ )ℓ∈[k])i∈N t . The adversary then selects the agents' disutilities dt and the learner incurs the fractional social cost fsc(yt , dt ).

Given the learner's obtained information, the learner can readily solve the convex linear program (3) using standard methods and obtain the optimal fractional assignment xt⋆,i of each agent i ∈ N t . The learner can then easily solve the convex linear program (4) via classic approaches and receive its optimal solution λt⋆ , µt⋆ , γ t⋆ . Using Lemma 4, the learner computes the corresponding subgradient. Finally, the learner computes the fractional partition yt+1 at time t + 1 by performing a gradient descent step w.r.t. the subgradient gt = ((-µt⋆,i,ℓ )ℓ∈[k])i∈N t corresponding to the current solution yt , where P∆nk (·) denotes the projection onto the nearest point in ∆nk . Finally, for any agent i ∈ N, the learner updates agent i's zt+1 i as yt+1 i if i ∈ N t , and yt i otherwise.

In Theorem 2, we show that Algorithm 1 is no-regret for a proper choice of η > 0. Note that an offline optimal decision for k-FOP is given by a fractional partition y, from which we can derive a fractional partition y|N t := (yi)i∈N t at time t.

Remark 3. At each time t, as zti = yt i for any i ∈ N t , note that the fractional social cost induces a loss function ft : ∆nk →Rgiven by ft(zt ) = fsc(zt |N t , dt ) = fsc(yt , dt ).

Theorem 2. For any sequence of agent sets {N t }t∈[T] with joint disutilities {dt }t∈[T] that are chosen by the adversary, the learner is no-regret when producing the fractional partitions {yt }t∈[T] using Algorithm 1 with η = √log(n) (m-1)W √2T , and the learner also obtains a minimax optimal static regret bound of O(2(m - 1)W √2T log(n)).

Proof. (Sketch) By Lemma 4 and using the triangle inequality, note that for any pair of fractional partitions yt , ˆyt : | fsc(yt , dt ) - fsc(ˆyt , dt )| ≤ | ∑ℓ∈[k] ∑i∈N t µt⋆,i,ℓ (ˆ yt i,ℓ - yt i,ℓ )| ≤ ∑ℓ∈[k] ∑i∈N t |µt⋆,i,ℓ |·|ˆ yt i,ℓ-yt i,ℓ | ≤ (m-1)W∥ˆytyt ∥1, where ∥ · ∥1 is the L1-norm. That is, fsc(·, dt ) is L-Lipschitz w.r.t. ∥ · ∥1 for L := (m - 1)W. In Appendix E, we show that this also applies to ft(·) from Remark

1. Hence, setting η = √log(n) L√2T , Corollary 2.14 by ShalevShwartz [2012] yields the desired static regret bound when applying it to the sequence of loss functions {ft}t∈[T].

Though no-static regret is hard to approximate for the original k-OP problem by Theorem 1, note that our obtained O(√T ) static regret is minimax optimal due to Abernethy et al. [2008] (i.e., the minimal static regret that can be attained in the worst case for convex programs).

Remark 4. Observe that the bound's dependence on W indicates that, if the agents' disutilities fluctuate moderately over time (or even remain unchanged as discussed in Remark 1), then the static regret is reduced.

Despite that we reached the minimax optimal static regret, recall that dynamic regret is still more suitable for evaluating the performance of the learner in our dynamic setting. Hence, we now focus on dynamic regret. It is well-known that the worst-case dynamic regret scales linearly in T since the agents' valuations arbitrarily fluctuate. Yet, it is possible to bound the dynamic regret in terms of certain regularities. We herein consider the path-length of the optimal sequence of fractional partitions [Zinkevich, 2003], given by S T ⋆ := ∑tt=2 ∥yt⋆ -yt-1 ⋆ ∥2, capturing the overall Euclidean norm of the difference between two successive solutions.

In Theorem 3, we show that Algorithm 1 is not only noregret, but it also has an optimal dynamic regret.

Theorem 3. For any sequence of agent sets {N t }t∈[T] with joint disutilities {dt }t∈[T] that are chosen by the adversary, the fractional partitions {yt }t∈[T] produced by the learner using Algorithm 1 with η = 1 2L for any constant L > 0 yield an optimal dynamic regret bound of O(S T ⋆ ).

Proof. (Sketch) In Appendix F, we first show that fsc(yt , dt ) is convex as a function of yt since it can be expressed as a linear function of yt . Then, we prove that it is L-smooth for any constant L > 0, i.e., as it twice differentiable, we show that z⊤∇2 fsc(yt , dt )z ≤ L∥z∥22 for any pair of fractional partitions yt , z and constant L > 0. Thus, ft(·) from Remark 3 is also convex and L-smooth. By setting η = 1 2L , the conditions of Theorem 3 by Yang et al. [2016] and we obtain the desired dynamic regret bound, when applying it to the sequence of loss functions {ft}t∈[T]. Since fsc(yt , dt ) is a linear function of yt , then it is not strongly convex (see Appendix G for a proof). Due to Proposition 1 by Yang et al. [2016], our dynamic regret of O(S T ⋆ ) is optimal for smooth and (non-strongly) convex functions.

Remark 5. We conclude that, if the learner runs Algorithm 1 with η as in Theorem 2, then the learner simultaneously obtains the optimal static and dynamic regret since we can invoke Theorem 3 as η = 1 2L for L = (m-1)W √2T 2√log(n) . Recall that no-dynamic regret is generally unattainable. However, if the optimal fractional partition only slightly changes between consecutive time steps, then our dynamic regret bound O(S T ⋆ ) can become smaller. For instance, if ∥yt⋆ -yt-1 ⋆ ∥ = Ω(1/√T) for each time t, then S T ⋆ = Ω(√T).

6 Randomized Rounding for k-OP

Recall that static regret not only fails to accurately reflect the learner's performance in dynamic environments, no-regret is also hard to approximate for k-OP due to Theorem 1. Hence, in this section we focus on the more stringent dynamic regret, which is also more suitable for our dynamic setting. Using standard randomized rounding techniques, we next show how the resulting fractional partition produced by Algorithm 1 can be converted into a randomized integral partition, while obtaining the optimal dynamic regret bound. Formally:

Mechanism 1. (Randomized Rounding) Given η > 0 as input, run Algorithm 1 with η. At any time t, given the fractional partition yt , we can obtain an integral partition πt via randomized rounding: If a fraction yt i,ℓ of agent i is assigned to the ℓ-th coalition, then agent i is assigned to the ℓ-th possible coalition with probability yt i,ℓ (Recall that ∑ℓ∈[k] yt i,ℓ = 1 for any agent i ∈ N t ). Note that decisions are independent among different agents and different time instants.

Our bound in Theorem 4 involves a new regularity metric for dynamic regret, called the interaction term, measuring the overall difference between the agents' disutilities from their interactions according to the fractional partition yt and the respective optimal solution xt of (3) at each time t. Namely, the interaction term is given as I T = ∑Tt=1 ∑i∈N t ∑ℓ∈[k] ∑i̸=j∈N t |[yt i,ℓ yt j,ℓ - 1xti,ℓ>0 · xtj,ℓ ]dti (j)|, which is at most O(T) (in the worst-case) as |yt i,ℓ yt j,ℓ -1xti,ℓ>0 · xtj,ℓ | ≤ 1 and |dti (j)| ≤ W. Intuitively, at time t, yt i,ℓ yt j,ℓ can be viewed as the probability that any pair of agents i, j are assigned to the ℓ-th possible coalition for any ℓ ∈ [k] (i.e., they form an interaction), where yt i,ℓ yt j,ℓdti (j) is agent i's resulting fractional disutility from their interaction. Similarly, 1xti,ℓ>0 · xtj,ℓ can be interpreted as the assignment probability of agent j to the ℓ-th coalition at time t, given that agent i is assigned to that coalition with a positive probability (i.e., xti,ℓ > 0), while agent i's resulting fractional disutility from their interaction is 1xti,ℓ>0 · xtj,ℓdti (j).

Theorem 4. For any sequence of agent sets {N t }t∈[T] with joint disutilities {dt }t∈[T] that are chosen by the adversary, the fractional partitions {yt }t∈[T] produced by the learner using Mechanism 1 with η = 1 2L for any constant L > 0 yield an optimal dynamic regret bound of I T +O(S T ⋆ ).

Proof. (Sketch) In Appendix H, we first prove ∑Tt=1 E[sc(πt , dt )] ≤ I T + ∑Tt=1 fsc(yt , dt ), from which the bound is obtained by Theorem 3. For optimality, we show that a sublinear dynamic regret is unattainable if the the path length is unconstrained (i.e., it is upper bounded by Ω(T)). However, if the path length is at most o(T), then we prove that it is impossible to get a better dynamic regret bound of I T +O((S T ⋆ )ψ ) for ψ ∈ (0, 1).

Remark 6. We obtained the following groundbreaking result: while no-static regret is hard to approximate for integral partitions (but the minimax optimal static regret is attainable for fractional ones), the more stringent dynamic regret can be solved optimally in both the fractional and integral settings. Recall that no-dynamic regret is generally unfeasible. Yet, if the optimal fractional partition and the agents' interactions only slightly change between consecutive time steps, then our dynamic regret bound can become smaller. For instance, if ∥yt⋆ - yt-1 ⋆ ∥ = Ω(1/√T) and |[yt i,ℓ yt j,ℓ - 1xti,ℓ>0 · xtj,ℓ ]dti (j)| = Ω(1/m2k√T) for each time t, agents i ̸= j and ℓ ∈ [k], then I T +S T ⋆ = Ω(√T).

7 Conclusions and FutureWork

In this paper, we presented a novel algorithmic framework for studying coalition formation in dynamic settings from the perspective of online learning. We characterized the learner's capabilities in terms of both static and dynamic regret, obtaining the following remarkable results. While no-static regret is hard to approximate for integral partitions, dynamic regret is not. However, for a fractional relaxation of our problem, we devised an algorithm that concurrently has optimal static and dynamic regret, thus achieving the best of both (regret) worlds. Unlike static regret, the more stringent dynamic regret can be also solved optimally for integral partitions. Further, we presented the interaction term, a new regularity for bounding dynamic regret that reflects the variation in agents' interactions, and has the potential of expanding the research on online learning in computational social choice.

Our research paves the way for many future works. Immediate directions are the investigation of other classes of hedonic games and other adversaries. Further, as in many realworld domains preferences may be inherently uncertain, future work warrants developing algorithms for online learning in hedonic games under partial and possibly noisy feedback. Another intriguing direction is considering other measures of economic efficiency (e.g., Pareto-optimality) as well as other solution concepts, such as stability and fairness notions.

Acknowledgments

This research was funded in part by ISF grant 1563/22.