# Algorithmic Game Theory, Mechanism Design and Computational Economics (AGT-CE)(Winter Semester 2017--2018, Max-Planck-Institut für Informatik)

## Basic Information

OFFICIAL Course Webpage: CLICK HERE. In my opinion, the template there is not good (I was forced to use it), so I make this cleaner version of unofficial course webpage. All updates after 27 February, 2018 will be made to this cleaner webpage ONLY.

We welcome feedback about the lecture notes of this course. The feedback can be pointing out mistakes or typos in the lecture notes, or proposing some important materials about the topics which we have missed, or suggesting how the current materials might be better organized. Please send your feedback to ycheung [AT] mpi-inf [DOT] mpg [DOT] de

Lecturer: Yun Kuen Cheung, Marco
Tutor (also holding two lectures for this course): Bhaskar Ray Chaudhury
Course Time: Basically, weekly lecture on Monday (4-6pm), biweekly exercise session on Tuesday (2-4pm). But there are exceptions; please see the precise schedule below.

## Course Description

Games and markets arise wherever there are two or more agents competing for selfish benefits. In their enormous applications, "agents" can refer to humans, animals, computers, bacterias or even molecules.

In the past 20 years, the algorithmic/computational aspects of game/market/auction theory have grown to become a popular topic in (theoretical) computer science, economics, operations research, dynamical system, and more. In this course, we will discuss the very core of this exciting new research direction. This course is divided into three parts.

In the first part, we cover some basic concepts in games, including Zero-sum Game and General-sum Game, Nash Equilibrium, Market Equilibrium, Correlated Equilibrium and Regret Minimization. Algorithms for finding such equilibria will be presented. Concerning equilibrium, one fundamental question is how good an equilibrium is. Prisoner Dilemma is a canonical example to show that Nash Equilibrium can be very bad. Efficiency measures and techniques, e.g., Price of Anarchy and Smoothness, will be covered.

In the second part, we address another fundamental question concerning equilibrium: how an equilibrium is reached. We will study a number of simple game/market dynamics, e.g., Multiplicative-Weight Updates, Tatonnement and Proportional Response Dynamic, aiming to explain how equilibrium can be reached in a highly distributed environment, in which individual agents can access very limited local information only. We will also look into an interesting special case of Linear Fisher and Arrow-Debreu markets, for which flow-type algorithms were developed.

In the third part, we focus on the prominent application of game theory in the digital era --- design of auction, or what we call the Mechanism Design, e.g., eBay, Google ad auction, spectrum auction. In the simplest setting, there is an auctioneer selling a number of items, and there are many bidders interested in those items. Mechanism design concerns
• the design of communication protocols betwee auctioneer and bidders
• design of efficient (poly-time, or even stricter time requirement due to practical constraints) algorithms to decide the allocation of items which achieve good efficiency
• design of truthful mechanism which motivates bidders not to be strategic on reporting their preferences
Our course will have some overlaps with the following materials. We will also provide self-contained lecture notes in this webpage.

## Lecture Notes, Exercise Sheets, Course Schedule and Suggested Readings

Lecture notes will be updated shortly after each lecture. Exercise sheet is handed out every two weeks, and typically you are given one week to finish; you are required to submit it just before the exercise session begins.