Algorithmic Game Theory, Mechanism Design and Computational Economics

This course is done. This webpage will NOT be further updated. However, we will make further updates (adding new materials, fixing typos) to the lecture notes; please see the cleaner course webpage for such updates.

- (15 Jan) Exercise Sheet 6 out. Deadline is 23 Jan, 2018.
- (18 Dec) Exercise Sheet 5 out. Deadline is 9 Jan, 2018.
- (4 Dec) Exercise Sheet 4 out. Deadline is 12 Dec.
- (20 Nov) Exercise Sheet 3 out. Deadline is 28 Nov.
- (6 Nov) Exercise Sheet 2 out. Deadline is 14 Nov.
- (23 Oct) Exercise Sheet 1 out. Deadline is 7 Nov.
- (14 Oct) Since the Semester-kick-off Meeting will be held at 4:30pm on 16 Oct, our first lecture will start on 23 October, 2017.

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, operational research, dynamical system, and more. In this course, we will discuss the very core of this exciting new research direction.

For ambitious students who want to develop rigorous theoretical training related to this topic, I can suggest extra materials for reading and thinking.

This course is divided into three parts.

In the first part, we cover some basic concepts in games and markets, including Zero-sum Game and General-sum Game, Nash Equilibrium, Market Equilibrium, Correlated Equilibrium and Regret Minimization. Algorithms for finding such equilibria in 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. 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/Exchange market, 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 agents who are interested in those items. Mechanism design concerns

• the design of communication protocols between auctioneer and agents
• design of efficient (poly-time, or even stricter time requirement due to practical applications) algorithms to decide the allocation of items which achieve good efficiency
• design of truthful mechanism which motivates agents 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.

• Thomas Ferguson's text on "Game Theory"
• Tim Roughgarden's courses on "Algorithmic Game Theory" and "Frontiers in Mechanism Design"
• Jason Hartline's text on "Mechanism Design and Approximation"

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

Below is a tentative schedule on the topics to be discussed. They are subject to change.