Algorithmische Spieltheorie (Sommersemester 2017)

Dozent: Prof. Dr. Tobias Friedrich (Algorithm Engineering) , Dr. Pascal Lenzner (Algorithm Engineering)

Allgemeine Information

• Semesterwochenstunden: 2
• ECTS: 3
• Benotet: Ja
• Einschreibefrist: 28.04.2017
• Lehrform: Seminar
• Belegungsart: Wahlpflichtmodul

Studiengänge, Modulgruppen & Module

Beschreibung

Algorithmic Game Theory is a jung and thriving research area in the intersection of Mathematics, Algorithmics and Economics. Motivated by the rise of the Internet and its related new kinds of problems, Algorithmic Game Theory was established within the last two decades to tackle classical problems from Game Theory with an algorithmic perspective.

Some prominent game-theoretic problems are:

• Every morning the following "game" happens on our streets: People commute by car to work and everyone wants to arrive as quickly as possible at their destination. Unfortunately, many drivers will use the same streets. The higher the traffic on a specific street the longer it takes for all cars on that street. Thus, every morning commuters face the problem of choosing the right route but which route is right depends on all the routes chosen by all other commuters. Here we have a complex interaction of many egoistically chosen strategies. One natural question is: Is there an equilibrium of this game? That is, is there a choice of routes such that no commuter wants to change her route given that all the other commuters stick to their route. Another even more important question is: How bad is the overall traffic induced by the egoistic behavior of all commuters? How much better can it be if we could force all commuters to take a specific route? 
• Assume you want to sell a painting in an auction and you can choose the specific auction design. Ideally you want to ensure that every bidder bids her true value for the painting since this maximizes the revenue and the painting goes to the bidder who values it most. However, the bidders want to minimize their payment for the painting and thus may bid strategically (e.g. lower). The question now is: Can you set up the auction such that the best bidding strategy of every bidder is to bid her true value? In other words: can you enforce that all bidders bid honestly? Is this even possible?

These two examples highlight everyday situations which can be analyzed via Game Theory. In the first example, the game is fixed and we want to understand its properties. In the second example it is the other way round: We want to enforce certain properties by choosing the rules of the game which incentivize strategic players to act accordingly. 

The goal of the seminar is to use suitably chosen examples to give a broad overview over the field of Algorithmic Game Theory. For this, we will encounter classical results from Game Theory along with recent results from Algorithmic Game Theory. Among others we will discuss the following questions:

• How can we solve assignment problems (e.g. assigning talks to students) such that all participants are happy with their assignment?
• Are there auctions in which all bidders want to bid honestly?
• How does the perfect voting system look like?
• Has every game an equilibrium, that is, an outcome in which all players are happy?
• Is it easy to find an equilibrium for a specific game?
• How good/bad are equilibria reached via egoistic behavior compared to the best centrally enforced solution?

Answers to the above questions have been awarded with 6 Nobel prices in Economics and some of the most prestigious awards in Mathematics and Computer Science and it is highly likely that some more will follow.

Voraussetzungen

The only requirements for this seminar are curiosity for a new research topic and a fundamental interest in algorithmic and game-theoretic problems. Moreover, we expect motivated, interactive and creative presentations. Prior knowledge in Algorithmics helps but is not required.

Lern- und Lehrformen

The seminar is intend to be highly interactive and student-focused. We achieve this by first assigning topics to all participants which shall then be presented in an interactive and engaging way. This not only includes a talk but also the design and implementation of a short exercise and/or experimental session to support the talk. Moreover, participants have to write short summaries of their topics which will then be published to all participants.

The exact seminar mode depends heavily on the number of participants and will thus be announced in the first seminar session.

Leistungserfassung

The grades will depend mostly on the quality of the seminar session led by the participants. The quality of the short summary will have only a minor influence on the grade.

Termine

• Time: weekly on Wednesday at 11:00 AM
• Room: A-2.1

Zurück