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 transformation from offline approximation algorithms for linear optimization problems to online algorithms that achieve low regret.

92 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]