Potential functions and the inefficiency of equilibria

• Autores: Tim Roughgarden
• Localización: Proceedings oh the International Congress of Mathematicians: Madrid, August 22-30,2006 : invited lectures / coord. por Marta Sanz Solé , Javier Soria de Diego , Juan Luis Varona Malumbres , Joan Verdera , Vol. 3, 2006, ISBN 978-3-03719-022-7, págs. 1071-1094
• Idioma: inglés
• Enlaces
  • Texto completo (pdf)
• Resumen

  • We survey one area of the emerging field of algorithmic game theory: the use of approximation measures to quantify the inefficiency of game-theoretic equilibria. Potential functions, which enable the application of optimization theory to the study of equilibria, have been a versatile and powerful tool in this area. We use potential functions to bound the inefficiency of equilibria in three diverse, natural classes of games: selfish routing networks, resource allocation games, and Shapley network design games.