Σε αυτή τη διπλωματική εργασία μελετάμε το πρόβλημα εύρεσης ενός 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 για την παραγωγή των παιγνίων της κλάσης
αυτής και παρουσιάζονται τα μήκη των μονοπατιών που κατασκευάζει ο αλγόριθμος παίγνια της
κλάσης. / In 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.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/5173 |
| Date | 26 April 2012 |
| Creators | Δελιγκάς, Αργύρης |
| Contributors | Καββαδίας, Δημήτριος, Deligkas, Argyris, Τσάντας, Νικόλαος, Αλεβίζος, Παναγιώτης |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0025 seconds