COMP559

Algorithmic Game Theory

Aims

  1. To provide a foundation for modelling various mechanism design problems together with their algorithmic aspects.
    To provide a foundation for modelling various mechanism design problems together with their algorithmic aspects.
  2. To provide the tools and paradigms for the design and analysis of efficient incentive compatible mechanisms.
  3. To review the links and interconnections between algorithmics and computational issues with selfish agents.
  4. To provide an in-depth, systematic and critical understanding of selected significant topics related to algorithmic mechanism design, together with the related research issues.

Syllabus

Introduction to Mechanism Design: Social Choice, Mechanisms with Money, Dominant Strategies, Characterisations of Incentive Compatible Mechanisms, Bayesian-Nash Implementation.  (6 lectures)

Mechanism Design without Money. (4 lectures)

Combinatorial Auctions (CA): Single-Minded Bidders, Bidding Languages, Iterative Auctions, Winner Determination, Applications. (5 lectures)

Approximate Incentive Compatible Mechanisms: Greedy and Primal-Dual Mechanisms for Single-Minded CA, Mechanisms for CA with General Bidders, Mechanisms for Job Scheduling, Impossibility Results. (5 lectures)

Profit Maximisation in Mechanism Design. (4 lectures)

Online Mechanisms (2 Lectures)

Current Topics in Algorithmic Mechanism Design (Sponsored Search Auctions, Price of Anachy in Auctions, Itembidding) (4 lectures)

Recommended Texts

Primary texts:

N. Nisan, T. Roughgarden, E. Tardos, V.V. Vazirani (Editors). Algorithmic Game Theory. Cambridge University Press, 2007.

 

Further reading:

M.J. Osborne, A. Rubinstein. A Course in Game Theory. MIT Press, 1994. 

P. Cramton, Y. Shoham, and R. Steinberg (Editors). Combinatorial Auctions. The MIT Press, 2005.

Microeconomic theory - MAS-COLELL, Andreu, WHINSTON, Michael D., GREEN, Jerry R. 1995

Mechanism Design- A Linear programming approach by Rakesh V. Vohra  2011

Bayesian Mechanism Design by Jason Hartline, 2013

Some lectures will be based on research papers.

Learning Outcomes

  1. A critical awareness of current problems and research issues in the field of algorithmic mechanism design. For example, algorithmic efficiency, incentive compatibility, maximisation of social welfare, and their impact on the revenue raised by the auction.
  2. The ability to formulate mechanism design models for the purpose of modelling particular applications.
  3. The ability to use appropriate algorithmic paradigms and techniques in context of a particular mechanism design model.
  4. The ability to read, understand and communicate research literature in the field of algorithmic mechanism design.
  5. The ability to recognise potential research opportunities and research directions.

Learning Strategy

Formal Lectures: Students will be expected to attend three hours of formal lectures in a typical week accompanied by one hour of seminar given by students in groups, or one hour of tutorials.

Private study: In a typical week students will be expected to devote six hours of unsupervised time to private study. The time allowed per week for private study will typically include three hours of time for reflection and consideration of lecture material and background reading, and three hours for completion of practical exercises.