Coalition formation concerns autonomous agents that strategically interact to form self-organized coalitions. When agents lack initial sufficient information to evaluate their preferences before interacting with others, they learn them online through repeated feedback while iteratively forming coalitions. In this work, we introduce online learning in coalition formation from a non-cooperative perspective, studying the impact of collective data utilization where selfish agents aim to accelerate their learning by leveraging a shared data platform. Thus, the efficiency and dynamics of the learning process are affected by each agent's local feedbacks, motivating us to explore the tension between semi-bandit and bandit feedback, which differ in the granularity of utility information observed by each agent. Under our non-cooperative viewpoint, we evaluate the system by means of Nash stability, where no agent can improve her utility by unilaterally deviating. Our main result is a sample-efficient algorithm for selfish agents that aims to minimize their Nash regret under both semi-bandit and bandit feedback, implying approximately Nash stable outcomes. Under both feedback settings, our algorithm enjoys Nash regret and sample complexity bounds that are optimal up to logarithmic factors.

Coalition formation concerns partitioning agents into disjoint coalitions based on their preferences for one another. In online learning of coalition structures, agents’ true preferences may be initially unknown. Thus, coalitions are repeatedly formed based on preferences learned online from iterative feedback derived from interactions in those coalitions. This work introduces a new fairness-oriented approach to online learning in coalition formation, relying only on partial noisy feedback observed after agents interact. We analyze the system in terms of envy-based fairness notions. Envy-freeness is a popular criterion, where no agent prefers another agent’s coalition over her own. While trivial envy-free solutions exist for unconstrained number of coalitions and coalition sizes, constraints may make envy-free partitions unattainable. We thus present a new envy-freeness-based metric into hedonic games: minimax envy partitions, which minimize the maximum envy experienced by any agent. We devise an algorithm designed to minimize maximum envy, proven to attain sublinear envy regret.

Coalition formation involves self-organized coalitions generated through strategic interactions of autonomous selfish agents. In online learning of coalition structures, agents' preferences toward each other are initially unknown before agents interact. Coalitions are formed iteratively based on preferences that agents learn online from repeated feedback resulting from their interactions. In this paper, we introduce online learning in coalition formation through the lens of distributed decision-making, where self-interested agents operate without global coordination or information sharing, and learn only from their own experience. Under our selfish perspective, each agent seeks to maximize her own utility. Thus, we analyze the system in terms of Nash stability, where no agent can improve her utility by unilaterally deviating. We devise a sample-efficient decentralized algorithm for selfish agents that minimize their Nash regret, yielding approximately Nash stable solutions. In our algorithm, each agent uses only one utility feedback per round to update her strategy, but our algorithm still has Nash regret and sample complexity bounds that are optimal up to logarithmic factors.

We study the friendship-based online coalition formation problem, in which agents that appear one at a time should be partitioned into coalitions, and an agent’s utility for a coalition is the number of her neighbors (i.e., friends) within the coalition. Unlike prior work, agents’ friendships may be uncertain. We analyze the desirability of the resulting partition in the common term of optimality, aiming to maximize the social welfare. We design an online algorithm termed Maximum Predicted Coalitional Friends (MPCF), which is enhanced with predictions of each agent’s number of friends within any possible coalition. For common classes of random graphs, we prove that MPCF is optimal, and, for certain graphs, provides the same guarantee as the best known competitive algorithm for settings without uncertainty.

Hedonic games model cooperative games where agents desire to form coalitions, and only care about the composition of the coalitions of which they are members. Focusing on various classes of dichotomous hedonic games, where each agent either approves or disapproves a given coalition, we propose the random extension, where players have an independent participation probability. We initiate the research on the computational complexity of computing the probability that coalitions and partitions are optimal or stable. While some cases admit efficient algorithms (e.g., agents approve only few coalitions), they become computationally hard (#P-hard) in their complementary scenario. We then investigate the distribution of coalitions in perfect partitions and their performance in majority games, where an agent approves coalitions in which the agent is friends with the majority of its members. When friendships independently form with a constant probability, we prove that the number of coalitions of size 3 converges in distribution to a Poisson random variable.

A network of robots can be viewed as a signal graph, describing the underlying network topology with naturally distributed architectures, whose nodes are assigned to data values associated with each robot. Graph neural networks (GNNs) learn representations from signal graphs, thus making them well-suited candidates for learning distributed controllers. Oftentimes, existing GNN architectures assume ideal scenarios, while ignoring the possibility that this distributed graph may change along time due to link failures or topology variations, which can be found in dynamic settings. A mismatch between the graphs on which GNNs were trained and the ones on which they are tested is thus formed. Utilizing online learning, GNNs can be retrained at testing time, overcoming this issue. However, most online algorithms are centralized and work on convex problems (which GNNs scarcely lead to). This paper introduces novel architectures which solve the convexity restriction and can be easily updated in a distributed, online manner. Finally, we provide experiments, showing how these models can be applied to optimizing formation control in a swarm of flocking robots.