Υπολογιστικά ζητήματα σε στρατηγικά παίγνια και διαδικασίες κοινωνικής επιλογής

Abstract

In this dissertation we consider auction markets and examine their properties and how these are affected by the way the participants act. An auction may refer to any mechanism or set of rules governing a resource allocation process. Designing such a mechanism is not an easy task and this is partly due to their vulnerability to strategic manipulation by the participants. Our goal is to examine the theoretical properties of auction mechanisms in order to predict, explain, or even adjust their behavior in practice in terms of some desired features.We focus on sponsored search auctions, which constitute the leading procedure in Internet advertising. We adopt a game-theoretic approach and provide Price of Anarchy bounds in order to measure the efficiency loss due to the strategic behavior of the players. Moreover, we prove revenue guarantees to bound the suboptimality of GSP (generalized second price mechanism) in that respect. Ιn particular, we define variants of the GSP auction mechanism that yield good revenue guarantees. We also consider the problem of designing an optimal auction in the single-item setting. We prove a strong APX-hardness result that applies to the 3-player case. We furthermore give a separation result between the revenue of deterministic and randomized optimal auctions.

Στην παρούσα διατριβή μελετάμε αγορές δημοπρασιών και εξετάζουμε διάφορες ιδιότητές τους καθώς και τον τρόπο που αυτές επηρεάζονται από τον τρόπο που συμπεριφέρονται και δρουν οι συμμετέχοντες. Η έννοια δημοπρασία αναφέρεται σε κάθε μηχανισμό, ή σύνολο κανόνων, που διέπει μια διαδικασία ανάθεσης αγαθών. Τέτοιοι μηχανισμοί είναι επιρρεπείς σε στρατηγικούς χειρισμούς (χειραγώγηση) από τους συμμετέχοντες, γεγονός που δικαιολογεί την έμφυτη δυσκολία στον σχεδιασμό τους. Σκοπός αυτής της εργασίας είναι η μελέτη σε θεωρητικό επίπεδο των ιδιοτήτων μηχανισμών δημοπρασίας έτσι ώστε να είμαστε σε θέση να προβλέψουμε, να εξηγήσουμε, ακόμα και να τροποποιήσουμε την απόδοσή τους στην πράξη.Εστιάζουμε την προσοχή μας σε δημοπρασίες χρηματοδοτούμενης αναζήτησης, οι οποίες αποτελούν την επικρατέστερη διαδικασία για την προβολή διαφημίσεων στο Διαδίκτυο. Υιοθετούμε παιγνιοθεωρητική προσέγγιση και υπολογίζουμε το Τίμημα της Αναρχίας για να φράξουμε την απώλεια αποδοτικότητας εξαιτίας της στρατηγικής συμπεριφοράς των παιχτών. Επίσης, αποδεικνύουμε εγγυήσεις εσόδων για να φράξουμε την απώλεια των εσόδων του μηχανισμού δημοπρασίας GSP (γενικευμένος μηχανισμός δεύτερης τιμής) σε αυτό το πλαίσιο. Για την ακρίβεια, ορίζουμε παραλλαγές του μηχανισμού δημοπρασίας GSP που δίνουν καλές εγγυήσεις εσόδων. Στη συνέχεια εξετάζουμε το πρόβλημα του σχεδιασμού της βέλτιστης δημοπρασίας ενός αντικειμένου. Αποδεικνύουμε ένα υπολογίσιμο φράγμα δυσκολίας στην προσέγγιση για την περίπτωση με τρεις παίχτες. Επίσης, αποδεικνύουμε ότι υπάρχει αξιοσημείωτη διαφορά ανάμεσα στα έσοδα που προκύπτουν από ντετερμινιστικούς φιλαλήθεις μηχανισμούς και πιθανοτικούς μηχανισμούς που είναι φιλαλήθεις κατά μέσο όρο.