Signaling in Bayesian Network Congestion Games: the Subtle Power of Symmetry


  • Matteo Castiglioni Politecnico di Milano
  • Andrea Celli Politecnico di Milano
  • Alberto Marchesi Politecnico di Milano
  • Nicola Gatti Politecnico di Milano



Game Theory


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.




How to Cite

Castiglioni, M., Celli, A., Marchesi, A., & Gatti, N. (2021). Signaling in Bayesian Network Congestion Games: the Subtle Power of Symmetry. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5252-5259.



AAAI Technical Track on Game Theory and Economic Paradigms