# Algorithmic Game Theory

Fall semester 2011-12

Department of Informatics and Telecommunications
University of Athens
Professor: Elias Koutsoupias

## News

#### [2012-02-04] Take-home exam clarification:

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

## General Information

### Rooms and Hours:

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

#### Office hours:

• Wednesday 1:30-2:30 (Room B7)

### Description

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.

### Sources

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.

#### Blogs

• Noam Nisan, the definite blog on algorithmic game theory

## Lectures

Here is a rough list of the topics covered in class. The scribe notes are given only as a reminder of the lecture material. It is an unreliable source and most likely it contains errors. For these topics, you should study the original sources (use, for example, google scholar to find and download the papers), notes from similar courses, and textbooks.

## Homework

### Problem Set 1. Hand in: Mon 19/12

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.