CO759: Algorithmic Game Theory
(Topics in Discrete Optimization)

Announcements (assignments etc.)

• Sep 13: Welcome to CO 759.
• Oct 13: Assignment 1 is available. (Last updated: Oct 21 Oct 28 Oct 31.)
  Due on Nov 1, 2010 Nov 3, 2010. Here are the Solutions.
• Oct 21: A typo in Q2(d) has been corrected: the time allowed is O((input size).log(1/ε)). The assignment has been updated.
• Oct 28: Some clarifications and corrections about Q2(d): the time allowed is polynomial in the input size and log(1/ε). Also, you are given an oracle that can solve polynomial-size set-cover LPs, and each call to this oracle counts as one operation.
  The assignment has been updated, and the due date has been extended to Nov 3.
• Oct 31: A minor, but crucial typo in Q4(a) has been corrected: it should be δ(a,b)=inf{v_i(a)-v_i(b): f(v_i,v_-i)=a}.
• Nov 26: Assignment 2 is available.
  Due by Dec 7, 2010. Here are the Solutions.
• Dec 7: The take-home final exam can be picked up from my office.
  You can pick up the exam either on Wednesday, Dec 8, or Thursday, Dec 9. The exam will be due 5 days from the pickup date.
  So pick up: Dec 8 => due by Dec 13, 5pm; pick up: Dec 9 => due by Dec 14, 5pm.
  
  I will be in my office on Dec 8 from 12-2pm, and on Dec 9 from 2-6pm. If you are unable to reach me in my office, then you may request to receive the final exam via email (but please try to pick it up in person from me first).
• Dec 8: Solutions to Assignment 2 have been posted.
• Dec 12: Solutions to Assignment 1 have been posted.

Course Overview and Outline

Algorithmic game theory applies algorithmic reasoning to game-theoretic settings. A prototypical motivating example for the problems we will consider is the Internet, which is a fascinating computational artifact in that it was not designed by any one central authority, or optimized for one specific purpose, but rather emerged from the interaction of several entities, such as network operators, ISPs, users, in varying degrees of coordination and competition. This course will investigate a variety of questions that arise from looking at problems (often classical optimization problems) from this point of view. We will examine, in part, algorithmic issues in games, and in part, algorithmic problems that arise in settings with strategic players.

Topics Covered (including relevant references)

• Sep 13: Course introduction. Some simple games and definitions of solution concepts. See sections 1.1-1.3.
• Sep 15: Started with algorithmic mechanism design. See Chapter 9. Introduction to mechanism-design, definition of a mechanism, notions of truthfulness/dominmant-strategy implementation, the single-item auction problem and the second-price auction. See sections 9.3.1, 9.3.2, 9.4.1, 9.4.2 (the definition of a mechanism here is slightly more general in that it allows the designer to define arbitrary strategy-sets, utility functions; see section 9.4.3 for why our definition is without loss of generality).
• Sep 20: The (algorithmic) implementation problem: which social-choice functions (SCFs) are (efficiently) implementable, or admit an approximation that is efficiently implementable. The VCG mechanism: definition, proof of truthfulness, and examples. See sections 9.3.3-9.3.5. The desirable features of VCG, and its limitation in the face of computational intractability.
• Sep 22: Single-dimensional domains: definition and examples. Characterization of implementable SCFs: the necessity of weak-monotonicity (WMON) and its sufficiency for single-dimensional domains. See sections 9.5.2, 9.5.4; the definition in section 9.5.4 corresponds to the special case where α_i is a {0,1}-vector. See definition 12.1 in section 12.2 for the more general setting (there is a typo in Theorem 12.2: the second integral should go from 0 to ∞).
• Sep 27: Applications involving single-dimensional domains: the set cover problem. Here are some references for the greedy algorithm for set cover.
  • Approximation Algorithms, Vijay Vazirani. Springer-Verlag 2001. See Section 2.1; also Section 13.1 describes the same algorithm, but the algorithm is stated and analyzed as a dual-fitting algorithm.
    
  • Algorithm Design, J. Kleinberg and É. Tardos. Addison-Wesley, 2005. See Section 11.3; the analysis here is also based on dual fitting, and is similar to the one in Section 13.1 of the above book.
  Started with metric facility location. (Section 15.4.2 gives a different interpretation of the algorithm discussed in class, based on the primal-dual method for approximation algorithms.)
• Sep 29: Applications contd.: finished facility location. Started with makespan-minimization on machines with speeds (called "related machines" in the scheduling literature). See section 12.2.1. Note: there are various typos in the proof of Lemma 12.6.
• Oct 4: Finished with makespan-minimization. Mechanism design in multidimensional domains: combinatorial auctions (CAs). Some examples.
• Oct 6: CAs contd.: truthful, approximaton mechanisms with single-minded valuations. See sections 11.1, 11.2.
• Oct 13: CAs contd.: finished the single-minded case. Truthful mechanisms for subadditive valuations.
• Oct 15: CAs contd.: a general technique for combining VCG and approximation algorithms to obtain truthful, approximation mechanisms. See section 12.3, and the following paper:
  • R. Lavi, C. Swamy. Truthful and near-optimal mechanism design via linear programming. Proceedings, FOCS 2005.
• Oct 20: CAs contd.: finished the proof showing the black-box reduction form LP-based approximation algorithms to truthful, approximation mechanisms.
• Oct 22: CAs contd.: black-box reduction converting an FPAS for a packing problem with polynomial dimension to a truthful-in-expectation FPAS. See the following paper:
  • S. Dughmi, T. Roughgarden. Black-box randomized reductions in algorithmic mechanism design. Proceedings, STOC 2010.

Prerequisites

There is no official prerequisite for the course. I will assume some basic knowledge of discrete structures like graphs, algorithms, and optimization. No prior knowledge of game theory will be assumed. If you would like to take the course but are unsure about the prerequisites, then come and talk to me.

Books and Supplementary Material

For many of the topics we will follow the book

• Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Éva Tardos, Vijay Vazirani (editors). Cambridge University Press, 2007.

Tentative list of topics

Some subset of the following topics will be covered. This is a course that offers plenty of flexibility. If there is a topic that is not in here and you would really like to see covered, come and talk to me about it!

1. Introduction to games and algorithms.
   
   
2. Algorithmic Mechanism Design. The design of computationally tractable games (called mechanisms) whose equilibria are efficient. Topics include:
   • Social-choice functions and the implementation problem in dominant strategies: truthful mechanism design with various social-choice functions
   • Combinatorial auctions: social-welfare maximization
   • Cost-sharing mechanisms
     
     
3. (In)Efficiency of equilibria. Quantifying the efficiency-loss in game-versions of various optimization problems due to uncoordinated behavior. Examples include:
   • Network routing or congestion games: flow/traffic controlled by strategic agents is routed between source-sink pairs
   • Network creation and connectivity games: agents are nodes/terminals that seek to create a graph or subgraph with certain connectivity properties
   • Load balancing games: agents are jobs that need to be distributed across machines
   • Bandwidth sharing games: a common resource, e.g., bandwidth, is to be shared across several agents
     
     
4. Computational Aspects of Equilibria.
   • Existence, complexity, and algorithmic aspects of Nash equilibria
   • Graphical games
   • Correlated equilibria and their computation
   • Markets and the computation of market equilibria