9/12/08:
Implementazione di meccanismi (Mechanism Design). Informazione pubblica e privata. Agenti versus sistema. Meccanismi veritieri. Problemi utilitari.
Implementazione efficiente di meccanismi (Algorithmic Mechanism Design). Il problema dell'asta con offerta in busta chiusa (asta di Vickrey).
Dispense: Algorithmic Mechanism Design
(stampare da pagina 2 a pagina 14).
Slides: Mechanism design
11/12/08:
Definizione del modello per problemi di ottimizzazione su grafi. Implementazione di un meccanismo VCG per la determinazione del cammino minimo tra due nodi con complessità temporale O(m + n logn). L'arco piu' vitale di un cammino minimo tra due nodi: Descrizione del problema; soluzioni banali. Algoritmo di Malik e studio della complessità.
Slides: Meccanismo VCG per il cammino minimo tra due nodi.
8/1/09:
Implementazione di un meccanismo VCG per il problema della determinazione del minimo albero ricoprente in tempo O(m \alpha(m,n)). Il problema dell'analisi di sensitivita' di un minimo albero ricoprente: descrizione del problema e soluzione efficiente che utilizza il Transmuter. Definizione della funzione di Ackermann e la sua inversa. Proprieta' della funzione.
Slides: Meccanismo VCG per minimo albero ricoprente.
15/1/09:
Problemi di mechanism design non utilitari. Meccanismi one-parameter e relative proprieta'. Il problema dell'albero dei cammini minimi a singola sorgente nel protocollo unicast.
Slides: Meccanismi One-Parameter.
20/1/09:
Il problema dell'albero dei cammini minimi a sorgente singola in un grafo non cooperativo: meccanismo one-parameter e relativa complessita' computazionale. Approfondimento: Esempio di determinazione dei pagamenti nel meccanismo VCG per il problema dell'albero dei cammini minimi.