CO759: Algorithmic Game Theory
(Topics in Discrete Optimization)

Announcements (assignments etc.)

• Apr 29: Welcome to CO 759.
• Jun 4: Assignment 1 is available. (Last update on Jun 4: some minor notational changes, the ordering of Q2 and Q3 was reversed.)
  Due by Jun 25, 2015.
• Jun 4: Starting Jun 9, the lectures will be from 10:30am-12:30pm. There will be a break of 5-10min. around 11:30am. The classroom will remain unchanged, i.e., MC 6486.
• Jun 16: There is no lecture on Jun 16, 18. We will resume our 2-hourly meetings on Jun 23.
• Jun 16: Clarifications about Assignment 1:
  • In Q2(b), you may assume that the alternative set A is finite.
  • In Q4(e), the approximation guarantee of 2ρ only needs to hold with respect to the optimal integral schedule; that is, we seek an implementable algorithm that returns a fractional schedule of makespan at most 2ρ times the optimal makespan (wrt. integral schedules).
• Jul 13: There is no lecture on Jul 14, 16. We will resume our 2-hourly meetings on Jul 21.
• Jul 20: The "Topics Covered" section has been updated and made current.
• Jul 21: Here is the missing bit from the proof of Nash's theorem using Brouwer's fixed-point theorem.
• Jul 21: Assignment 2 is available. (Last update on Aug 4: Q8 added)
  Due by Aug 14, 2015.
  Note: You may answer any 5 questions on the assignment (or answer more for bonus marks). There are currently 7 8 questions on the assignment; a couple more questions will be posted in the coming week; Q8 was added on Aug 4. All questions carry equal weightage.
• Jul 28: No lecture. There will be an extra lecture on Jul 30 (which will be the last lecture).
• Jul 28: Clarifications about Assignment 2:
  • There was a typo in Q1: in the definition of A', each x_i's is either m or a multiple of the ceiling of m/n² (not the floor).
  • The wording in the first sentence of Q7(b) has slightly changed. The part asks you to prove a contrapositive (qualitatively speaking) of Q7(a).

Course Overview and Outline

This is a graduate-level, introductory course on algorithmic game theory. 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)

• May 5, 7: Course introduction and overview. Some simple games and definitions of solution concepts. See sections 1.1-1.3.
• May 12: Started with algorithmic mechanism design. See Chapter 9. Introduction to mechanism-design, definition of a mechanism, notions of truthfulness/dominmant-strategy incentive compatibility, 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).
• May 14: 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.
• May 19: The desirable features of VCG, and its limitation in the face of computational intractability. The necessary condition of weak-monotonicity (WMON) for truthfulness. Single-dimensional domains: definition and examples.
• May 21: Characterization of implementable SCFs: the equivalence of WMON with the monotonicity condition for single-dimensional domains, 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 α⁽ⁱ⁾ 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 ∞).
• May 26: 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.
    
  • The Design of Approximation Algorithms by David Williamson and David Shmoys. Cambridge University Press, 2011. See Theorem 1.11. Theorem 1.12 proves a stronger guarantee for the same algorithm via a dual-fitting analysis.
  Started with metric facility location and the Mettu-Plaxton algorithm. (Section 15.4.2 gives a different interpretation of the Mettu-Plaxton algorithm, based on the primal-dual method for approximation algorithms.) Here is the Mettu-Plaxton paper: "The Online Median Problem", SIAM Journal on Computing, 32:816-832, 2003.
• May 28: 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.
• Jun 2: Finished with makespan-minimization and introduced truthful-in-expectation mechanisms. Started with mechanism design in multidimensional domains. Defined combinatorial auctions (CAs). Gave some motivation and examples, and discussed issues arising from a combination of computational and game-theoretic concerns.
• Jun 4: Described truthful, approximaton mechanisms for CAs with single-minded valuations. See sections 11.1, 11.2. Described a truthful mechanism for subadditive valuations based on constructing a maximal-in-range (MIR) mechanism, where we exactly optimize over a subset of allocations.
• Jun 9: Started with a general technique for combining VCG and approximation algorithms to obtain truthful, approximation mechanisms. See section 12.3, and the following paper:
  • R. Lavi and C. Swamy. Truthful and near-optimal mechanism design via linear programming. Journal of the ACM, 2011.
  Outlined the ellipsoid method and stated a theorem summarizing its performance. Here are the slides on ellipsoid method used in lecture.
• Jun 11: Finished the proof showing the black-box reduction from LP-based approximation algorithms to truthful, approximation mechanisms. Showed various mechanisms that one obtains as a corollary of this result. Observed that this construction can be viewed as using an LP-based ρ-approximation algorithm to identify a subset (called the range) of the convex hull of integer allocations such that: (a) one can (exactly) optimize efficiently over this subest; and (b) the optimum over the subset is within a ρ-factor of the optimal social welfare. This type of construction is often called a maximal-in-distributional-range (MIDR) mechanism, and implies that a approximation algorithm can sometimes be viewed as exactly optimizing over a certain (large, meaningful) subset.
  Started with another construction showing that a similar black-box transformation (from approximation algorithms to MIDR mechanisms) can be obtained from FPTASes for packing problems. Defined packing problems, and the concept of an FPTAS.
• Jun 16, 18: No lecture.
• Jun 23: Described the black-box reduction converting an FPTAS for a packing problem with polynomial dimension to a truthful-in-expectation FPTAS using tools from smoothed complexity. See the following paper:
  • S. Dughmi and T. Roughgarden. Black-box randomized reductions in algorithmic mechanism design. Proceedings, STOC 2010.
• Jun 25: Non-truthful mechanisms for CAs. Defined simultaneous item-bidding auctions and gave some examples. Defined the (complete-information) price of anarchy (PoA) and non-overbidding strategies. Proved a PoA bound of 2 for simultaneous second-price auctions with non-overbidding subadditive players. See the following paper:
  • K. Bhawalkar and T. Roughgarden. Welfare guarantees for combinatorial auctions with item bidding. Proceedings, SODA 2011.
  Stated that with submodular players a non-overbidding pure NE (i.e., a pure NE with non-overbidding strategies) always exists.
• Jun 30: Described a greedy algorithm that computes a non-overbidding pure NE for simultaneous second-price auctions with submodular players. See the following paper (Section 3.2):
  • G. Christodoulou, A. Kovacs, and M. Schapira. Bayesian combinatorial auctions. Proceedings, ICALP 2008.
  Defined load-balancing games. Proved existence of pure NE. Considered the objective of minimizing of maximum player cost (equivalently, the minimum makespan objective), defined the concepts of price of anarchy (PoA) and price of stability (PoS), and obtained PoA and PoS bounds. See sections 20.1, 20.2 (unfortunately the book uses the reverse notation of i to index jobs and j to index machines); the notes at the end of Chapter 20 give pointers to work in other models. See also the following paper, which is the source of Theorem 20.6 on the fast convergence to a Nash equilibrium via (carefully chosen) improving moves, and which also studies the convergence time of improving moves in other related load balancing games:
  • Eyal Even-Dar, Alex Kesselman, Yishay Mansour. Convergence time to Nash equilibria. ACM Transactions on Algorithms, 3(3), 2007.
  Started with atomic (unsplittable) routing games: definition and examples. See section 18.2.2.
• Jul 2: Atomic routing games contd. Existence of pure NE via a potential function. Defined potential games. See sections 18.2.2, 18.3.2 for atomic routing games, and sections 19.3.2, 19.3.3 for potential games and potential functions. Analysis of PoA and PoS for the sum-of-players'-costs objective. Used the potential function to obtain PoS bounds. Proved a PoA bound of 5/2 for linear latency functions (which we later re-interpret using the smoothness framework), and showed that this is tight. See section 18.4.2 and the following paper:
  • George Christodoulou, Elias Koutsoupias. The price of anarchy of finite congestion games. Proceedings, STOC 2005.
    This considers atomic congestion games (which generalize atomic routing games). The proof of the 5/2-bound on the PoA with linear latencies is taken from here.
  See example 18.6 for the PoA lower bound of 5/2 for linear latencies; here are the slides used to illustrate in lecture to illustrate this. Showed that pure NE in single source-sink atomic routing games can be computed via a min-cost flow computation.
• Jul 7: Defined the concept of (λ μ)-smooth games. Defined the notions of correlated equilibria (CE) and coarse-correlated equilibria (CCE), and gave some examples of CE. Proved that the PoA with respect to even CCE is at most λ/(1-μ) in (λ μ)-smooth games. Observed that the PoA bound of 5/2 for atomic routing games with linear latencies obtained previously implies that these games are (5/3,1/3)-smooth, and hence yields a 5/3-PoA bound with respect to CCE. The following paper introduced this smoothness framework and contains many other results.
  • T. Roughgarden. Intrinsic robustness of the price of anarchy. Proceedings, STOC 2009.
  Started with nonatomic routing games: definition, examples, and definition of a Nash flow. See section 18.2.1.
• Jul 9: Stated convex optimization theorem. Defined (convex) potential function for nonatomic routing games and used the convex optimization theorem to prove existence and uniqueness (in terms of edge latencies) of a Nash flow. See section 18.3.1. Proved tight PoA bounds for any class of latency functions containing all constant functions. See section 18.4.1.
• Jul 14, 16: no lecture.

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. Dominant-strategy incentive compatibility, Bayesian incentive compatibility, truthful mechanism design with various social-choice functions
   • Combinatorial auctions: social-welfare maximization and profit maximization
   • Mechanisms with good Nash equilibria: Simultaneous first- and second-price auctions
   • Cost-sharing mechanisms
     
     
3. (In)Efficiency of equilibria. Quantifying the efficiency-loss in game-versions of various optimization problems due to uncoordinated behavior. Topics include:
   • Network routing or congestion games: flow/traffic controlled by strategic agents is routed between source-sink pairs
   • Smoothness analysis of price of anarchy
   • Load balancing games, bandwidth sharing games
     
     
4. Computational Aspects of Equilibria.
   • Existence, complexity, and algorithmic aspects of Nash equilibria
   • Correlated equilibria and their computation
   • Markets and the computation of market equilibria