Θεωρία Παιγνίων (ΣΕΠ19)
Παναγιώτης Μερτικόπουλος
Η θεωρία παιγνίων είναι η μελέτη μαθηματικών μοντέλων στρατηγικών αλληλεπιδράσεων μεταξύ ορθολογικών οντοτήτων που επιθυμούν να μεγιστοποιήσουν την ωφέλεια των αποφάσεών τους. Το περιβάλλον στο οποίο λαμβάνονται οι αποφάσεις αυτές μπορεί να είναι είτε "κλειστό" (δηλαδή οι παίκτες αλληλεπιδρούν μόνο με άλλους παίκτες) είτε "ανοικτό" (δηλαδή τα αποτελέσματα των αποφάσεων των παικτών μπορεί να επηρεάζονται και από εξωγενείς, μη ορθολογικούς παράγοντες, όπως η φύση, ο καιρός, κλπ).
Σε κάθε περίπτωση ο στόχος είναι ο ίδιος: να λαμβάνονται πιο τεκμηριωμένες αποφάσεις που οδηγούν σε καλύτερες πληρωμές με την πάροδο του χρόνου. Ως εκ τούτου, η θεωρία παιγνίων έχει βρει ένα ευρύ φάσμα εφαρμογών, από τη βιολογία και τα οικονομικά, μέχρι τη μηχανική μάθηση, την επιστήμη δεδομένων και, γενικότερα, την επιστήμη των υπολογιστών.
Το μάθημα αυτό έχει ως στόχο να προσφέρει μια ευρυγώνια εισαγωγή στη θεωρία παιγνίων και τη θεωρία πολυπρακτορικής μάθησης (multi-agent learning). Συγκεκριμένα, θα καλύψουμε μερικές βασικές έννοιες της θεωρίας παιγνίων (κυριαρχημένες στρατηγικές, σημεία στρατηγικής ισορροπίας, συσχετισμένες στρατηγικές,...), καθώς και τα βασικά μοντέλα και τεχνικές μονοπρακτορικής και πολυπρακτορικής μάθησης (την έννοια της μεταμέλειας / regret, multi-armed bandits, προβλήματα επαναληπτικής κυρτής βελτιστοποίησης, κλπ).
ΛιγότεραΗ θεωρία παιγνίων είναι η μελέτη μαθηματικών μοντέλων στρατηγικών αλληλεπιδράσεων μεταξύ ορθολογικών οντοτήτων που επιθυμούν να μεγιστοποιήσουν την ωφέλεια των αποφάσεών τους. Το περιβάλλον στο οποίο λαμβάνονται οι αποφάσεις αυτές μπορεί να είναι είτε "κλειστό" (δηλαδή οι παίκτες αλληλεπιδρούν μόνο με άλλους παίκτες) είτε "ανοικτό" (δηλαδή τα αποτελέσματα των αποφάσεων των παικτών μπορεί να επηρεάζονται και από εξωγενείς, μη ορθολογικούς παράγοντες, όπως η φύση, ο καιρός, κλπ).
Σε κάθε περίπτωση ο στόχος είναι ο ίδιος: να λαμβάνονται πιο τεκμηριωμένες αποφάσεις που οδηγούν σε καλύτερες πληρωμές με την πάροδο του χρόνου. Ως εκ τούτου, η θεωρία παιγνίων έχει βρει ένα ευρύ φάσμα εφαρμογών, από τη βιολογία και τα οικονομικά, μέχρι τη μηχανική μάθηση, την επιστήμη δεδομένων και, γενικότερα, την επιστήμη των υπολογιστών.
Το μάθημα αυτό έχει ως στόχο να προσφέρει μια ευρυγώνια εισαγωγή στη θεωρία παιγνίων και τη θεωρία πολυπρακτορικής μάθησης (multi-agent learning). Συγκεκριμένα, θα καλύψουμε
Η θεωρία παιγνίων είναι η μελέτη μαθηματικών μοντέλων στρατηγικών αλληλεπιδράσεων μεταξύ ορθολογικών οντοτήτων που επιθυμούν να μεγιστοποιήσουν την ωφέλεια των αποφάσεών τους. Το περιβάλλον στο οποίο λαμβάνονται οι αποφάσεις αυτές μπορεί να είναι είτε "κλειστό" (δηλαδή οι παίκτες αλληλεπιδρούν μόνο με άλλους παίκτες) είτε "ανοικτό" (δηλαδή τα αποτελέσματα των αποφάσεων των παικτών μπορεί να επηρεάζονται και από εξωγενείς, μη ορθολογικούς παράγοντες, όπως η φύση, ο καιρός, κλπ).
Σε κάθε περίπτωση ο στόχος είναι ο ίδιος: να λαμβάνονται πιο τεκμηριωμένες αποφάσεις που οδηγούν σε καλύτερες πληρωμές με την πάροδο του χρόνου. Ως εκ τούτου, η θεωρία παιγνίων έχει βρει ένα ευρύ φάσμα εφαρμογών, από τη βιολογία και τα οικονομικά, μέχρι τη μηχανική μάθηση, την επιστήμη δεδομένων και, γενικότερα, την επιστήμη των υπολογιστών.
Το μάθημα αυτό έχει ως στόχο να προσφέρει μια ευρυγώνια εισαγωγή στη θεωρία παιγνίων και τη θεωρία πολυπρακτορικής μάθησης (multi-agent learning). Συγκεκριμένα, θα καλύψουμε
Περίγραμμα
Περιεχόμενο μαθήματος
Τί θα καλύψουμε;
- Βασικές έννοιες από τη θεωρία παιγνίων: κυριαρχημένες στρατηγικές, ισορροπία 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. [ΠΡΟΣΟΧΗ: Η αίθουσα είναι πιθανό να αλλάξει].
Ώρες γραφείου: Δευτέρα, μετά το μάθημα (ή κατόπιν συνεννοήσεως).
Τί θα καλύψουμε;
- Βασικές έννοιες από τη θεωρία παιγνίων: κυριαρχημένες στρατηγικές, ισορροπία 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. [ΠΡΟΣΟΧΗ: Η αίθουσα είναι πιθανό να αλλάξει].
Ώρες γραφείου: Δευτέρα, μετά το μάθημα (ή κατόπιν συνεννοήσεως).
Στόχος της παρουσίασης είναι (i) να εκτεθείτε σε ένα ευρύ φάσμα από τρέχοντα ερευνητικά θέματα, (ii) να εξοικειωθείτε με το διάβασμα και την ανάλυση επιστημονικών άρθρων, και (iii) να αποτκήσετε μία ιδέα για τα μαθηματικά που χρησιμοποιούνται ενεργά στην έρευνα σε κάθε έναν από αυτούς τους τομείς.
Η παρουσίαση θα μετρήσει για το 50% του τελικού σας βαθμού.
Για την παρουσίασή σας, θα πρέπει να διαβάσετε προσεκτικά ένα ερευνητικό άρθρο της επιλογής σας, είτε από τον κατάλογο προτάσεων που ακολουθεί, είτε που θα βρείτε μόνοι σας και το οποίο θα είναι κατάλληλο για το μάθημα (μετά από συνεννόηση μαζί μου). Στη συνέχεια θα πρέπει να προετοιμάσετε μια παρουσίαση που θα συνοψίζει τις βασικές συνεισφορές της εργασίας, την τοποθέτησή της στο ευρύτερο πλαίσιο του μαθήματος και τους περιορισμούς των αποτελεσμάτων της. Θα κάνετε αυτή την παρουσίαση κατά τη διάρκεια του εξαμήνου, και θα πρέπει επίσης να είστε έτοιμοι να απαντήσετε σε εύλογες ερωτήσεις σχετικά με την εργασία (οι λεπτομέρειες θα ανακοινωθούν κατά τη διάρκεια του εξαμήνου).
Τα άρθρα θα ανατεθούν με σειρά προτεραιότητας (first come, first served). Θα πρέπει να έχετε κατά νου ότι θα χρειαστείτε αρκετό χρόνο για να μελετήσετε ήρεμα και λεπτομερώς το άρθρο, να προετοιμάσετε την παρουσίασή σας, και να επιλύσετε τυχόν επίμαχα σημεία ή δυσκολίες που μπορεί να συναντήσετε. Μέρος του τρόπου με τον οποίο μαθαίνει κανείς να κάνει έρευνα είναι να διαβάζει προσεκτικά την υπάρχουσα βιβλιογραφία, και ο στόχος εδώ είναι ακριβώς να αναπτύξετε αυτή τη συνήθεια.
Η τελική λίστα των άρθρων παρατίθεται παρακάτω, και μπορείτε να δείτε ανά πάσα στιγμή ποιά άρθρα παραμένουν διαθέσιμα εδώ:
https://docs.google.com/spreadsheets/d/1uVt3oOIOWElBZ3eA-iXB_ZFzIL3HQx8YI_2MspRHW58/edit?usp=sharing
Αφού επιλέξετε το άρθρο που θα θέλατε να παρουσιάσετε (και την ημερομηνία που προτιμάτε), τη δηλώνετε εδώ:
https://forms.gle/psmzYtD2QJTsSL1TA
