AF: SMALL: Frontiers in Algorithmic Game Theory

近年来，世界上许多经济活动都通过获得在线存在的旧市场和直接受到互联网启发和推动的新市场转移到互联网上，如赞助搜索和广告拍卖。在网络经济活动日益重要的推动下，人们越来越有兴趣通过计算机科学和经济学的接口来研究其联合计算和经济特性。经济学为研究经济系统提供了量化模型和方法。但很快就清楚了，这些模型和方法需要适应，因为其目的是研究涉及数千或数百万参与者的计算性系统。这种思想催生了算法博弈论(AGT)领域，该领域在过去的15年里已经发展成为一门成熟的研究学科。本项目将识别和研究该领域的新研究前沿，重点放在以下几个方面：-通过(I)弱化优化重要目标(如收入)所需的分配假设，加深我们对多项目机制的理解；(Ii)通过从真实机制转向可通过在线学习解决的机制，克服福利最大化的既定计算难题障碍；以及(Iii)使用最优传输理论来描述最优机制的结构。-通过了解如何(I)从对投标人分布的弱形式的样本访问中学习收入最优的拍卖，(Ii)从样本中测试给定拍卖的接近最佳性，以及(Iii)通过研究如何为拍卖人设计最优的信号发送方案以供拍卖人在常见的环境中使用，例如赞助搜索，通过研究如何为拍卖人设计最优的信号发送方案来描述最优机制的结构。-最后，回顾该领域的计算基础，研究因式分解和纳什均衡之间的关系。算法博弈论的工作本质上是跨学科的。该项目将通过在影响较大的经济学期刊上发表研究成果、组织跨学科研究会议、跨学科研究协作和研究调查，进一步促进计算机科学与经济学之间的互动。该项目的教育部分将包括对有意在研究或工业领域追求自己职业生涯的研究人员进行指导和教育，以及设计计算机科学和经济学接口的开创性课程。为了进一步促进该项目的教育和推广影响，PI将通过麻省理工学院PRIMES计划指导高中生进行计算机科学研究，将参与当地小学的计算机科学不插电活动，并将通过公共讲座与更广泛的公众接触。

Recent years have seen much of the world's economic activity transferred to the Internet through old markets that obtained online presence and new markets that are directly inspired and enabled by the Internet, such as sponsored search and ad auctions. Driven by the increasing importance of online economic activity, there has been much interest in investigating its joint computational and economic characteristics through research at the interface of Computer Science and Economics. Economics brought to the table quantitative models and methodology for studying economic systems. But it soon became clear that these models and methodology required adaptation, since the intention was to study systems that are computational while involving thousands or millions of participants. This thinking gave rise to the field of Algorithmic Game Theory (AGT), which has in the past fifteen years grown into a mature research discipline.This project will identify and investigate new frontiers of research in this field, focusing on the following:- Furthering our understanding of multi-item mechanisms by (i) weakening the distributional assumptions required for optimizing important objectives such as revenue; (ii) overcoming well-established computational intractability barriers for welfare maximization by moving away from truthful mechanisms to mechanisms solvable via online learning; and (iii) using optimal transport theory to characterize the structure of optimal mechanisms.- Discerning the role of learning and signaling in auction settings, by understanding how to (i) learn a revenue-optimal auction from weak forms of sample access to the bidders' distributions, (ii) test the near-optimality of a given auction from samples, and (iii) further a line of research going back to classical works of Akerlof and Milgrom-Weber by investigating how to design optimal signaling schemes for the auctioneer to use in common settings, such as sponsored search, where the auctioneer owns information about the properties of the items that the bidders do not have.- Finally, revisiting the computational foundations of the field, investigating the relation between Factoring and Nash equilibrium.The work in Algorithmic Game Theory is inherently interdisciplinary. This project will further the interaction between Computer Science and Economics through the publication of the research outcomes in high-impact Economics journals, organization of interdisciplinary research meetings, interdisciplinary research collaborations, and research surveys. The educational component of the project will involve the mentoring and education of researchers who intend to pursue their own careers in research or industry, and the design of pioneering classes in the interface of Computer Science and Economics. Furthering the educational and outreach impact of the project, the PI will be mentoring high school students in Computer Science research through the MIT PRIMES program, will be engaged in Computer Science Unplugged activities at local elementary schools, and will engage with the broader public through public lectures.