Topics in Algorithmic Game Theory and Economics

Advanced Course, 2+1

Basic Information

Lecturer: Pieter Kleer
Lectures: Wednesday, 14:00-16:00
Teaching Assistant: Golnoosh Shahkarami
Tutorials: TBA
Credits: 5
Prerequisites: Basic knowledge about:
  • Algorithms and data structures, and their analyses
  • Calculus
  • Linear Algebra (including how to solve linear systems).
  • Probability theory (distributions, random variables, expectations)
Familiarity with linear programming and combinatorial optimization is useful, but not required.

 

Announcements

Lectures will be given on Zoom.

Description

In this course we will cover topics in the areas of Algorithmic Game Theory and Computational Economics, which can be placed at the intersection of economics and theoretical computer science. The course consists of two parts.

 

Game theory is concerned with the study of mathematical models of strategic interaction between players. One of its core aspects is the study of equilibrium situations: `Stable' states of the model in which no player has an incentive to switch strategies. Roughly twenty years ago, computer scientists became interested in studying the algorithmic aspects of such equilibria. Can we compute them efficiently, that is, in polynomial time? In the first part of this course we will cover results addressing this question, and more, in general n-player games and the special class of potential (or congestion) games. We will mostly focus on computational questions concerning Nash equilibria.

 

In the second part of this course we study problems in the area of Computational Economics, with a focus on online selection problems. One example here is the selling of an item on an online platform in which buyers arrive in an unknown order, and where we have to irrevocably decide upon a buyer's arrival if we want to sell to her or not. This problem is closely related to, e.g., the classical secretary problem. We will cover various results and online models in this area, such as combinatorial secretary problems and prophet inequalities, and also discuss connections to online mechanism design.

Lectures and Exercises

DateTopicSlides/ExercisesReferences
TBA