This talk presents repeated game analysis as an important and practical tool for network and protocol designers. Incentives are a potential concern for a number of networked applications. Well studied examples include routing, where profit-maximizing firms control the flow of traffic, and peer-to-peer networks. To the extent that incentives significantly impact the outcome of a system, application and protocol designers require tools and frameworks that allow them to better understand the impact of their design decisions on the outcome of these systems.
Repetition is a prevalent and critical aspect of many networking applications and protocols. Most networked protocols and architectures seek to optimize performance over a longer timescale and many have explicit support for repetition. Similarly, most players in networked applications are interested in longer horizons, whether they be firms building a business or typical individuals trying to use a system. Fortunately, the notion of repeated games is a well-understood and developed area of Economic and Game Theory research. A key conclusion from that literature is that the outcome of the repeated game can differ qualitatively from that of the one-shot game. Nonetheless, the tools of repeated games have rarely if ever been brought to bear on networking problems.
Our work presents the descriptive and prescriptive power of repeated game analysis by making specific contributions to several relevant networking problems. The applications considered are inherently repeated in practice, yet our research is the first to consider the repeated model for the particular problem. As an illustrative example, this this particular talk will focus on one practical problem: the design of incentive-based routing protocols. We find that various protocol parameters -- such as protocol period, minimum bid size, and unit of measure (e.g., Mbps vs MBps) -- can have a significant impact on the system outcome. The conclusions have practical importance and can be used by protocol designers to address the problem of the repeated dynamic.
Finally, we argue that the results obtained in this and other networking problems considered stem from properties fundamental to networked applications -- and their natural relationship with properties of repeated games. This suggests that the intuitions and tools of repeated game theory are applicable to a broad class of networking problems. Indeed we hope that these results represent the beginning of an increased use of repeated games for networked applications.
