Katrina Ligett

Thesis Title: A Learning Perspective on Selfish Behavior in Games
Degree Type: Ph.D. in Computer Science
Advisor(s): Avrim Blum
Graduated: August 2009

Abstract:

Computer systems increasingly involve the interaction of multiple self-interested agents. The designers of these systems have objectives they wish to optimize, but by allowing selfish agents to interact in the system, they lose the ability to directly control behavior. What is lost by this lack of centralized control? What are the likely outcomes of selfish behavior?

In this work, we consider learning dynamics as a tool for better classifying and understanding outcomes of selfish behavior in games. In particular, when such learning algorithms exist and are efficient, we propose “regret-minimization” as a criterion for self-interested behavior and study the system-wide effects in broad classes of games when players achieve this criterion. In addition, we present a general trans- formation from offline approximation algorithms for linear optimization problems to online algorithms that achieve low regret.

Thesis Committee:
Avrim Blum (Chair)
Anupam Gupta
R. Ravi
Eva Tardos (Cornell University)

Keywords:
algorithmic game theory, online algorithms, regret minimization