Algorithmic Game Theory Lecture Notes (Cornell CS6840)

### Algorithmic Game Theory Lecture Notes (Cornell CS6840) #### Overview The lecture notes for Cornell University's CS6840 course on Algorithmic Game Theory provide a comprehensive introduction to the intersection of game theory and computer science, focusing on algorithm design and analysis in the context of games. The course, taught by Eva Tardos with scribe notes by Costandino Dufort Moraites, explores fundamental concepts, theoretical frameworks, and practical applications within the field. #### Motivation and Connection Between Game Theory and Computer Science The notes emphasize the evolving role of computer science, particularly in the era of the internet. Traditionally, computer science was focused on optimizing algorithms for individual machines; however, the advent of the internet has transformed this landscape. Now, algorithms designed by one entity can impact a global network, making it crucial to consider the interactions between multiple agents or players. This shift necessitates a deeper understanding of how these agents make decisions and interact with each other, which is where game theory comes into play. #### Different Perspectives The course highlights several distinct perspectives that differentiate its approach from traditional game theory: 1. **Algorithms and Complexity:** A significant emphasis is placed on designing and analyzing algorithms, which is a core skill set for computer scientists. Economists may not prioritize the complexity of finding equilibria in a system as much as computer scientists do. From a computer science perspective, exploring the complexity of equilibrium computation leads to interesting theoretical results. 2. **Simplicity of Mechanisms:** From a systems background, mechanisms must be simple and easy to implement. Complexity in design can lead to practical challenges, especially when considering real-world deployment. 3. **(Approximate) Optimality:** In many scenarios, achieving perfect optimality might not be feasible or even necessary. For example, in the context of average response times, the difference between 7 and 8 seconds might not be significant. Therefore, the focus shifts towards approximate optimality. #### Course Structure and Materials The course syllabus is outlined on the web page, providing a detailed schedule of topics to be covered throughout the semester. The notes mention that since the publication of the main textbook, there have been changes in the field of mechanism design. As a result, Jason Hartline's book on mechanism design will be used more extensively than the listed textbook. Additionally, Ken Binmore's introductory text on game theory is recommended for those seeking a quick overview of the subject. #### Example: Braess' Paradox To illustrate some of the concepts discussed, the lecture notes delve into an example known as Braess' paradox. This paradox demonstrates a counterintuitive phenomenon where adding a new road to a network can actually increase traffic congestion. **Graph Representation:** Consider a graph with two strategies: Strategy 1 represents the bottom path, while Strategy 2 represents the top path. Each edge has a delay function \(d(e)\) that is monotone increasing, meaning the delay increases as more players use the edge. For simplicity, assume \(d(e) = x\) if \(x\) players use the edge. The graph includes two edges with a weight of 100, representing a high fixed delay. In this setup, players choose their strategies based on minimizing their delay. However, Braess' paradox occurs when a new edge is introduced with a low delay, seemingly improving the network but ultimately leading to worse overall performance due to the change in player behavior. **Implications:** Braess' paradox highlights the importance of understanding how network structure affects player behavior and outcomes. It also underscores the need for careful design and analysis of mechanisms, particularly in complex systems where the addition of resources does not always yield positive results. #### Conclusion The lecture notes for Cornell's CS6840 course offer valuable insights into the intersection of game theory and computer science. By examining the unique perspectives brought by computer scientists and economists, the course provides a rich foundation for understanding the complexities of algorithmic game theory. Through examples like Braess' paradox, students gain a deeper appreciation for the intricate dynamics at play in networked systems and the importance of considering both efficiency and simplicity in mechanism design.