Algorithmic Game Theory

In problem 3, you can assume that the graph \(G\) is 2-edge-connected.

• Monday 2-4, Room Ε (notice the change)
• Friday 4-6, Room Γ

Recently we have witnessed a fusion of the fields of Game Theory, Algorithms, and Networks, driven mostly by the social and economic issues of the Internet and the Web. This course addresses many of the research directions that have been developed in this framework such as computational issues of games, the price of anarchy, and mechanisms.

This course is for graduate students with sufficient background in mathematics and algorithms. There are no specific prerequisites other than "mathematical" maturity. If in doubt, please discuss it with the instructor.

The final grade will depend on

• final exam (60%)
• homework (20%)
• project: an evaluation or review article about a problem or a publication (20%)

A passing grade is required for each one.

We will use original research articles, notes available on the web of similar courses, and the book

• N. Nisan, E. Tardos, T. Roughgarden, and V. Vazirani. Algorithmic Game Theory. Available online.

• scibe notes
• Sources:
  • Chapter 1 of AGT book
  • Papadimitriou. Algorithms, games, and the internet

• scibe notes
• Sources:
  • Chapter 1 of AGT book
  • Introductory chapters in game theory books
  • Nash. Non-cooperative games

• scibe notes
• Sources:
  • Chapters 1 and 2 of AGT book
  • Aumann. Correlated equilibrium as an expression of Bayesian rationality

• scibe notes
• Sources:
  • Chapter 2 of AGT book
  • Daskalakis, Goldberg, and Papadimitriou. The complexity of computing a Nash equilibrium
  • Lipton, Markakis, and Mehta. Playing large games using simple strategies

• scibe notes
• Sources:
  • Chapter 3 of AGT book

1. Consider 2 player games with 2 strategies for every player
   • Show that a game cannot have more than 2 pure Nash equilibria, unless it has infinitely many mixed Nash equilibria
   • Give necessary and sufficient conditions for the existence of a mixed equilibrium
2. Show how the Lemke-Howson algorithm works for the instance $$A= \left(\begin{array}{ccc} 1 & 4 & 2\\ 1 & 2 & 4\\ 4 & 2 & 1 \end{array}\right) \qquad\text{and}\qquad B= \left(\begin{array}{ccc} 2 & 2 & 4\\ 4 & 1 & 1\\ 1 & 4 & 1 \end{array}\right). $$

   Use the lexicographically first move when there are more than one choices.

3. Consider the task allocation problem (scheduling) on identical machines. In the usual analysis of the Price of Anarchy we consider as social cost the makespan. Here we want to study another social objective related to unfairness; in a ideally fair situation, all machines will be equally loaded. We want to study how much a Nash equilibrium can be away from this ideal situation. Specifically, we consider as social objective the minimum load among the machines and we want this to be as maximum as possible.
   • Show that for 2 machines the Price of Anarchy is 2.
   • Find upper and lower bounds for 3 or more machines.