Ισορροπία Nash σε παίγνια μηδενικού αθροίσματος και σε παίγνια μη-μηδενικού αθροίσματος, θεωρήματα σταθερού σημείου, υπολογισμός ισορροπίας Nash, η κλάση PPAD, προσεγγιστικοί αλγόριθμοι για τον υπολογισμό ισορροπίας Nash. Παίγνια συμφόρησης και ιδιοτελής δρομολόγηση, αμιγείς ισορροπίες Nash και συναρτήσεις δυναμικού, η κλάση PLS, τίμημα της αναρχίας και τίμημα της σταθερότητας, άνω και κάτω φράγματα, βελτίωση του τιμήματος της αναρχίας (διόδια, πολιτικές Stackelberg, μηχανισμοί συντονισμού, το παράδοξο του Braess). Σχεδιασμός μηχανισμών, κοινωνική επιλογή, θεωρήματα Arrow και Gibbard-Satterthwaite, φιλαλήθεις μηχανισμοί. Μηχανισμοί χωρίς χρηματικά ανταλλάγματα, παίγνια χωροθέτησης, ο χαρακτηρισμός Moulin, ευσταθή ταιριάσματα, top-trading-cycles. Δρομολόγηση σε ιδιοτελείς μηχανές. Δημοπρασίες, θεώρημα Myerson, μηχανισμός VCG, συνδυαστικές δημοπρασίες, multiplicative weight updates και μηχανισμοί με posted prices, άμεσοι μηχανισμοί και το πρόβλημα επιλογής γραμματέως. Φιλαλήθεια και πολυωνυμική προσεγγισιμότητα για προβλήματα μεγιστοποίησης κοινωνικής ωφέλειας. Μη φιλαλήθεις μηχανισμοί, smooth μηχανι- σμοί και το τίμημα της αναρχίας, επικοινωνιακή πολυπλοκότητηα συνδυαστικών δημοπρασιών, κάτω φράγματα στο τίμημα της αναρχίας από υπολογιστικά κάτω φράγματα στην προσεγγισιμότητα.
Τύπος
Επιλογής
Περιγραφή μαθήματος