Università degli Studi dell'Aquila
Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica
Via Vetoio, Località Coppito, 67010 L'AQUILA
A.Y. 2020/21 Prof. Guido Proietti
PART I: Equilibria in networks
October 7, 2020: Introduction to non-cooperative networks. Basics of game theory. Equilibria. Dominant strategy equilibrium: the prisoners’ dilemma.
October 8, 2020: 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 14, 2020: 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 15, 2020 (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.
October 21, 2020 (Dott. Monaco): Network creation games. Hardness of finding a best response.
October 22, 2020 (Dott. Monaco): Network creation games: Stable graphs: cliques and stars. Upper bound to the PoS. Upper bound to the PoA.
PART II: Algorithmic mechanism design (AMD)
October 28, 2020: The implementation problem. Second-price auction. Mechanism design. Computational aspects of mechanisms. Strategy-proof mechanisms. Utilitarian problems. VCG mechanisms.
October 29, 2020: VCG mechanisms. Clarke payments. Algorithmic Mechanism Design for graph optimization problems.
November 4, 2020: 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.
November 5, 2020: 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.
November 11, 2020 (Dott. Leucci): Non-utilitarian, one-parameter problems. One-parameter mechanisms. Truthfulness of one-parameter mechanisms.
November 12, 2020: 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.
November 19, 2020, at 11.50, Teams channel 3alrsbo: Mid-term exam.