Michael Kearns: Game Theory and Machine Learning

Definition and Origins

• Game theory is a mathematical framework for reasoning about collective outcomes in systems of interacting individuals, requiring at least two actors.
• While rooted in economics, the field has expanded over the last 20 years into "algorithmic game theory" by computer scientists.
• Classic examples, such as the Prisoner's Dilemma, demonstrate how individual self-interest can lead to collective outcomes worse than those achievable through cooperation.

Key Theoretical Concepts

• John Nash established the existence of competitive equilibrium under general circumstances, providing the conceptual stability necessary to reason about potential outcomes.
• A central insight in algorithmic game theory is the connection between game theory and "no regret learning," a branch of machine learning.
• This connection demonstrates that self-interested players can reach an equilibrium in a relatively short number of steps through iterative behavior.

Real-World Applications and Mechanisms

• Navigation apps (e.g., Google Maps, Waze) and social media algorithms use machine learning to compute selfish best responses for users based on the current actions of all other players.
• These platforms effectively nudge users toward a competitive or Nash equilibrium by optimizing individual utility (e.g., minimizing travel time or maximizing engagement).
• Optimization is driven by machine learning models predicting traffic patterns, user preferences, and newsfeed engagement.

Critical Limitations and Risks

• Reaching a competitive equilibrium does not guarantee an optimal collective outcome; theory and traffic data indicate it can significantly increase total driving time compared to alternative solutions.
• A primary lesson from game theory is that the state of equilibrium may not represent the best possible scenario for all participants.
• The field explores the design of platforms and algorithms capable of influencing outcomes to avoid inefficient equilibria.