Algorithmic Game Theory (WS 2012/13)

Basic Information

Lecture time:	Monday 14-16
Lecture room:	024, Campus E 1.4 (5.11. 029, E 1.5)
Lecturer:	Sayan Bhattacharya, Rob van Stee
Tutorial time:	TBA
Tutorial room:	024, Campus E 1.4
Tutor:	Sebastian Ott
Audience:	The course counts as computer science lecture (4 SWS, 6 CP). The lecture will be given in English.
Prerequisites:	Basics in discrete mathematics, optimization, algorithms, and complexity.
Schedule:	The first lecture will take place on Monday, October 15.
Exercises:	We will hand out exercises every week and each student should score at least 50% in the first half of the course and 50% in the second half in order to be allowed to take the exam.
Final Exam:	Oral (30 minutes), in the last week of the semester
Re-Exam:	8 April 2013, 14-16. Contact Sebastian Ott for an appointment. If you participate in the re-exam, your grade you get there will replace your exam grade.
Book:	Algorithmic Game Theory

Description

The Internet is a structure that has not been created by a single entity, but rather emerged from the interaction of many agents, individuals or companies. Agents normally aim at maximizing their individual benefits. For example, an individual might want to minimize the cost he pays for an item from an online store, or to maximize the bandwidth they get from a service provider. These agents can be viewed as players in a large, distributed game that aim at maximizing their individual utilities, possibly at the cost of other players.

This class will focus on algorithmic aspects of economics and game theory as they arise in modern information networks. We will cover a range of topics at the intersection of classical game theory and algorithm design, such as equilibrium concepts, mechanism design, auctions, non-cooperative and cooperative games, inefficiency of equilibria.

Lectures

--> --> --> --> --> -->

Date	Topic	Reference	Homework		Lecturer
Oct 15	Introduction to game theory	Chapter 1	1		van Stee
Oct 22	Two-player zero-sum games, best responses	1.4, 2.1	2		van Stee
Oct 29	Complexity of Nash, mechanism design	2.2-3, 9.3.1	3		van Stee
Nov 5	VCG-mechanisms	9.1-3	4		van Stee
Nov 12	Single-minded bidders	11.1-2	5		van Stee
Nov 19	Algorithmic mechanism design	AMD paper	6		van Stee
Nov 26	Truthful scheduling	1, 2	7		van Stee
Dec 3	Truthful scheduling, the price of anarchy	1, 2	8		van Stee
Dec 10	The price of anarchy and stability	18.1-2, 19.3	9	--	Huang
Dec 17	Local connection game (missing proof)	19.2	10		van Stee
Jan 7	Smooth games	Robust PoA Paper	11		Bhattacharya
Jan 14	Bayesian Mechanism design	9.5, 9.6, 13.2	12		Bhattacharya
Jan 21	Prior-free auctions		13		Bhattacharya
Jan 28	Current paper		--		Bhattacharya

Re-exam

8 April 2013, 14-16. Contact Sebastian Ott for an appointment. If you participate in the re-exam, your grade you get there will replace your exam grade.

More Courses of the Algorithms and Complexity Group