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

Επίσημο περίγραμμα μαθήματος του ΤΜΗΥΠ (Πανεπιστήμιο Πατρών), όπως δημοσιεύεται στη σελίδα του μαθήματος και στο συνημμένο αρχείο «Περίγραμμα Μαθήματος». Το κείμενο παρατίθεται αυτούσιο, χωρίς τα πρότυπα οδηγιών του εντύπου.

Στόχοι

• Με την επιτυχή ολοκλήρωση του μαθήματος, οι φοιτητές/τριες θα είναι σε θέση :
• Να αναγνωρίζουν και να αναλύουν αμερόληπτα συνδυαστικά παίγνια ως προς την έκβασή τους, μέσω της αριθμητικής στοιβών ΝΙΜ.
• Να μοντελοποιούν καταστάσεις συνεργασίας ή/και ανταγωνισμού μεταξύ διαφορετικών οντοτήτων, με τη μορφή παιγνίων εκτενούς μορφής και στρατηγικών παιγνίων.
• Να αντιλαμβάνονται θεμελιώδη σκεπτικά λύσεων για διαφορετικές μορφές παιγνίων, όπως τέλειες ως προς υποπαίγνια ισορροπίες Nash για παίγνια σε εκτενή μορφή, ισορροπίες Nash και συσχετιζόμενες ισορροπίες για στρατηγικά παίγνια, Nash λύσεις για διαπραγματεύσεις, κ.λπ.
• Να κατασκευάζουν τέλειες-ως-προς-υποπαίγνια ισορροπίες για παίγνια εκτενούς μορφής με πλήρη γνώση, μέσω της προς τα πίσω επαγωγής.
• Να αντιλαμβάνονται και να αξιοποιούν τη συσχέτιση μεταξύ παιγνίων σε εκτενή μορφή και στρατηγικών παιγνίων.
• Να υπολογίζουν όλες τις ισορροπίες για στρατηγικά παίγνια δύο παικτών με το πολύ δύο δράσεις για έναν εκ των δύο παικτών, με τις μεθόδους των διαφορών και του άνω-φακέλου.
• Να υπολογίζουν ΜΑΧΜΙΝ στρατηγικές σε παίγνια δύο παικτών, μέσω τεχνικών γραμμικού προγραμματισμού.
• Να εκτελούν αλγορίθμους υπολογισμού μιας επακριβούς ή προσεγγιστικής ισορροπίας σε παίγνια δύο παικτών, αξιοποιώντας τεχνικές γραμμικού προγραμματισμού για μητρικά παίγνια και συνδυαστικούς αλγορίθμους (π.χ., Lemke-Howson) για γενικά παίγνια.
• Να κατανοούν τη σημασία των προσεγγιστικών ισορροπιών Nash και να εφαρμόζουν αποδοτικούς αλγορίθμους για κατασκευή τους στρατηγικά παίγνια δύο παικτών.
• Να μοντελοποιούν προβλήματα ανταγωνισμού του πραγματικού κόσμου ως στρατηγικά παίγνια συμφόρησης, και γενικότερα ως παίγνια δυναμικού, και να προσδιορίζουν τις συναρτήσεις δυναμικού που τα διέπουν.
• Να αναλύουν στρατηγικά παίγνια ως προς το κόστος/την τιμή της ευστάθειάς τους, χρησιμοποιώντας τη μέθοδο της συνάρτησης δυναμικού.
• Να σχεδιάζουν δημοπρασίες σφραγισμένων προσφορών, τύπου VCG.
• Να αντιλαμβάνονται τη σημασία της φιλαλήθειας των πλειοδοτών και να διακρίνουν αν συγκεκριμένες δημοπρασίες πληρούν τη συγκεκριμένη ιδιότητα.
• Να αναλύουν σενάρια αλληλεπίδρασης σε συνεργατικά περιβάλλοντα, όπως οι διαπραγματεύσεις, και να προβλέπουν τις καταστάσεις ισορροπίας (Nash bargaining solutions) που θα προκύψουν.
• Να αντιλαμβάνονται τη θεωρία παιγνίων ως ένα καινοτόμο μοντέλο, για τον σχεδιασμό και την ανάλυση της συμπεριφοράς αυτόνομων οντοτήτων, αλγορίθμων και μηχανισμών, που καλούνται να λειτουργήσουν σε, συνεργατικά ή μη, αποκεντρωμένα υπολογιστικά περιβάλλοντα.
• Να εφαρμόζουν κανόνες ψηφοφοριών και να αναγνωρίζουν προφίλ ψηφοφοριών που επιδέχονται χειραγώγησης.

Περιεχόμενο (ύλη)

Συνδυαστικά Παίγνια: Ορισμός και μέθοδοι επίλυσης για αμερόληπτα συνδυαστικά παίγνια (αριθμητική ΝΙΜ σωρών και κανόνας ΜΕΧ). Παίγνια Εκτενούς Μορφής: Παίγνια με πλήρη γνώση, με ελλιπή γνώση, και με ή χωρίς τέλεια ανάκληση (μνήμης). Στρατηγικά παίγνια: Παίγνια μηδενικού αθροίσματος, βέλτιστες στρατηγικές, μεικτές στρατηγικές, κυρίαρχες στρατηγικές, ισορροπίες Nash, συσχετιζόμενες ισορροπίες, προσεγγιστικές ισορροπίες. Αλγόριθμοι και πολυπλοκότητα υπολογισμού μιας ή όλων των ισορροπιών Nash (μέθοδος άνω-φακέλου, απαρίθμησης κορυφών, Lemke-Howson, κ.λπ.) για στρατηγικά παίγνια δύο παικτών. Ορισμός και αποδοτικές μέθοδοι υπολογισμού ΜΑΧΜΙΝ στρατηγικών. Διαπραγματεύσεις: Μοντελοποίηση ως επαναλαμβανόμενα στρατηγικά παίγνια με απομείωση ωφελειών. Αξιωματικός χαρακτηρισμός και μέθοδοι υπολογισμού λύσης (Nash bargaining solution) για διαπραγματεύσεις. Μηχανισμοί: Σχεδιασμός φιλαληθών μηχανισμών. Θεώρημα των Gibbard & Shatterthwaite. Θεωρία δημοπρασιών. Λήμμα του Myerson, δημοπρασίες κατά Vickrey. Δημοπρασίες VCG. Γενικευμένες δημοπρασίες δεύτερης τιμής. Παίγνια συμφόρησης: Μοντελοποίηση ως παίγνια δυναμικού. Τίμημα της αναρχίας/ευστάθειας. Παίγνια σχεδιασμού δικτύων. Θεωρία ψηφοφοριών: Κανόνες ψηφοφορίας (πλειοψηφία, βέτο, Borda, δικτατορίες). Θεώρημα του Arrow.

Αξιολόγηση

Γλώσσα εξέτασης: Ελληνική (Αγγλική αν χρειαστεί, π.χ., για φοιτητές/φοιτήτριες Erasmus+)

Μέθοδος αξιολόγησης: Η αξιολόγηση περιλαμβάνει αναθέσεις για το σπίτι (τουλάχιστον δύο, ατομικές ή ανά δύο άτομα) και τελική γραπτή εξέταση του μαθήματος.

Αναθέσεις για το σπίτι: Περιλαμβάνουν θεωρητικό και προγραμματιστικό μέρος, ενώ αποτελούνται από δύο παραδοτέα, ένα αφορά τον πηγαίο κώδικα και το άλλο αφορά γραπτή αναφορά με παρουσίαση της υλοποίησης και επισκόπηση πειραματικής αξιολόγησης των υλοποιημένων μεθόδων.

Γραπτή εξέταση: Αποτελείται από ερωτήματα διαβαθμισμένης δυσκολίας, όπως, ερωτήσεις πολλαπλής επιλογής, ερωτήσεις ανάπτυξης μαθηματικών επιχειρημάτων, ή προβλήματα και ασκήσεις (π.χ., εκτέλεση κάποιου αλγορίθμου για την εύρεση κάποιας ισορροπίας)

Βιβλιογραφία

Προτεινόμενη Βιβλιογραφία στον ΕΥΔΟΞΟ:

• [133035991] «Στρατηγικές και Παίγνια», 2η Έκδοση (ISBN: 9786182211427)". Dutta Prajit, Vergote Wouter. ΕΚΔΟΣΕΙΣ Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε. (2025) .
• [133040559] «ΘΕΩΡΙΑ ΠΑΙΓΝΙΩΝ ΚΑΙ ΣΥΜΠΕΡΙΦΟΡΕΣ». JEFFREY CARPENDER, ANDREA ROBBETT. ΕΚΔΟΣΕΙΣ ΚΛΕΙΔΑΡΙΘΜΟΣ ΕΠΕ (2025).

• [86056102] «ΘΕΩΡΙΑ ΠΑΙΓΝΙΩΝ» (ISBN: 9789925575404). McCain Roger A. BROKEN HILL PUBLISHERS LTD (2019).

• [35241] «ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΠΑΙΓΝΙΩΝ» (ISBN: 9789604613939). MARTIN J. OSBORNE. ΕΚΔΟΣΕΙΣ ΚΛΕΙΔΑΡΙΘΜΟΣ ΕΠΕ (2010).

• [1063] «ΘΕΩΡΙΑ ΠΑΙΓΝΙΩΝ» (ISBN: 9789606706301). ΜΗΛΟΛΙΔΑΚΗΣ ΚΩΝΣΤΑΝΤΙΝΟΣ. "σοφία" Ανώνυμη Εκδοτική & Εμπορική Εταιρεία (2009).
• [320188] «ΘΕΩΡΙΑ ΠΑΙΓΝΙΩΝ» (ISBN:978-960-603-349-0). ΓΕΩΡΓΙΟΣ ΣΤΑΜΑΤΟΠΟΥΛΟΣ. Εκδόσεις ΚΑΛΛΙΠΟΣ, Ηλεκτρονικό Βιβλίο (2016).

Λοιπή Βιβλιογραφία (εκτός ΕΥΔΟΞΟΥ):

• B. von Stengel: Game Theory Basics. Cambridge University Press, ISBN 9781108910118 (2020).
• T. Roughgarden: Twenty Lectures on Algorithmic Game Theory. Cambridge University Press (2016).
• N. Nisan, T. Roughgarden, E. Tardos, & V. Vazirani (editors). Algorithmic Game Theory. 2007.
• F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. Procaccia (editors). Handbook of Computational Social Choice. Cambridge University Press, 2016.
• D. Easley & J. Kleinberg. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press, 2010. Συναφή επιστημονικά περιοδικά: Πρόκειται για επιστημονικό αντικείμενο με έντονη ερευνητική δραστηριότητα που συνήθως δημοσιεύεται σε πολύ υψηλής ποιότητας περιοδικά της Θεωρητικής Επιστήμης των Υπολογιστών (Journal of the ACM, SIAM Journal on Computing, ACM Transactions on Algorithms), της Τεχνητής Νοημοσύνης (Journal of Artificial Intelligence Research, Artificial Intelligence), της Οικονομικής Θεωρίας (π.χ., Journal of Economic Theory, Games and Economic Behavior, Econometrica), καθώς και διεπιστημονικά περιοδικά (όπως το ACM Transactions on Economics and Computation).