Παρουσίαση/Προβολή
(ΣΕΠ19) - Παναγιώτης Μερτικόπουλος
Περιγραφή Μαθήματος
Η θεωρία παιγνίων είναι η μελέτη μαθηματικών μοντέλων στρατηγικών αλληλεπιδράσεων μεταξύ ορθολογικών οντοτήτων που επιθυμούν να μεγιστοποιήσουν την ωφέλεια των αποφάσεών τους. Το περιβάλλον στο οποίο λαμβάνονται οι αποφάσεις αυτές μπορεί να είναι είτε "κλειστό" (δηλαδή οι παίκτες αλληλεπιδρούν μόνο με άλλους παίκτες) είτε "ανοικτό" (δηλαδή τα αποτελέσματα των αποφάσεων των παικτών μπορεί να επηρεάζονται και από εξωγενείς, μη ορθολογικούς παράγοντες, όπως η φύση, ο καιρός, κλπ).
Σε κάθε περίπτωση ο στόχος είναι ο ίδιος: να λαμβάνονται πιο τεκμηριωμένες αποφάσεις που οδηγούν σε καλύτερες πληρωμές με την πάροδο του χρόνου. Ως εκ τούτου, η θεωρία παιγνίων έχει βρει ένα ευρύ φάσμα εφαρμογών, από τη βιολογία και τα οικονομικά, μέχρι τη μηχανική μάθηση, την επιστήμη δεδομένων και, γενικότερα, την επιστήμη των υπολογιστών.
Το μάθημα αυτό έχει ως στόχο να προσφέρει μια ευρυγώνια εισαγωγή στη θεωρία παιγνίων και τη θεωρία πολυπρακτορικής μάθησης (multi-agent learning). Συγκεκριμένα, θα καλύψουμε μερικές βασικές έννοιες της θεωρίας παιγνίων (κυριαρχημένες στρατηγικές, σημεία στρατηγικής ισορροπίας, συσχετισμένες στρατηγικές,...), καθώς και τα βασικά μοντέλα και τεχνικές μονοπρακτορικής και πολυπρακτορικής μάθησης (την έννοια της μεταμέλειας / regret, multi-armed bandits, προβλήματα επαναληπτικής κυρτής βελτιστοποίησης, κλπ).
Ημερομηνία δημιουργίας
Δευτέρα 2 Οκτωβρίου 2023
-
Περιεχόμενο μαθήματος
Τί θα καλύψουμε;
- Βασικές έννοιες από τη θεωρία παιγνίων: κυριαρχημένες στρατηγικές, ισορροπία Nash, συσχετισμένες στρατηγικές, παίγνια μηδενικού αθροίσματος, παίγνια συμφόρησης,...
- Εξελικτικές δυναμικές / δυναμικές μάθησης στη θεωρία παιγνίων: δυναμική των αντιγραφέων (replicator dynamics), εξάλειψη των κυριαρχημένων στρατηγικών, σταθερότητα και στασιμότητα σημείων ισορροπίας,...
- Θεωρία μονοπρακτορικής μάθησης (single-agent learning): multi-armed bandits, η έννοια της μεταμέλειας (regret), αλγόριθμοι no-regret (Hedge, EXP3),...
- Online κυρτή βελτιστοποίηση: πολιτικές καθοδήγησης (leader-following policies), ελάττωση κλίσης, κατοπτρικοί αλγόριθμοι,...
Θα προσπαθήσουμε να καλύψουμε τα πιο θεμελιώδη αποτελέσματα σε καθένα από τα παραπάνω θέματα, παρέχοντας παράλληλα και μερικές πρακτικές επιδείξεις (όπου αυτό είναι δυνατό / σχετικό).
Βιβλιογραφία
- Matthew O. Jackson, A Brief Introduction to the Basics of Game Theory, lecture notes.
- Tor Lattimore and Csaba Szepesvári, Bandit algorithms, Cambridge University Press, Cambridge, UK, 2020.
- William H. Sandholm, Population games and evolutionary dynamics, MIT Press, Cambridge, MA, 2010.
- Shai Shalev-Shwartz, Online learning and online convex optimization, Foundations and Trends in Machine Learning 4 (2011), no. 2, 107–194
Διδάσκοντες
Στο χειμερινό εξάμηνο 2023-2024 το μάθημα διδάσκεται απο τον Π. Μερτικόπουλο, κάθε Δευτέρα, 09:00-13:00, στην αίθουσα Α12. [ΠΡΟΣΟΧΗ: Η αίθουσα είναι πιθανό να αλλάξει].
Ώρες γραφείου: Δευτέρα, μετά το μάθημα (ή κατόπιν συνεννοήσεως).