Publications

Self-play red team is an established approach to improving AI safety in which different instances of the same model play attacker and defender roles in a zero-sum game, i.e., where the attacker tries to jailbreak the defender; if self-play converges to a Nash equilibrium, the model is guaranteed to respond safely within the settings of the game. Although the parameter sharing enforced by the use of the same model for the two roles improves stability and performance, it introduces fundamental theoretical and architectural limitations. We show that the set of Nash equilibria that can be reached corresponds to a broad class of behaviours that includes trivial always refuse strategies and oracle-like defenders, thus limiting practical applicability. We then show that when attacker and defender share and update the same base model, the dynamics collapse to self-consistency, so that attacks do not enforce adversarial pressure on the defender. In response, we propose Anchored Bipolicy Self-Play, which trains distinct role-specific LoRA adapters on top of a frozen base model, thereby maintaining stable optimisation while preserving adversarial pressure through explicit role separation. In relation to standard self-play, we show up to 100x greater parameter efficiency than finetuning and consistent improvements in safety compared to self-play fine-tuned models. We evaluate on Qwen2.5-{3B, 7B,14B}-IT models across widely used safety benchmarks, showing improved robustness without loss of reasoning ability. Cross-play experiments further show that our attacker and defender models are superior to self-play in terms of adversarial defence and safety.

Clustering is a fundamental problem, aiming to partition a set of elements, like agents or data points, into clusters such that elements 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.

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 feedback is stored in a fixed offline dataset, and we aim to efficiently infer the agents' preferences from this dataset. We analyze the impact of diverse dataset information constraints by studying two types of utility feedback that can be stored in the dataset: agent- and coalition-level utility feedback. For both feedback 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, in which no agent can improve her utility by unilaterally deviating. Our additional goal is devising algorithms with low sample complexity, requiring only a small dataset to obtain a desired approximation to Nash stability. Under agent-level 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. However, under coalition-level feedback, we show that only under 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 that our algorithm converges to a low approximation level to Nash stability across diverse settings.

Graph Neural Networks (GNNs) are key tools for graph representation learning, demonstrating strong results across diverse prediction tasks. In this paper, we present Convexified Message-Passing Graph Neural Networks (CGNNs), a novel and general framework that combines the power of message-passing GNNs with the tractability of convex optimization. By mapping their nonlinear filters into a reproducing kernel Hilbert space, CGNNs transform training into a convex optimization problem, which projected gradient methods can solve both efficiently and optimally. Convexity further allows CGNNs' statistical properties to be analyzed accurately and rigorously. For two-layer CGNNs, we establish rigorous generalization guarantees, showing convergence to the performance of an optimal GNN. To scale to deeper architectures, we adopt a principled layer-wise training strategy. Experiments on benchmark datasets show that CGNNs significantly exceed the performance of leading GNN models, obtaining 10-40% higher accuracy in most cases, underscoring their promise as a powerful and principled method with strong theoretical foundations. In rare cases where improvements are not quantitatively substantial, the convex models either slightly exceed or match the baselines, stressing their robustness and wide applicability. Though over-parameterization is often used to enhance performance in non-convex models, we show that our CGNNs yield shallow convex models that can surpass non-convex ones in accuracy and model compactness.

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 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.

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.

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.

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.

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.

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).

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.

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.

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-k via Cognitive Hierarchy GrPR2 (GrPR2-CH), which lets each level-k 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 actor-critic scheme, and illustrate that GrPR2-CH outperforms strong MARL baselines in the particle environment.

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.

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.