8803 Connections between Learning, Game Theory, and Optimization,
Fall 2010
Course Information
Lectures: Tues/Thurs 4:35-5:55, Instr Center 117.
Instructor: Maria
Florina
Balcan
(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).
Bandit algorithms.
- Zero sum games. Nash equilibria. Experts learning and the minimax
theorem.
- Nash equilibria and approximate nash equilibria in general sum
bimatrix games.
- Learning in a distributional setting. Sample complexity results
for classes of finite VC dimension.
- Weak-learning vs. Strong-learning. Boosting with connections to
game theory.
- 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
maximization.
- Auctions for revenue maximization in unlimited supply (Digital
goods).
- Reductions from the mechanism design problem to the algorithm
design
problem based on machine learning techniques.
- Algorithmic pricing problems and online learning techniques.
- Submodularity with connections to game theory and machine
learning.
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.