Author name cluster

Saar Cohen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers

1 author row

AAMAS Conference 2026 Conference Paper

Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals

Saar Cohen

Clustering is a fundamental problem, aiming to partition a set of elements, likeagentsordatapoints, intoclusterssuchthatelements in the same cluster are closer to each other than to those in other clusters. In this paper, we present a new framework for studying online non-centroid clustering with delays, where elements, that arrive one at a time as points in a finite metric space, should be assigned to clusters, but assignments need not be immediate. Specifically, upon arrival, each point’s location is revealed, and an online algorithm has to irrevocably assign it to an existing cluster or create a new one containing, at this moment, only this point. However, we allow decisions to be postponed at a delay cost, instead of following the more common assumption of immediate decisions upon arrival. This poses a critical challenge: the goal is to minimize both the total distance costs between points in each cluster and the overall delay costs incurred by postponing assignments. In the classic worst-case arrival model, where points arrive in an arbitrary order, no algorithm has a competitive ratio better than sublogarithmic in the number of points. To overcome this strong impossibility, we focus on a stochastic arrival model, where points’ locations are drawn independently across time from an unknown and fixed probability distribution over the finite metric space. We offer hope for beyond worst-case adversaries: we devise an algorithm that is constant competitive in the sense that, as the number of points grows, the ratio between the expected overall costs of the output clustering and an optimal offline clustering is bounded by a constant.

PDF

AAMAS Conference 2026 Conference Paper

Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions

Saar Cohen

Coalition formation concerns strategic collaborations of selfish agents that form coalitions based on their preferences. It is often assumed that coalitions are disjoint and preferences are fully known, which may not hold in practice. In this paper, we thus present a new model of coalition formation with possibly overlapping coalitions under partial information, where selfish agents may be part of multiple coalitions simultaneously and their full preferences are initially unknown. Instead, information about past interactions and associated utility feedbacks is stored in a fixed offline dataset, from which we aim to efficiently infer agents’ preferences. We analyze the impact of diverse dataset information constraints by studying two utility feedback models: semi-bandit (agent-level) and bandit (coalition-level) feedbacks. For both models, we identify assumptions under which the dataset covers sufficient information for an offline learning algorithm to infer preferences and use them to recover a partition that is (approximately) Nash stable, i. e. , no agent can improve her utility by unilaterally deviating. We also aim to devise algorithms with low sample complexity, requiring only a small dataset to obtain a desired approximation to Nash stability. Under semi-bandit feedback, we provide a sample-efficient algorithm proven to obtain an approximately Nash stable partition under a sufficient and necessary assumption on the information covered by the dataset. Yet, under bandit feedback, we show that only a stricter assumption is sufficient for sample-efficient learning. Still, in multiple cases, our algorithms’ sample complexity bounds have optimality guarantees up to logarithmic factors. Finally, extensive experiments show our algorithm’s approximation to Nash stability.

PDF

IJCAI Conference 2025 Conference Paper

Decentralized Online Learning by Selfish Agents in Coalition Formation

Saar Cohen
Noa Agmon

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.

PDF Details DOI

AAMAS Conference 2025 Conference Paper

Egalitarianism in Online Coalition Formation

Saar Cohen
Noa Agmon

We investigate the online coalition formation problem, where agents arrive one by one and must be assigned to coalitions, with their utilities for others revealed upon arrival. Our focus lies on additively separable hedonic games, where agents assign cardinal utilities to others, assumed to be controlled by an adversary in our online context. This paper introduces the evaluation of partitions based on their egalitarian social welfare, with the goal of maximizing the minimum utility of any agent. This objective strikes balance between fairness and efficiency by prioritizing the satisfaction of the least well-off agents. For various real-life scenarios, we establish tight or nearly tight upper bounds on the competitive ratio and complement these findings with optimal or near-optimal algorithms. However, we also demonstrate that in some cases, no competitive algorithm is feasible. In particular, under the classic worst-case adversarial model, where agents arrive in an arbitrary order, we show that no algorithm has a non-trivial competitive ratio, if at all.

PDF

AAAI Conference 2025 Conference Paper

Online Learning of Coalition Structures by Selfish Agents

Saar Cohen
Noa Agmon

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.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

Near-Optimal Online Resource Allocation in the Random-Order Model

Saar Cohen
Noa Agmon

We study the problem of allocating either divisible or indivisible items (goods or chores) among a set of agents, where the items arrive online, one at a time. Each agent’s non-negative value for an item is set by an adversary upon the item’s arrival. Our focus is on a unifying algorithmic framework for finding online allocations that treats both fairness and economic efficiency. For this sake, we aim to optimize the generalized means of agents’ received values, covering a spectrum of welfare functions including average utilitarian welfare and egalitarian welfare. In the traditional adversarial model, where items arrive in an arbitrary order, no algorithm can give a decent approximation to welfare in the worst case. To escape from this strong lower bound, we consider the random-order model, where items arrive in a uniformly random order. This model provides us with a major breakthrough: we devise algorithms that guarantee a nearly-optimal competitive ratio for certain welfare functions, if the welfare obtained by the optimal allocation is sufficiently large. We prove that our results are almost tight: if the optimal solution’s welfare is strictly below a certain threshold, then no nearly-optimal algorithm exists, even in the random-order model.

PDF

IJCAI Conference 2024 Conference Paper

Online Learning of Partitions in Additively Separable Hedonic Games

Saar Cohen
Noa Agmon

Coalition formation involves partitioning agents into disjoint coalitions based on their preferences over other agents. In reality, agents may lack enough information to assess their preferences before interacting with others. This motivates us to initiate the research on coalition formation from the viewpoint 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 change over time, are revealed. The learner's goal is optimizing social cost by minimizing his (static or dynamic) regret. We show that even no-static regret is hard to approximate, and constant approximation in polynomial time is unattainable. Yet, for a fractional relaxation of our problem, we devise an algorithm that simultaneously gives the optimal static and dynamic regret. We then present a rounding scheme with an optimal dynamic regret, which converts our algorithm's output into a solution for our original problem.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Coalition Formation in Sequential Decision-Making under Uncertainty

Saar Cohen

As real-world applications of coalition formation continuously evolve, the design of new efficient algorithms that maintain a decent and consistent solution over time is required. Specifically, when agents arrive one at a time, a moderator (i. e. , an online algorithm) must decide to which coalition the agent should be assigned, if at all. Each agent may be further accompanied with relevant information (e. g. , her set of capabilities, her preferences over the previously disclosed agents), based on which the moderator performs its decisions. Multi-agent systems further encompass uncertainties in a variety of forms: the nature of the agents’ participation and arrivals may be probabilistic or even unknown. Additionally, their preferences might be not assured and even incomplete or strategic. This research will thus lay the theoretical foundations for studying the interplay between coalition formation and online, uncertain settings, while characterizing the factors which make the moderator’s objective susceptible. Our methods will be further tied to practical applications, specifically ones in physical settings (e. g. , task allocation in actual robots).

PDF

AAAI Conference 2023 Conference Paper

Complexity of Probabilistic Inference in Random Dichotomous Hedonic Games

Saar Cohen
Noa Agmon

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.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Online Coalitional Skill Formation

Saar Cohen
Noa Agmon

Efficiently allocating heterogeneous tasks to agents that arrive dynamically and have diverse skills is a central problem in multi-agent systems called online task allocation. In many cases, a single agent does not meet the skill levels required by a particular task, which incentivizes the agents to form coalitions for handling it. In this paper, we propose a new framework, termed as online coalitional skill formation (OCSF), for handling online task allocation via coalition formation, where tasks require different skills for being successfully fulfilled, and each agent has different levels at mastering each skill. The goal of the organizer is therefore to assign agents that arrive online to a coalition responsible for performing some task, so as to optimally approach the desired skill levels of all tasks. Focusing on the case in which the set of possible mastering levels for each skill is discrete, we suggest different assignment algorithms based on the knowledge the organizer has on the arriving agents. When agents arrive i. i. d. according to some unknown distribution, we propose a greedy and adaptive scheme that assigns an agent to a task, proving a tight bound on the system’s performance. If the distribution is known, we devise a novel correlation to Constrained Markov Decision Processes whose goal is maximizing the rate at which agents are assigned to each task while respecting their requirements. We then construct a non-adaptive approach that terminates when all the tasks’ requirements are met. Finally, if the distribution is unknown, we provide two algorithms that learn it online. We have fully implemented the algorithms, showing that in many cases a higher diversity in skills may yield poor assignments.

PDF

AAMAS Conference 2022 Conference Paper

Optimizing Multi-Agent Coordination via Hierarchical Graph Probabilistic Recursive Reasoning

Saar Cohen
Noa Agmon

Multi-agent reinforcement learning (MARL) requires coordination by some means of interaction between agents to efficiently solve tasks. Interaction graphs allow reasoning about joint actions based on the local structure of interactions, but they disregard the potential impact of an agent’s action on its neighbors’ behaviors, which could rapidly alter in dynamic settings. In this paper, we thus present a novel perspective on opponent modeling in domains with only local interactions using (level-1) Graph Probabilistic Recursive Reasoning (GrPR2). Unlike previous work on recursive reasoning, each agent iteratively best-responds to other agents’ policies over all possible local interactions. Agents’ policies are approximated via a variational Bayes scheme for capturing their uncertainties, and we prove that an induced variant of Q-learning converges under self-play when there exists only one Nash equilibrium. In cooperative settings, we further devise a variational lower bound on the likelihood of each agent’s optimality. Opposed to other models, optimizing the resulting objective prevents each agent from attaining an unrealistic modelling of others, and yields an exact tabular Q-iteration method that holds convergence guarantees. Then, we deepen the recursion to level-𝑘 via Cognitive Hierarchy GrPR2 (GrPR2-CH), which lets each level-𝑘 player best-respond to a mixture of strictly lower levels in the hierarchy. We prove that: (1) level-3 reasoning is the optimal hierarchical level, maximizing each agent’s expected return; and (2) the weak spot of the classical CH models is that 0-level is uniformly distributed, as it may introduce policy bias. Finally, we propose a practical actorcritic scheme, and illustrate that GrPR2-CH outperforms strong MARL baselines in the particle environment.

PDF

IJCAI Conference 2021 Conference Paper

Convexified Graph Neural Networks for Distributed Control in Robotic Swarms

Saar Cohen
Noa Agmon

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.

PDF Details DOI

AAMAS Conference 2021 Conference Paper

Spatial Consensus-Prevention in Robotic Swarms

Saar Cohen
Noa Agmon

In this work, we define the consensus-prevention problem, which examines the canonical swarm robotic consensus problem from an adversarial point of view: how (if at all) is it possible to lead a swarm into a disagreement, that is, prevent them from reaching an agreement. We focus on consensus-prevention in physically grounded tasks, concentrating on influencing the direction of movement of a flocking swarm and guaranteeing that the swarm will never converge to the same direction by the use of external, predefined agents, referred to as diverting agents. We formally define the notion of disagreement within a flock, and propose a way of measuring it. We show a correlation between the consensus-prevention problem and the coalition formation problem, whose players aim at maximizing the disagreement measure. While the general problem of optimizing disagreement between flocking agents is NP-hard, we focus on a case which is solvable in polynomial time, using a variant of the graph clustering problem where the clusters constitute the desired coalitions. This allows us to determine both the number of coalitions that optimize disagreement, and the behavior of the diverting agents for a given number of coalitions that will lead to optimal disagreement. Finally, we demonstrate in simulation the impact of the number of diverting agents on the disagreement measure in different scenarios, and discuss the limitations of the diverting agents in dynamic settings.

PDF