Algorithmic game theory.

Tutorial for the algorithmic game theory in winter semester 2023/2024. In S9 in Mala Strana on Thursday at 9:00.

Credit requirements

  • The tutorials take place irregularly according to the preliminary schedule shown below
  • You can receive up to 35 points for solving homework problems assigned during the semester. Each problem is evaluated according to its difficulty. Usually you will have two or three weeks to solve the problems and write your solutions. It is not possible to get any points for solving the problems after a deadline has passed. However, it is possible to hand in the solution multiple time if done sufficiently soon before deadline
  • You can also receive up to 15 points for a written test (midterm) that will be assigned roughly after the first half of the semester (I will tell soon enough). The test will consist of several problems, each again evaluated according to its difficulty.
  • You need at least one half of all available points, that is 25 points, to get credit for the course.
  • For at least 42 points, you will pass the exam with grade 1.
  • On the day of a deadline, your solutions should be handed in before the tutorial. You can try to solve homework multiple times if your solution is handed sufficiently soon and I can manage to look at it.
  • All homeworks will be available at postal owl. To sign in for the course, use the token 1a3a684b8292. All exercies from tutorials will be available here on this website. All homeworks will be available on the postal owl. We can discuss solutions individually there. If there is any problem with signing in the postal owl let me know!

    Literature

    • On Martin Balko website you can find lecture notes and several extra sources for this course. I would recommend as a material the twenty lectures of Tim Roughgarden which you can find in pdf or on youtube. There is quite a lot extra material in these lectures to this course but some could be helpful as an extra.

    Materials and tutorial content

    -->
    5.10.2023 Linear Programming bootcamp Exercises solution to exercise 5
    12.10.2023 Nash equilibria and LP bootcamp duality Exercises
    19.10.2023 Rest of Nash equilibria exercise.
    26.10.2023 Matrix games(2 players) Exercises
    2.11.2023 NO TUTORIAL! It is a dean's day.
    9.11.2023 Lemke-Howson algorithm. Exercises Example on L-H
    16.11.2023 Types of equilibria. Complete solutions Handwritten notes
    23.11.2023 Midterm.
    30.11.2023 Regret minimization(external regret) + CCE. Exercises
    7.12.2023 Regret minimization.(external, swap, internal) Exercises
    14.12.2023 NO Tutorial.
    21.12.2023 Extensive form games and basics of mechanism design. Exercises
    4.1.2024 No tutorial.
    11.1.2024(PLAN) Revenue-maximizing auctions. Exercises