# Reinforcement Learning for Game-Theoretic Resource Allocation on Graphs

arXiv: https://arxiv.org/abs/2505.06319 · HTML: https://mlsanity.com/paper/2505.06319/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 23 of its 52 references that are in the map.
- First posted on arXiv 8 May 2025.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 23 of 23)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [PettingZoo: Gym for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2009.14471/) (2020)
- [Tianshou: a Highly Modularized Deep Reinforcement Learning Library](https://mlsanity.com/paper/2107.14171/) (2021)
- [Towards Playing Full MOBA Games with Deep Reinforcement Learning](https://mlsanity.com/paper/2011.12692/) (2020)
- [Multi-Agent Reinforcement Learning Based Resource Allocation for UAV Networks](https://mlsanity.com/paper/1810.10408/) (2018)
- [Reinforcement Learning through Asynchronous Advantage Actor-Critic on a GPU](https://mlsanity.com/paper/1611.06256/) (2016)
- [Giraffe: Using Deep Reinforcement Learning to Play Chess](https://mlsanity.com/paper/1509.01549/) (2015)
- [From Duels to Battefields: Computing Equilibria of Blotto and Other Games](https://mlsanity.com/paper/1603.00119/) (2016)
- [Double Oracle Algorithm for Game-Theoretic Robot Allocation on Graphs](https://mlsanity.com/paper/2312.11791/) (2023)
- [HiBid: A Cross-Channel Constrained Bidding System with Budget Allocation by Hierarchical Offline Deep Reinforcement Learning](https://mlsanity.com/paper/2312.17503/) (2023)
- [Stackelberg Game Approaches for Anti-jamming Defence in Wireless Networks](https://mlsanity.com/paper/1805.12308/) (2018)
- [Failure-Resilient Coverage Maximization with Multiple Robots](https://mlsanity.com/paper/2007.02204/) (2020)
- [Sampling Equilibria: Fast No-Regret Learning in Structured Games](https://mlsanity.com/paper/2201.10758/) (2022)
- [Reinforcement Learning Agents in Colonel Blotto](https://mlsanity.com/paper/2204.02785/) (2022)
- [Dynamic Defender-Attacker Blotto Game](https://mlsanity.com/paper/2112.09890/) (2021)
- [Cyber Network Resilience against Self-Propagating Malware Attacks](https://mlsanity.com/paper/2206.13594/) (2022)
- [To Compute or not to Compute? Adaptive Smart Sensing in Resource-Constrained Edge Computing](https://mlsanity.com/paper/2209.02166/) (2022)
- [Fairness-aware Competitive Bidding Influence Maximization in Social Networks](https://mlsanity.com/paper/2308.10209/) (2023)

## Built on by (most cited first, 1 of 1)

- [GraphAllocBench: A Flexible Benchmark for Preference-Conditioned Multi-Objective Policy Learning](https://mlsanity.com/paper/2601.20753/) (2026)

## Abstract (arXiv)

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