ICES: Small: A Probabilistic Look at Algorithmic Game Theory

近年来，通信网络和覆盖在这些网络上的计算平台有了显着的增长；主要的例子是因特网及其创建和启用的系统。与此同时，人们已经认识到，为了正确地理解和设计这种系统，人们需要将计算机科学和经济学的见解和方法纳入他们的研究中，因为这些系统往往是大型的、高度分散的，并由数千甚至数百万自利的各方拥有、运营和使用。拟议的研究将促进计算机科学和经济学之间日益增长的互动，这是一个新的研究方向，其动机是系统地研究不确定性在经济系统的结构和可控性中的作用。这项研究的关键将是使用统计物理学和概率论的概念和工具，最终加强这些领域与算法博弈论的相互作用。不确定性肯定既存在，也在研究相互作用的个人系统时被考虑在内。游戏的玩家可能不确定她的对手的收益，甚至她自己的收益，可能不能完全观察其他玩家使用的策略和由这些策略创建的潜在机会，或者甚至可能不确定对手的确切数量、游戏的结构、玩家的移动顺序等。同样，社会规划者或机制设计者可能对机制中的代理人的价值或预算、参与者的数量、参与者具有的关于其他参与者的信息等具有不确定性。这种不确定性有时通过将概率信念分配给不固定的系统参数来建模，通过获得最坏情况的保证来消除其他时间。以贝叶斯方式利用不确定性和通过最坏情况/先前免费的结果来处理不确定性都是博弈论发展的核心。然而，我们认为，通过将概率论、统计物理学和算法的工具引入博弈论，对不确定性进行系统处理仍然可以获得巨大的好处。我们将使用这些工具(1)了解聚集形式的大型博弈(具有许多对称性或匿名性的博弈)的均衡结构和复杂性，(2)在最优多维机制设计方面取得进展，(3)研究网络博弈中的动力学，(4)了解交互个体的大型网络中行为的相关性，(5)表征博弈随机集成中均衡的复杂性和结构性质，以及(6)研究自私路由博弈中无政府的价格，其中参与者的效用是延迟的非线性概率函数。

Recent years have seen a remarkable growth of communication networks and computational platforms overlaid on these networks; primary examples are the Internet and the systems created and enabled by it. At the same time, it has been recognized that to properly understand and engineer such systems one needs to incorporate insights and methods from both Computer Science and Economics into their study, as these systems tend to be large, highly distributed, and owned, operated and used by thousands, or even millions, of self-interested parties. The proposed research will contribute to the growing interactions between Computer Science and Economics a new research direction motivated by a systematic study of the role of uncertainty in the structure and tractability of economic systems. Crucial in this study will be the use of concepts and tools from Statistical Physics and Probability Theory, ultimately strengthening the interaction of these fields with Algorithmic Game Theory.Uncertainty is most certainly both present and taken into account in the study of systems of interacting individuals. A player of a game may be uncertain about her opponents'payoffs or even her own payoff, may be unable to fully observe the strategies used by the other players and the potential opportunities created by these strategies, or may even be uncertain about the exact number of opponents, the structure of the game, the order of players' moves, etc. Likewise a social planner, or mechanism designer, may have uncertainty about the values or budgets of the agents in the mechanism, the number of participants, the information that the participants have about the other participants, etc. This uncertainty is sometimes modeled by assigning probabilistic beliefs to the parameters of the system that are not fixed, and other times eliminated by obtaining worst-case guarantees.Both harnessing uncertainty in the Bayesian way and tackling it via worst-case/prior-free results have been central in the development of Game Theory. Nevertheless, we believe that there still remain large benefits to be obtained by a systematic treatment of uncertainty, through the import of tools from Probability Theory, Statistical Physics and Algorithms into Game Theory. We will employ these tools (1) to understand the equilibrium structure and complexity of large games of aggregative form (games with a lot of symmetries or anonymity), (2) to make progress in optimal multi-dimensional mechanism design, (3) to study dynamics in network games, (4) to understand the correlation of behaviors across large networks of interacting individuals, (5) to characterize the complexity and structural properties of equilibria in random ensembles of games, and (6) to study the Price of Anarchy in selfish routing games where the players' utilities are non-linear probabilistic functions of the delay.