Gli ultimi decenni hanno visto un enorme sviluppo delle reti ed una crescente convergenza tra reti sociali, intese come insieme di contatti e relazioni tra utenti in possesso di informazioni, e reti tecnologiche, intese come l'infrastruttura che abilita la comunicazione tra utenti indipendentemente dalla loro posizione fisica e dalla tecnologia utilizzata per comunicare. Gli ultimi anni sono stati segnati dall'amergenza di sistemi come il Web e e le Reti Sociali che sono diventati strumenti fondamentali di lavoro e svago ma anche piattaforma di interazione sociale e comunicazione.

Queste reti sono caratterizzate da una sostanziale mancanza di coordinamento centrale: non c'è un autorità centrale che controlla la rete, ne determina la struttura e definisce i comportamenti dei singoli utenti; invece ci sono tantissimi agenti, sia singoli utenti che grosse organizzazioni, che utilizzano la rete in maniera autonoma secondo i propri fini e le proprie esigenze che a volte possono anche essere molto differenti tra loro. E' l'interazione tra i comportamenti degli agenti che definisce la struttura della rete e ne influenza le prestazioni (si pensi per esempio al modo in cui un utente inserisce link all'interno delle proprie pagine web o decide di inserire link tra i propri segnalibri, oppure ai legami di vicinanza che un utente di una rete sociale stabilisce con altri utenti). Poichè queste reti sono diventate parte integrante della nostra vita è fondamentale riuscire a comprenderne la struttura in modo da poter progettare algoritmi per svolgere attivtà fondamentali (ad esempio al ricerca) che siano pensati per essere efficienti su questo tipo di reti.

Il corso cercherà di dare un quadro della recente ricerca sullo studio e l'analisi delle moderne reti e la definizione di modelli che le possano descrivere efficacemente. Per fare ciò dobbiamo necessariamente individuare dei modelli che permettano di descrivere il comportamento egoista e razionale dei singoli agenti le cui interazioni raggiungono un punto di equilibrio che descrive lo stato della rete. Per questo motivo una buona parte del corso sarà dedicata alla Teoria dei Giochi, pur se vista da un punto di vista propriamente algoritmico, ed in particolare al meccanismo delle aste che sta trovando sempre maggiore applicazione all'interno di applicazioni sviluppate per le moderne reti. Altri possibile temi del corso saranno modelli per descrivere le reti basati su grafi casuali, algoritmi per la ricerca, tecniche per descrivere la diffusione dell'informazione sulle reti.

Programma orientativo

Diario delle lezioni

• 24 Settembre 2010: Presentazione del corso.
• 28 Settembre 2010: Introduzione alla Teoria dei Giochi. Teoria della scelta razionale e del ragionamento strategico. Definizione di giochi in forma strategica e loro soluzioni. Esempi di giochi: Dilemma del Prigioniero. (Rif. OR cap. 1, par. 2.1, NRTV par. 1.1-1.2).
• 1 Ottobre 2010: Concetti di Soluzione. Soluzioni con strategie dominanti. Asta di Vickrey. (Rif. OR par. 2.2).
• 4-17 Ottobre 2010: Sospensione dei corsi per protestare contro il DDL di riforma del sistema universitario proposto dal ministro Gelmini.
• 19 Ottobre 2010: Concetti di soluzione: soluzioni in Equilibrio Nash. Esempi di giochi con un solo Equilibrio Nash, con più di una soluzione in Equilibrio Nash e senza soluzioni in Equilibrio Nash. Soluzioni in Equilibrio di Nash misto (Rif. OR par. 2.2-2.5, NRTV par. 1.3-1.4).
• 22 Ottobre 2010: Soluzioni in Equilibrio Nash con strategie miste. Teorema di Nash. Caratterizzazione delle proprietà di una soluzione in Equilibrio Nash. Definizione di best response e di supporto di una strategia. Algoritmo di programmazione lineare per il calcolo di soluzioni in Equilibrio Nash con strategie miste per giochi a due giocatori e a somma zero (Rif. OR par. 3.1, NRTV par. 1.3-1-4).
• 26 Ottobre 2010: Equilibri Correlati. Giochi con informazione incompleta: Bayesian Games e concetto di equilibrio in Bayesian Games. (Rif. OR par. 2.6 e 3.3).
• 29 Ottobre 2010: Calcolo di Equilibri Nash con strategie miste in giochi a due giocatori. Best response property e algoritmo di enumerazione dei supporti. Caratterizzazione del politopo delle best-response. (Rif. NRTV par. 3.1-3.3)
• 2 Novembre 2010: Algoritmo di Lemke-Hawson. Complessità computazionale del calcolo di un Equilibrio Nash. La classe PPAD. (Rif. NRTV par. 3.4-3.5, 2.1-2.4)
• 3 Novembre 2010: Dimostrazione di appartenenza di NASH a PPAD, sketch della prova di PPAD-completeness di NASH, immplicazioni di questo risultato per calcolo di equilibri Nash esatti ed approssimati (Rif. DGP, NRTV par. 2.5-2.6).
• 11 Novembre 2010: Regret Minimization: definizione del problema, esempi. External Regret, analisi di un algoritmo Greedy, lower bound per algoritmi deterministici. Analisi di un algoritmo Randomized Greedy (NRTV: Cap. 4.1, 4.2, 4.3.1)
• 12 Novembre 2010: Analisi dell'algoritmo Randomized Weighted Majority. Teoria dei Giochi e Regret Minimization. Equilibri correlati e Swap Regret Minimization (NRTV: Cap. 4.3.2, 4.4.1, 4.4.3)
• 16 Novembre 2010: Valutazione dell'efficienza degli equilibri; Price of Anarchy e Price of Stability; Selfish routing non atomico: definizione del problema, caratterizzazione di flussi ottimi e in equilibrio (Rif. NRTV par. 17.1-17.2, 18.1, -18.2.1).
• 19 Novembre 2010: (lezione tenuta dal Dott. Paolo Penna) Caratterizzazione dei giochi in cui dinamiche concorrenti convergono a Equilibri di Nash puri. Giochi NBR-solvable.
• 23 Novembre 2010: (lezione tenuta dal Dott. Paolo Penna) Caratterizzazione dei giochi NBR-solvable che sono anche compatibili agli incentivi.
• 24 Novembre 2010: (lezione tenuta dal Dott. Paolo Penna) Protocollo BGP e Teoria dei Giochi. Ruota della disputa e non-esistenza di soluzioni stabili. Analisi del problema nel modello reale di Internet di Gao-Rexford e dimostrazione delle convergenza e compatibilità agli incentivi di BGP.
• 30 Novembre 2010: Selfish routing non atomico: esistenza e unicità di flussi in equilibrio. (NRTV: Cap. 18.3.1)
• 1 Dicembre 2010: Calcolo del price of anarchy per il selfish roting non atomico. Definizione del problema atomico e esistenza di soluzioni in equilibrio. (NRTV: Cap. 18.4.1, 18.5, 18.2.2)
• 3 Dicembre 2010: Calcolo del Price of Anarchy per istanze con funzioni di latenza affini. Potential games e congestion games. Tecnica della funzione potenziale per calcolare equilibri Nash e limitare il Price of Stability in potential games. Problemi di network formation. Global Connection Game. (NRTV: Cap. 18.3.2, 18.4.2, 19.1, 19.3)
• 7 Dicembre 2010: Algorithmic Mechanism Design. Funzioni di scelta sociale. Teorema di impossibilità di Arrow. (RN, NRTV: Cap. 9.1, 9.2, 9.3)
• 10 Dicembre 2010: Teorema di Arrow (cont.). Meccanismi con pagamenti. Meccanismi compatibili agli incentivi. Meccanismi VCG. (NRTV: Cap. 9.3)
• 14 Dicembre 2010: Applicazioni dei meccanismi VCG. AstMeccanismo per lo Shortest-Path (cenni sul Minimum Spanning Tree). Limiti dei meccanismi VCG. Meccanismi generici e implementabilità di funzioni di scelta sociale con strategie dominanti o ex-post Nash. Revelation Principle. (Rif. NRTV, cap. 9.4)
• 15 Dicembre 2010: Caratterizzazione di funzioni implementabili: weak monotoniticity e cycle monotonicity. Teorema di Roberts. Implementazione di funzioni su domini single-parameter. (Rif. NRTV cap. 9.5, V)

• Lezione 1: Introduzione alla Teoria dei Giochi.
• Lezione 2: Concetti di soluzione.
• Lezione 3: Soluzioni in Equilibrio Nash.
• Esercizi: Esercizi su calcolo di soluzioni in equilibrio in giochi strategici.
• Lezione 4: Equilibri Correlati e Bayesian Games (nuova).
• Lezione 5: Calcolo di Equilibri Nash in giochi a due giocatori (nuova).
• Lezione 6: Complessità del problema del calcolo di Equiilbri Nash (in preparazione).
• Lezione 7: Regret Minimization.
• Lezione 8: Inefficienza degli Equilibri.
• Lezione 9: Giochi NBR-solvable.
• Lezione 10: Selfish Routing non Atomico.
• Lezione 11: Selfish Routing Atomico e Potential Games.
• Lezione 12: Algorithmic Mechanism Design.
• Lezione 13: Meccanismi con pagamenti (applicazioni e limiti).
• Lezione 14: Meccanismi generici e Revelation Principle.
• Lezione 15: Caratterizzazione di funzioni implementabili in modo compatibile agli incentivi.

Testi di riferimento

[NRTV]
		N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani
		Algorithmic Game Theory
		Cambridge University Press, 2007
		Una versione elettronica di questo libro è liberamente scaricabile qui
[OR]
		M. Osborne, A. Rubinstein.
		A Course in Game Theory
		MIT Press, 1994

Altri riferimenti

[R]
	T. Roughgarden
	An Algorithmic Game Theory Primer
	http://theory.stanford.edu/~tim/papers/tcs08.pdf
[DGP]
	C. Daskalakis, P. Goldberg, C. Papadimitriou
	The Complexity of Computing a Nash Equilibrium
	http://www.eecs.berkeley.edu/~christos/papers/cacmDGP-2.pdf
[R2]
	T. Roughgarden
	Computing Equilibria: A Computational Complexity Perspective
	http://theory.stanford.edu/~tim/papers/et.pdf
[RN]
	P. Reny
	Arrow’s Theorem and the Gibbard-Satterthwaite Theorem: A Unified Approach
	http://home.uchicago.edu/~preny/papers/arrow-gibbard-satterthwaite.pdf