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

• URL: http://arxiv.org/abs/2002.05190v1
• Date: Wed, 12 Feb 2020 19:38:15 GMT
• Title: Signaling in Bayesian Network Congestion Games: the Subtle Power of Symmetry
• Authors: Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Nicola Gatti
• Abstract summary: The paper focuses on the problem of optimal ex ante persuasive signaling schemes, showing that symmetry is a crucial property for its solution. We show that an optimal ex ante persuasive scheme can be computed in time when players are symmetric and have affine cost functions.
• Score: 66.82463322411614
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
  We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings.
  arXiv  Detail & Related papers  (2024-06-23T00:27:28Z)
• Adversarial Knapsack and Secondary Effects of Common Information for Cyber Operations [0.9378911615939924]
  We formalize a dynamical network control game for Capture the Flag (CTF) competitions and detail the static game for each time step. We define the Adversarial Knapsack optimization problems as a system of interacting Weighted Knapsack problems. Common awareness of the scenario, rewards, and costs will set the stage for a non-cooperative game.
  arXiv  Detail & Related papers  (2024-03-16T03:41:12Z)
• Learning How to Strategically Disclose Information [6.267574471145217]
  We consider an online version of information design where a sender interacts with a receiver of an unknown type. We show that $mathcalO(sqrtT)$ regret is achievable with full information feedback. We also propose a novel parametrization that allows the sender to achieve $mathcalO(sqrtT)$ regret for a general convex utility function.
  arXiv  Detail & Related papers  (2024-03-13T17:44:16Z)
• Information Design in Multi-Agent Reinforcement Learning [61.140924904755266]
  Reinforcement learning (RL) is inspired by the way human infants and animals learn from the environment. Research in computational economics distills two ways to influence others directly: by providing tangible goods (mechanism design) and by providing information (information design)
  arXiv  Detail & Related papers  (2023-05-08T07:52:15Z)
• Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
  Nayyar et al. (2013) showed that imperfect information can be abstracted away from common-payoff games by having players publicly announce their policies as they play. This work shows that certain regularized equilibria do not possess the aforementioned non-correspondence problem. Because these regularized equilibria can be made arbitrarily close to Nash equilibria, our result opens the door to a new perspective to solving two-player zero-sum games.
  arXiv  Detail & Related papers  (2023-01-22T16:54:06Z)
• Commitment with Signaling under Double-sided Information Asymmetry [19.349072233281852]
  This work considers a double-sided information asymmetry in a Bayesian Stackelberg game. We show that by adequately designing a signaling device that reveals partial information regarding the leader's realized action to the follower, the leader can achieve a higher expected utility than that without signaling.
  arXiv  Detail & Related papers  (2022-12-22T01:30:54Z)
• Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure of Costs [65.23158435596518]
  Solving the multi-vehicle routing problem as a team Markov game with partially observable costs. Our multi-agent reinforcement learning approach, the so-called multi-agent Neural Rewriter, builds on the single-agent Neural Rewriter to solve the problem by iteratively rewriting solutions.
  arXiv  Detail & Related papers  (2022-06-13T09:17:40Z)
• Algorithmic Information Design in Multi-Player Games: Possibility and Limits in Singleton Congestion [10.817873935576412]
  This paper initiates the algorithmic information design of both emphpublic and emphprivate signaling in games with negative externalities. For both public and private signaling, we show that the optimal information design can be efficiently computed when the number of resources is a constant.
  arXiv  Detail & Related papers  (2021-09-25T22:02:32Z)
• Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
  We focus on the problem of finding an optimal strategy for a team of two players that faces an opponent in an imperfect-information zero-sum extensive-form game. In that setting, it is known that the best the team can do is sample a profile of potentially randomized strategies (one per player) from a joint (a.k.a. correlated) probability distribution at the beginning of the game. We provide an algorithm that computes such an optimal distribution by only using profiles where only one of the team members gets to randomize in each profile.
  arXiv  Detail & Related papers  (2020-09-21T17:51:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.