CAREER: Dynamics of Searching for Equilibria

Purdue University, West Lafayette IN

Investigators

Abstract

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.