| Περίληψη: | Στην παρούσα διπλωματική εργασία αρχικά αναλύονται οι βασικές έννοιες της θεωρίας παιγνίων καθώς και ένα θεμελιώδες ζήτημα της αλγοριθμικής θεωρίας παιγνίων ο υπολογισμός της ισορροπίας Nash, που χαρακτηρίζει όλα τα πεπερασμένα παίγνια με μεικτές στρατηγικές. Στην περίπτωση δύο παικτών ο υπολογισμός της γίνεται με τη βοήθεια του αλγορίθμου Lemke-Howson, που έχει εκθετικής τάξης χρονική πολυπλοκότητα στη χείριστη περίπτωση. Επιπλέον μελετώνται ορισμένες σημαντικές κλάσεις για την ένταξη του προβλήματος του υπολογισμού των ισορροπιών Nash ως προς την υπολογιστική πολυπλοκότητα του και κατηγοριοποιείται το πρόβλημα αυτό σαν πλήρες για την κλάση PPAD. Ο αλγοριθμικός σχεδιασμός μηχανισμών αποτελεί υποπεδίο της θεωρίας παιγνίων και θέτει τους κανόνες του παιγνίου, ώστε να αποφεύγουν οι παίκτες τη στρατηγική συμπεριφορά. Στον σχεδιασμό μηχανισμών χωρίς χρήματα, αποδείχτηκε ότι το θεώρημα Gibbard-Satterthwaite έχει σημαντικές συνέπειες και ήταν αναγκαία η προσθήκη χρημάτων στο μοντέλο. Δημιουργήθηκε λοιπόν ο σχεδιασμός μηχανισμών με χρήματα όπου πολύ σημαντική είναι η συμβολή του στις δημοπρασίες. Στην παρούσα εργασία μελετάμε δύο είδη δημοπρασιών σε μονοπαραμετρικά περιβάλλοντα, τις δημοπρασίες ενός αντικειμένου με έμφαση στις δημοπρασίες δεύτερης τιμής και τις δημοπρασίες χρηματοδοτούμενης αναζήτησης. Οι στόχοι του σχεδιασμού μηχανισμών στις δημοπρασίες επιτυγχάνονται με τη βοήθεια του λήμματος του Myerson. Επιπλέον αναλύονται τρεις διαφορετικοί μηχανισμοί δημοπρασιών που χρησιμοποιούνται από τις μηχανές αναζήτησης, οι Generalized First Price (GFP), Vickrey-Clarke-Groves (VCG) και Generalized Second Price (GSP), ο οποίος είναι ο επικρατέστερος παρόλο που δεν είναι φιλαλήθης.
|
|---|
