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 4 best marks will be considered), 15% homework during week 5, 15% scribe notes (template to be used, an example), 55% final exam. 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 9, 2015): introduction to the course [pptx], an electrical example (Kelly&Yudovina, section 4.1). Scribe notes [pdf], [tex].
Fourth lesson (January 13, 2016): Fair capacity sharing and how it can be achieved in a distributed way (Kelly&Yudovina, sections 7.1 and 7.2). Scribe notes [pdf], [tex].
Fifth lesson (January 20, 2016): 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), how to optimize in presence of selfish rational agents: notions on games (Easley&Kleinberg, sections 6.1-6.4). Slides on game theory [pdf].
Sixth lesson (January 27, 2016): Nash Equilibria, auctions (Easley&Kleinberg, sections 9.1-9.5, 9.7.A and 9.7.B), Google ads and VCG mechanism (Easley&Kleinberg, sections 15.1-15.8). Slides [pdf]. Scribe notes [pdf], [tex].
Seventh lesson (February 2, 2016): Google ads, VCG mechanism for capacity sharing (Shakkottai&Srikant, section 6.1), 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). Slides [pdf]. Scribe notes [pdf], [tex].
Assignments
First (and unique) assignment, deadline January 27 2016 at the begin of the class, [pdf]