Algorithmic Game Theory

Type
Elective
Course Description

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

Name Year Semester Taught by
Algorithmic Game Theory 2021-2022 Spring Dimitris Fotakis, Evangelos Markakis, Thanasis Lianeas
Algorithmic Game Theory 2020-2021 Spring Dimitris Fotakis, Evangelos Markakis, Thanasis Lianeas
Algorithmic Game Theory 2019-2020 Spring Dimitris Fotakis, Evangelos Markakis, Thanasis Lianeas