## CENTER FOR ALGORITHMIC SYSTEMS

## MSc Programme ``Computing Science"
2010-2011

## 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. Some ten years ago it became
clear that these situations, well-known in classical game theory, can be attacked (and
analysed) algorithmically, with many possible assumptions about how parties cooperate and
about the desired economics of the game. Can one always find algorithmic mechanisms that
are viable, from a practical viewpoint? How can algorithmic mechanisms be used e.g. to
create *auctions* over the Internet? Algorithm game theory and mechanism design are
now 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 9.00-10.45, in:
BBL 061.
- Wednesday 11.00-12.45, in: MIN 211.

- First meeting: Wednesday, April 27, 11.00-12.45 (in: MIN
211).
- Office hours: by appointment.
- Final exam: The grade will be based on the course work (see below).
- Here is the weekly schedule (tentative).

## Prerequisites

The seminar is part of the MSc program `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 from the very 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 (in pairs), each
presentation being a 45-minute part of one seminar session. (The seminar will be in
English unless all participating students are fluent in Dutch.)

*Term papers*
In the second part
of the seminar each participant must write a term paper (in English) on a special topic
from the seminar domain, consisting of a summary and analysis of one or several research
papers from the relevant literature.

*Participation*
Students are expected to participate in an active way. Attendance is recorded.

*Note*: To accommodate the considerable interest for the seminar, students may be
asked to work in groups of two for the presentations part of the seminar requirement.
## Grading

The grade depends on the given presentations (40%), term paper
(40%) and active participation (20%).
## Information

- Last year's seminar: here (2009-2010).
- Noam Nisan, Algorithmic Game-Theory/Economics, weblog.
- Peter Crampton, Market Design, weblog.
- Harvard: EconCS group.
- R. Aumann, What is Game Theory Trying to accomplish? (pdf).

## Useful further references

- D. Easley, J. Kleinberg, Networks, crowds, and markets: Reasoning about a highly
connected world, Cambridge University Press, Cambridge, 2010.
- A. Mas-Colell, M.D. Whinston, J.R. Green, Microeconomic theory, Oxford University
Press, New York, 1995.
- 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 20, 2011