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. 2016/17 Prof. Guido Proietti
PART I: Equilibria in networks
September 21,
2016: Introduction to non-cooperative networks. Basics of
game theory.
Slides: Introductory
elements.
September 22,
2016: Equilibria. Dominant
strategy equilibrium: the prisoners’ dilemma. Nash equilibrium (NE): the battle
of sexes. Games without equilibria: Head or Tail
game. The Nash’s Theorem.
September 28, 2016: Existence of NE in pure and mixed
strategies. Computational aspects of NE. The price of anarchy (PoA).
September 29, 2016: The selfish routing problem. Pigou’s example and Braess’
paradox. Existence of a Nash flow. PoA for the selfish
routing: linear and non-linear latencies.
October 5,
2016: Global connection games. Existence of a NE: the
potential method. The price of stability
(PoS). Lower and upper bounds for the PoA and the PoS.
Slides: Global connection games.
October 6,
2016: Network creation games. Stable graphs: cliques and
stars.
October 12,
2016: Network creation games: Upper bound to the PoA. Hardness of finding a best response.
Slides: Network creation games.
PART II: Algorithmic mechanism design (AMD)
Lecture notes: Algorithmic Mechanism Design (print from page 2 to
page 14).
October 13, 2016: The implementation problem. Second-price
auction. Mechanism design. Computational aspects of mechanisms. Strategy-proof
mechanisms. Utilitarian problems. VCG mechanisms.
October 19, 2016: VCG mechanisms. Clarke payments.
Algorithmic Mechanism Design for graph optimization problems.
Slides: Algorithmic mechanism design.
October 20, 2016: 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 26, 2016: 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.