8803 Connections between Learning, Game Theory, and Optimization, Fall 2010

Learning, Game Theory, and Optimization

Maria Florina Balcan

Time: Tues/Thurs 4:35-5:55, Place: Instr Center 117.

Course description: Over the past 10 years, researchers have discovered a number of important and deep connections between machine learning theory, algorithmic game theory, and combinatorial optimization. This course will explore these connections, discussing fundamental topics in each area and how ideas from each area can shed light on the others. You can find more info here

Office hours: Just stop by my office or make an appointment.

Homeworks

Project ideas

Lecture Notes & Handouts

  1. 08/24: Introduction.
  2. 08/26: Online Learning, Combining Experts Advice, and Regret Minimization. The Weighted Majority Algorithm.
    See also: An Online learning survey by A. Blum. The original Weighted Majority paper by N. Littlestone and M. Warmuth.
  3. 08/31: Experts Learning and The Minimax Theorem for Zero-Sum Games.
    See also: Game Theory, On-line Prediction and Boosting by Y. Freund and R. Schapire. COLT 1996.
  4. 09/02: A generic conversion from algorithms with good external regret guarantees to algorithms with good swap regret guarantees.
    See also: From External to Internal Regret by A. Blum and Y. Mansour, COLT 2005, as well as chapter 4 of the Algorthmic Game Theory book.
  5. 09/07: Nash Equilibria in General-Sum Games.
  6. 09/09: Approximate Nash Equilibria in General Sum Games.
    See: Playing Large Games using Simple Strategies by R. Lipton, E. Markakis, and A. Mehta, EC 2003.
  7. 09/14: Approximate Nash Equilibria in Stable Games.
    See: On Nash-Equilibria of Approximation-Stable Games. by P. Awasthi, M. F. Balcan, A. Blum, O. Sheffet, and Santosh Vempala, SAGT 2010.
  8. 09/16: Passive supervised learning in a distributional setting with feature information. The realizable case.
  9. 09/21: Passive supervised learning. Sample complexity results for the non-realizable case.
  10. 09/23: Sample complexity results for infinite hypothesis spaces.
  11. 09/28: Adaboost. See Rob Schapire's notes.
    See also: a great 2007 NIPS tutorial by R. Schapire.
  12. 09/30: More on Boosting. Boosting and the Minimax Theorem.
  13. 10/05: Potential games. Congestion Games. Price of Anarchy and Price of Stability.
    See chapters 17, 18, 19 of the Algorthmic Game Theory book.
  14. 10/07: Price of Anarchy in Unsplitable Linear Congestion Games.
    See also: The Price of Routing Unsplittable Flow by B. Awerbuch, Y. Azzar, and A. Epstein, STOC 2005.
    Leading dynamics to good behavior.
    See also: Improved Equilibria via Public Service Advertising by M.F. Balcan, A. Blum, and Y. Mansour, SODA 2009.
  15. 10/12: Weighted majority dynamics in congestion games.
    See Multiplicative updates outperform generic no-regret learning in congestion games by R. Kleinberg, G. Piliouras, and É. Tardos, STOC 2009.
  16. 10/14: Mechanism Design.
  17. 10/21: Mechanism Design (cont'd). See Introduction to Mechanism Design (for Computer Scientists) by N. Nisan.
  18. 10/26: Welfare Maximization in Combinatorial Auctions with Single Minded Bidders. See Combinatorial Auctions by L. Blumrosen and N. Nisan.
  19. 10/28: Mechanism Design via Machine Learning.
    See also: Reducing Mechanism Design to Algorithm Design via Machine Learning by M.F. Balcan, A. Blum, J. Hartline, and Y. Mansour, JCSS 2008.
  20. 11/02: Mechanism Design via Machine Learning (cont'd).
  21. 11/04: Item Pricing for Revenue Maximization in Combinatorial Auctions.
    See also: Approximation Algorithms and Online Mechanisms for Item Pricing. by M.F. Balcan and A.Blum. TOC 2007.
  22. 11/09: Online Learning for Online Pricing Problems.
    See also: Online Learning in Online Auctions by A.Blum, V. Kumar, A. Rudra, and F. Wu. SODA 2003; Near-Optimal Online Auctions by A.Blum and J. Hartline, SODA 2005.
    See also: The nonstochastic multiarmed bandit problem. by P. Auer, N. Cesa-Bianchi, Y. Freund, and R. Schapire. SICOMP 2002.
  23. 11/11: Matroid congestion games.
    See also: On the Impact of Combinatorial Structure on Congestion Games. by H. Ackermann, H. Röglin, and B. Vöcking, Journal of the ACM, 2008.
    See also: Lecture notes on Matroid Optimization. by M. Goemans.
  24. 11/16: Submodular functions and learning.
    See also: Learning Submodular Functions by M. F. Balcan and N. Harvey.
  25. 11/18: Students presentations.

Additional Readings & More Information

We will use a number of survery articles and tutorials. Students may find the following (completely optional) textbooks useful for exploring some of the topics that we cover in more depth: