Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/5173
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorΚαββαδίας, Δημήτριος-
dc.contributor.authorΔελιγκάς, Αργύρης-
dc.contributor.otherDeligkas, Argyris-
dc.date.accessioned2012-04-26T08:09:36Z-
dc.date.available2012-04-26T08:09:36Z-
dc.date.copyright2011-
dc.date.issued2012-04-26-
dc.identifier.urihttp://hdl.handle.net/10889/5173-
dc.description.abstractΣε αυτή τη διπλωματική εργασία μελετάμε το πρόβλημα εύρεσης ενός 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 για την παραγωγή των παιγνίων της κλάσης αυτής και παρουσιάζονται τα μήκη των μονοπατιών που κατασκευάζει ο αλγόριθμος παίγνια της κλάσης.el
dc.language.isogrel
dc.relation.isformatofΗ ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της.el
dc.rights0el
dc.subjectΑλγοριθμική θεωρία παιγνίωνel
dc.subjectΠαίγνια διπίνακαel
dc.subject.ddc519.3el
dc.titleΠαίγνια δύο παικτών, υπολογιστικά θέματα και αλγόριθμοιel
dc.title.alternativeBimatrix games, computational issues and algorithmsel
dc.typeThesisel
dc.contributor.committeeΤσάντας, Νικόλαος-
dc.contributor.committeeΑλεβίζος, Παναγιώτης-
dc.description.translatedabstractIn this thesis we study the problem of finding a Nash equilibrium for bimatrix games. We describe Lemke - Howson algorithm and its complexity. Also we study the PPAD complexity class and we give the reduction which shows that the problem of finding a Nash equilibrium (NASH) is PPAD complete even for bimatrix games. In section 1, we give a short history view of game theory and some essential notions about games, players and game solutions such as Nash equilibrium. In section 2, we define bimatrix games: each player's strategies, payoffs, mixed strategies, best response, Nash equilibria and we demonstrate all of them with an example. After that, we present best response polyhedra and best response polyhedra in which the Lemke - Howson algorithm is based. In section 3, we discribe in detail Lemke - Howson algorithm intuitively, by mones on best response polytopes, and arithmetically, by integer pivoting, which is a variant of simplex method. In section 4, is described a class of games where Lemke - Howson needs exponetial time to find a Nash equilibrium. For the construction of the games we use cyclic polytopes and the Gale evenness condition and their properties. We show in detail the Lemke - Howson paths and we compute their lengths for each dropped label. In section 5, we give a reduction from Perfect Matching to Nash equilibrium for a special case of games and we show that at these games a Nash equilibrium can be computed in polynomial time. In the final section we study the complexity class PPAD. First of all, we define formally the class and we give the first complete problem for this class, END OF LINE. After that, we reduce END OF LINE to SPERNER and SPERNER to BROUWER which is a simplified, discretized version of finding a fixed point for a continuous function f . Finally, we give in detail the reduction from BROUWER to 2NASH and we show that 2NASH is PPAD-complete which means that there is no polynomial time algorithm for 2NASH unless P = PPAD. At the end there are two appendices: At the first one we demonstrate the LH paths and at the second we give the source code in MATLAB for the construction of payoff tables for the LH worst case.el
dc.subject.alternativeGame theoryel
dc.subject.alternativeBimatrix gamesel
dc.subject.alternativeLemke Howsonel
dc.subject.alternativePPADel
dc.degreeΜεταπτυχιακή Εργασίαel
Appears in Collections:Τμήμα Μαθηματικών (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
Deligkas_Argyris.pdf859.32 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.