CENTER FOR ALGORITHMIC SYSTEMS
MSc Programme ``Applied Computing Science"
2009-2010
Seminar: Algorithms, Games and the Internet (MSAGI)
Lecturer:
Course overview
Many internet applications involve (large) pools of users which all strive for their share in
the available services or resources, on their own or as groups. What mechanisms can be used
to achieve this in a reasonable manner? Some ten years ago it became clear that these
situations, well-known in classical game theory, can indeed be attacked algorithmically, with
a host of possible assumptions about how the parties cooperate and the desired economics of
the game. Can one always find algorithmic mechanisms that are viable, from a practical
viewpoint? This unique blend of game theory and algorithm design is now one of the most
exciting research domains in computer science, with companies like Google and Yahoo depending
on the novel mechanisms that are developed. In the seminar we will explore the beautiful
techniques that are at the basis of the field, aiming to eventually understand some of the
concrete algorithmic methods as applied by some of the big information companies on the web.
Class schedule
- Seminar hours:
- Monday        11.00-12.45, in: BBL 077.
- Wednesday   9.00-10.45, in: BBL 075.
- First meeting: Monday, April 26, 11.00-12.45 (in: BBL
077).
- Office hours: by appointment.
- Final exam: The grade will be based on the course work (see below).
- Here is the weekly schedule.
Prerequisites
The seminar is part of the MSc program `Applied Computing Science' and is to be taken after
you have completed at least several of the regular courses in the program. If you have not, see
your MSc-program advisor: you may not be admissable to this seminar yet. (The seminar will be
self-contained, but some basics also occur in the course on Multi-Agent Systems. No
prerequisites from this course are needed, but please inform the instructor if you have taken
this course.)
Text
The seminar is based on the book
- N. Nisan, T. Roughgarden, E. Tardos, V.V. Vazirani (Eds), Algorithmic
Game Theory, Cambridge University Press, Cambridge, 2007.
The book is required and should be at your disposal at the start of the seminar, to study the
weekly readings from the very beginning. (The book can be previewed for
free here.)
We will treat a selection of chapters from this book. Additional material will be
listed in the weekschedule as the seminar develops.
Course Work
- Presentations
The seminar meets twice a week. After a few introductory lectures by the lecturer, students
are expected to give presentations on (specific parts of) the book chapters and related
material. Students are expected to give at least two presentations each, each presentation
being a 45-minute part of one seminar session. (The course will be in English unless all
participating students are fluent in Dutch.)
- Studies/Summaries
Students are challenged to explore their topics in an active way. Towards the end of the
seminar every participant must write a summary (in English) of a special topic from the
seminar domain and present an outline of it, typically based on new research material.
- Participation
Students are expected to participate in an active way. Attendance is recorded.
Grading
The grade depends on the given presentations (50%), summary reports
(30%) and active participation (20%).
Recommended
Useful references
- D. Easley, J. Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly
Connected World, Cambridge University Press, Cambridge, 2010 (pre-publication).
- M.J. Osborne, An Introduction to Game Theory, Oxford University Press, New York, 2004.
- Y. Shoham, K. Leyton-Brown, Multiagent Systems: Algorithmic, Game-theoretic, and Logical
Foundations, Cambridge University Press, Cambridge, 2009.
Search tools
Other links
Last modified: April 24, 2010