Algorithmic Game Theory is a young 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 lecture 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/projects 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 7 "Nobel prices" in Economics (most recently, the 2020 Econimics Nobel price!) and some of the most prestigious awards in Mathematics and Computer Science and possibly some more will follow.
