8803 Connections between Learning, Game Theory, and Optimization,
Lectures: Tues/Thurs 4:35-5:55, Instr Center 117.
(KACB 2144 , 404-385-8640).
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.
Prerequisites: No specific background in learning theory or
game theory is required.
Evaluation and Responsibilities: Grading will be based on 4
homework assignments and a class presentation or project.
General structure of the course: Here is a short outline of
the "core" portion (some bullets correspond to multiple lectures):
- Online learning. Combining expert advice. Regret minimization
(no external regret and no internal regret).
- Zero sum games. Nash equilibria. Experts learning and the minimax
- Nash equilibria and approximate nash equilibria in general sum
- Learning in a distributional setting. Sample complexity results
for classes of finite VC dimension.
- Weak-learning vs. Strong-learning. Boosting with connections to
- Quality of equilibria (Price of anarchy/stability).
- Games with many players. Potential games.
- Dynamics in games and the price of learning.
- Mechanism design. Goals, examples.
- Combinatorial auctions. Maximizing social welfare and revenue
- Auctions for revenue maximization in unlimited supply (Digital
- Reductions from the mechanism design problem to the algorithm
problem based on machine learning techniques.
- Algorithmic pricing problems and online learning techniques.
- Submodularity with connections to game theory and machine
Textbooks: The recommended (not required) textbook is
Algorithmic Game Theory by Noam Nisan, Tim Rougharden,
Eva Tardos, and Vijay Vazirani.
You can find a link to free online edition here. Additionally, we
will use a number of papers, survery articles, and tutorials.