Learning-Augmented Coordination Mechanisms

The inefficiency of decentralized resource allocation, a core challenge in Algorithmic Game Theory, is classically measured by the Price of Anarchy (PoA) and the Price of Stability (PoS). The most widely studied and foundational class of these models are atomic and non-atomic congestion games, for which a robust theory quantifying the inefficiency of equilibria is well-established. To mitigate the effects of this selfish behavior, we employ Coordination Mechanisms, which modify resource costs to incentivize socially improved equilibrium outcomes. In their standard form, Coordination Mechanisms have been limited by a pessimistic, worst-case view; it is assumed that the demand is unknown and adversarially chosen. Consequently, positive results remain sparse, applying mainly to specialized network topologies like parallel links. We address this limitation by studying the design and analysis of learning-augmented coordination mechanisms, where the mechanism is endowed with a potentially inaccurate prediction of the demand $\bar{r}$. We study general atomic and non-atomic congestion games with polynomial latency functions of degree $d$. Our main positive result is a learning-augmented coordination mechanism tuned by a confidence parameter $\beta$ which achieves a "best of both worlds" type of result: it achieves approximately optimal performance for an accurate prediction without sacrificing the worst-case guarantee of a good equilibrium (PoS). We further establish bounds on a stronger robustness measure, the PoA-Robustness (worst equilibrium performance under cost modification). The mechanism's construction relies on transforming approximate equilibria of the original game into exact equilibria of the modified game using a carefully defined approximate potential function. We complement our positive results by providing impossibility results. We first show that a stronger notion of consistency, requiring that all equilibria have optimal social cost for an accurate prediction, fails to guarantee bounded robustness. We also show a strong error tolerance limit: any mechanism achieving optimal consistency in non-atomic games suffers a sharp, discontinuous performance that collapses to the original PoA value under even infinitesimally small prediction errors, highlighting the limits of efficiency guarantees in non-atomic congestion games.