Παίγνια δύο παικτών, υπολογιστικά θέματα και αλγόριθμοι

• Κύριος συγγραφέας: Δελιγκάς, Αργύρης
• Άλλοι συγγραφείς: Καββαδίας, Δημήτριος
• Μορφή: Thesis
• Γλώσσα: Greek
• Έκδοση: 2012
• Θέματα: Αλγοριθμική θεωρία παιγνίων; Παίγνια διπίνακα; Game theory; Bimatrix games; Lemke Howson; PPAD; 519.3

Σε αυτή τη διπλωματική εργασία μελετάμε το πρόβλημα εύρεσης ενός Nash σημείου ισορροπίας για παίγνια δύο παικτών. Παρουσιάζεται ο αλγόριθμος Lemke - Howson, η πολυπλοκότητα του αλγορίθμου καθώς και η κλάση πολυπλοκότητας PPAD, όπου και αποδεικνύεται ότι το πρόβλημα εύρεσης ενός Nash σημείου ισορροπίας είναι πλήρες για την κλάση αυτή. Αναλυτικότερα, στο πρώτο κεφάλαιο γίνεται μία σύντομη ιστορική αναδρομή της θεωρίας παιγνίων, παρουσιάζονται κάποιες βασικές έννοιες και προτείνονται κάποιες καταστάσεις ως λύσεις ενός παιγνίου, με κύρια αυτή του Nash σημείου ισορροπίας. Το δεύτερο κεφάλαιο ασχολείται με τα παίγνια δύο παικτών ή παίνγια διπίνακα. Αρχικά ορίζονται τα στοιχεία που συνιστούν το παίγνιο, δηλαδή οι παίκτες, οι στρατηγικές τους, η βέλτιστη απόκριση και το Νash σημείο ισορροπίας και παρουσιάζονται με τη βοήθεια ενός παραδείγματος. Στη συνέχεια, ορίζονται τα πολύεδρα και τα πολύτοπα βέλτιστης απόκρισης με βάση τους πίνακες κερδών των δύο παικτών, που αποτελούν και βάση του αλγορίθμου Lemke - Howson. Στο τρίτο κεφάλαιο παρουσιάζεται αναλυτικά ο αλγόριθμος Lemkle - Howson στη γεωμετρική και στην αριθμητική του μορφή και εφαρμόζεται για ένα συγκεκριμένο παίγνιο. Η γεωμετρική εφαρμογή γίνεται με τη βοήθεια των πολυτόπων βέλτιστης απόκρισης και η αριθμητική μέσω του ακέραιου pivoting, που είναι μια παραλλαγή της μεθόδου simplex. Στο τέταρτο κεφάλαιο μελετάται μία κατηγορία παιγνίων όπου ο αλγόριθμος δεν είναι αποδοτικός. Για την κατασκευή των παιγνίων της κατηγορίας αυτής χρειάζεται πρώτα να δούμε τα κυκλικά πολύτοπα και να παρουσίασουμε κάποιες ιδιότητές τους. Στη συνέχεια αποδεικνύεται ότι ο αλγόριθμος απαιτεί εκθετικό χρόνο μέχρι να καταλήξει σε ένα Nash σημείο ισορροπίας του παιγνίου, σε σχέση με το μέγεθος του παιγνίου. Στο πέμπτο κεφάλαιο παρουσιάζεται μία αναγωγή του προβλήματος της εύρεσης ενός Nash σημείου ισορροπίας ενός παιγνίου δύο παικτών σε αυτό του πλήρους ταιριάσματος ενός γραφήματος, όπου και πάλι χρησιμοποιούμε ιδιότητες των πολυτόπων βέλτιστης απόκρισης καθώς και των δεικτοδοτημένων συμβολοσειρών Gale. Το έκτο και τελευταίο κεφάλαιο ασχολούμαστε με την κλάση πολυπλοκότητας PPAD. Αρχικά, ορίζουμε την κλάση και δίνουμε το πλήρες πρόβλημα οδηγό για την κλάση αυτη, το END OF LINE. Στη συνέχεια, δίνουμε μια διαισθητική αναγωγή του παραπάνω προβλήματος στο πρόβλημα SPERNER και έπειτα του SPERNER στο πρόβλημα BROUWER που πρόκειται για μία διακριτοποιημένη και απλόποιημένη εκδοχή της εύρεσης ενός σταθερού σημείου μίας συνάρτησης f. H τελευταία αναγωγή είναι αυτή του BROUWER στο 2NASH, δηλαδή την εύρεση ενός Nash σημείου ισορροπίας σε ένα παίγνιο δύο παικτών. Με αυτό τον τρόπο αποδεικνύεται ότι το 2NASH είναι PPAD πλήρες και δεν υπάρχει πολυωνυμικός αλγόριθμος για το πρόβλημα αυτό εκτός και αν P = PPAD. Στο τέλος της εργασίας υπάρχουν δύο παραρτήματα, όπου στο πρώτο παρουσιάζονται τα μονοπάτια που κατασκευάζει ο αλγόριθμος Lemke - Howson και κάποιες ιδιότητες αυτού και στο δεύτερο παράρτημα παρουσιάζεται ένα παράδειγμα κατασκευής ενός παιγνίου όπου ο αλγόριθμος δεν είναι αποδοτικός, παρατίθεται ο κώδικας σε MATLAB για την παραγωγή των παιγνίων της κλάσης αυτής και παρουσιάζονται τα μήκη των μονοπατιών που κατασκευάζει ο αλγόριθμος παίγνια της κλάσης.