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. 2017/18 Prof. Guido Proietti
PART I: Equilibria in networks
September 20,
2017: Introduction to non-cooperative networks. Basics of
game theory.
Slides: Introductory
elements.
September 21,
2017: 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 27, 2017: Existence of NE in pure and mixed
strategies. Computational aspects of NE. The price of anarchy (PoA).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.
September 28,
2017: 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 4,
2017: Network creation games. Hardness of finding a best
response.
October 5,
2017: 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 11, 2017: The implementation problem. Second-price
auction. Mechanism design. Computational aspects of mechanisms. Strategy-proof mechanisms.
Utilitarian problems. VCG mechanisms.
October 12, 2017: VCG mechanisms. Clarke payments.
Algorithmic Mechanism Design for graph optimization problems.
Slides: Algorithmic mechanism design.
October 18, 2017: 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 19, 2017: 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 25, 2017: Non-utilitarian, one-parameter problems.
One-parameter mechanisms. Truthfulness of one-parameter mechanisms.
October 26, 2017: 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.