Αλγοριθμική θεωρία παιγνίων και σχεδιασμός μηχανισμών
Στην παρούσα διπλωματική εργασία αρχικά αναλύονται οι βασικές έννοιες της θεωρίας παιγνίων καθώς και ένα θεμελιώδες ζήτημα της αλγοριθμικής θεωρίας παιγνίων ο υπολογισμός της ισορροπίας Nash, που χαρακτηρίζει όλα τα πεπερασμένα παίγνια με μεικτές στρατηγικές. Στην περίπτωση δύο παικτών ο υπολογισμό...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Γλώσσα: | Greek |
| Έκδοση: |
2021
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/15164 |
| id |
nemertes-10889-15164 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-151642022-09-05T20:48:52Z Αλγοριθμική θεωρία παιγνίων και σχεδιασμός μηχανισμών Algorithmic game theory and mechanism design Χριστοδουλοπούλου, Βενέτα Christodoulopoulou, Veneta Αλγοριθμική θεωρία παιγνίων Σχεδιασμός μηχανισμών Δημοπρασίες Algorithmic game theory Mechanism design Auctions Στην παρούσα διπλωματική εργασία αρχικά αναλύονται οι βασικές έννοιες της θεωρίας παιγνίων καθώς και ένα θεμελιώδες ζήτημα της αλγοριθμικής θεωρίας παιγνίων ο υπολογισμός της ισορροπίας Nash, που χαρακτηρίζει όλα τα πεπερασμένα παίγνια με μεικτές στρατηγικές. Στην περίπτωση δύο παικτών ο υπολογισμός της γίνεται με τη βοήθεια του αλγορίθμου Lemke-Howson, που έχει εκθετικής τάξης χρονική πολυπλοκότητα στη χείριστη περίπτωση. Επιπλέον μελετώνται ορισμένες σημαντικές κλάσεις για την ένταξη του προβλήματος του υπολογισμού των ισορροπιών Nash ως προς την υπολογιστική πολυπλοκότητα του και κατηγοριοποιείται το πρόβλημα αυτό σαν πλήρες για την κλάση PPAD. Ο αλγοριθμικός σχεδιασμός μηχανισμών αποτελεί υποπεδίο της θεωρίας παιγνίων και θέτει τους κανόνες του παιγνίου, ώστε να αποφεύγουν οι παίκτες τη στρατηγική συμπεριφορά. Στον σχεδιασμό μηχανισμών χωρίς χρήματα, αποδείχτηκε ότι το θεώρημα Gibbard-Satterthwaite έχει σημαντικές συνέπειες και ήταν αναγκαία η προσθήκη χρημάτων στο μοντέλο. Δημιουργήθηκε λοιπόν ο σχεδιασμός μηχανισμών με χρήματα όπου πολύ σημαντική είναι η συμβολή του στις δημοπρασίες. Στην παρούσα εργασία μελετάμε δύο είδη δημοπρασιών σε μονοπαραμετρικά περιβάλλοντα, τις δημοπρασίες ενός αντικειμένου με έμφαση στις δημοπρασίες δεύτερης τιμής και τις δημοπρασίες χρηματοδοτούμενης αναζήτησης. Οι στόχοι του σχεδιασμού μηχανισμών στις δημοπρασίες επιτυγχάνονται με τη βοήθεια του λήμματος του Myerson. Επιπλέον αναλύονται τρεις διαφορετικοί μηχανισμοί δημοπρασιών που χρησιμοποιούνται από τις μηχανές αναζήτησης, οι Generalized First Price (GFP), Vickrey-Clarke-Groves (VCG) και Generalized Second Price (GSP), ο οποίος είναι ο επικρατέστερος παρόλο που δεν είναι φιλαλήθης. In the present thesis initially the fundamental concepts of game theory are analysed along with a fundamental issue of algorithmic game theory, the problem of finding Nash equilibria, which characterises all finite games with mixed strategies. In the case of two players it can be solved by the Lemke-Howson algorithm, which is exponential in the worst case. Moreover, some fundamental complexity classes for the computational complexity of this problem are studied, with this problem characterized as complete for the class PPAD. The algorithmic mechanism design constitutes a subfield of game theory and sets the rules of the game so as the players to avoid the strategic behavior. At the mechanism design without money, the Gibbard-Satterthwaite theorem was shown to have important consequences and the addition of money in the model is necessary in order to have certain properties. So mechanism design with money was introduced, whose the contribution is very important at auctions. In this thesis we study two kinds of auctions in single parameter environments, the single item auctions like second price auctions and sponsored search auctions. The targets of mechanism design are realised with the aid of Myerson's lemma. Moreover three different auction mechanisms being used from search engine are analysed. The Generalized First Price (GFP) mechanism, the Vickrey-Clarke-Groves (VCG) and the Generalized Second Price (GSP) mechanism, which is the most common despite the fact that it is not truthful. 2021-09-03T05:11:16Z 2021-09-03T05:11:16Z 2021-09-02 http://hdl.handle.net/10889/15164 gr application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Αλγοριθμική θεωρία παιγνίων Σχεδιασμός μηχανισμών Δημοπρασίες Algorithmic game theory Mechanism design Auctions |
| spellingShingle |
Αλγοριθμική θεωρία παιγνίων Σχεδιασμός μηχανισμών Δημοπρασίες Algorithmic game theory Mechanism design Auctions Χριστοδουλοπούλου, Βενέτα Αλγοριθμική θεωρία παιγνίων και σχεδιασμός μηχανισμών |
| description |
Στην παρούσα διπλωματική εργασία αρχικά αναλύονται οι βασικές έννοιες της θεωρίας παιγνίων καθώς και ένα θεμελιώδες ζήτημα της αλγοριθμικής θεωρίας παιγνίων ο υπολογισμός της ισορροπίας Nash, που χαρακτηρίζει όλα τα πεπερασμένα παίγνια με μεικτές στρατηγικές. Στην περίπτωση δύο παικτών ο υπολογισμός της γίνεται με τη βοήθεια του αλγορίθμου Lemke-Howson, που έχει εκθετικής τάξης χρονική πολυπλοκότητα στη χείριστη περίπτωση. Επιπλέον μελετώνται ορισμένες σημαντικές κλάσεις για την ένταξη του προβλήματος του υπολογισμού των ισορροπιών Nash ως προς την υπολογιστική πολυπλοκότητα του και κατηγοριοποιείται το πρόβλημα αυτό σαν πλήρες για την κλάση PPAD. Ο αλγοριθμικός σχεδιασμός μηχανισμών αποτελεί υποπεδίο της θεωρίας παιγνίων και θέτει τους κανόνες του παιγνίου, ώστε να αποφεύγουν οι παίκτες τη στρατηγική συμπεριφορά. Στον σχεδιασμό μηχανισμών χωρίς χρήματα, αποδείχτηκε ότι το θεώρημα Gibbard-Satterthwaite έχει σημαντικές συνέπειες και ήταν αναγκαία η προσθήκη χρημάτων στο μοντέλο. Δημιουργήθηκε λοιπόν ο σχεδιασμός μηχανισμών με χρήματα όπου πολύ σημαντική είναι η συμβολή του στις δημοπρασίες. Στην παρούσα εργασία μελετάμε δύο είδη δημοπρασιών σε μονοπαραμετρικά περιβάλλοντα, τις δημοπρασίες ενός αντικειμένου με έμφαση στις δημοπρασίες δεύτερης τιμής και τις δημοπρασίες χρηματοδοτούμενης αναζήτησης. Οι στόχοι του σχεδιασμού μηχανισμών στις δημοπρασίες επιτυγχάνονται με τη βοήθεια του λήμματος του Myerson. Επιπλέον αναλύονται τρεις διαφορετικοί μηχανισμοί δημοπρασιών που χρησιμοποιούνται από τις μηχανές αναζήτησης, οι Generalized First Price (GFP), Vickrey-Clarke-Groves (VCG) και Generalized Second Price (GSP), ο οποίος είναι ο επικρατέστερος παρόλο που δεν είναι φιλαλήθης. |
| author2 |
Christodoulopoulou, Veneta |
| author_facet |
Christodoulopoulou, Veneta Χριστοδουλοπούλου, Βενέτα |
| author |
Χριστοδουλοπούλου, Βενέτα |
| author_sort |
Χριστοδουλοπούλου, Βενέτα |
| title |
Αλγοριθμική θεωρία παιγνίων και σχεδιασμός μηχανισμών |
| title_short |
Αλγοριθμική θεωρία παιγνίων και σχεδιασμός μηχανισμών |
| title_full |
Αλγοριθμική θεωρία παιγνίων και σχεδιασμός μηχανισμών |
| title_fullStr |
Αλγοριθμική θεωρία παιγνίων και σχεδιασμός μηχανισμών |
| title_full_unstemmed |
Αλγοριθμική θεωρία παιγνίων και σχεδιασμός μηχανισμών |
| title_sort |
αλγοριθμική θεωρία παιγνίων και σχεδιασμός μηχανισμών |
| publishDate |
2021 |
| url |
http://hdl.handle.net/10889/15164 |
| work_keys_str_mv |
AT christodoulopouloubeneta algorithmikētheōriapaigniōnkaischediasmosmēchanismōn AT christodoulopouloubeneta algorithmicgametheoryandmechanismdesign |
| _version_ |
1771297320293367808 |
