CSE 599m: Algorithms and Economics of Networks

CSE Home

About Us

Search

Contact Info

Instructors:

Abraham Flaxman and Vahab S. Mirrokni.
Meeting times: Wednesday and Friday 12:00 – 1:20 in CSE 503.
Office hours: Wednesday and Friday 1:30 – 2:20 in CSE 436.

Course announcement

Course requirements and grading

Homework

Potential Projects

Reading Group

Template for scribe notes

Syllabus

Lecture 1

Introduction, real networks, n-player game theory

• Slides: Class1.ppt
• Required reading: None
• Recommended reading:
• A good book on Introduction to Game Theory by Martin J. Osborne. The first two chapters (about Nash equilbria) are available online: http://www.chass.utoronto.ca/~osborne/igt/
• For the definition of Potential Games, State Graph, and the price of anarchy see section 1.2 of Vahab's thesis: Approximation Algorithms for Distributed and Selfish Agents by V. Mirrokni, Massachusetts Institute of Technology, June, 2005. Available online: http://theory.csail.mit.edu/~mirrokni/finalthesis.ps

Lecture 2

Price of anarchy, Load balancing games

• Required reading: None
• Recommended reading:
• Congestion Games: R. W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65-67, 1973.
• Price of Anarchy of Congestion Games. George Christodoulou, Elias Koutsoupias: The price of anarchy of finite congestion games. STOC 2005: 67-73. http://cgi.di.uoa.gr/~gchristo/p67-christodoulou.pdf
• Related reading:
• Load Balancing Games.
• Elias Koutsoupias, Christos H. Papadimitriou: Worst-case Equilibria. STACS 1999: 404-413.
• Artur Czumaj, Berthold Vöcking: Tight bounds for worst-case equilibria. ACM Transactions on Algorithms 3(1): (2007)
• Martin Gairing, Thomas Lücking, Marios Mavronicolas, Burkhard Monien: Computing Nash equilibria for scheduling on restricted parallel links. STOC 2004: 613-622

Lecture 3

(Network) Congestion games, Market Sharing Games

• Slides: Class3.ppt
• Required reading: None
• Recommended reading:
• Congestion Games: R. W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65-67, 1973.
• Price of Anarchy of Congestion Games. George Christodoulou, Elias Koutsoupias: The price of anarchy of finite congestion games. STOC 2005: 67-73. http://cgi.di.uoa.gr/~gchristo/p67-christodoulou.pdf
• Related reading:
• Price of anarchy of Congestion Games
• Tim Roughgarden, Éva Tardos: How bad is selfish routing? J. ACM 49(2): 236-259 (2002)
• Baruch Awerbuch, Yossi Azar, Amir Epstein: The price of routing unsplittable flow. STOC 2005 : 57-66
• Michel X. Goemans, Erran L. Li, Vahab S. Mirrokni, Marina Thottan: Market sharing games applied to content distribution in ad-hoc networks. MobiHoc 2004: 55-66
• Convergence of Congestion Games
• H. Ackermann, H. Röglin, and B. Vöcking, On the Impact of Combinatorial Structure on Congestion Games, In Proc. 47th FOCS (Berkeley, 2006).

Lecture 4

Coordination Mechanism Design

• Slides: UWCoordination.ppt
• Scribe: Chih-Wei (Gary) Huang
• Scribe Notes: Lecture 4 Notes
• Required reading: None
• Recommended reading:
• George Christodoulou, Elias Koutsoupias, Akash Nanavati: Coordination Mechanisms. ICALP 2004: 345-357
• Nicole Immorlica, Li Li, Vahab S. Mirrokni, Andreas Schulz: Coordination Mechanisms for Selfish Scheduling. WINE 2005: 55-69
• Related reading:
• Yossi Azar, Kamal Jain, Vahab S. Mirrokni: Optimal Coordination Mechanisms for Unrelated Machine Scheduling. Unpublished Manuscript, 2007.

Lecture 5

Models of network formation 1 --- Erdos-Renyi graphs

• Scribe: Elisa Celis
• Scribe Notes: Lecture 5 Notes
• Required reading: None
• Recommended reading:
• Chapter 1 of R. van der Hofstad, Random Graphs and Complex Networks, http://www.win.tue.nl/%7Erhofstad/NotesRGCN.pdf
• Related reading:
• B. Bollobas, Random Graphs, 2000
• S. Janson, A. Luczak, A. Rucinski, Random Graphs, 2000

Lecture 6

Degree Distributions and Concentration Inequalities

• Scribe: Ben Birnbaum
• Scribe Notes: Lecture 6 Notes
• Required reading: None
• Recommended reading:
• D. Achlioptas, A. Clauset, D. Kempe, and C. Moore, On the bias of Traceroute sampling, STOC'05, http://www.cs.ucsc.edu/~optas/papers/traceroute.pdf

Lecture 7

Bias in traceroute sampling

• Scribe: Vibhor Rastogi
• Scribe Notes: Lecture 7 Notes
• Required reading: None
• Recommended reading:
• D. Achlioptas, A. Clauset, D. Kempe, and C. Moore, On the bias of Traceroute sampling, STOC'05, http://www.cs.ucsc.edu/~optas/papers/traceroute.pdf
• Related reading:
• J. Leguay, M. Latapy, T. Friedman, and K. Salamatian, Describing and simulating internet routes, IFIP-TC6 Networking Conference, 2005.

Lecture 8

Bias reduction for traceroute sampling, Models of network formation 2: Preferential Attachment

• Required reading: None
• Recommended reading: Chapter 8 of R. van der Hofstad, Random Graphs and Complex Networks, http://www.win.tue.nl/%7Erhofstad/NotesRGCN.pdf

Lecture 9

Preferential Attachment Graphs, Potential Games

• Required reading: None
• Recommended reading: Chapter 8 of R. van der Hofstad, Random Graphs and Complex Networks, http://www.win.tue.nl/%7Erhofstad/NotesRGCN.pdf

Lecture 10

Convergence in Potential Games

• Slides: Convergence.pdf
• Slides: Congestiongames.pdf
• Required reading:
• H. Ackermann, H. Röglin, and B. Vöcking, On the Impact of Combinatorial Structure on Congestion Games, In Proc. 47th FOCS (Berkeley, 2006), http://www-i1.informatik.rwth-aachen.de/~roeglin/publications/FOCS06.pdf

• Recommended reading:
• Alex Fabrikant, Christos Papadimitriou, Kunal Talwar, "The Complexity of Pure Nash Equilibria". In Proc. of STOC 2004, pages 604-612.
• Heiner Ackermann, Heiko Röglin, and Berthold Vöcking, Pure Nash Equilibria in Player-Specific and Weighted Congestion Games, In Proc. of the 2nd WINE (Patras, Greece, 2006), Pages 50-61. http://www-i1.informatik.rwth-aachen.de/~roeglin/publications/WINE06.pdf
• G. Christodolou, V. S. Mirrokni, and A. Sidiropolous, Convergence and Approximation in Potential Games , STACS, 2006. http://theory.csail.mit.edu/~mirrokni/potential06.ps

Lecture 11

Sink Equilibria and Convergence

• Required reading:
• M. Goemans, V. S. Mirrokni, and A. Vetta, Sink Equilibria and Convergence, FOCS, 2005, http://theory.csail.mit.edu/~mirrokni/sink.ps

• Recommended reading:
• A. Vetta, Nash equilibria in competitive societies with applications to facility location, traffic routing and auctions, FOCS, pp416-425, 2002 http://www.math.mcgill.ca/~vetta/Research.dir/nash.ps
• V. Mirrokni and A. Vetta, Convergence Issues in Competitive Games, RANDOM-APPROX, 2004. http://www.math.mcgill.ca/~vetta/Research.dir/fast.ps

Lecture 12

Spread of Influence in Social Networks

• Recommended Reading:
• D. Kempe, J. Kleinberg, E. Tardos, Maximizing the spread of influence through a social network, KDD'03.
• D. Kempe, J. Kleinberg, E. Tardos, Influential nodes in a diffusion model for social networks, ICALP'05.
• E. Mossel, S. Roch, On the submodularity of influence in social networks, STOC'07.

Lecture 13

Network formation games

• Recommended reading:
• A. Fabrikant, A. Luthra, E. Maneva, C. Papadimitriou, S. Shenker, On a network creation game, PODC 2003, http://www.cs.berkeley.edu/~alexf/papers/flmps03.pdf
• S. Albers, S. Eilts, E. Even-Dar, Y. Mansour, L. Roditty, On Nash equlibria for a network creation game, SODA 2006, http://www.math.tau.ac.il/~mansour/papers/06soda.pdf
• Related reading:
• Economists have been working on similar-but-different models of network formation for a while now: http://www.stanford.edu/~jacksonm/ has survey-style introductions

Lecture 14

Streaming and semi-streaming models

• Required reading: None
• Recommended reading:
• N. Alon, Y. Matias, M. Szegedy, The space complexity of approximating the frequence moments, STOC 1996, http://www.citeulike.org/article/1091652
• J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, J. Zhang, On graph problems in a semi-streaming model, ICALP 2004, http://www.springerlink.com/content/qr7h100awelu6hkc/
• Related reading:
• S. Muthukrishnan, Data streams: algorithms and applications, 2005, http://www.citeulike.org/article/1290739

Lecture 15

Market Equilibria and Power Assignment in Wireless Networks

• Slides: power.ppt
• Required reading: P. Bahl; M.T. Hajiaghayi; K. Jain; V.S. Mirrokni; L. Qui; A. Saberi; Cell Breathing in Wireless LANs: Algorithms and Evaluation, IEEE Transactions on Mobile Computing, http://theory.csail.mit.edu/~mirrokni/cellbreath.pdf
• Recommended Reading:
• Kamal Jain, Vijay V. Vazirani, Yinyu Ye: Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. SODA 2005: 63-71
• Yinyu Ye: Computing the Arrow-Debreu Competitive Market Equilibrium and Its Extensions. AAIM 2005: 3-5
• Rahul Garg, Sanjiv Kapour, Auction Algorithms for Market Equilibrium, Math of OR, Nov. 2006.
• N. Devanur, C. Papadimitriou, and A. Saberi, V. Vazirani, ``Market Equilibrium via a Primal-Dual Algorithm for a Convex Program, To appear in Journal of ACM.

• Related Reading:
• Lisa Fleischer, Kamal Jain, Mohammad Mahdian: Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games. FOCS 2004: 277-285
• Kamal Jain: A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities. FOCS 2004: 286-294

Lecture 16

Pagerank, personalized pagerank, the pagerank axioms

• Recommended Reading:
• I. Palacois-Huerta and O. Volij, The measurement of intellectual influence, Econometrica 2004, http://ideas.repec.org/a/ecm/emetrp/v72y2004i3p963-977.html
• A. Altman and M. Tennenholtz, Ranking Systems: The PageRank Axioms, EC 2005, http://iew3.technion.ac.il/~moshet/pagerank.pdf
• Related Reading:
• J. Kleinberg, Authoritative sources in a hyperlinked environment, JACM 1999, http://www.cs.cornell.edu/home/kleinber/auth.pdf
• L. Page, S. Brin, R. Motwani, T. Winograd, The pagerank citation ranking: bringing order to the web, Stanford Tech Report 1998, http://dbpubs.stanford.edu:8090/pub/1999-66

Lecture 17

Pagerank computation on a laptop

• Recommended Reading:
• Frank McSherry, A uniform approach to accelerated PageRank computation, http://doi.acm.org/10.1145/1060745.1060829,

Lecture 18

Clustering: Impossibility, k-means, and spectral

• Recommended Reading:
• J. Kleinberg, An impossibility theorem for clustering, http://www.cs.cornell.edu/home/kleinber/nips15.ps
• Related Reading:
• D. Spielman and S. Teng, Spectral partitioning works: Planar graphs and finite element meshes, http://www.eecs.berkeley.edu/Pubs/TechRpts/1996/CSD-96-898.pdf
• D. Arthur and S. Vassilvitskii, kmeans++: the advantages of careful seeding, http://www.stanford.edu/~sergeiv/papers/kMeansPP-soda.pdf
• R. Ostrovsky, Y. Rabani, L. Schulman, C. Swamy, The effectiveness of Lloyd-type methods for the k-means problem, http://www.cs.ucla.edu/~rafail/PUBLIC/76.pdf

Lecture 19

Combinatorial Clustering and Rank Aggregation

• Recommended Reading:
• Reid Andersen, Fan R. K. Chung, Kevin Lang: Local Graph Partitioning using PageRank Vectors. FOCS 2006: 475-486

• Related Reading:
• R. Fagin, Ravi Kumar and D. Sivakumar. Efficient similarity search and classification via rank aggregation, Proc. 2003 ACM SIGMOD Conference (SIGMOD '03), pp. 301-312.
• R. Fagin, Amnon Lotem and Moni Naor. Optimal aggregation algorithms for middleware, J. Computer and System Sciences 66 (2003), pp. 614-656. Extended abstract appeared in Proc. 2001 ACM Symposium on Principles of Database Systems (PODS '01), pp. 102-113
• R. Fagin, Ravi Kumar, Mohammad Mahdian, D. Sivakumar, and Erik Vee. Comparing and aggregating rankings with ties, Proc. 2004 ACM Symposium on Principles of Database Systems

Lecture 20

Rank Aggregation and Two-sided Markets

• Recommended Reading:
• Nir Ailon, Moses Charikar, Alantha Newman: Aggregating inconsistent information: ranking and clustering. STOC 2005: 684-693
• Roth, A.E. and Vande Vate, J.H., "Random Paths to Stability in Two-Sided Matching," Econometrica, 58, 1990, 1475-1480
• D. Knuth, Mariages Stables, et leurs relations avec d'autres problèmes combinatoires par Donald E. Knuth (Montréal: Les Presses de l'Université de Montréal, 1976), 106pp.
• Related Reading:
• Michel X. Goemans, Erran L. Li, Vahab S. Mirrokni, Marina Thottan: Market sharing games applied to content distribution in ad-hoc networks. MobiHoc 2004: 55-66
• H. Ackermann, P. Goldberg, V. Mirrokni, H. Röglin, and B. Vöcking, Uncoordinated Two-sided Markets, Manuscript.
• Nir Ailon, Aggregation of Partial Rankings, p-Ratings and Top-m Lists, SODA 2007.
• Claire Kenyon-Mathieu and Warren Schudy. How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments, STOC 2007.

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to Abraham Flaxman]