Teoria Dei Giochi E Progetto Di Reti 2016/2017

1. Giochi in forma normale. equilibri di Nash. Pareto ottimalità. strategie debolmente e strettamente dominanti. Strategie conservative. Payoff e preordini totali. 2. Un' applicazione delle strategie dominanti: i meccanismi di asta. Aste di primo prezzo e aste secondo prezzo (o di Vickrey). Un'applicazione degli equilibri di Nash: la legislazione di incidente. 3. Giochi antagonistici e a somma zero. Punti di sella ed equilibri di Nash per giochi a somma zero. Giochi strettamente competitivi.    4. Estensione in strategia mista di un gioco antagonistico. L'esistenza di un equilibrio nella strategia mista per i giochi aantagonistico e valore del gioco. Il teorema di von Neumann. Bluff, underbid e poker di Kuhn. 5. i giochi cooperativi. Nucleo di un gioco. Il teorema di Bondareva-Shapley. I mercati con utilità trasferibile. Giochi semplici e valore di Shapley. 6. Giochi cooperativi con l'utilità non trasferibile. Il problema dell'house allocation. Il problema dello stable marriage. 7. Facility location: teoria ed algoritmi risolutivi esatti ed approssimati, deterministici e randomizzati. Algoritmo primale duale e meccanismi di cost sharing. Facility location games.  8. Albero ricoprente di peso minimo: teoria e algoritmi esatti. Alberi di Steiner: teoria ed algoritmi risolutivi esatti ed approssimati. Algoritmo primale duale e meccanismi di cost sharing. Giochi con alberi di Steiner.