Abstract:

In many online systems participants use data and algorithms to experiment and learn how to best use the system. Examples include traffic routing as well as online auctions. Game theory classically studies Nash equilibrium as the outcome of selfish interaction, and has many examples illustrating that selfish behavior can lead to suboptimal outcome for all participants. Over the last decade, we developed good understanding how to quantify the impact of strategic user behavior on overall performance in Nash equilibria of games. In this talk we will focus on games where players use a form of learning that helps them adapt to the environment. We ask if the quantitative guarantees obtained for Nash equilibria extend to such out of equilibrium game play,  possibly even in dynamically changing environments?