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,
Straffin, Game theory and strategy
Evaluation: 10% classwork (a 10 minutes test at every lesson, only best 5 marks will be considered), 30% homework, 60% 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 10, 2014): introduction to the course,[pptx], [pdf]; an electrical example (Kelly&Yudovina, section 4.1).
Second lesson (December 19, 2014): crash course on Lagrange multipliers (A gentle introduction to the interpretation of Lagrange multipliers and a more formal one).
Fourth lesson (January 14, 2015): Fair capacity sharing (Kelly&Yudovina, section 7.2) and how it can be achieved in a distributed way (Kelly&Yudovina, section 7.3), what is TCP doing (Kelly&Yudovina, sections 7.4 and 7.5)
Fifth lesson (January 21, 2015): How to optimize when utilities are unknown: notions on games (Easley&Kleinberg, sections 6.1-6.4), 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)
Sixth lesson (January 28, 2015): VCG mechanism for capacity sharing (Shakkottai&Srikant, section 6.1), distributed incentive compatible capacity sharing (Kelly&Yudovina, sections 7.1 and 7.6), 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)
Seventh lesson (February 4, 2015): how to solve optimization problems through potential games, the case of marginal contribution protocol, price of anarchy for cost/welfare sharing games, some learning algorithms: fictitious play, simple experimentation dynamics, log-linear learning (Marden&Shamma sections 2.1-2.3, sections 3.1-3.2)
Second assignment, deadline February 7 2015, [pdf]
Exam
Each student has been assigned a research paper on January 23rd (list below).
The final exam task is to explain the paper putting it in the framework of what we have learned during our course. In particular each student will have to
write a short report (950-1050 words) summarizing the paper and its relation with what we have learned in the course,
prepare a 45 minute lesson (including 15 minutes for questions) for the class during which he/she explains the paper.
The exam will be hold on Wednesday February 11th at Inria in room Lagrange gris (last floor of Lagrange building) from 9.30 until 13.00 (Tuholokova, Sirenko, Scheller, Mahfoudi), and from 14.00 until 18.00 (Taddei, Taouab, Cantore, Livi, Ismaeil).
List of assigned papers:
CANTORE: Fairness and optimal stochastic control for heterogeneous networks, Michael Neely, Eytan Modiano, Chih-Ping Li, Proc. IEEE Infocom 2005
ISMAEIL: Downlink Resource Allocation and Pricing for Wireless Networks, P. Marbach and R. Berry, Proc. IEEE Infocom, June 2002
LIVI: Measurement-Based Self Organization of Interfering 802.11 Wireless Access Networks, Bruno Kauffmann, Francois Baccelli, Augustin Chaintreau, Vivek Mhatre, Konstantina Papagiannaki, Christophe Diot, Prof. IEEE Infocom 2007
MAHFOUDI: Optimal Distributed Gradient Methods for Network Resource Allocation Problems, A. Beck, A. Nedich, A. Ozdaglar, and M. Teboulle, IEEE Transactions on Control of Network Systems, Vol. 1, No. 1, Pages 64-74, 2014
SCHELLER: Adaptive Back-Pressure Congestion Control Based on Local Information, Leandros Tassiulas, IEEE Transactions on Automatic Control, Vol. 40, No. 2, February 1995
SIRENKO: Efficiency Loss in a Network Resource Allocation Game: The Case of Elastic Supply, Ramesh Johari, Shie Mannor, and John N. Tsitsiklis, IEEE Transactions on Automatic Control, Vol. 50, No. 11, November 2005
TADDEI: Internet congestion control, Steven H. Low, Fernando Paganini, and John Doyle, IEEE Control Systems Magazine, Vol. 22, pages 28-43, 2002
TAOUAB: Path Selection and Multipath Congestion Control, Peter Key, Laurent Massoulié, Don Towsley, Communications of the ACM, Vol. 54 No. 1, Pages 109-116, 2011
TUHOLUKOVA: How Bad is Selfish Routing?, T. Roughgarden and E. Tardos, Journal of the ACM, Vol. 49, No. 2, March 2002
