  שנה"ל תש"ף  תורת המשחקים האלגוריתמית
Algorithmic Game Theory
0368-4483
מדעים מדויקים
קבוצה 01       סמ'  ב'1400-1700 שיעור ות פרופ פלדמן מיכל
דרישות קדם   בחינה   רשימת התפוצה
ש"ס:  3.0

סילבוס מקוצר

Syllabus (tentative)

• Introduction: games, mechanism design, inefficiency of equilibrium and equilibrium computation
• Nash equilibrium and Nash’s theorem
• Zero-sum games: normal form and extensive form, minmax theorem, Yao’s principle
• Congestion games and potential games, pure NE existence and computation, best-response dynamics
• Inefficiency of equilibria: price of anarchy, price of stability, smoothness framework (extension to correlated equilibrium and regret minimization)
• Mechanism design basics: single-item auctions, Myerson’s lemma
• Algorithmic mechanism design: Multi-unit auctions: computation and communication
• VCG mechanisms
• Market models, equilibium, Welfare theorems, computational aspects

Course Requirements

• Class attendance is mandatory.
• Scribe notes (latex templatelatex tutorial)
• Problem sets: 2-3 problem sets will be given during the semeter. You should submit them in pairs.
• Final exam.
Course description
Algorithmic Game Theory

Instructor: Prof. Michal Feldman
Time & Place: Wednesday, 2-5pm (place TBA)
Prerequisites: probability theory, algorithms, complexity

Tentative list of topics:
Introduction to algorithms and games
Two-player zero-sum games (Minmax theorem)
Regret minimization and correlated equilibrium
Nash equilibrium
Mixed equilibrium and Nash theorem
Pure equilibrium
Equilibrium existence
Congestion games
Quality of equilibrium: price of anarchy and smoothness
Social choice and Mechanism Design
Introduction to social choice
Mechanism design without money (and approximation)
Social welfare maximization (VCG)
Combinatorial auctions
Revenue maximization (optimal mechanisms)
Markets and pricing
Walrasian equilibrium
First and second welfare theorems
Ascending price auctions