2018 Lecturer: Eva Tardos
Learning and Efficiency of Outcomes in Games
Selfish behavior can often lead to suboptimal outcome for all participants, a phenomenon illustrated by many classical examples in game theory. Over the last two decades our community developed good understanding on how to quantify the impact of strategic user behavior on the overall performance in many games by analyzing Nash equilibria of these games (including traffic routing as well as online auctions). Learning outcomes emerged in recent years as an attractive alternative to Nash equilibrium, modeling players who haven’t reached a stable equilibrium, but rather use algorithmic learning. We propose that learning is a good model of behavior in games where the systems has high economic value overall, but where stakes of individual items are low, which makes exploring and learning a good behavior. Such games include both Internet packet routing as well as online auctions. In this talk we consider a few closely related questions: What are broad classes of learning behaviors that guarantee high social welfare in games, are these results robust to situations when the game or the population of players is dynamically changing, and does data from such games suggest that learning is indeed a good behavioral model of the participants.