ΕΘΝΙΚΟ ΜΕΤΣΟΒΙΟ ΠΟΛΥΤΕΧΝΕΙΟ | ΜΕΤΑΠΤΥΧΙΑΚΟ ΠΡΟΓΡΑΜΜΑ ΣΠΟΥΔΩΝ | ΕΠΙΣΤΗΜΗ ΔΕΔΟΜΕΝΩΝ ΚΑΙ ΜΗΧΑΝΙΚΗ ΜΑΘΗΣΗ

Αλγοριθμική Θεωρία Παιγνίων

Περιγραφή

Παίγνια δύο παικτών μηδενικού αθροίσματος, θεώρημα minimax, παίγνια δύο παικτών, ισορροπία Nash, γενίκευση για παίγνια πολλών παικτών. Υπολογιστική πολυπλοκότητα ισορροπίας Nash, η κλάση PPAD. Correlated ισορροπία, άμεση κυρτή βελτιστοποίηση και ελαχιστοποίηση regret, swap-regret και correlated ισορροπία. Παίγνια συμφόρησης και παίγνια ιδιοτελούς δρομολόγησης, αμιγείς ισορροπίες Nash, συναρτήσεις δυναμικού και σύγκλιση στην ισορροπία Nash, η κλάση PLS, τίμημα της αναρχίας και τίμημα της σταθερότητας, μηχανισμοί για τη μείωση του τιμήματος της αναρχίας. Κοινωνική επιλογή και σχεδιασμός μηχανισμών, κυρίαρχες στρατηγικές και φιλαλήθεια, αποτελέσματα αδυναμίας των Arrow και Gibbard-Satterthwaite, κανόνες ψηφοφορίας, single-peaked προτιμήσεις, generalized median μηχανισμοί, παίγνια facility location. Ευσταθή ταιριάσματα, top-trading cycles. Βελτιστοποίηση ωφέλειας και κέρδους, μονοπαραμετρικοί παίκτες, χαρακτηρισμός Meyerson, βέλτιστη δημοπρασία Myerson, πολυπαραμετρικοί παίκτες, VCG μηχανισμός, συνδυαστικές δημοπρασίες, υπολογιστικά αποδοτικοί μηχανισμοί, συναρτήσεις ωφέλειας, ερωτήματα απαίτησης και τιμής, υπολογιστικά αποδοτικοί μηχανισμοί για submodular και XOS συναρτήσεις ωφέλειας. Δημοπρασίες για την αγορά υπηρεσιών και μηχανισμοί με περιορισμούς προϋπολογισμού. Μηχανισμοί που με στόχο τη βελτιστοποίηση του κέρδους. Απλές μη-φιλαλήθεις δημοπρασίες και ανάλυση του τιμήματος της αναρχίας μέσω smoothness. Generalized Second Price δημοπρασίες και ηλεκτρονική διαφήμιση. Δημοπρασίες φάσματος.

Διδάσκοντες
Εξάμηνο
Εαρινό Εξάμηνο
Κατηγορία
Επιλογής
Ώρες Θεωρίας
3 ώρες
Ώρες Εργαστηρίου
0 ώρες
Credits
5