Jason R. Marden

David Grimsman, Mohd. Shabbir Ali, João P. Hespanha et al.

The maximization of submodular functions is an NP-Hard problem for certain subclasses of functions, for which a simple greedy algorithm has been shown to guarantee a solution whose quality is within 1/2 of the optimal. When this algorithm is implemented in a distributed way, agents sequentially make decisions based on the decisions of all previous agents. This work explores how limited access to the decisions of previous agents affects the quality of the solution of the greedy algorithm. Specifically, we provide tight upper and lower bounds on how well the algorithm performs, as a function of the information available to each agent. Intuitively, the results show that performance roughly degrades proportionally to the size of the largest group of agents which make decisions independently. Additionally, we consider the case where a system designer is given a set of agents and a global limit on the amount of information that can be accessed. Our results show that the best designs partition the agents into equally-sized sets and allow agents to access the decisions of all previous agents within the same set.

Yue Guan, Daigo Shishika, Jason R. Marden et al. · gatech

This work introduces the dynamic Defender-Attacker Blotto (dDAB) game, extending the classical static Blotto game to a dynamic resource allocation setting over graphs. In the dDAB game, a defender is required to maintain numerical superiority against attacker resources across a set of key nodes in a connected graph. The engagement unfolds as a discrete-time game, where each player reallocates its resources in turn, with resources allowed to move at most one hop per time step. The primary goal is to determine the necessary and sufficient amount of defender resources required to guarantee sustained defense, along with the corresponding strategies. To address the central challenge arising from graph-constrained resource reallocation, we conduct a reachability analysis, starting with simplified settings where attacker resources act as a single cohesive group. We then extend the framework to allow attacker resources to split and merge arbitrarily, and construct defender strategies using superposition principles. A set-based dynamic programming algorithm is developed to compute the optimal strategies, as well as the minimum amount of defender resources to ensure successful defense. The effectiveness of our approach is demonstrated through numerical simulations and hardware experiments on the Georgia Tech Robotarium platform.

Rahul Chandan, Dario Paccagnan, Jason R. Marden

Today's multiagent systems have grown too complex to rely on centralized controllers, prompting increasing interest in the design of distributed algorithms. In this respect, game theory has emerged as a valuable tool to complement more traditional techniques. The fundamental idea behind this approach is the assignment of agents' local cost functions, such that their selfish minimization attains, or is provably close to, the global objective. Any algorithm capable of computing an equilibrium of the corresponding game inherits an approximation ratio that is, in the worst case, equal to its price-of-anarchy. Therefore, a successful application of the game design approach hinges on the possibility to quantify and optimize the equilibrium performance. Toward this end, we introduce the notion of generalized smoothness, and show that the resulting efficiency bounds are significantly tighter compared to those obtained using the traditional smoothness approach. Leveraging this newly-introduced notion, we quantify the equilibrium performance for the class of local resource allocation games. Finally, we show how the agents' local decision rules can be designed in order to optimize the efficiency of the corresponding equilibria, by means of a tractable linear program.

Vinod Ramaswamy, Dario Paccagnan, Jason R. Marden

The price of anarchy and price of stability are three well-studied performance metrics that seek to characterize the inefficiency of equilibria in distributed systems. The distinction between these two performance metrics centers on the equilibria that they focus on: the price of anarchy characterizes the quality of the worst-performing equilibria, while the price of stability characterizes the quality of the best-performing equilibria. While much of the literature focuses on these metrics from an analysis perspective, in this work we consider these performance metrics from a design perspective. Specifically, we focus on the setting where a system operator is tasked with designing local utility functions to optimize these performance metrics in a class of games termed covering games. Our main result characterizes a fundamental trade-off between the price of anarchy and price of stability in the form of a fully explicit Pareto frontier. Within this setup, optimizing the price of anarchy comes directly at the expense of the price of stability (and vice versa). Our second results demonstrates how a system-operator could incorporate an additional piece of system-level information into the design of the agents' utility functions to breach these limitations and improve the system's performance. This valuable piece of system-level information pertains to the performance of worst performing agent in the system.

Rahul Chandan, Dario Paccagnan, Jason R. Marden

The design of distributed algorithms is central to the study of multiagent systems control. In this paper, we consider a class of combinatorial cost-minimization problems and propose a framework for designing distributed algorithms with a priori performance guarantees that are near-optimal. We approach this problem from a game-theoretic perspective, assigning agents cost functions such that the equilibrium efficiency (price of anarchy) is optimized. Once agents' cost functions have been specified, any algorithm capable of computing a Nash equilibrium of the system inherits a performance guarantee matching the price of anarchy. Towards this goal, we formulate the problem of computing the price of anarchy as a tractable linear program. We then present a framework for designing agents' local cost functions in order to optimize for the worst-case equilibrium efficiency. Finally, we investigate the implications of our findings when this framework is applied to systems with convex, nondecreasing costs.

Philip N. Brown, Holly P. Borowski, Jason R. Marden

A challenge in multiagent control systems is to ensure that they are appropriately resilient to communication failures between the various agents. In many common game-theoretic formulations of these types of systems, it is implicitly assumed that all agents have access to as much information about other agents' actions as needed. This paper endeavors to augment these game-theoretic methods with policies that would allow agents to react on-the-fly to losses of this information. Unfortunately, we show that even if a single agent loses communication with one other weakly-coupled agent, this can cause arbitrarily-bad system states to emerge as various solution concepts of an associated game, regardless of how the agent accounts for the communication failure and regardless of how weakly coupled the agents are. Nonetheless, we show that the harm that communication failures can cause is limited by the structure of the problem; when agents' action spaces are richer, problems are more susceptible to these types of pathologies. Finally, we undertake an initial study into how a system designer might prevent these pathologies, and explore a few limited settings in which communication failures cannot cause harm.

Dario Paccagnan, Jason R. Marden

A fundamental challenge in multiagent systems is to design local control algorithms to ensure a desirable collective behaviour. The information available to the agents, gathered either through communication or sensing, naturally restricts the achievable performance. Hence, it is fundamental to identify what piece of information is valuable and can be exploited to design control laws with enhanced performance guarantees. This paper studies the case when such information is uncertain or inaccessible for a class of submodular resource allocation problems termed covering problems. In the first part of this work we pinpoint a fundamental risk-reward tradeoff faced by the system operator when conditioning the control design on a valuable but uncertain piece of information, which we refer to as the cardinality, that represents the maximum number of agents that can simultaneously select any given resource. Building on this analysis, we propose a distributed algorithm that allows agents to learn the cardinality while adjusting their behaviour over time. This algorithm is proved to perform on par or better to the optimal design obtained when the exact cardinality is known a priori.

Keith Paarporn, Jason R. Marden

Resource allocation problems across multiple contests are ubiquitous in adversarial settings, from military operations to market competition. While Colonel Blotto and General Lotto games have provided valuable theoretical foundations for such problems, their equilibrium characterizations typically permit resources to be arbitrarily allocated across all contests -- a flexibility that rarely aligns with practical constraints. This paper introduces a novel constrained variant of the General Lotto game where one player is restricted to allocating resources to only a single contest. In this model we provide lower and upper bounds on the security values for this constrained player, quantifying how the inability to distribute resources across multiple contests fundamentally changes optimal strategic behavior and performance guarantees. These findings contribute to a broader understanding of how operational constraints shape strategic outcomes in competitive resource allocation, with implications for decision-makers facing similar constraints in practice.

Keith Paarporn, Rahul Chandan, Mahnoosh Alizadeh et al.

Resource allocation under strategic adversarial constraints represents a fundamental challenge in control systems, from cybersecurity defense to infrastructure protection. While game-theoretic frameworks have long informed such problems, Colonel Blotto games -- despite their direct relevance to allocation decisions -- remain underutilized and underappreciated in the controls community compared to other game-theoretic models like the Prisoner's Dilemma. The disparity stems largely from analytical complexity: Colonel Blotto games typically require characterizing intricate mixed-strategy equilibria that resist the clean, closed-form solutions control theorists prefer. Yet as Golman and Page observe, this very complexity ``makes Blotto all the more compelling in its interpretations.'' The goal of this expository article is to showcase the power and versatility of Colonel Blotto game frameworks for the controls community, demonstrating how allocation problems across cybersecurity, network defense, and multi-agent systems can be modeled within this unified theoretical structure. We survey recent analytical and computational breakthroughs, highlight diverse applications, and examine extensions addressing incomplete information, network effects, and multi-stage decision-making -- illustrating how Colonel Blotto games provide both practical tools and fundamental insights for strategic resource allocation in adversarial environments.

Aya Hamed, Jason R. Marden, Jeff S. Shamma

Strategic multi-agent systems are fundamentally characterized by decentralization, uncertainty, and ambiguity. Agents operating under limited observations will often need to make decisions based on simplified internal models of the environment, reflecting bounded rationality in both computational capacity and environmental knowledge. The Empirical Evidence Equilibrium (EEE) framework explicitly accounts for these limitations by modeling each agent as forming a potentially misspecified belief derived from signals obtained through partial observations of the environment. The resulting equilibrium concept captures the system's steady state under bounded rationality and decentralization. In this work, we study games in which the environment dynamics are driven jointly by exogenous factors and agents' actions. We analyze agent behavior under Q-value iteration where each agent independently forms a belief model, computes Q-values, and derives a greedy strategy, yet the collective actions of all agents jointly shape the environment each agent faces at the next stage. We prove that despite this decentralization, an EEE emerges from the joint dynamics when the coupling between agents' actions and the environment is sufficiently weak. We further extend this result to softmax policies, establishing a contraction result under a sufficient coupling condition.

Gilberto Diaz-Garcia, Keith Paarporn, Jason R. Marden

In competitive resource allocation, a central coordinator may seek to gain an advantage not by directly controlling subordinate agents, but by strategically manipulating the information they receive. We study this problem within the framework of multi-player Tullock contests, where the coordinator influences subordinate players by designing their reported valuations of the contested prize, a mechanism that preserves the Tullock structure of the subordinates' objectives and thereby enables tractable equilibrium analysis. We first characterize the Nash equilibrium of the general multi-player Tullock contest, establishing how valuations and per-unit costs jointly determine equilibrium bids and payoffs. We then derive the optimal reported valuations for a coordinator managing two subordinates against a single opponent, and show that the structure of the optimal solution extends to contests with an arbitrary number of subordinates, reducing the coordinator's optimization to a two-variable problem regardless of system size.

Rui Yan, Xiaoming Duan, Zongying Shi et al.

This paper introduces two metrics (cycle-based and memory-based metrics), grounded on a dynamical game-theoretic solution concept called sink equilibrium, for the evaluation, ranking, and computation of policies in multi-agent learning. We adopt strict best response dynamics (SBRD) to model selfish behaviors at a meta-level for multi-agent reinforcement learning. Our approach can deal with dynamical cyclical behaviors (unlike approaches based on Nash equilibria and Elo ratings), and is more compatible with single-agent reinforcement learning than alpha-rank which relies on weakly better responses. We first consider settings where the difference between largest and second largest underlying metric has a known lower bound. With this knowledge we propose a class of perturbed SBRD with the following property: only policies with maximum metric are observed with nonzero probability for a broad class of stochastic games with finite memory. We then consider settings where the lower bound for the difference is unknown. For this setting, we propose a class of perturbed SBRD such that the metrics of the policies observed with nonzero probability differ from the optimal by any given tolerance. The proposed perturbed SBRD addresses the opponent-induced non-stationarity by fixing the strategies of others for the learning agent, and uses empirical game-theoretic analysis to estimate payoffs for each strategy profile obtained due to the perturbation.

Philip N. Brown, Holly Borowski, Jason R. Marden

In a multi-agent system, transitioning from a centralized to a distributed decision-making strategy can introduce vulnerability to adversarial manipulation. We study the potential for adversarial manipulation in a class of graphical coordination games where the adversary can pose as a friendly agent in the game, thereby influencing the decision-making rules of a subset of agents. The adversary's influence can cascade throughout the system, indirectly influencing other agents' behavior and significantly impacting the emergent collective behavior. The main results in this paper focus on characterizing conditions under which the adversary's local influence can dramatically impact the emergent global behavior, e.g., destabilize efficient Nash equilibria.