Algorithmic Information Design in Multi-Player Games: Possibilities and Limits in Singleton Congestion
Algorithmic Information Design in Multi-Player Games: Possibilities and Limits in Singleton Congestion
复制标题
多人游戏中的算法信息设计：单例拥塞的可能性和限制
DOI：
10.1145/3490486.3538238
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Xu, Haifeng
中科院分区：
文献类型：
--
作者：
Zhou, Chenghan;Nguyen, Thanh H.;Xu, Haifeng
大多数算法研究多代理信息设计集中在限制的情况下，最佳公共信号没有代理间的外部性，只有少数例外，调查特殊的游戏类，如零和游戏和第二价格拍卖。本文提出了一个基本类的负外部性博弈中的公共和私人信号的算法信息设计，即，原子单例拥塞博弈，在调度、路由、网络设计等方面有着广泛的应用.对于公共和私有信令，当资源数为常数时，我们证明了最优信息设计可以有效地计算.据我们所知，这是第一套高效的精确算法的信息设计简洁地表示多人游戏。我们的研究结果取决于新的技术，如开发某些简化形式，以competitively表征公共信号的均衡或代表球员的边际信念，在私人信号。当有许多资源，我们显示计算的棘手性的结果。https://arxiv.org/pdf/2109.12445.pdf这里，我们引入了一个新的概念（均衡）-oblikelihood NP-硬度，它排除了计算一个好的信令方案的任何可能性，而不管均衡选择。
Most algorithmic studies on multi-agent information design have focused on the restricted situation of optimal public signaling with no inter-agent externalities; only a few exceptions investigated special game classes such as zero-sum games and second-price auctions. This paper initiates the algorithmic information design of both public and private signaling in a fundamental class of games with negative externalities, i.e., atomic singleton congestion games, with a wide range of applications in scheduling, routing, and network design, etc.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. To our knowledge, this is the first set of efficient exact algorithms for information design in succinctly representable many-player games. Our results hinge on novel techniques such as developing certain reduced forms to compactly characterize equilibria in public signaling or to represent players' marginal beliefs in private signaling. When there are many resources, we show computational intractability results. Here, we introduce a new notion of (equilibrium)-obliviously NP-hardness, which rules out any possibility of computing a good signaling scheme, irrespective of the equilibrium selection.full version of this paper can be accessed from the following link: https://arxiv.org/pdf/2109.12445.pdf