Rahul Chandan

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.

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.

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.

Bo Fu, Zhe Chen, Rahul Chandan et al.

We introduce the Block Rearrangement Problem (BRaP), a challenging component of large warehouse management which involves rearranging storage blocks within dense grids to achieve a target state. We formally define the BRaP as a graph search problem. Building on intuitions from sliding puzzle problems, we propose five search-based solution algorithms, leveraging joint configuration space search, classical planning, multi-agent pathfinding, and expert heuristics. We evaluate the five approaches empirically for plan quality and scalability. Despite the exponential relation between search space size and block number, our methods demonstrate efficiency in creating rearrangement plans for deeply buried blocks in up to 80x80 grids.