Northeastern University CS - Fall 2008
Algorithmic Game Theory Reading Group
Every Wednesday from 10:30 to 11:30 in room #164 WVH Building
Textbook: Algorithmic Game Theory, [Nisan, Roughgarden, Tardos, Vazirani]



Members:
Dimitrios Kanoulas
Eric Miles
Laura Poplawski
Rajmohan Rajaraman
Zhifeng Sun

Weekly Meetings:

• First meeting - 10/15/2008- Chapter 2 [Dimitrios Kanoulas]
  2.1 Introduction
  2.2 Is the Nash Equilibrium Problem NP-Complete
  2.3 The Lemke-Howson Algorithm
  
• Second meeting - 10/22/2008 - Chapter 2 [Laura Poplawski]
  2.4 The Class PPAD
  2.5 Succinct Representation of Games
  2.6 The Reduction
  Note: Laura used a proof for the reduction which you can find in these 2 papers:
  1. The Complexity of Computing a Nash Equilibrium [Daskalakis, Goldberg, Papadimitriou]
  2. Reducibility Among Equilibrium Problems [Goldberg, Papadimitriou]
  
• Third meeting - 10/28/2008 - Chapter 2 [Eric Miles]
  Note: We will focus on correlated Equilibria. We will use these two papers:
  1. Computing Correlated Equilibria in Multi-Player Games [Papadimitriou]
  2. Computing Equilibria in Multi-Player Games [Papadimitriou, Roughgarden]
  OR
  1. Computing Correlated Equilibria in Multi-Player Games [Papadimitriou, Roughgarden]
• Forth meeting - 11/04/2008 - Chapter 4 [Zhifeng Sun]
  4. Learning, Regret Minimization, and Equilibria
  4.1 Intro
  4.2 Model and Preliminaries
  4.3 External Regret Minimization (until Theorem 4.5)
• Fifth meeting - 11/12/2008 - Chapter 4 [Zhifeng Sun]
  4. Learning, Regret Minimization, and Equilibria
  Continue with the rest of the Chapter
• Sixth meeting - 11/19/2008 - Chapter 7 [Dimitrios Kanoulas]
  7. Graphical Games
  7.1 Intro
  7.2 Preliminaries
  7.3 Computing NE in Tree Graphical Games
• 11/26/2008 - Thanksgiving Holidays
• Seventh meeting - 12/03/2008 - Chapter 8 [Laura Poplawski]
  8. Cryptography and Game Theory
  8.1 Cryptographic Notions and Settings
  8.2 Game Theory Notions and Settings
  8.3 Contrasting MPC and Games
• Eighth meeting - 12/10/2008 - Chapter 8 [Laura Poplawski]
  8. Cryptography and Game Theory
  8.4 Cryptographic Influences on Game Theory
  8.5 Game Theoretic Influences on Cryptography
  8.6 Conclusions