Speakers Eyal Even-Dar Vahab Mirrokni Tutorial Abstract Recently, a lot of effort has been devoted to analyzing response dynamics in various games. Questions about the dynamics themselves and their convergence properties attracted a great deal of attention. This includes, for example, questions like “How long do uncoordinated agents need to reach an equilibrium?” and “Do uncoordinated agents quickly reach a state with low social cost?”. An important aspect in studying such dynamics is the learning model employed by self-interested agents in these models. Studying the effect of learning algorithms on the convergence rate of players is crucial for developing a solid understanding of the corresponding games. In this tutorial, we first describe an overview of the required terminology from game theory. Then, we survey results about the convergence of myopic and learning-based best responses of players to equilibria and approximately optimal solutions, and study the effect of various learning algorithms in convergence (rate). Throughout the tutorial, we describe fundamental connections between local search algorithms and learning algorithms with the convergence of best-response dynamics in multi-agent games. Slides A preliminary draft of the slides is here. Note that the slides are still work in progress. Biography of Speakers Eyal Even-Dar is research scientist at Google New York. He holds a Ph.D from Tel Aviv University since 2005, and has since been a postdoctoral at University of Pennsylvania and a researcher at Google, NY. He is currently interested in learning theory, theoretical and practical aspects of algorithms, and algorithmic game theory. His personal homepage is here. Vahab Mirrokni is a research scientist at Google New York. He joined Google Research after receiving a B.Sc. from Sharif University in 2001 and a Ph.D from MIT in 2005, one year as a researcher at Amazon.com and MIT, and two years at Microsoft Research, theory group. Vahab's main research interests are algorithmic game theory, approximation algorithms, and the Internet Economics. He has published more than 55 papers in journals and conferences and has filed more than 12 patents in these areas. He has been the co-winner of the SODA 2005 best student paper award, and the ACM EC 2008 best paper award. His personal homepage is here. References |