Signaling in Bayesian Network Congestion Games: the Subtle Power of Symmetry
This addresses the challenge of improving network efficiency through strategic information provision in multi-agent systems, with incremental contributions to algorithmic game theory.
The paper tackles the problem of designing optimal information structures to reduce social cost in Bayesian network congestion games, showing that an optimal ex ante persuasive signaling scheme can be computed in polynomial time for symmetric players with affine cost functions, but becomes NP-hard for asymmetric players.
Network congestion games are a well-understood model of multi-agent strategic interactions. Despite their ubiquitous applications, it is not clear whether it is possible to design information structures to ameliorate the overall experience of the network users. We focus on Bayesian games with atomic players, where network vagaries are modeled via a (random) state of nature which determines the costs incurred by the players. A third-party entity---the sender---can observe the realized state of the network and exploit this additional information to send a signal to each player. A natural question is the following: is it possible for an informed sender to reduce the overall social cost via the strategic provision of information to players who update their beliefs rationally? The paper focuses on the problem of computing optimal ex ante persuasive signaling schemes, showing that symmetry is a crucial property for its solution. Indeed, we show that an optimal ex ante persuasive signaling scheme can be computed in polynomial time when players are symmetric and have affine cost functions. Moreover, the problem becomes NP-hard when players are asymmetric, even in non-Bayesian settings.