חיפוש חדש  חזור
מידע אישי לתלמיד

שנה"ל תש"ף

  תורת המשחקים האלגוריתמית
  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
 
Course requirements and grading: 
Problem sets (possibly including grading)  
Final project (either a research project or a survey) – max 10 pages (possibly including presentation)
Scribe notes
 
Some references
    Roughgarden, An algorithmic game theory primer (2008) http://theory.stanford.edu/~tim/papers/tcs08.pdf
    Shoham, Communications of the ACM, Computer Science and Game Theory, http://robotics.stanford.edu/~shoham/www%20papers/CSGT-CACM080417.pdf
    Halpern. Computer science and game theory: a brief survey
http://www.cs.cornell.edu/home/halpern/papers/csgt.pdf

להצהרת הנגישות


אוניברסיטת ת 1