252-1407-00L  Algorithmic Game Theory

SemesterAutumn Semester 2015
LecturersP. Widmayer
Periodicityyearly course
Language of instructionEnglish



Catalogue data

AbstractGame theory provides a formal model to study the behavior and interaction of self-interested users and programs in large-scale distributed computer systems without central control. The course discusses algorithmic aspects of game theory.
ObjectiveLearning the basic concepts of game theory and mechanism design, acquiring the computational paradigm of self-interested agents, and using these concepts in the computational and algorithmic setting.
ContentThe Internet is a typical example of a large-scale distributed computer system without central control, with users that are typically only interested in their own good. For instance, they are interested in getting high bandwidth for themselves, but don't care about others, and the same is true for computational load or download rates. Game theory provides a particularly well-suited model for the behaviour and interaction of such selfish users and programs. Classical game theory dates back to the 1930s and typically does not consider algorithmic aspects at all. Only a few years back, algorithms and game theory have been considered together, in an attempt to reconcile selfish behavior of independent agents with the common good.

This course discusses algorithmic aspects of game-theoretic models, with a focus on recent algorithmic and mathematical developments. Rather than giving an overview of such developments, the course aims to study selected important topics in depth.

Outline:
- Introduction to classical game theoretic concepts.
- Existence of stable solutions (equilibria), algorithms for computing equilibria, computational complexity.
- The cost difference between an optimum under central control and an equilibrium under selfish agents, known as the "price of anarchy".
- Auction-like mechanisms and algorithms that "direct" the actions of selfish agents into a certain desired equilibrium situation.
- Selected current research topics of Algorithmic Game Theory, such as Web-Search Based Keyword Auctions, or Information Cascading in Social Networks
Lecture notesNo lecture notes.
Literature"Algorithmic Game Theory", edited by N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Cambridge University Press, 2008;

"Game Theory and Strategy", Philip D. Straffin, The Mathematical Association of America, 5th printing, 2004

Several copies of both books are available in the Computer Science library.
Prerequisites / NoticeAudience: Although this is a Computer Science course, we encourage the participation from all students who are interested in this topic.

Requirements: You should enjoy precise mathematical reasoning. You need to have passed a course on algorithms and complexity. No knowledge of game theory is required.

Performance assessment

Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course
ECTS credits7 credits
ExaminersP. Widmayer
Typesession examination
Language of examinationEnglish
Course attendance confirmation requiredNo
RepetitionThe performance assessment is only offered in the session after the course unit. Repetition only possible after re-enrolling.
Mode of examinationwritten 180 minutes
Additional information on mode of examinationThere will be one graded exercise sheet that will contribute with a weight of 15% towards the final grade. The graded exercise sheet will be in the middle of the semester.
Written aidsno supporting material allowed
This information can be updated until the beginning of the semester; information on the examination timetable is binding.

Learning materials

 
Main linkInformation
Only public learning materials are listed.

Courses

NumberTitleHoursLecturers
252-1407-00 VAlgorithmic Game Theory3 hrs
Mon09-12CAB G 51 »
P. Widmayer
252-1407-00 UAlgorithmic Game Theory2 hrs
Mon15-17CAB G 56 »
15-17CAB G 59 »
15-17NO D 11 »
P. Widmayer
252-1407-00 AAlgorithmic Game Theory
Project Work, no fixed presence required.
1 hrsP. Widmayer

Restrictions

There are no additional restrictions for the registration.

Offered in

ProgrammeSectionType
Certificate of Advanced Studies in Computer ScienceFocus Courses and ElectivesWInformation
Computer Science TCSpecialized Courses in Respective Subject with Educational FocusWInformation
Computer Science Teaching DiplomaSpec. Courses in Resp. Subj. w/ Educ. Focus & Further Subj. DidacticsWInformation
Computer Science MasterFocus Core Courses Theoretical Computer ScienceWInformation
Mathematics BachelorSelection: Math. Optimization, Discrete Mathematics, Computer ScienceWInformation
Mathematics MasterSelection: Math. Optimization, Discrete Mathematics, Computer ScienceWInformation
Computational Science and Engineering TCFurther Subject DidacticsWInformation
Robotics, Systems and Control MasterCore CoursesWInformation