|
|
|
Algorithmic Issues in Mechanism Design (by Prof. Giuseppe Persiano)
|
|
In this lecture, I will give an introduction to the field of Algorithmic Mechanism Design. The discussion will focus on mechanisms for computationally hard problems including scheduling problems. We will study mechanisms that are truthful with respect to dominant strategies and with respect to Bayesian-Nash Equilibria and mechanisms that allow verification and those that do not.
Lecture material in pdf format
|
|
Approximate Nash Equilibria (by Prof. Paul Spirakis)
|
|
In this lecture, we first review basic notions of Game Theory (including Nash Equilibria and their existence proof). Then we define epsilon-Nash equilibria and we present recent results about existence of them , the complexity of finding them and some algorithms for computing such equilibria.
Lecture material in pdf format
|
|
One Hundred Bounds on the Price of Anarchy (by Prof. Marios Mavronicolas)
|
|
The Price of Anarchy was originally defined by Koutsoupias and Papadimitriou as a measure of the performance loss for a computer system due to the selfish behavior of its components. The components may be the users, the machines, the links or the agents. The performance loss is measured using the so called Social Cost (the cost to the system). Price of Anarchy is a worst-case measure: it refers to the worst-possible acceptable system behavior, usually (but not always) identified with Nash equilibrium.
The last seven years have witnessed a vast amount of effort towards proving bounds on the Price of Anarchy for a wide variety of system models and definitions of Social Cost. In these lecture, we will survey the most interesting such bounds. We will place some emphasis on a categorization of techniques used to prove the bounds, and we will address open problems.
Lecture material in pdf format
|
|
|
|
