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

- Homework 1 [ps, pdf]. Solutions.
- Homework 2 [ps, pdf].
- Homework 2.5 [ps, pdf].
- Homework 3 [ps, pdf].

- 08/24: Introduction.
- 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. - 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. - 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. - 09/07: Nash Equilibria in General-Sum Games.
- 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. - 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. - 09/16: Passive supervised learning in a distributional setting with feature information. The realizable case.
- 09/21: Passive supervised learning. Sample complexity results for the non-realizable case.
- 09/23: Sample complexity results for infinite hypothesis spaces.
- 09/28: Adaboost.
See Rob
Schapire's
notes.

See also: a great 2007 NIPS tutorial by R. Schapire. - 09/30: More on Boosting. Boosting and the Minimax Theorem.
- 10/05:
Potential games. Congestion Games. Price of Anarchy and
Price of Stability.

See chapters 17, 18, 19 of the Algorthmic Game Theory book. - 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. - 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. - 10/14: Mechanism Design.
- 10/21: Mechanism Design (cont'd). See Introduction to Mechanism Design (for Computer Scientists) by N. Nisan.
- 10/26: Welfare Maximization in Combinatorial Auctions with Single Minded Bidders. See Combinatorial Auctions by L. Blumrosen and N. Nisan.
- 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. - 11/02: Mechanism Design via Machine Learning (cont'd).
- 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. - 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.

- 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. - 11/16: Submodular
functions
and
learning.

See also: Learning Submodular Functions by M. F. Balcan and N. Harvey. - 11/18: Students presentations.

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:

*Algorithmic Game Theory*by Noam Nisan, Tim Rougharden, Eva Tardos, and Vijay Vazirani. You can find a link to free online edition here.*Prediction, learning, and games*by Nicolò Cesa-Bianchi and Gábor Lugosi.