CAREER: Dynamics of Searching for Equilibria

竞争和纳什均衡是描述多个相互作用的参与者的系统的关键经济概念，每个参与者都有自己的激励。这些概念有不同的应用，从通知和平协议和劳动力市场的设计，以提供对生物过程的见解。竞争和纳什均衡的概念是静态的，而动态可能更好地反映了玩家不断适应当前世界状态的场景。本研究的目标是研究动态，游戏和学习空间中的新的基本问题。这项研究的灵感来自于一些应用，例如在在线平台上设计高效和公平的市场，以及设计分配废物的机制。该项目是跨学科的，汇集了来自博弈论，算法，复杂性，动力系统，经济学，优化，机器学习，概率和统计学的工具。该项目包括为研究生和本科生开发课程和培训，组织一系列研讨会，并成立一个计算机科学和数学俱乐部，以帮助将学生社区聚集在一起。具体的研究方向包括：（i）市场动态，其中具有本地信息的计算有限的参与者只会随着时间的推移而相互作用。尽管每个参与者都进行了局部优化，但是否可能达到全球有效的分配？市场会增长/萎缩吗？(ii)学习的激励，专注于游戏，即使是几个玩家一起学习，但有不同的激励，可以影响他们的行动。玩家应该使用什么算法？(iii)局部搜索，它对拥塞博弈中的最佳响应动态等过程进行建模。一个高层次的问题是：图的几何形状如何与局部搜索的复杂性相关？通过回答这个领域的问题，这项研究将有助于游戏，学习和动力学的理论基础，同时也为激励应用提供见解。这个奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Competitive and Nash equilibria are key economic concepts that describe systems with multiple interacting players, each with its own incentives. These concepts have diverse applications, from informing peace agreements and the design of labor markets to giving insights into biological processes. The competitive and Nash equilibrium notions are static, while dynamics may better reflect scenarios where players are continually adapting to the current state of the world. The goal of this research is to study new fundamental questions in the space of dynamics, games, and learning. The research is inspired by applications such as designing efficient and equitable markets on online platforms and devising mechanisms for allocating waste. The project is interdisciplinary, bringing together tools from game theory, algorithms, complexity, dynamical systems, economics, optimization, machine learning, probability, and statistics. The project includes course development and training for graduate and undergraduate students, organizing a series of workshops, and forming a computer science and math club to help bring together the student community.Concrete research directions include: (i) Market dynamics, where computationally bounded players with local information only interact over time. Are globally efficient allocations likely to be reached, despite each player optimizing locally? Will the market grow/shrink? (ii) Incentives in learning, focusing on games where even a few players are learning together but have different incentives that can influence their actions. What algorithms should the players use? (iii) Local search, which models processes such as best response dynamics in congestion games. A high-level question is: How is the geometry of the graph related to the complexity of local search? By answering questions in this space, the research will contribute to the theoretical foundations of games, learning, and dynamics while also providing insight into motivating applications. The project will also include organizing workshops on Games and Learning.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.