The purpose of this course is to introduce students to techniques for distributed optimization in networks, also in the case when agents have different and conflicting utilities.
Teacher: Giovanni Neglia
Main references:
Frank Kelly and Elena Yudovina, Stochastic networks, freely available here,
Srinivas Shakkottai and R. Srikant, Network Optimization and Control, a preprint is available here,
David Easley and Jon Kleinberg, a preprint is available here,
J. R. Marden and J.S. Shamma, Game Theory and Distributed Control, Handbook of Game Theory Vol. 4, edited by Peyton Young and Shmuel Zamir, Elsevier Science, 2013, a preprint is available here,
Evaluation: 15% classwork (a 10 minutes test at every lesson, only 5 best marks will be considered), 15% homework during week 4, 15% scribe notes (template to be used, an example), 55% final exam. The scribe notes from the previous year will be made available on github. Students have to create a new branch and update it. Marks are here.
Lessons
You can freely use the slides below for your presentations, but I would like to be informed and please acknowledge the source in your presentation. Any comment is welcome.
First lesson (December 7, 2016): introduction to the course [pptx], an electrical example (Kelly&Yudovina, section 4.1). Scribe notes [pdf], [tex]. Crash course on Lagrange multipliers (A gentle introduction to the interpretation of Lagrange multipliers and a more formal one).
Second lesson (December 14, 2016): crash course on convex optimization. Road traffic models (Kelly&Yudovina, section 4.2).
Third lesson (January 4, 2017): Network Utility Maximization (NUM), dynamics of the distributed approach to capacity sharing (Kelly&Yudovina, section 7.3), what is TCP doing (Kelly&Yudovina, sections 7.4 and 7.5)
Fourth lesson (January 11, 2017): convergence of rate control dynamics for NUM, simulated annealing
Fifth lesson (January 18, 2017): decentralized optimization with simulated annealing, how to optimize in presence of selfish rational agents: notions on games (Easley&Kleinberg, sections 6.1-6.4) and auctions (Easley&Kleinberg, sections 9.1-9.5, 9.7.A and 9.7.B). Slides on game theory introduction,
auctions part 1.
Sixth lesson (January 25, 2017): First price auction, Google ads and VCG mechanism (Easley&Kleinberg, sections 15.1-15.8). Slides [pdf].
Seventh lesson (February 1, 2017): Generalities on the use of game theory for engineering (Marden&Shamma, sec. 1), best response dynamics (Easley&Kleinberg, section 8.3 A), price of anarchy and price of stability, potential games (Marden&Shamma sec 2.1).
Assignments
First (and unique) assignment, deadline January 18 2017 before the beginning of the lecture, [pdf]