# Algorithmic Game Theory

Fall semester 2011-12

Department of Informatics and Telecommunications

University of Athens

Professor: Elias Koutsoupias

## Table of Contents

## News

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

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

#### [2011-11-27] Problem Set 1 is due Dec 19.

#### [2011-10-31] The time and room for the Monday lectures have changed

#### [2011-10-29] Classes begin on Monday 31/10

## 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.

#### Similar courses

#### 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.

### Overview of algorithmic game theory (games, price of anarchy, mechanisms)

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

### Introduction to game theory, Nash's Theorem

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

### Correlated equilibria, zero-sum games

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

### Computational complexity of equilibria, PPAD, Lipton-Markakis-Mehta

### The Lemke-Howson algorithm

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

## Homework

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

- 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

- 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.

- 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.