Coupling-Aware Reinforcement Learning for Co-Evolving Graph Games

Building hydrogen station networks, electric vehicle (EV) charging grids, or vaccine distribution systems requires coordinating two separately operated graphs - demand-side facilities and the supply-side networks they depend on - where each operator's payoff depends on the other's choices. We formalize this as the Co-Evolving Graph Game (CEGG), a setting that sits between facility location, interdependent-network analysis, and graph-based multi-agent reinforcement learning (MARL) but is not jointly addressed by any of them. We propose Cross-Graph Attention with Policy Mirror Descent (CGA-PMD), pairing cross-graph attention - which lets each agent read only the partner-graph nodes structurally coupled to its own - with a policy mirror descent update for stable training. Across three reward domains and a range of practical network scales, we find that the structure of the coupling selects which method wins: at small scale most methods are competitive, but as scale grows or coupling becomes irregular, only CGA-PMD remains productive while own-only, unmasked-attention, and Proximal Policy Optimization (PPO)-based variants all fail in distinct ways. Our theoretical analysis explains why: PMD's Kullback-Leibler (KL) regularization admits an iteration-uniform cumulative drift bound while PPO's clip update does not, predicting CGA-PMD's stability in the hard regime where PPO-based methods collapse.