Decentralized Online Learning by Selfish Agents in Coalition Formation

1 Introduction

Freelance developers collaborating on open-source projects pursue individual goals like skill enhancement and portfolio building. Their self-interest affects their collaborative choices of forming project teams, but they cannot make optimal decisions as they initially lack clarity on their preferences about other developers, team size, or project types. After contributing to a certain team, these selfish developers learn about their preferences from feedback only about their team's productivity and satisfaction with the collaborative dynamics. This adaptive process allows them to selfishly optimize their working experiences, making informed decisions to join project teams that best align with their personal goals and working styles. Such scenarios and many other real-life cases exemplify online learning in coalition formation, where coalitions are formed iteratively based on preferences that agents learn online from repeated feedback about their interactions.

Hedonic games [Dreze and Greenberg, 1980] are a popular framework for studying coalition formation, where the utilities of selfish agents only depend on the coalition they are part of, disregarding the structure of other coalitions, i.e., externalities are ignored. The outcome of such games is a set of disjoint coalitions (hereafter, partition), whose desirability is often assessed in terms of stability [Aziz and Savani, 2016; Bullinger and Romen, 2024], reflecting the likelihood of selfish agents maintaining their coalitions. Traditional literature on stability in hedonic games often focuses only on the final outcome of coalition formation, ignoring the process of reaching stable partitions. Particularly, in most existing works it is implicitly assumed that a central authority can attain the agents' preferences, find a stable partition and impose it on the agents. Recent works, however, consider a dynamic process where, starting from an initial partition, agents deliberately move between coalitions based on their preferences [Boehmer et al., 2023; Brandt et al., 2022]. In many realistic cases as our project teams example, agents' preferences toward others are initially unknown prior to interactions (see, e.g., [Cohen and Agmon, 2023a]). Hence, each agent must make decisions individually based on her own preferences, which she learns online from repeated feedback by iteratively joining coalitions. To reflect such cases, Cohen and Agmon [2024b] study online learning in hedonic games, aiming to maximize social welfare. Recently, Cohen and Agmon [2025b] explored a centralized setting where selfish agents seek to maximize their own utility.

In contrast, in this paper we introduce and study a new model for online learning in coalition formation, reflecting such realistic situations from the perspective of decentralized decision-making by self-interested agents. As agents are usually not aware of other agents' strategies, we assume bandit feedback, i.e., agents solely observe their utility from the coalition they joined. We exhibit our findings for additively separable hedonic games with symmetric preferences [Bogomolnaia and Jackson, 2002], where an agent's utility for a coalition is the sum of her utilities from other coalition members. Essentially, our framework has no global coordination among agents, and thus they learn only from their own history of strategies, coalitions' composition and utility feedbacks.

Agents' selfish behavior can lead to stable partitions, which we evaluate by means of Nash stability, where no agent can improve her utility by unilaterally deviating. This stability notion is well-suited to our distributed context as it does not allow any agent to coordinate with others to determine if she can increase her utility (see, e.g., [Balliu et al., 2019]). In this setting, the partition formed by uncoordinated selfish agents can be inferior to a centrally designed one. Under our online learning setup, a popular metric for such inefficiency of equilibria is Nash regret [Ding et al., 2022; Liu et al., 2021], comparing an agent's learnt strategy against her best response strategy at any round. Sublinear Nash regret translates to low sample complexity as it implies bestiterate convergence to an approximate Nash stable solution with fewer samples (by classic online-to-batch conversion due to, e.g., [Jin et al., 2018]), strongly tying these notions to our online learning setting.

Our Contributions. We develop a sample-efficient decentralized algorithms for online learning in coalition formation by selfish agents that minimizes its Nash regret, thus obtaining approximately Nash stable partitions. Such a distributed approach is also often favored over centralized ones due to its simplicity of implementation, versatility, and faster execution resulting from reduced communication overhead. We devise a Frank-Wolfe-based algorithm for distributed online learning in coalition formation, where each agent only utilizes one sample per round to update her strategy. We prove that our algorithm obtains Nash regret and sample complexity bounds that are optimal (up to logarithmic factors). All omitted proofs can be found in the supplementary materials [Cohen and Agmon, 2025a].

2 RelatedWork

Hedonic games were introduced by Dr`eze and Greenberg [1980], and later expanded to the study of various notions of stability, fairness, and optimality (see, e.g., [Aziz and Savani, 2016]). We focus on additively separable hedonic games (ASHGs) with symmetric preferences [Bogomolnaia and Jackson, 2002], where a large body of work evaluates the system in terms of stability. Unlike cooperative approaches (e.g., core stability [Bogomolnaia and Jackson, 2002]), we explore a non-cooperative perspective, where many works study Nash stability [Balliu et al., 2019; Aloisio et al., 2020; Banerjee et al., 2001; Ballester, 2004]. Particularly, Bogomolnaia and Jackson [2002] proved that Nash stable partitions may not exist in general ASHGs, while Sung and Dimitrov [2010] showed that checking if an instance admits such partition is NP-complete in the strong sense. Yet, for symmetric preferences, the existence of a Nash stable outcome is guaranteed by potential function argument [Bogomolnaia and Jackson, 2002], but computing such partitions is PLScomplete [Gairing and Savani, 2019]. However, the above works explore offline settings, while we regard online ones.

Hence, our work is closely related to time-dependent models in hedonic games, including their online variant introduced by Flammini et al. [2021b], where agents arrive one at a time and should be immediately and irrevocably assigned to coalitions with the goal of maximizing social welfare. This problem was recently extended to other setups [Cohen and Agmon, 2024a; Bullinger and Romen, 2023], with Bullinger and Romen [2024] also exploring various stability concepts. However, the assumption that the agents are partitioned by a central authority may be unrealistic, as agents typically make decisions individually. In contrast, we adopt a decentralized perspective, where agents make selfishly decide to either form a new coalition or to join an existing one based only on their local information from past rounds. Recently, dynamic and distributed approaches to hedonic games have also received increased attention, focusing on deviation dynamics [Bil`o et al., 2018; Boehmer et al., 2023; Brandt et al., 2022].

However, existing works on online and dynamic hedonic games unrealistically require that the agents' preferences are fully known. Research on PAC learnability in hedonic games attempts to tackle this issue [Sliwinski and Zick, 2017; Fioravanti et al., 2023]. Unlike our work, they take a cooperative approach, aiming to efficiently infer preferences from a limited, fixed number of offline samples. They also assume exact knowledge of preferences before making decisions, limiting practicality as agents often need time to learn their own preferences from social interactions, as in our project teams example. In particular, the PAC learning approach is unfit to our dynamic setting due to its static nature, requiring a fixed set of preferences that is known in advance. We consider situations where each agent dynamically learns her own preferences through repeated interactions, enabling her to adapt to changing scenarios so as to learn the coalitions proven most relevant and effective for her selfish desires.

We propose a novel framework that addresses these challenges by examining online learning in coalition formation through the lens of decentralized decision-making by selfish agents, unlike the centralized approaches presented by Cohen and Agmon [2024b; 2025b]. We also contribute to the growing focus on online learning in combinatorial domains (e.g., online task allocation [Cohen and Agmon, 2023b]). Traditional literature on learning in games often studies how various dynamics asymptotically converge to a Nash equilibrium (e.g., no-regret dynamics [Daskalakis et al., 2021; Chen and Peng, 2020], fictitious play [Daskalakis and Pan, 2014; Leslie and Collins, 2006]). In contrast, we focus on non-asymptotic convergence, as done in recent studies on multi-agent reinforcement learning where Nash regret serves as a key performance metric [Ding et al., 2022; Liu et al., 2021], comparing an agent's learnt strategy with her best response strategy at each round. This metric is thus well-suited to the inherently non-stationary nature of our setting. By classic online-to-batch conversion (e.g., [Jin et al., 2018, Section 3.1]), sublinear Nash regret yields low sample complexity, yielding best-iterate convergence to approximate Nash stable solutions with fewer samples.

Matching markets also relate to our work. Unlike prior works [Maheshwari et al., 2022; Zhang et al., 2022; Liu et al., 2020], we address more practical and complex settings with broader utility functions under bandit feedback that go beyond matchings. Our work also ties to potential games, where prior distributed methods often rely on computationally expensive projection-based approaches [Ding et al., 2022; Leonardos et al., 2022], using costly or even intractable projection operations. Conversely, our projectionfree Frank-Wolfe method resolves both issues by using a more efficient linear optimization step. Unlike prior methods for potential games, whose sample complexity and Nash regret scale linearly in the number of actions an agent may take, our algorithm removes this dependency (See Appendix H for details). For congestion games, a subclass of potential games, Cui et al. [2022] also provide a projection-free Frank-Wolfe method, yet it suffers from suboptimal sample complexity and Nash regret bounds, relying on large minibatches of samples and thus not updating optimization parameters frequently enough due to Defazio et al. [2019]. Yet, existing one-sample Frank-Wolfe schemes either exhibit suboptimal convergence rates [Mokhtari et al., 2018] or make restrictive assumptions such as knowing each agent's true utility function [Zhang et al., 2020]. In contrast, without knowing actual utilities, our one-sample algorithm uses a single sample per round while having optimal sample complexity and Nash regret bounds (up to logarithmic factors). Our algorithm also contrasts with that of Dadi et al. [2024], which has suboptimal sample complexity and generally exponential running time, becoming polynomial only for restricted cases, whereas our algorithm runs in polynomial time. Finally, unlike prior methods that update policies independently [Ding et al., 2022; Leonardos et al., 2022], our algorithms exploit awareness of other coalition members for better guarantees.

3 Preliminaries

We study an online learning version of hedonic games, where selfish agents with initially unknown preferences partition themselves into disjoint subsets (i.e, coalitions) over a known number of rounds T, which holds in many real-life scenarios as our project teams example, where developers may join project teams over a predefined number of project milestones. Formally, our strategic game is given by a finite set N = {1, . . . , n} of n selfish agents with unknown preferences. Hereafter, we denote [k] := {1, . . . , k} for k ∈ N and [0] = {0}. At any time t ∈ [T], each agent can join one of n candidate coalitions since there are n agents (i.e., a partition can contain between 1 to n coalitions). In our project teams example, this can be thought of as if each developer picks which room to enter among n rooms. Thus, each agent i joins a certain coalition among n candidate ones at time t following a mixed strategy φti , built based only on local information from past rounds. Time t = 1 is exceptional, where each agent i arbitrarily initializes her strategy φ1i . Formally, φti ∈ Sn where Sn is the probability simplex over [n], i.e., for any x ∈ [n], agent i picks the xth candidate coalition with probability φti (x) ∈ [0, 1]. Let φt = (φti )i∈N ∈ S n n be the agents' joint mixed strategy at time t. At any time t, each agent i then samples an assignment xi ∈ [n] from φti independently from other agents, forming a joint assignment x = (xi)i∈N. Thus, the agents' iterative process of distributed decision-making at time t unfolds as follows:

1. Each agent i samples xi ∼ φti and joins the xith candidate coalition, forming a joint assignment x = (xi)i∈N.
2. Each agent i observes the other members in the coalition she joined and gets bandit feedback about the utility gained from her own coalition.
3. Based only on this obtained information, agent i updates her strategy to be φt+1 i andmoves to the next round t+1.

We term the game formed by this learning process as decentralized online learning ASHGs (DOL-ASHGs). Next, we elaborate on this process in detail. The constructed joint assignment x induces a partition of the agents πx = (C x ℓ )ℓ∈[n], where, for any ℓ ∈ [n], C x ℓ is the set of agents joining the ℓth candidate coalition, i.e., C x ℓ = {i ∈ N : xi = ℓ}. As the number of candidate coalitions equals to the number of agents, some coalitions may be empty. Thereby, we denote by |πx | the number of non-empty coalitions in πx . After her assignment, notice that agent i becomes aware of the other members within the coalition she joined. We thus denote the coalition in πx containing agent i as πx (i).

Afterwards, we can derive each agent's utility from her chosen strategy, determined by aggregating her utilities of other agents. We focus on additively separable hedonic games (ASHGs) with symmetric preferences, where any pair of agents assign the same numerical value toward each other, indicating the intensity by which they prefer each other to another agent. As common in the literature (see, e.g., [Flammini et al., 2021a]), we assume that agents' valuations are within [-1, 1]. Recall that preferences are unknown and even the agents themselves may not be aware of them. Thus, for any pair of distinct agents i, j, the uncertainty about their mutual valuation is captured by an unknown and fixed distribution Di,j over [-1, 1] with mean di,j , which agents i, j aim to learn. At any time t, the utility vt i,j of agents i, j for each other is then independently drawn from Di,j. We use the convention that vt i,i = di,i = 0 for any agent i. For any joint assignment x sampled at time t, agent i's utility from the induced partition πx is then vt i (x) = ∑i̸=j∈πx (i) vt i,j , whose mean is di(x) = ∑i̸=j∈πx (i) di,j. Agent i's utility from her strategy φti at time t is thus defined as Vi(φt ) := Ex∼φt [di(x)].

Each agent's strategies are evaluated by her true unknown utility, but she cannot observe her true utility. We thus consider the most general decentralized setting where each agent should learn her own preferences from repeated partial feedbacks. At any time t and for any joint assignment x, we assume that each agent i can only receive bandit feedback, i.e., in practice, agent i only obtains her utility from the entire partition induced by x (i.e., vt i (x)), with no information about the utility vt i,j gained from interacting with any other agent j.

Each agent joins a coalition with the goal of maximizing her own utility. We thus want to study stability under single agents' incentives to deviate between coalitions. The traditional literature on hedonic games focuses on pure strategies (e.g., [Aziz et al., 2013; Bil`o et al., 2018]), where each agent i's strategy is joining a single candidate coalition at time t by only selecting some xi ∈ [n]. Let x-i = (xj)j̸=i be the joint strategy of all agents except for agent i. Agent i can then deviate by moving from her selected coalition to another one with index yi ∈ [n], which is a Nash deviation if it improves her utility, i.e., V t i (x-i, yi) > V t i (x-i, xi). Unlike prior work on hedonic games, we also study mixed strategies, where we define the other notion of mixed Nash deviations. Consider the joint strategy φt at time t. Letting φt-i = (φtj )j̸=i for any agent i, agent i may perform a (mixed single-agent) deviation from her strategy φti to another strategy ϕi ∈ Sn, which is a mixed Nash deviation only if it immediately makes her better off, i.e., Vi(φt-i , ϕi) > Vi(φt ). Hence, a (pure or mixed) joint strategy for which no Nash deviation is possible is said to be Nash stable (NS), also called a Nash equilibrium (NE). As mentioned earlier, for symmetric preferences under pure strategies, the existence of a Nash stable outcome is guaranteed by potential function argument [Bogomolnaia and Jackson, 2002], but computing such strategies is PLS-complete [Gairing and Savani, 2019].

We thus further consider an approximate notion of Nash stability. At each time t, note that agent i's best response to the other agents' strategies is a Nash deviation given by a strategy ϕ⋆,t i satisfying V ⋆ i (φt-i ) := Vi(φt-i , ϕ⋆,t i ) = maxϕ∈Sn Vi(φt-i , ϕ). Thus, for any ε ≥ 0, the agents' joint strategy φt at time t is ε-approximate Nash stable (ε-NS) if no agent can improve her gain by more than ε, i.e., maxi∈N(V ⋆ i (φt-i ) - Vi(φt )) ≤ ε. Here, the quantity maxi∈N (V ⋆ i (φt-i ) -Vi(φt )) measures the worst agent's local gap between the expected utilities she receives from her best response and her current strategy at time t.

Remark 1. Consider the following mixed strategy where each agent treats all coalitions as equally desirable, i.e., the mixed strategy φti of any agent i and each time t satisfies φti (x) = 1n for any x ∈ [n]. Clearly, this is an exact mixed NS strategy. However, it ignores the agents' preferences entirely, which is unrealistic in practical scenarios as agents often act strategically based on their own preferences, not arbitrarily. Instead, our framework aims to learn meaningful mixed NS strategies that align with agents' preferences, reflecting reallife behavior by accounting for agents' incentives.

Our goal is thus devising a decentralized algorithm that learns an ε-NS joint strategy for some ε ≥ 0, which aligns with agents' preferences. Putting everything together, at any time t, each agent i updates her strategy from time t-1 based only on her own local history up to time t - 1, consisting only of her strategies, the composition of the coalitions she joined and the bandit feedbacks from her own utilities until time t-1, without any information about other coalitions and utilities. We analyze the performance of such algorithm via Nash regret [Ding et al., 2022; Liu et al., 2021], comparing each agent's learnt strategy with her best response strategy at any time instant. Formally, given a sequence of joint strategies {φt }Tt=1 , the Nash regret after T rounds is:

The intuition behind the Nash regret lies in our definition of approximate NS strategies. As maxi∈N(V ⋆ i (φt-i ) -Vi(φt )) is the worst agent's local gap at time t, the Nash regret in (1) is the total sum of the worst agent's local gap at each individual round. That is, at each time t, the Nash regret compares learned strategy φti of each agent i with the best strategy agent i can take by fixing the other agents' strategies φt-i . By our definition of an approximate NS strategy, the Nash regret thus evaluates how far the agents' strategies in each round are from being an (approximate) NS strategy.

For any ε ≥ 0, it is well-known that the the above connection between ε-NS strategies and Nash regret can be used to show that an algorithm with a Nash regret bound of ε obtains an ε-NS strategy (see, e.g., [Ding et al., 2022]). Hence, one of our objectives is minimizing the Nash regret, i.e., attaining a Nash regret bound that is sublinear in the number of rounds T and polynomial in the number of agents n. Another goal is finding an ε-NS strategy using a number of rounds T that is small in its dependency on the number of agents n and 1/ε, guaranteeing a (PAC) sample complexity bound. An algorithm with low sample complexity requires a fewer rounds for best-iterate convergence to an ε-NS strategy. In fact, any algorithm with sublinear Nash regret can be directly converted to a polynomial-sample algorithm via standard online-to-batch conversion (see, e.g., [Jin et al., 2018]).

3.1 DOL-ASHGs as Series of Potential Games

We begin with a useful structural property satisfied by our model. For a single round (i.e., T = 1), a Nash stable strategy is guaranteed for ASHGs with known symmetric preferences through a potential function argument [Bogomolnaia and Jackson, 2002]. In general DOL-ASHGs, where the symmetric preferences are unknown at any time t, we show that the game associated with each time t is also a potential game:

Lemma 1. At each time t, the ASHG with symmetric and unknown preferences associated with time t is a potential game.

Proof. Consider a joint mixed strategy φt at time t. Given a joint assignment x ∼ φt , note that Φt (x) = ∑i∈N vt i (x) is a potential function for pure strategies as Φt (x-i, xi) - Φt (x-i, x′i ) = vt i (x-i, xi) - vt i (x-i, x′i ) for any agent i and another assignment x′i ∈ [n] of agent i. Therefore, by slight abuse of notation, Φ(φt ) = ∑i∈N Vi(φt ) is a potential function for mixed strategies as Φ(φt-i , φti ) - Φ(φt-i , ϕi) = Vi(φt-i , φti ) - Vi(φt-i , ϕi) for any agent i and another strategy ϕi ∈ Sn of agent i. Note that, for pure strategies, the potential is denoted as Φt as it directly depends on t through the utilities. Yet, for mixed strategies, it is expressed by Φ(φt ) as it does not directly depend on t, while its input φt does.

Thus, online learning algorithms for our context should be based on the principle that any Nash stable strategy is a stationary point of the potential function from Lemma 1. Other key design factors are computational efficiency and scalability. Note that one main challenge in our setting is that the size of the joint pure strategies' space equals to the number of possible partitions over n agents which grows exponentially with the number of agents n [Sandholm et al., 1999]. Thus, an efficient algorithm should exhibit Nash regret and sample complexity polynomial in the number of agents n, without dependence on the size of the joint pure strategies space.

As mentioned in Section 2, existing methods for online learning in potential games are unfit for our context [Cui et al., 2022; Ding et al., 2022; Leonardos et al., 2022]. Hence, we devise a Frank-Wolfe method [Hazan and Kale, 2012], replacing projections with a less expensive linear optimization step, and thus can be implemented efficiently in highdimensional domains such as ours. The classic Frank-Wolfe algorithm addresses constrained convex optimization problems by iteratively approximating the objective function with its first-order Taylor expansion around the current solution and solving the resulting linear problem over the feasible set. In each iteration, it identifies a feasible direction by optimizing the linear approximation, and updates the current solution via a convex combination with a properly chosen step size.

Tailored to decentralized online learning in ASHGs, our algorithm also exploits each agent's knowledge about the identities of other members in the coalitions she joins. Namely, each agent makes decisions based only on her own history of strategies, the members of the coalitions she joined and the resulting utility feedbacks, without communicating with other agents to coordinate their strategies. Instead of using large mini-batches as done by Cui et al. [2022], in our algorithm each agent only uses one sample per round (Section 4), yet it has Nash regret and sample complexity bounds that are optimal up to logarithmic factors. At each round, agents form coalitions, obtain a single utility feedback, update their strategies and move to the next round (i.e., agents consecutively follow the stages (1), (2), (3) from the iterative process specified in Section 3).

4 Distributed One-Sample Algorithm

In this section, we devise a sample-efficient decentralized online learning algorithm for DOL-ASHGs (Algorithm 1), termed as Decentralized One-Sample Frank-Wolfe (D1SFW), that requires only one sample per round to update the optimization variables and obtains sublinear Nash regret that is also polynomial in the number of agents n. As input, D1SFW receives the number of rounds T, a set of n agents and step sizes ρt, ηt, µt ∈ (0, 1) for each time t whose choices affect the resulting Nash regret and sample complexity bounds, as detailed later. Next, we depict D1S-FW's main components. Note that we do not have access to the exact gradient of the potential function from Lemma 1. Thus, at any time t, each agent i first computes an unbiased and variance reduced gradient estimation of the potential function at time t using only one utility feedback (Section 4.1). Using this estimation, agent i then follows the classic Frank-Wolfe update rule to pick her next strategy (Section 4.2). Finally, we prove that D1S-FW has Nash regret and sample complexity bounds that are optimal up to logarithmic factors (Section 4.3).

4.1 The Gradient Estimation Step

Our algorithm first modifies the momentum variance reduction approach in [Mokhtari et al., 2018; Mokhtari et al., 2020; Zhang et al., 2020] to compute an unbiased estimator of the potential's gradient using a single utility feedback. Formally, at each time t, note that the potential's gradient w.r.t. any joint strategy φ is given by ∇Φ = ( ∂Φ ∂φi (xi))i∈N,xi∈[n], or equivalently ∇Φ = (∇φi Φ)i∈N where ∇iΦ := ∇φi Φ = ( ∂Φ ∂φi (xi))xi∈[n] is the potential's gradient w.r.t. agent i's strategy φi. A naive approach for agent i is thus using an unbiased one-sample estimation ̂∇tiΦ at time t of ∇iΦ(φt ). Yet, this method yields a high variance. To reduce the variance, in our algorithm agent i sets her gradient estimation gt i

Algorithm 1 D1S-FW

Input: T rounds; n agents; Step sizes ρt, ηt, µt ∈ (0, 1) ∀t.

• 1: Initialize an arbitrary initial policy φ1i for each agent i.
• 2: for each time t = 1, . . . , T do
• 3: Each agent i joins a coalition by sampling xti ∼ φti .
• 4: Each agent i receives a utility vt i from her coalition.
• 5: for each agent i ∈ N individually do
• 6: Compute ̂∇tiΦ using (5).
• 7: if t = 1 then
• 8: Set the gradient estimation as g1 i := ̂∇1i Φ.

9:

else

10:

11:

Compute the gradient estimator gt

• 12: Calculate ˆ ϕti = arg maxϕ∈Sn ⟨ϕ, gt i ⟩.

i using (2).

• 13: Compute πt i using (6) (See Remark 4).
• 14: Set φt+1 i = (1 -ρt)[φti + ηt(ˆ ϕti - φti )] + ρtπt i .

at time t to be a weighted average involving the previous gradient estimate gt-1 i and the one-sample estimation ̂∇tiΦ:

where µt ∈ (0, 1) is an averaging parameter and ̂∆ti is an unbiased estimator of the gradient variation ∆ti = ∇iΦ(φt ) - ∇iΦ(φt-1 ). Intuitively, adding the term ̂∆ti to gt-1 i in (2) ensures that gt i is an unbiased estimator of ∇iΦ due to an inductive argument. Indeed, if gt-1 i is an unbiased estimate of ∇iΦ(φt-1 ) and ̂∆ti is an unbiased estimate of ∆ti , then E[gt i ] = (1 - µt)(∇iΦ(φt-1 ) + ∇iΦ(φt ) - ∇iΦ(φt-1 )) + µt∇iΦ = ∇iΦ, where the expectation is over all randomness up to time t. Next, we explain how to compute the one-sample gradient estimator ̂∇tiΦ and the gradient variation estimator ̂∆ti , both in an unbiased manner. Particularly, we prove that this can be done by approximating each agent's mean utilities from others using linear regression.

One-Sample Gradient Estimator. To come up with such estimator, we first need to know the closed form of the true gradient. In Lemma 2, we show that, for each agent i and any selection xi ∈ [n], the gradient (∇iΦ)xi := ∂Φ ∂φi (xi) evaluated at φt can be written as an inner product between the vector ξi = [di,j]j∈N of all agent i's mean utilities from any agent j ∈ N and the vector φt (xi) ∈ [0, 1]n given by [φt (xi)]j = φtj (xi) for any joint strategy φt at time t. Intuitively, this will allow us to obtain our one-sample gradient estimator by proving that linear regression can be applied to approximate ξi at time t via a least squares estimator.

Lemma 2. For each agent i, the gradient evaluated at φt , which is given by (∇iΦ(φt ))xi , can be rephrased as follows:

where φt (xi) ∈ [0, 1]n is defined as [φt (xi)]j = φtj (xi) for any joint strategy φt at time t, xi ∈ [n] and agent j ∈ N.

Proof. See Appendix A for a detailed proof.

Compute ̂∆ti = ̂∇tiΦ- ̂∇t-1

i Φ.

Using Lemma 2, at any time t, each agent i can derive a one-sample gradient estimation as follows. First, agent i samples her chosen candidate coalition xti ∈ [n] from her strategy φti (line 3). After forming the partition πt := πxt , each agent i obtains a utility feedback vt i from her coalition πt (i) (line 4), whose expectation given that the agents' joint assignment is xt ∈ [n]n at time t can be expressed as E[vt i |xt ] = di(xt ) = ∑i̸=j∈πt (i) di,j = ∑i̸=j∈N 1{xtj = xti }di,j, where, for any xi, xj ∈ [n], 1{xj = xi} equals to 1 if xj = xi and 0 otherwise. This can be rephrased as follows:

where ψi(xt ) ∈ {0, 1}n is given by [ψi(xt )]j = 1{xtj = xti } for any agent j ∈ N, capturing whether agent j joined agent i's selected coalition or not.

Remark 2. In practice, each agent i can compute ψi(xt ) by only using her knowledge about other agents in the coalition she joined via [ψi(xt )]j = 1{j ∈ πt (i)} for any agent j.

Therefore, by Lemma 2, we can use linear regression to estimate ξi at time t via the least squares estimator ˆ ξt i = ( ˆΨti )-1ψi(xt )vt i , where ˆΨti = Exi∼φti [∥ψi(xt-i , xi)∥22 ] is the covariance matrix and ∥ · ∥2 is the standard Euclidean norm (i.e., ∥ψi(xt-i , xi)∥22 = ψi(xt-i , xi)ψi(xt-i , xi)⊤). We can obtain an estimator ̂∇tiΦ(xi) = ⟨ψi(xt-i , xi), ˆ ξt i ⟩ of (∇iΦ(φt ))xi , which satisfies the following:

One can easily verify that this is indeed an unbiased estimator of the potential's gradient, as we prove in Appendix B.

Remark 3. From the perspective of agent i, she deduces ψi(xt ) only from the coalition πt (i) she joined, but we include the implicit dependence on the agents' joint selection xt for the sake of the analysis so as to, e.g., reason about the covariance matrix.

One-Sample Gradient Variation Estimator. For any agent i, our one-sample approach for estimating the gradient variation ∆ti = ∇iΦ(φt ) -∇iΦ(φt-1 ) at time t is computing the difference between our one-sample gradient estimation for agent i's current selection and that for her previous one, i.e., ̂∆ti = ̂∇tiΦ - ̂∇t-1 i Φ. As we saw earlier (Recall Lemma B.1), ̂∇tiΦ and ̂∇t-1 i Φ are unbiased estimators of ∇iΦ at times t and t-1 (resp.), and thus E[ ̂∆ti ] = ∆ti , where the expectation is over all randomness up to time t. That is, ̂∆ti is an unbiased estimator of the gradient variation∆ti .

4.2 The Frank-Wolfe Update Step

At each time t, in line 12 each agent i then optimizes a linear optimization problem to get the feasible ascent strategy ˆ ϕti as the regular Frank-Wolfe method. Instead of updating her strategy at window t + 1 to be φti + ηt(ˆ ϕti - φti ) as in the standard Frank-Wolfe update, in line 14 agent i mixes this strategy with an exploratory strategy πt i which is computed in line 13. Specifically, agent i computes a G-optimal design πt i for {ψi(xt-i , xi)}xi∈[n] (see, e.g., [Lattimore and Szepesv´ari, 2020, Chapter 21]). The G-optimal design minimizes the maximal mean-squared prediction error in linear regression. In our context, the G-optimal design can be viewed as the strategy allowing a uniformly well estimation of ξi over all candidate coalitions. That is, sampling a candidate coalition xi ∈ [n] in proportion to πt i (xi) minimizes the number of samples required for reaching a desired level of accuracy in estimating E[vt i |xt-i , xi] = ⟨ψi(xt-i , xi), ξi⟩. Formally, agent i's G-optimal design πt i at time t satisfies:

where f t i (ϕ) = maxxi∈[n] ψi(xt-i , xi)⊤(Ψti,ϕ )-1ψi(xt-i , xi). Hence, agent i then mixes πt i with the strategy φti+ηt( ˆ ϕti-φti ) obtained from the standard Frank-Wolfe update.

Remark 4. While the original G-optimal design problem is NP-hard [Soare et al., 2014], for our purposes it suffices to compute an approximate G-optimal design with minimal impact on performance. For instance, using the Frank-Wolfe algorithm and a proper initialization, agent i can efficiently find an approximate G-optimal design ˆπt i with f t i (ˆπt i ) ≤ 2n. For easing the analysis in the main text, we hereafter assume that a G-optimal design can be found efficiently and accurately, which is an assumption common in the literature (see, e.g., [Yang and Tan, 2022]). See Appendix G for a vast discussion on the minor effect of using an approximate G-optimal design in our algorithm, including a time complexity analysis.

4.3 Nash Regret Analysis of D1S-FW

To obtain the Nash regret bound of D1S-FW (Algorithm 1), the key step is devising an upper bound on our estimators' errors. First, mixing the regular Frank-Wolfe update with the exploration strategy πt i allows us to regulate the one-sample gradient estimator's error as follows:

Lemma 3. At each time t, for all δ ∈ (0, 1], agent i and xi ∈ [n], the following holds with probability at least 1 - δ:

In particular, if ρt ≤ 2 log(1/δ) 9 , then the following holds with probability at least 1- δ:

Proof. (Sketch) At any time t, let Rt = ψi(xt-i , xi)⊤(Ψti,φti )-1ψi(xt )vt i . In Appendix D, we first prove that |Rt| ≤ n2 ρt (Lemma D.1) and Et [R2t ] ≤ n3 ρt (Lemma D.2), where Et [·] is the expectation over xti ∼ φt for each agent i and all the utilities' randomness at time t. As we proved in Lemma B.1 that ̂∇tiΦ(xi) from (5) is an unbiased estimator of (∇iΦ(φt ))xi (i.e., Et [̂∇tiΦ(xi)] = E[Rt] = (∇iΦ(φt ))xi ), we can apply Bernstein's inequality to obtain both (7) and (8).

We next supply the required upper bound on the error Ati := ∥∇iΦ(φt ) - gt i ∥∞ of agent i's gradient estimator in (2), where ∥ · ∥∞ is the L∞ norm (i.e., ∥z∥∞ = maxi∈[n] |zi| for any z ∈ Rn ).

Lemma 4. For any time t ≥ 3 and any δ ∈ (0, 1], the following holds with probability at least 1 - δ for any agent i:

where Bt := √ n4 log(nT/δ) ρt + n3 log(nT/δ) ρt . If ρt ≤ 2 log(1/δ) 9 for any time t, then an improved bound in (9) is obtained for Bt := n3 log(nT/δ) ρt . For t ∈ {1, 2}, the errors A1i and A2i are bounded as in Lemma 3 since Ati = ∥∇iΦ(φt )- ̂∇tiΦ∥∞ for t ∈ {1, 2}.

Proof. (Sketch) As g1 i = ̂∇1i Φ, then A1i is bounded as in Lemma 3. For any time t ≥ 2, we first prove in Appendix E that our estimators satisfy Ati := ∥(1 - µt)(∇iΦ(φt-1 ) - gt-1 i ) + (1 - µt)(̂∇t-1 i Φ - ∇iΦ(φt-1 )) + (∇iΦ(φt ) - ̂∇tiΦ)∥∞ for each agent i, from which our bound for time 2 can be easily obtained. For each time t ≥ 3, this equality allows us to prove (9) by induction on t.

We are now ready to establish our Nash regret bound:

Theorem 1. For any δ ∈ (0, 1], D1S-FW (Algorithm 1) with ρt = 1 T , ηt = 1 √T , µt = 1 - 1 T for any time t and T ≥ 2 obtains the following Nash regret bound with probability at least 1 - δ:

If δ ≤ e- 9 2T , then, with probability at least 1 - δ, the Nash regret bound in (10) can be reduced to:

Proof. (Sketch) The key idea behind our proof is using the fact that the Nash regret is at most the sum of the Frank-Wolfe gaps across all rounds (Appendix C). Namely, as the FrankWolfe gap of any joint strategy φ w.r.t. the potential function Φ(φ) is given by G(φ) = maxφ′∈S n n ⟨φ′ - φ,∇φΦ⟩, then RT ≤ ∑t∈[T ] G(φt ), and thus we derive an upper bound on the right-hand side to attain our Nash regret bound. First, consider the joint strategies ˆϕt = (ˆ ϕti )i∈N and πt = (πt i )i∈N obtained from the strategies computed in lines 12-13. As the potential function Φ(φ) = ∑i∈N Vi(φ) is n2 -smooth w.r.t. the L1-norm ∥·∥1 by Lemma F.1 in Appendix F, then Φ(φt+1 ) ≥ Φ(φt ) + ⟨∇Φ(φt ), φt+1 - φt ⟩ - n2 2 ∥φt+1 -φt ∥21 . Combined with line 14, we prove in Appendix F that:

Thus, we then devise a lower bound on the right-hand side. In Appendix F, we first show that ⟨∇Φ(φt ), ˆϕt - φt ⟩ ≥ G(φt ) - 2n∥∇Φ(φt ) - gt ∥∞, where gt = (gt i )i∈[n] is the gradient estimator of ∇Φ(φt ). After applying this inequality to (12), we rearrange the resulting inequality to obtain:

By summing this inequality over all rounds T while noting that ∑t∈[T] [Φ(φt+1 ) - Φ(φt )] = Φ(φt+1 ) - Φ(φ1 ) as a telescoping series and |Φ(φt+1 )-Φ(φ1 )| ≤ n, we then have that the Nash regret is upper bounded by:

Recall that this bound also serves as an upper bound on the Nash regret incurred by our algorithm since RT ≤ ∑t∈[T] G(φt ). Further, our bound in (14) depends on the algorithm's error term, for which we have already supplied an upper bound in Lemma 4. Hence, after plugging the algorithm's inputs ρt = 1 T , ηt = 1 √T , µt = 1 - 1 T for any time t and T ≥ 2 to (14), in Appendix F we then apply Lemma 4 to obtain the Nash regret bounds in (10)-(11).

Remark 5. Theorem 1 indicates that D1S-FW has a Nash regret bound of ˜O(√T). By standard online-to-batch conversion (see, e.g., [Jin et al., 2018]), our Nash regret bound suggests a sample complexity bound of T = O(n8 /ε2 ) for obtaining an ε-NS strategy. Surprisingly, though D1S-FW uses only one sample per round, our Nash regret and sample complexity bounds are optimal up to logarithmic factors [Hassani et al., 2020; Bai and Jin, 2020]. To guarantee those bounds, Theorem 1 dictates that the step sizes should depend on the number of rounds T , which is known in our context. As mentioned earlier, this is practical in many realistic cases as our project teams example from Section 1, where developers may participate in project teams over a predefined number of project milestones. Even if T is not explicitly known in some cases, developers often have a rough estimate based on the nature of open-source projects. For example, they may anticipate a typical project duration based on prior experience or the project's roadmap. Hence, agents can still execute our algorithm in a distributed manner even without knowing T .

5 Conclusions and FutureWork

In this paper, we presented a new model for studying online learning in coalition formation through the lens of decentralized decision-making by selfish agents. Our goal was designing sample-efficient distributed algorithms for self-interested agents that minimize their Nash regret, resulting in approximately Nash stable partitions. As such, we devised a FrankWolfe methods, where every agent uses one sample per round for gradient estimation, yet it attains Nash regret and sample complexity bounds that are optimal up to logarithmic factors.

Our work opens the way for plenty future studies. Immediate directions include the investigation of other classes of hedonic games, other solution concepts and an empirical analysis. Future studies also warrants exploring other models of partial information (e.g., semi-bandit feedback), and study cases where the number of rounds is not necessarily known. Finally, an interesting future direction is devising distributed algorithms with no-regret guarantees for any agent adopting them, ensuring that each agent has diminishing regret, regardless of how others update their strategies.

Acknowledgments

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