Course Objective

The course focusses on the modeling, analysis and optimization of
complex decision making processes which involve human behavior (such as
selfish, risk-averse, altruistic or malicious behavior). Building on
game-theoretic foundations, you learn to model processes of complex
decision making and to quantify the inefficiency caused by human
behavior.

The main goal of the course is to equip you with algorithmic
optimization techniques to master the challenging task of reducing the
inefficiency of such processes. These techniques find their applications
for example in Traffic Routing, Network Design, Cost Sharing,
Resource Allocation and Auction Design.

Course Content

• network routing and the price of anarchy
• Braess paradox and the network design problem
• computation and inefficiency of equilibria
• congestion games and cost sharing games
• smoothness framework and learning in games
• combinatorial auctions and the VCG mechanism
• sponsored search auctions

Teaching Methods

Lectures and tutorials. Exercises will be given each week and students
are expected to present their solutions during the tutorials. In
addition, students will have to work on and hand in three take-home
assignments (which will be graded).

Method of Assessment

Final exam – Individual assessment

Assignments – Individual assessment

Entry Requirements

Students should have some background knowledge of combinatorial
optimization; in particular, they should be familiar with fundamental
optimization problems (shortest path, matching, flow, scheduling),
algorithms and complexity (exact and approximation algorithms, P vs.
NP), and linear and convex programming (duality, KKT conditions).

Literature

• N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Editors),
Algorithmic Game Theory, Cambridge University Press, 2007.
• Y. Shoham and K. Leyton-Brown, Multiagent Systems, Cambridge
University Press, 2009.
• Lecture Notes