ICES: Small: A Probabilistic Look at Algorithmic Game Theory

ICES：小：算法博弈论的概率视角

• 批准号: 1101491
• 负责人: Constantinos Daskalakis
• 金额: $ 40万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1101491&HistoricalAwards=false
• 关键词: ICES; Small; Probabilistic; Look; Algorithmic

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.

近年来，通信网络和覆盖在这些网络上的计算平台显著增长;主要的例子是互联网和由它创建和启用的系统。同时，人们已经认识到，要正确理解和设计这样的系统，需要将计算机科学和经济学的见解和方法结合到他们的研究中，因为这些系统往往很大，高度分散，由成千上万甚至数百万的自利团体拥有、经营和使用。拟议的研究将有助于计算机科学和经济学之间日益增长的相互作用，这是一个新的研究方向，其动机是系统地研究不确定性在经济系统结构和易处理性中的作用。在这项研究中，至关重要的是使用统计物理学和概率论的概念和工具，最终加强这些领域与博弈论的相互作用。在相互作用的个体系统的研究中，不确定性肯定是存在和考虑的。一个游戏的参与者可能不确定她的对手的收益，甚至她自己的收益，可能无法完全观察其他参与者使用的策略和这些策略创造的潜在机会，甚至可能不确定对手的确切数量，游戏的结构，玩家的行动顺序等。可能具有关于机制中的代理的值或预算、参与者的数量、参与者具有的关于其他参与者的信息等的不确定性。这种不确定性有时通过将概率信念分配给不固定的系统参数来建模，其他时候则通过获得最坏情况保证来消除。以贝叶斯方式利用不确定性并通过最坏情况/无先验结果来解决不确定性一直是博弈论发展的核心。尽管如此，我们相信，仍然有很大的好处，通过系统地处理不确定性，通过进口的工具，从概率论，统计物理和算法到博弈论。我们将使用这些工具（1）来理解聚合形式的大型博弈的均衡结构和复杂性（具有大量对称性或匿名性的游戏），（2）在最佳多维机制设计方面取得进展，（3）研究网络游戏中的动力学，（4）了解交互个体大型网络中行为的相关性，（5）刻画了随机博弈系综中均衡的复杂性和结构性质;（6）研究了局中人效用是时延的非线性概率函数的自私路由博弈中的无政府价格。