Reinforcement Learning for Game-Theoretic Resource Allocation on Graphs
Zijian An, Lifeng Zhou* · 2025
Read Reinforcement Learning for Game-Theoretic Resource Allocation on Graphs by Zijian An, Lifeng Zhou* (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-06319.txt.
Introduction
Zijian An and Lifeng Zhou wrote this paper in two thousand twenty-five. It trains reinforcement learning agents to fight over nodes on a graph, in a multi-step game based on the Colonel Blotto setup.
Two players spread forces across rounds to hold prized nodes, and the best plan is hard to find since moves shift with the graph. The authors cast the game as a Markov decision process and run two learners, Deep Q-Network and Proximal Policy Optimization. A matrix trick builds the legal move set at each step from the graph's links. On varied graphs, both learners beat random and greedy rivals and held even against a trained foe. On lopsided graphs they learned to use shape as an edge.
Catalog record
| CREATOR | Zijian An, Lifeng Zhou* |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-06319
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reinforcement Learning for Game-Theoretic Resource Allocation on Graphs Zijian An, Lifeng Zhou* Abstract Game-theoretic resource allocation on graphs (GRAG) involves two players competing over multiple steps to control nodes of interest on a graph, a problem modeled as a multi-step Colonel Blotto Game (MCBG). Finding optimal strategies is challenging due to the dynamic action space and structural constraints imposed by the graph. To address this, we formulate the MCBG as a Markov Decision Process (MDP) and apply Reinforcement Learning (RL) methods, specifically Deep Q-Network (DQN) and Proximal Policy Optimization (PPO). To enforce graph constraints, we introduce an action-displacement adjacency matrix that dynamically generates valid action sets at each step. We evaluate RL performance across a variety of graph structures and initial resource distributions, comparing against random, greedy, and learned RL policies. Experimental results show that both DQN and PPO consistently outperform baseline strategies and converge to a balanced 50 % 50\% win rate when competing against the learned RL policy. Particularly, on asymmetric graphs, RL agents successfully exploit structural advantages and adapt their allocation strategies, even under disadvantageous initial resource distributions. Note to Practitioners: This work presents an RL-based framework for solving the GRAG, with a particular focus on DQN and PPO as the core learning algorithms. The framework is designed to compute optimal strategies for resource allocation in competitive settings constrained by graph topology. The methodology and findings of this study have practical relevance across a wide range of domains where strategic resource allocation under spatial or network constraints is essential. Applications include autonomous surveillance and reconnaissance, where robots gather information in the presence of adversaries; cybersecurity, where attackers and defenders allocate limited resources to protect or compromise sensing and communication assets; and financial markets, where firms strategically bid for customer segments to gain competitive advantages. This framework is especially valuable for practitioners in robotics, control, and networked systems operating in contested, dynamic environments, where robust and adaptive strategies are essential. I Introduction Recent advances in computing, sensing, and communication technologies have reinforced the central role of resource allocation across a broad spectrum of engineering and automation applications [ 1 , 2 ] . Many areas inherently involve the competitive strategic distribution of limited resources under spatial and structural constraints. Such competitive and resource-constrained scenarios appear across a broad range of domains. In surveillance and reconnaissance tasks [ 3 , 4 , 5 , 6 ] , robotic agents must be strategically deployed to monitor expansive areas while responding to the presence of adversarial forces or contested terrain. In cybersecurity [ 7 , 8 , 9 , 10 , 11 ] , defenders and attackers compete by allocating limited resources to either preserve or disrupt network integrity. Similarly, competitive market bidding [ 12 , 13 ] involves budget-constrained companies strategically distributing marketing efforts or pricing incentives across customer groups to maximize influence and market share. The Colonel Blotto Game (CBG) has been widely adopted to model these competitive resource allocation scenarios. Originally introduced by Borel [ 14 ] and further developed in [ 15 ] , the CBG captures zero-sum strategic scenarios where two players allocate limited resources across multiple battlefields to maximize territorial gains. Traditionally, the CBG assumes a one-shot interaction, reflecting instantaneous strategic decisions, but its principles naturally extend to sequential or spatially structured competitive environments encountered in real-world automation and control applications. Fig. 1: GRAG on a five-node graph involves two players, the red and blue, each with eight units of resources. The players make moves simultaneously. In the left subfigure, the game begins in a tied status. The red has a clear winning strategy: moving a resource from node 1 to node 5. However, the blue player is aware of this strategy and can counter it by moving one resource from node 5 to node 1. As shown in the right subfigure, this counteraction restores a tie, and the game continues and evolves to the next step. In [ 16 ] and [ 17 ] , the conventional CBG is extended into the CBG on a graph, where two players compete over a networked battlefield. This formulation introduces a graphical constraint that limits resource movement to adjacent nodes. As a result, the game evolves from a single-step allocation problem into a multi-step dynamic process. Starting from an initial resource distribution, both players strategically maneuver their resources across connected nodes over multiple steps until one side secures control of the majority. Due to its ability to capture both the spatial structure and the sequential nature of competitive interactions, the MCBG on graphs serves as a natural and expressive model for GRAG, as illustrated in Figure 1 . Reinforcement Learning (RL) has proven to be a powerful tool for computing optimal policies in strategic games. A notable example is the game of Go, where the RL agent AlphaGo Zero achieved superhuman performance through self-play training [ 18 , 19 , 20 , 21 ] . Beyond Go, RL has been applied to various other competitive settings. For instance, [ 22 ] introduced a game theory-reinforcement learning (GT-RL) approach for fair and efficient benefit allocation in multi-operator, multi-reservoir systems. Similarly, [ 23 ] evaluated RL algorithms, particularly Q-learning and Sarsa variants, for micromanaging combat units in StarCraft: Brood War, demonstrating their effectiveness in optimizing unit control and decision-making in dynamic environments. Additionally, [ 24 ] proposed a deep RL-based learning paradigm for Multiplayer Online Battle Arena (MOBA) games, successfully training AI agents that outperformed top esports players in Honor of Kings. Beyond gaming applications, RL has been widely employed in resource allocation problems. [ 25 ] developed an RL-based mechanism for vehicle-to-vehicle communication, while [ 26 ] introduced a multi-agent RL framework for dynamic resource allocation in UAV-enabled networks. In [ 27 ] , an RL-based resource allocation system for edge computing optimized service trustworthiness by modeling the resource adjustment process as a Markov Decision Process (MDP) and training policies to maximize service-level agreement (SLA) compliance. Furthermore, [ 28 ] applied RL to compute optimal strategies for a conventional Blotto game with three nodes and ten resources, achieving a 60\% win rate against a random-policy agent. Building on these advancements, we present the first RL framework designed to solve the GRAG. Specifically, we model GRAG as an on-graph CBG, which we further formulate as a Markov Decision Process (MDP). A fundamental challenge in leveraging learning-based algorithms for the GRAG is the principled design of action spaces, state abstractions, and reward structures that guide the learning process toward effective and generalizable policies. An overly detailed state representation may lead to high-dimensional input spaces, increasing training complexity and the risk of overfitting. In addition, overly abstract representations may degrade learning performance due to insufficient information. To this end, we propose a tailored state representation that enables efficient training and improved learning performance. Another challenge in applying RL to GRAG is that while Deep Neural Networks (DNNs) in RL operate with a fixed structure, the action space varies dynamically at each step due to the graph constraints. To address this, we introduce an action-displacement adjacency matrix to determine valid actions at each step, enabling both players to effectively navigate the dynamic action space. For evaluation, we assess the strategies trained with