Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/30257Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Πρόσκος, Δανιήλ-Δημήτριος | el |
| dc.date.accessioned | 2020-11-11T11:26:00Z | - |
| dc.date.available | 2020-11-11T11:26:00Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/30257 | - |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.10145 | - |
| dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | * |
| dc.subject | Θεωρία παιγνίων | el |
| dc.subject | Ισορροπία Nash | el |
| dc.subject | Game-theoretic | en |
| dc.subject | Nash equilibrium | en |
| dc.title | Προσεγγιστικοί αλγόριθμοι για θέματα ισορροπιών Nash σε παίγνια διπίνακα | el |
| dc.title | Approximation algorithms for Nash equilibria in bimatrix games | en |
| heal.type | masterThesis | - |
| heal.type.en | Master thesis | en |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.classification | Θεωρία παιγνίων | - |
| heal.dateAvailable | 2020-11-11T11:27:00Z | - |
| heal.language | el | - |
| heal.access | free | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.publicationDate | 2016 | - |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 67-71 | el |
| heal.abstract | Κατά τη μελέτη ενός συστήματος εγωιστικών οντοτήτων που αλληλεπιδρούν για τη λήψη μιας απόφασης υπό το πρίσμα της θεωρίας παιγνίων, μας ενδιαφέρει να προσδιορίσουμε ένα σημείο ισορροπίας του, το οποίο ορίζουμε μέσω ενός σκεπτικού λύσης. Το δημοφιλέστερο σκεπτικό λύσης στη θεωρία παιγνίων είναι η ισορροπία Nash, η οποία εκφράζει μια σταθερή κατάσταση του συστήματος όπου καμία οντότητα δεν μπορεί να επωφεληθεί από την επιλογή ενός διαφορετικού πλάνου ενεργειών, δεδομένου ότι οι υπόλοιπες οντότητες δεν αποκλίνουν από τις δικές τους επιλογές ενεργειών. Η ανάγκη της προσομοίωσης συστημάτων εγωιστικών οντοτήτων οδήγησε στη μελέτη της υπολογιστικής πολυπλοκότητας του προβλήματος υπολογισμού ισορροπιών Nash σε πεπερασμένα στρατηγικά παίγνια. Μια σειρά αποτελεσμάτων PPAD-πληρότητας του προβλήματος εύρεσης μιας ισορροπίας Nash κατέδειξε τη δυσκολία αυτού του προβλήματος, ακόμη και στην απλή περίπτωση των παιγνίων διπίνακα. Για τον λόγο αυτόν, η έρευνα στράφηκε τα τελευταία χρόνια προς την κατεύθυνση της ανάπτυξης αλγορίθμων για τον υπολογισμό προσεγγιστικών ισορροπιών Nash, αλλά και στον εντοπισμό υποκλάσεων παιγνίων για τα οποία υπάρχουν πολυωνυμικού χρόνου επακριβείς αλγόριθμοι, ή τουλάχιστον σχήματα προσέγγισης, για τον υπολογισμό ισορροπιών Nash. Στην παρούσα εργασία μελετάται το πρόβλημα διεύρυνσης της υποκλάσης των παιγνίων διπίνακα που επιδέχονται ένα πολυωνυμικού χρόνου προσεγγιστικό σχήμα για τον υπολογισμό μιας ισορροπίας Nash. Η πρότασή μας για την επέκταση της κλάσης παιγνίων διπίνακα που επιδέχονται ένα τυχαιοκρατικό πολυωνυμικού χρόνου προσεγγιστικό σχήμα για τον υπολογισμό μιας ^-ισορροπίας Nash βασίζεται στη θεώρηση ενός κυρτού συνδυασμού των μεταμελειών των δύο παικτών ως αντικειμενική συνάρτηση ενός προγράμματος βελτιστοποίησης, για κάποια παράμετρο λ Ε (0,1) Αρχικά παρουσιάζουμε ένα τυχαιοκρατικό πολυωνυμικού χρόνου προσεγγιστικό σχήμα για τον υπολογισμό ^-ισορροπιών Nash παιγνίων διπίνακα των οποίων το άθροισμα των πινάκων ωφελειών έχει σταθερή τιμή στη γ^-νόρμα. Στη συνέχεια, αποδεικνύουμε ότι αν για ένα παίγνιο διπίνακα (Α, Ο υπάρχει μια τιμή λ* t (0,1) μακριά από τα άκρα του διαστήματος για την οποία ο πίνακας Ζ(/Is1) \=X*R + (1 —Λ*1)C έχει σταθερή νόρμα είναι εφικτός ο υπολογισμός σε sininUT.l—Λ'Ι πολυωνυμικο χρονο μιας ε-ισορροπιας Nash χρησιμοποιώντας ενα----net, το οποίο κατασκευάζουμε με χρήση του αλγορίθμου των Alon et al (2013), με μεγάλη πιθανότητα. Επίσης, αποδεικνύουμε ότι είναι εφικτή η εξέταση σε πολυωνυμικό χρόνο αν υπάρχει ένα λ* Ε (0,1) για το οποίο ισχύει ότι γΐ'*4= 0(1), μέσω της επίλυσης ενός θετικά ημιορισμένου προγράμματος. Τέλος, διεξάγουμε εκτενή πειραματική αξιολόγηση με στόχο τον προσδιορισμό της γενικότητας και της σημαντικότητας της υποκλάσης παιγνίων διπίνακα που προτείνουμε, εστιάζοντας κυρίως σε παίγνια διπίνακα νίκης-ήττας. | el |
| heal.abstract | When we study a system of selfish agents that interact during a decision making process under the lens of game theory, our main issue is to identify an equilibrium point of this system. We define such a point by a solution concept. The most popular game-theoretic solution concept is the Nash Equilibrium. A Nash Equilibrium reflects a steady state of the system, in which no single entity can benefit from a unilateral change of its plan of actions. The demand of simulating systems of interacting selfish agents led to the study of the computational complexity of computing a Nash Equilibrium of a finite game (as Nash, in 1951, proved that each finite game has at least one Nash Equilibrium). Unfortunately, a series of PPAD-Hardness results for this problem demonstrated the hardness of computing a Nash Equilibrium even for the simple case of bimatrix games (i.e., strategic games of two players). Thus, the current research on Nash Equilibria computation has inevitably turned to the directions of designing constant approximation algorithms (or even a polynomial time approximation scheme) for computing approximate Nash Equilibria of general bimatrix games, as well as identifying subclasses of bimatrix games that admit a polynomial time algorithm, or at least a (fully) polynomial time approximation scheme for this problem. In this thesis, we study the problem of expanding the subclass of bimatrix games that admit a polynomial time approximation scheme for the problem of computing a Nash Equilibrium. To this direction, we propose a way of identifying bimatrix games that admit a randomized polynomial time approximation scheme in polynomial time, based on a definition of a convex combination of players’ regrets as the objective function of an optimization problem, for a parameter . At first, we present a randomized polynomial time approximation scheme for -Nash Equilibrium computation of a bimatrix game, the sum of payoff matrices of which has constant value in its norm. Its building blocks are a modification of the approximation algorithm for the problem of computing the approximate rank of a matrix, designed by Lee and Shraibman (2008), along with the near-optimal –net construction algorithm of Alon et al (2013). Since the computation of the norm of a matrix can be done by solving a semidefinite program, we are able to identify if a given bimatrix game admits this randomized polynomial time approximation scheme in polynomial time. Next, we prove that if, for a given bimatrix game , there is a value , bounded away from the boundaries of this interval, for which the matrix has constant norm, then we can compute a –Nash Equilibrium for this bimatrix game using a –net that we obtain by the algorithm of near-optimal -net construction of Alon et al (2013), with high probability. Furthermore, we prove that it is feasible to identify in polynomial time if there is a value for which it holds that , by solving a semidefinite program, thus proving the feasibility of polynomial-time identification of the bimatrix games that belong to the proposed subclass. An additional important contribution that we made is our proofs that the constant-sum bimatrix games and the fixed-rank bimatrix games are contained to the subclass of games that their sum of payoff matrices has constant value in its norm. Finally, in order to determine the generality and importance of the subclass of bimatrix games that we propose, we conducted an extensive experimental evaluation as a first step to this direction. We conducted our experiments on win-lose games. | en |
| heal.advisorName | Κοντογιάννης, Σπυρίδων | el |
| heal.committeeMemberName | Κοντογιάννης, Σπυρίδων | el |
| heal.committeeMemberName | Νικολόπουλος, Σταύρος | el |
| heal.committeeMemberName | Παληός, Λεωνίδας | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.academicPublisherID | uoi | - |
| heal.numberOfPages | 75 σ. | - |
| heal.fullTextAvailability | true | - |
| Appears in Collections: | Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΥ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Μ.Ε. ΠΡΟΣΚΟΣ ΔΑΝΙΗΛ-ΔΗΜΗΤΡΙΟΣ 2016.pdf | 2.27 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
