Game-Theoretic and Algorithmic Analyses of Multi-Agent Routing under Crossing Costs

This paper introduces the Multi-Agent Routing under Crossing Cost model on mixed graphs, a novel framework tailored for asynchronous settings. In our model, instead of treating conflicts as hard constraints, each agent is assigned a path, and the system is evaluated through a cost function that measures potential head-on encounters. This ''crossing cost'', which is defined as the product of agents traversing an edge in opposite directions, quantifies the risk of congestion and delay in decentralized execution. Our contributions are both game-theoretic and algorithmic. We model the setting as a congestion game with a non-standard cost function, prove the existence of pure Nash equilibria, and analyze the dynamics leading to them. Equilibria can be found in polynomial time under mild conditions, while the general case is PLS-complete. From an optimization perspective, deciding whether a solution with zero crossing cost exists generalizes the Steiner Orientation problem, making the problem NP-complete. To address this hardness barrier, we design a suite of parameterized algorithms for minimizing crossing cost, with parameters including the number of arcs, edges, agents, and structural graph measures such as vertex cover.