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. 2023/24 Prof. Guido Proietti
PART I: Equilibria in
networks
September 27,
2023: Introduction to non-cooperative networks. Basics of
game theory. Equilibria. Dominant strategy equilibrium: the prisoners dilemma.
September 28,
2023: Nash equilibrium (NE): the battle of the 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 4, 2023: 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 5,
2023: 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 11,
2023: Network creation games Existence of cycles of
better-response strategies. Hardness of finding a best response. Optimal
graphs: cliques and stars.
October 12,
2023: 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 18, 2023: The implementation problem. Second-price
auction. Mechanism design. Computational aspects of mechanisms. Strategy-proof
mechanisms. Utilitarian problems. VCG mechanisms.
October 19, 2023: VCG mechanisms. Clarke payments.
Algorithmic Mechanism Design for graph optimization problems.
Slides: Algorithmic mechanism design
October 25, 2023: 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, 2023: 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
November 2, 2023 (prof. Stefano Leucci): Non-utilitarian, one-parameter problems. One-parameter mechanisms.
Truthfulness of one-parameter mechanisms.
Slides: One-parameter mechanisms.
November 8, 2023:
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-edge SPT problem.
Final-term exam: November 9
2023, at 16.30, in Room C1.16.