Università degli Studi dell'Aquila
Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica
Via Vetoio, Località Coppito, 67010 L'AQUILA
COURSE PROGRAM
Non-cooperative Networks
A.Y. 2019/20 Prof. Guido Proietti
PART I: Equilibria in
networks
September 25,
2019: Introduction to non-cooperative networks. Basics of
game theory. Equilibria. Dominant strategy equilibrium: the prisoners’ dilemma.
Slides: Introductory
elements.
September 25,
2019: Nash equilibrium (NE): the battle of sexes. Games
without equilibria: Head or Tail game. The Nash’s Theorem. Computational
aspects of Nash equilibria: mixed and pure strategies. Existence of NE in pure
and mixed strategies.
October 2, 2019: The selfish routing problem. The price of anarchy (PoA).
Pigou’s example and Braess’ paradox. Existence of a
Nash flow. PoA for the selfish routing: linear and
non-linear latencies.
October 3,
2019 (Dott. Monaco): Global
connection games. Existence of a NE: the potential method. Lower and upper
bounds for the PoA. The price of stability (PoS). Lower and upper
bounds for the PoS.
Slides: Global connection games.
October 9,
2019 (Dott. Monaco): Network
creation games. Hardness of finding a best response.
October 10,
2019 (Dott. Monaco): Network
creation games: Stable graphs: cliques and stars.
Upper bound to the PoS. Upper bound to the PoA.
Slides: Network creation games.
PART II: Algorithmic
mechanism design (AMD)
Lecture notes: Algorithmic Mechanism Design (print from page 2 to
page 14).
October 16, 2019: The implementation problem. Second-price
auction. Mechanism design. Computational aspects of mechanisms. Strategy-proof
mechanisms. Utilitarian problems. VCG mechanisms.
October 17, 2019: VCG mechanisms. Clarke payments. Algorithmic
Mechanism Design for graph optimization problems.
Slides: Algorithmic mechanism design.
October 23, 2019: VCG-mechanism for the private-edge
Shortest-Path problem. Trivial O(mn)
time implementation. Efficient O(m + n log n) time
implementation based on the Malik, Mittal, and Gupta algorithm.
Slides: VCG-mechanism for the private-edge SP problem.
October 24, 2019: VCG-mechanism for the private-edge
Minimum Spanning Tree problem. Trivial O(mn α(m,n)) time
implementation. Efficient O(m α(m,n)) time implementation based on the transmuter.
Slides: VCG-mechanism for the private-edge MST problem.
October 30, 2019 (Dott. Vinci): Non-utilitarian,
one-parameter problems. One-parameter mechanisms. Truthfulness
of one-parameter mechanisms.
October 31, 2019: One-parameter mechanism for the private-edge
Shortest-Path Tree problem. Trivial O(mn+n2
log n) time implementation. Efficient O(m + n log n)
time implementation based on the transmuter. Summary and question time.
Slides: VCG-mechanism for the private-edges SPT problem.
November
6, 2019, at 9.30, Room A1.2:
Mid-term exam.