Northeastern University CS - Spring 2009
Algorithmic Game Theory Reading Group
All meetings are held in room #164 WVH Building, every Friday from 11:30 to 13:30
Textbook: Algorithmic Game Theory, [Nisan, Roughgarden, Tardos, Vazirani]


About AGT Reading Group
The general format of the meetings will be whiteboard presentations followed by interactive open-problem discussions.

• Each team member is supposed to read at least the beginning sections (introduction, problem setup, main results) before the meeting.
• After each meeting, the presenter shall write a small memo summarizing the open problems either mentioned in the paper or raised by the team members.

Activities of AGT Reading Group in previous terms:
Fall 2008

Members:
Dimitrios Kanoulas
Eric Miles
Evangelos Kanoulas
Rajmohan Rajaraman
Wu Jiang
Zhifeng Sun

This semester`s general topic: Algorithmic Mechanism Design

Weekly Meetings:

• First meeting - 01/13/2009 - Organizational meeting.

• Second meeting - 01/23/2009 - Chapter 9 [ Eric Miles ]
  9. Introduction to Mechanism Design (for Computer Scientists)
  9.1 Introduction
  9.2 Social Choice
  9.3 Mechanism with Money
  9.4 Implementation in Dominant Strategies

• Third meeting - 01/30/2009 - Chapter 9 [ Eric Miles and Dimitrios Kanoulas ]
  9. Introduction to Mechanism Design (for Computer Scientists)
  9.5 Characterization of Incentive Compatible Mechanisms
  9.6 Bayesian-Nash Implementation
  9.7 Further Models
  9.8 Notes

• Forth meeting - 02/06/2009 - Chapter 10 [ Dimitrios Kanoulas ]
  10. Mechanism Design without money
  10.1 Introduction
  10.2 Single-Peaked Preferences over Policies

• Fifth meeting - 02/13/2009 - Chapter 10 [ Dimitrios Kanoulas ]
  10. Mechanism Design without money
  10.3 House Allocation Problem
  10.4 Stable Matchings
  10.5 Future Directions
  10.6 Notes and References

• Sixth meeting - 02/20/2009 - Chapter 11 [ Zhifeng Sun ]
  11. Combinatorial auctions
  11.1 Introduction
  11.2 The Single-Minded Case
  11.3 Walrasian Equilibrium and the LP Relaxation

• Seventh meeting - 02/27/2009 - Chapter 11 [ Zhifeng Sun ]
  11. Combinatorial auctions
  11.4 Bidding Languages
  11.5 Iterative Auctions: The Query Model
  11.6 Communication Complexity
  11.7 Ascending Auctions
  11.8 Bibliographic Notes

• Seventh meeting - 03/13/2009 - Chapter 12 [ Eric Miles ]
  12. Computationally Efficient Approximation Mechanisms
  12.1 Introduction
  12.2 Single-Dimensional Domains: Job Scheduling

• Eighth meeting - 03/20/2009 - Chapter 12 [ Eric Miles]
  12. Computationally Efficient Approximation Mechanisms
  12.3 Multidimensional Domains: Combinatorial Auctions
  12.4 Impossibilities of Dominant Strategy Implementability
  12.5 Alternative Solution Concepts
  12.6 Bibliographic Notes

Additional Links

• Algorithmic Mechanism Design - Talk by Noam Nisan [Google Tech Talks]
  Talk abstract: One of the challenges that the Internet raises is the necessity of designing distributed protocols for settings where the participating computers are owned and operated by different owners with different goals. Over the last decade or so there has been much research that aims to address these issues using ideas taken from the micro-economic field of mechanism design. In this talk I will survey the current state of the field: how mechanism design is applied in computational settings, how far can classical ideas go, and what are the challenges for further research. Among the applications discussed will be combinatorial auctions, cost sharing, scheduling, and routing in networks.