1 Basic Information

Lecture time:	Wednesday 16:00-18:00
Lecture room:	HS 001, Geb. E 1 3
Lecturers:	Giorgos Christodoulou , Khaled Elbassioni , and Julián Mestre
Tutorial time:	Monday 16:15-17:30
Tutorial room:	E14 022
Tutor:	Evangelia Pyrga
Book:	Algorithmic Game Theory Available online (user: agt1user, pass: camb2agt)

2 Lectures

Below is a detailed list of the topics covered in class with pointers to the relevant book chapter.

Date	Topic	Book Chapter	Lecturer	Handouts
Apr 16	Introduction and basic concepts	1	Khaled
Apr 23	Combinatorial auctions	11 and 9.3.1-4	Khaled	Tutorial Sheet 1
Apr 30	Single-minded case and Walrasian Equilibrium	11.2-3	Khaled
May 7	Social Choice, Condorcet's Paradox, Voting Methods, Arrow's Theorem, Gibbard-Satterthwaite Theorem, Mechanisms with Money	9	Giorgos
May 14	Mechanisms, Revelation Principle, Monotonicity, Truthful Scheduling	9 and AMD	Giorgos	Nisan's Google Talk Tutorial Sheet 2
May 21	Cost allocations	15.1-2	Julian
May 28	Mechanism Design with Cost sharing schemes	15.3 and 15.4.2	Julian	Tutorial Sheet 3
June 4	Selfish Task Allocation, Price of Anarchy, Coordination Ratio	17, 20.1-2 and KP	Giorgos
June 11	Price of Anarchy of congestion games, Price of stability of congestion games, Atomic Selfish Routing	18.1, 18.{2,3,4}.2, 19.3 and CK	Giorgos	Tutorial Sheet 4
June 18	Influence in Social Networks: Cascade model, submodular functions and the greedy algorithm	KKT	Julian
June 25	Sponsored search auctions	28	Khaled
July 2	Sponsored search auctions	28	Khaled	Tutorial Sheet 2
July 9	Influence in Social Networks: Threshold model	KKT	Julian

3 Ground Rules

Your final grade will be based on homework assignments (30%) and a final presentation (70%).

Here is a tentative list of the topic that we intend to cover, in no particular order:

• Pricing: Envy-free pricing, revenue maximization: complexity and approximation algorithms
• Algorithmic mechanism design (Chapter 9): VCG mechanisms, mechanisms for scheduling, lower bounds
• Cost shares (Chapter 15) : the core of games, Shapley value, group-stretegyproof mechanisms, and cross-monotonic cost-shares (upper and lower bounds).
• Inefficiency of equilibria (Chapters 17,18): price of anarchy, price of stability, routing games, congestion games.
• Combinatroial auctions (Chapter 11): the VCG-mechanism, Walrasian equlibrium, single minded-case, approximate winner determination, some computational aspects.
• Sponsored search auctions (Chapter 28): models and mechanisms used by current search engines, equilibrium properties, online allocation.
• Influence of social networks: models of influence (critical mass vs. diminishing returns), submodularity and the greedy algorithm.

4 Final Grades

In order to preserve your privacy we only display the last three digits of your matriculation number. If you have any questions about your grade please get in touch with one of the lecturers.

Mat. Number	Final Grade
556	2.3
522	1.0
270	2.7
076	2.3
811	2.7
343	1.3
892	2.0
245	2.3
921	3.3
585	1.7
925	2.0
808	4.0