Implementation theory 1000-2M16TIM
The problem of implementation is defined as follows: given a set of socially optimal outcomes for different states of the world (a social choice rule) design a game (or a mechanism) such that the autonomous, rational and self-interested agents (or players) will have incentives to make individual choices that lead to optimal outcomes. A simple example of such a mechanism is a second price auction (widely used in on-line auction sites such as allegro or e-bay) that creates incentives for the buyers to submit bids that are equal to how much the object is valuable for them. Another example are online rating systems that create incentives for the users to submit truthful rankings.
Which social choice rules are implementable in the sense described above? What are the key properties requires? How to implement them? These are the key questions addressed by implementation theory.
The research on implementation theory was initiated by Leonid Hurwicz, a graduate of Warsaw University. Together with Eric Maskin and Roger Myerson, he was awarded a Nobel Price in Economics for his fundamental contributions to the theory of implementation and mechnism design.
1. Resource allocation with rational self-interested agents (an introduction)
2. Implementation in dominant strategies (direct mechanisms, revelation principle)
3. Implementation in Nash equilibrium and in undominated Nash equilibrium
4. Incomplete information (Bayesian implementation)
Type of course
Course coordinators
Learning outcomes
Knowledge:
Knows fundamental problems in implementation theory and formal tools to analyse them
Knows the notion of incentive compatibility and understands its different variants
Knows basic properties of social choice rules implementable in different types of solution concepts.
Skills:
Is able to analyse implementability of social choice rules in different solution concepts
Is able to propose mechnisms implementing given social choice rules
Competences:
Knows basic properties of implementable social choice rules and corresponding notions of incentive compatibility
Knows limitations of his/her knowledge, is willing to constantly upgrade and update his/her knowledge and raise qualifications within the field of computer science and related scientific areas and disciplines (K_K01)
Knows how to precisely formulate questions in order to deepen own understanding of the studied subject (in particular in contacts with non-computer scientists) or to find gaps in own reasoning about the subject (K_K02)
The PhD students know the development trends in their field against the background of other natural and exact sciences, as well as the related dilemmas of the modern civilisation, the PhD students know their discipline-specific achievements at the level allowing for its creative development and the research methodology in their discipline, know how to make use of the sources (books, articles, etc.) that present the results in their discipline, also in a foreign language, are able to present advanced ideas and results in their discipline, are able to organised self-education in their discipline, and are ready to undertake the task of a researcher in the society.
Assessment criteria
Final grade is based on points scored in a written exam. Same rules apply in the retake session.
For PhD students: reading a recent research paper in the area of implementation theory, chosen together with the lecturer.
Bibliography
Basic literature
L. Corchón, The theory if implementation of Socially Optimal Decisions in Economics
N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani, Algorithmic game theory
Supplementary literature
E. Maskin, T. Sjöström, Implementation Theory
M. Jackson, A crash course in implementation theory
T. Börgers, An introduction to the theory of mechanism design
M. Osborne, A. Rubinstein, A course in game theory (http://books.osborne.economics.utoronto.ca/)
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: