Computational Topics in Game Theory

55923 — נושאים חישוביים בתורת המשחקים


This course will combine computational, game-theoretic, and economic tools to analyze and design computational auctions, markets, and other cooperative tasks performed by rational entities over computerized platforms.  The course will be theoretic in nature.


The course will be based mostly on Part II of the book Algorithmic Game Theory (online version).


  1. Social Choice Theory
    • Arrow and Gibbard-Satterthwaite theorems
    • Frequency and Computational hardness of manipulation
    • Stable matching
  2. Auctions, Mechanisms, and Incentive-Compatibility
    • Second Price Auction
    • VCG mechanisms
    • Mechanisms for computational problems: routing, digital goods, cost sharing
    • Dominant-Strategy implementation and the revelation principle
  3. Combinatorial Auctions
    • The LP relaxation and its dual
    • Incentives vs. Computation
    • Preference elicitation and Communication bottlenecks
    • Ascending Auctions and the unit-demand case
  4. Bayesian Mechanism Design
    • Games with imperfect information
    • The first price auction
    • Myerson optimal auctions
    • Revenue Equivalence
  5. Ad auctions
    • The Generalized Second Price Auction
    • Repeated auctions with a budget


  • We will have 3-4 significant home exercises, and their grades will determine the final grade.  No exam.
  • We do require students to attend (essentially) all lectures.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: