CO759: Algorithmic Game Theory
(Topics in Discrete Optimization)

Announcements (assignments etc.)

• May 6: Welcome to CO 759.
• May 20: Assignment 1 is available. Due on June 10, 2008. Here are the Solutions.
  
  
• May 20: Two clarifications about today's lecture.
  • The potential function Φ(f) = (∑_e ∑_i=1…Nfe l_e(i / N))/N that I mentioned for the atomic routing game with N players, each routing 1/N units of flow, is an inexact potential function (the change in Φ is 1/N × (change in the deviating player's cost)). But it does tend to the potential function used for the nonatomic game as N → ∞.
  • As I mentioned in class, the problem of minimizing the potential function Φ for a single-source, single-sink atomic routing game with latency functions that are not necessarily increasing is NP-hard. Here is a sketch of the reduction. First suppose that there are multiple sinks t₁,…,t_k. Consider the latency functions l_e(f_e)=c_e if f_e=1 and 0 otherwise. Then, Φ(f) is simply the c_e-cost of the edges with f_e not equal to 0. So minimizing Φ amounts to finding a min-cost set of edges containing a directed path from the source s to each t_i. This problem is NP-hard since the set-cover problem can be reduced to it. One can now reduce the multiple-sink problem to the single-sink problem by adding a new sink t with edges (t_i ,t) for each i, and giving each such edge a latency function that is 0 for x ≤ 1 and which increases steeply beyond 1. Thus, these edges effectively encode unit capacities, making the single-sink problem equivalent to the multiple-sink problem.
  
  
• May 22: Read section 18.5.1, which shows that imposing tolls on edges can completely mitigate any efficiency-loss due to selfish behavior in the nonatomic routing game.
• May 27: Regarding the question of which strategy profiles giving rise to the star-graph constitute a NE for α ≥ 1, it is indeed true that for all α ≥ 1, any strategy profile yielding the star is a NE.
• June 2: There was a typo in Q5 of assignment 1: the quantity α should be defined so that we have l_e(x+1) ≤ α l_e(x) for all x ≥ 1 and all e. The assignment has been updated.
• June 3: I will hold office hours on Thursday June 5, after class till 3:30pm in lieu of my office hours on Tuesday June 10.
• June 10: Assignment 2 is available. Due on July 3, 2008. Here are the Solutions.
  
  
• June 16: Solutions to Assignment 1 have been posted.
• June 23: In addition to my office hours this Tuesday (June 24), I will hold office hours on Friday June 27 from 2 to 3pm since next Tuesday, July 1, is a holiday.
• June 25: There was a typo in Q4 of assignment 2: the definition of social welfare given in words and its mathematical formula were somewhat contradictory. This has been corrected.
• June 27: Assignment 2 has been corrected and updated again. My proposed fix of Q4 on assignment 2 introduced some other problems. As a result Q4 on the assignment has changed somewhat and the assignment has been updated. Please make sure you have the latest version, which defines V(S) = ∑_j p_j|union of all R_ijs| - ∑_i c_i|S_i|.
• July 6: Solutions to Assignment 2 have been posted.
• July 10: Assignment 3 is available. Due by August 7, 2008.
  
  
• July 10: There will be no class on July 15.
• July 17: Regular lecture today.
• July 18: Q2c) on assignment 3 has been clarified.
• July 23: A small parenthetical remark has been added at the end of Q3 on assignment 3.
• July 28: As announced earlier, there will be an extra meeting on Thursday, July 31, from 1-2:30pm. The room is MC 5136B (note the change in location).
• Aug 19: Your assignments have been graded and can be picked up.

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)

• May 6: Course introduction. Some simple games and definitions of solution concepts. See sections 1.1-1.3.
• May 8: Load balancing game. Existence of pure Nash equilibria (NE), bounds on price of anarchy (PoA) and price of stability (PoS). 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.
  
  
• May 13: Atomic routing game, potential functions and potential games. Existence of pure NE and bounds on PoS via potential functions. 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.
• May 15: Atomic routing game contd. Bounds on PoA with linear latencies. See section 18.4.2. Computation of pure NE and the class PLS. See section 19.3.4, which discusses PLS and the PLS-completeness of finding a local minimum of Φ in more detail. Nonatomic routing game: definition and some examples. See section 18.2.1. See also the following papers:
  • George Christodoulou, Elias Koutsoupias. The price of anarchy of finite congestion games. Proceedings, STOC 2005.
    This considers a class of games called congestion games, which generalizes the atomic routing game. The proof of the 5/2-bound on the PoA with linear latencies is taken from here.
  • Alex Fabrikant, Christos Papadimitriou, Kunal Talwar. The complexity of pure Nash equilibria. Proceedings, STOC 2004.
    Shows the PLS-completeness of computing a pure NE in (network) congestion games.
  • Steve Chien, Alistair Sinclair. Convergence to approximate Nash equilibria in congestion games. Proceedings, SODA 2007.
    Shows that "approximate Nash-dynamics" converge to an "approximate Nash equilibrium" in (symmetric) congestion games. See also Q5 on Assignment 1 for another argument.
  
  
• May 20: Nonatomic routing game contd. Existence and uniqueness of pure NE via a potential-function argument. See section 18.3.1.
• May 22: Nonatomic routing game contd. Bounds on PoA including bicriteria bounds, ways of reducing PoA. See sections 18.4.1, 18.5. Section 18.5.1 shows that imposing tolls on edges can completely mitigate the efficiency-loss in nonatomic routing. See also the following paper about Braess' paradox and the network design problem motivated by it:
  • Tim Roughgarden. On the severity of Braess's paradox: designing networks for selfish users is hard. Journal of Computer and System Sciences, 72(5), 2006.
  
  
• May 27: Proof of convex-optimization theorem. Congestion games. See section 19.3.2. Introduction and motivation for game-theoretic models of network formation. Network creation game: definition, optimal solutions, Nash equilibria, and PoS bounds. See sections 19.2.1, 19.2.2. See also the following surveys: the first discusses both random-graph and game-theoretic models for network formation, contrasting the two approaches; the second is a more detailed survey on network-formation models considered in the economics literature.
  • Matthew Jackson. The economics of social networks. Advances in Economics and Econometrics, Theory and Applications: Ninth World Congress of the Econometric Society, volume I, 2006.
  • Matthew Jackson. A survey of models of network formation: stability and efficiency. Group Formation in Economics: Networks, Clubs and Coalitions, 2004.
  
  
• May 29: PoA bounds for the network creation game. See section 19.2.3. The proofs presented in class are adapted from the following papers:
  • E. Demaine, M. Hajiaghayi, H. Mahini, M. Zadimoghaddam. The price of anarchy in network creation games. Proceedings, PODC 2007.
    
  • S. Albers, S. Ellis, E. Even-Dar, Y. Mansour, L. Roddity. On Nash equilibria of a network creation game. Proceedings, SODA 2006. Among other results, proves an O(1) bound on the PoA when α ≥ 12 n log n.
  
  
• June 3: Facility location game and utility games. Definition, existence of pure NE, PoS and PoA bounds. See section 19.4 (all subsections). Section 19.4.5 shows that one can even bound the social-welfare value of a solution that need not be a NE.
• June 5: Proof of Nash's theorem using Brouwer's fixed point theorem. Sperner's Lemma and its use in the proof of Brouwer's fixed point theorem. Slides (ppt) containing the proof of the (2D) Sperner's lemma.
• June 10: Stated d-dimensional Sperner's Lemma. Proof of Brouwer's theorem using Sperner's Lemma. Started with the proof showing that finding a NE that maximizes the total payoff to the players is NP-hard.
• June 12: NP-completeness proof contd. Described and analyzed the "mixing" gadget and the "consistency" gadget.
• June 17: Finished NP-completeness proof. See section 2.2. The class TFNP of total search problems, definition and examples. The NP-completeness proof is adapted from the following paper:
  • V. Conitzer, T. Sandholm. New complexity results about Nash equilibria. Games and Economic Behavior, 63(2), 2008.
  
  
• June 19: The class PPAD, definition and examples. See section 2.4. Started with sketch of proof showing that r-NASH is PPAD-complete. See sections 2.5, 2.6. See also:
  • Talk given by Paul Goldberg that covers total search problems (the class TFNP), the class PPAD and another subclass of TFNP, and indicates why r-NASH is in the class PPAD.
    
  • Paul Goldberg, Christos Papadimitriou. Reducibility among equilibrium problems. Proceedings, STOC 2006.
    Shows that r-NASH ≤ 4-NASH by showing that multiplayer games can be reduced to graphical games with degree 3 (and 2 strategies per-node), which in turn can be reduced to constant-player games. The graphical-game gadgets developed here form the basis of all subsequent PPAD-hardness proofs.
  
  
• June 24: Completed the proof-sketch of the PPAD-completeness result. See also the following papers. The first paper proves that the 2D-SPERNER problem and a discrete 2D-version of Brouwer's fixed-point problem are PPAD-complete. The next two papers show respectively that 4-NASH and 2-NASH are PPAD-complete. Both these results use a reduction from a discrete 3D-version of Brouwer's problem instead of 2D-SPERNER, which we used in class.
  • Xi Chen, Xiaotie Deng. On the complexity of 2D discrete fixed point problem. Proceedings, ICALP 2006.
  • C. Daskalakis, P. Godlberg, C. Papadimitriou. The complexity of computing a Nash equilibrium. Proceedings, STOC 2006.
  • Xi Chen, Xiaotie Deng. Settling the complexity of two-player Nash equilibrium. Proceedings, FOCS 2006.
  
  
• June 26: Computation of approximate NE. Gave algorithms for computing a 0.382-NE and a 0.5-well-supported NE in {0,1}-games. These algorithms are taken from the following papers respectively.
  • H. Bosse, J. Byrka, E. Markakis. New algorithms for approximate Nash equilibria in bimatrix games. Proceedings, WINE 2007.
  • S. Kontogiannis, P. Spirakis. Efficient algorithms for constant well supported approximate equilibria in bimatrix games. Proceedings, ICALP 2007.
  
  
• July 1: No class - university holiday.
• July 3: 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). The (algorithmic) implementation problem: which social-choice functions (SCFs) are (efficiently) implementable, or admit an approximation that is efficiently implementable.
• July 8: 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.
• July 10: 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 ∞).
• July 15: Class canceled.
• July 17: Completed characterization of implementability in single-dimensional domains. Applications: the set cover problem.
• July 22: Applications contd.: 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.)
• July 24: More applications: scheduling to minimize makespan 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.
• July 29: Mechanism design in multidimensional domains: combinatorial auctions (CAs). Truthful, approximaton mechanisms with single-minded valuations. See sections 11.1, 11.2.
• July 31: CAs contd.: truthful mechanisms for subadditive valuations. A general technique for combining VCG and approximation algorithms to obtain truthful, approximation mechanisms. Slides (ppt) of lecture presentation and more. See section 12.3, and the following paper:
  • R. Lavi, C. Swamy. Truthful and near-optimal mechanism design via linear programming. Proceedings, FOCS 2005.

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. 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
     
     
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. 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