Lectures.
Time: Tuesday and Thursday, 11.30am - 1pm.
Location: McConnell Engineering Building, Room 103.
Topics.
We consider the area of algorithmic game theory. We are interested in
combining ideas from economics (such as rationality and mechanism design)
with concepts from theoretical computer science (such as complexity and
algorithm design) and applying them to "real-world" problems. Our approach
will be entirely mathematical. Theoretical concepts will, however,
be complemented by examples drawn mainly from computer science, e.g. network and
traffic routing, online auctions, bandwidth allocation, webpage advertising etc.
Specific topics for study include:
Equilibria: e.g. Nash equilibria; Correlated equilibria; Sink equilibria.
Auctions: e.g. Combinatorial Auctions; Online Auctions.
Mechanism Design e.g. Pricing Mechanisms; Cost Sharing.
Coalition Games.
Complexity: Algorithms and Hardness results.
A description of the lectures and links to references can be found here.
Pre-requisites.
This course is primarily aimed at graduate students in mathematics, computer
science or economics. No formal experience with these topics
will be needed, but a strong mathematical background is necessary.
Coursework.
The course will be graded as follows:
There will be one assignment: 20%.
Students will be responsible for giving one lecture based on a research paper selected in coordination with the instructor: 30%.
Students will write-up a report based upon their investigation into an open problem in the field: 50%.
Suggestions for presentation topics can be found here.
The assignment can be found here. You must work on
the assignment independently; no collaboration is allowed.
Solutions to the assignment.
Textbook.
There is no course textbook. Much of the material will, however, be inspired
by courses of a similar nature. See, for example,
the courses of Eva Tardos, Tim Roughgarden and Christos Papadimitriou.
