AGT - Lecture Notes Summary

Lecture Info

La nascita della Algorithmic Game Theory

Game Theory Basics

• Esempi

  • The Prisoner's Dilemma

  • A Network Game

Normal Form of a Game

• Dominant Strategy Equilibrium

• Nash Equilibrium

Equilibri di Nash

• Esistenza

• Qualità

  • Price of Anarchy (PoA)

  • Price of Stability (PoS)

  • Osservazioni generali

Note Finali

• Selfish Routing: Pigou's game

• The Braess's Paradox

• Schema del corso

• Esercizi

Lecture Info

Network Formation Games

Global Connection Game

• Esempi

• Obiettivi Analisi

• PoA

  • Lower Bound

  • Upper Bound

• PoS

  • Lower Bound

  • Upper Bound

• Best Response

• Bound on NE is NP-Hard

  • 3D Matching Problem

  • Riduzione

Potential Function Method

• Esistenza di un NE

• Convergenza della Better Response Dynamics

• Upper Bound per PoS

Lecture Info

Local Connection Game

• Esempio

• Obiettivi Analisi

Struttura delle Reti Ottime

• Ottimili Sociali Stabili

Upper Bound on PoS

Upper Bound on PoA

• Diametro Rete Stabile

• Reti Stabili e Non-Cut Edges

• Costo Sociale di una Rete Stabile

• Risultato Finale

La Best Reponse è NP-Hard

Lecture Info

Single Item Auction

• No Payment

• Pay Your Bid

• Vickery's Second Price Auction

Mechanism Design

• Truthful Mechanisms

• Examples

• Minimization Problems

  • Vicker Auction (2nd version)

Utilitarian Problems

• VCG Mechanism

  • How to Define \(h_i(r_{-i})\)

Algorithmic Contributions

Lecture Info

Shortest Path (with Selfish-Edges)

• Designing a Mechanism

• Complexity Analysis

• Exercise

One-Parameter (OP) Problems

• \(M\) Truthful \(\Rightarrow\) \(g(\cdot)\) Monotone

• OP (Truthful) Mechanism

  • How to Define \(h_i(r_{-i})\)

Shortest-Paths Tree (with Selfish-Edges)

• Designing a Mechanism

• Complexity Analysis

Binary Demand Problems

Esercizi

Lecture Info

Combinatorial Auction

• VCG Mechanism

  • Impossibility Result

• OP Mechanism

  • Greedy Algorithm

  • Computing Payments

  • Approximation Result

Lecture Info

MST Problem

• Kruskal's Algorithm

  • Example

Stacklberg MST Game

• Example

• Assumptions

NP-Hardness Result

• Minimum Set Cover

• Reduction

  • Part 1: \((\Rightarrow)\)

  • Part 2: \((\Leftarrow)\)

Approximation Result

• Single Price Algorithm

• Analysis

• Can We Do Better?

Exercises

Lecture Info

Congestion Game

Complexity Theory

• NP vs FNP

• FNT-Completeness

  • CG-NE is (likely) not FNP-Complete

• TFNP

  • Syntactic vs Semantic Classes

• PLS

  • Maximum Cut Problem

  • Reductions in PLS

• PPAD

CG-NE is PLS-Complete

• CG-NE \(\in\) PLS

• Max-Cut \(\preceq\) CG-NE