Υπολογιστικά ζητήματα σε στρατηγικά παίγνια και διαδικασίες κοινωνικής επιλογής
Στην παρούσα διατριβή μελετάμε αγορές δημοπρασιών και εξετάζουμε διάφορες ιδιότητές τους καθώς και τον τρόπο που αυτές επηρεάζονται από τον τρόπο που συμπεριφέρονται και δρουν οι συμμετέχοντες. Η έννοια δημοπρασία αναφέρεται σε κάθε μηχανισμό, ή σύνολο κανόνων, που διέπει μια διαδικασία ανάθεσης αγα...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2014
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/7774 |
| id |
nemertes-10889-7774 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Δημοπρασίες χρηματοδοτούμενης αναζήτησης Ανάλυση καταστάσεων ισορροπίας Τίμημα της αναρχίας Μοντέλο μερικής πληροφόρησης Γενικευμένος μηχανισμός δεύτερης τιμής Σχεδιασμός βέλτιστης δημοπρασίας Ντετερμινιστικοί μηχανισμοί δημοπρασίας Μοντέλο συσχετιζόμενων αξιών Sponsored search auction design Equilibrium analysis Price of anarchy Incomplete information games Generalized second price auction Optimal auction design Deterministic auctions Correlated valuations 381.170 285 467 8 |
| spellingShingle |
Δημοπρασίες χρηματοδοτούμενης αναζήτησης Ανάλυση καταστάσεων ισορροπίας Τίμημα της αναρχίας Μοντέλο μερικής πληροφόρησης Γενικευμένος μηχανισμός δεύτερης τιμής Σχεδιασμός βέλτιστης δημοπρασίας Ντετερμινιστικοί μηχανισμοί δημοπρασίας Μοντέλο συσχετιζόμενων αξιών Sponsored search auction design Equilibrium analysis Price of anarchy Incomplete information games Generalized second price auction Optimal auction design Deterministic auctions Correlated valuations 381.170 285 467 8 Κυροπούλου, Μαρία Υπολογιστικά ζητήματα σε στρατηγικά παίγνια και διαδικασίες κοινωνικής επιλογής |
| description |
Στην παρούσα διατριβή μελετάμε αγορές δημοπρασιών και εξετάζουμε διάφορες ιδιότητές τους καθώς και τον τρόπο που αυτές επηρεάζονται από τον τρόπο που συμπεριφέρονται και δρουν οι συμμετέχοντες. Η έννοια δημοπρασία αναφέρεται σε κάθε μηχανισμό, ή σύνολο κανόνων, που διέπει μια διαδικασία ανάθεσης αγαθών. Τέτοιοι μηχανισμοί είναι επιρρεπείς σε στρατηγικούς χειρισμούς (χειραγώγηση) από τους συμμετέχοντες, γεγονός που δικαιολογεί την έμφυτη δυσκολία στον σχεδιασμό τους. Σκοπός αυτής της εργασίας είναι η μελέτη σε θεωρητικό επίπεδο των ιδιοτήτων μηχανισμών δημοπρασίας έτσι ώστε να είμαστε σε θέση να προβλέψουμε, να εξηγήσουμε, ακόμα και να τροποποιήσουμε την απόδοσή τους στην πράξη.
Εστιάζουμε την προσοχή μας σε δημοπρασίες χρηματοδοτούμενης αναζήτησης, οι οποίες αποτελούν την επικρατέστερη διαδικασία για την προβολή διαφημίσεων στο Διαδίκτυο. Υιοθετούμε παιγνιοθεωρητική προσέγγιση και υπολογίζουμε το Τίμημα της Αναρχίας για να φράξουμε την απώλεια αποδοτικότητας εξαιτίας της στρατηγικής συμπεριφοράς των παιχτών. Επίσης, αποδεικνύουμε εγγυήσεις εσόδων για να φράξουμε την απώλεια των εσόδων του μηχανισμού δημοπρασίας GSP (γενικευμένος μηχανισμός δεύτερης τιμής) σε αυτό το πλαίσιο. Για την ακρίβεια, ορίζουμε παραλλαγές του μηχανισμού δημοπρασίας GSP που δίνουν καλές εγγυήσεις εσόδων. Στη συνέχεια εξετάζουμε το πρόβλημα του σχεδιασμού της βέλτιστης δημοπρασίας ενός αντικειμένου. Αποδεικνύουμε ένα υπολογίσιμο φράγμα δυσκολίας στην προσέγγιση για την περίπτωση με τρεις παίχτες. Επίσης, αποδεικνύουμε ότι υπάρχει αξιοσημείωτη διαφορά ανάμεσα στα έσοδα που προκύπτουν από ντετερμινιστικούς φιλαλήθεις μηχανισμούς και πιθανοτικούς μηχανισμούς που είναι φιλαλήθεις κατά μέσο όρο. |
| author2 |
Κακλαμάνης, Χρήστος |
| author_facet |
Κακλαμάνης, Χρήστος Κυροπούλου, Μαρία |
| format |
Thesis |
| author |
Κυροπούλου, Μαρία |
| author_sort |
Κυροπούλου, Μαρία |
| title |
Υπολογιστικά ζητήματα σε στρατηγικά παίγνια και διαδικασίες κοινωνικής επιλογής |
| title_short |
Υπολογιστικά ζητήματα σε στρατηγικά παίγνια και διαδικασίες κοινωνικής επιλογής |
| title_full |
Υπολογιστικά ζητήματα σε στρατηγικά παίγνια και διαδικασίες κοινωνικής επιλογής |
| title_fullStr |
Υπολογιστικά ζητήματα σε στρατηγικά παίγνια και διαδικασίες κοινωνικής επιλογής |
| title_full_unstemmed |
Υπολογιστικά ζητήματα σε στρατηγικά παίγνια και διαδικασίες κοινωνικής επιλογής |
| title_sort |
υπολογιστικά ζητήματα σε στρατηγικά παίγνια και διαδικασίες κοινωνικής επιλογής |
| publishDate |
2014 |
| url |
http://hdl.handle.net/10889/7774 |
| work_keys_str_mv |
AT kyropouloumaria ypologistikazētēmatasestratēgikapaigniakaidiadikasieskoinōnikēsepilogēs AT kyropouloumaria computationalaspectsinstrategicgamesandsocialchoiceprocedures |
| _version_ |
1771297345006206976 |
| spelling |
nemertes-10889-77742022-09-05T20:13:13Z Υπολογιστικά ζητήματα σε στρατηγικά παίγνια και διαδικασίες κοινωνικής επιλογής Computational aspects in strategic games and social choice procedures Κυροπούλου, Μαρία Κακλαμάνης, Χρήστος Κακλαμάνης, Χρήστος Σπυράκης, Παύλος Καραγιάννης, Ιωάννης Βαρβαρίγος, Εμμανουήλ Ζαρολιάγκης, Χρήστος Κοσμαδάκης, Σταύρος Νικολετσέας, Σωτήρης Kyropoulou, Maria Δημοπρασίες χρηματοδοτούμενης αναζήτησης Ανάλυση καταστάσεων ισορροπίας Τίμημα της αναρχίας Μοντέλο μερικής πληροφόρησης Γενικευμένος μηχανισμός δεύτερης τιμής Σχεδιασμός βέλτιστης δημοπρασίας Ντετερμινιστικοί μηχανισμοί δημοπρασίας Μοντέλο συσχετιζόμενων αξιών Sponsored search auction design Equilibrium analysis Price of anarchy Incomplete information games Generalized second price auction Optimal auction design Deterministic auctions Correlated valuations 381.170 285 467 8 Στην παρούσα διατριβή μελετάμε αγορές δημοπρασιών και εξετάζουμε διάφορες ιδιότητές τους καθώς και τον τρόπο που αυτές επηρεάζονται από τον τρόπο που συμπεριφέρονται και δρουν οι συμμετέχοντες. Η έννοια δημοπρασία αναφέρεται σε κάθε μηχανισμό, ή σύνολο κανόνων, που διέπει μια διαδικασία ανάθεσης αγαθών. Τέτοιοι μηχανισμοί είναι επιρρεπείς σε στρατηγικούς χειρισμούς (χειραγώγηση) από τους συμμετέχοντες, γεγονός που δικαιολογεί την έμφυτη δυσκολία στον σχεδιασμό τους. Σκοπός αυτής της εργασίας είναι η μελέτη σε θεωρητικό επίπεδο των ιδιοτήτων μηχανισμών δημοπρασίας έτσι ώστε να είμαστε σε θέση να προβλέψουμε, να εξηγήσουμε, ακόμα και να τροποποιήσουμε την απόδοσή τους στην πράξη. Εστιάζουμε την προσοχή μας σε δημοπρασίες χρηματοδοτούμενης αναζήτησης, οι οποίες αποτελούν την επικρατέστερη διαδικασία για την προβολή διαφημίσεων στο Διαδίκτυο. Υιοθετούμε παιγνιοθεωρητική προσέγγιση και υπολογίζουμε το Τίμημα της Αναρχίας για να φράξουμε την απώλεια αποδοτικότητας εξαιτίας της στρατηγικής συμπεριφοράς των παιχτών. Επίσης, αποδεικνύουμε εγγυήσεις εσόδων για να φράξουμε την απώλεια των εσόδων του μηχανισμού δημοπρασίας GSP (γενικευμένος μηχανισμός δεύτερης τιμής) σε αυτό το πλαίσιο. Για την ακρίβεια, ορίζουμε παραλλαγές του μηχανισμού δημοπρασίας GSP που δίνουν καλές εγγυήσεις εσόδων. Στη συνέχεια εξετάζουμε το πρόβλημα του σχεδιασμού της βέλτιστης δημοπρασίας ενός αντικειμένου. Αποδεικνύουμε ένα υπολογίσιμο φράγμα δυσκολίας στην προσέγγιση για την περίπτωση με τρεις παίχτες. Επίσης, αποδεικνύουμε ότι υπάρχει αξιοσημείωτη διαφορά ανάμεσα στα έσοδα που προκύπτουν από ντετερμινιστικούς φιλαλήθεις μηχανισμούς και πιθανοτικούς μηχανισμούς που είναι φιλαλήθεις κατά μέσο όρο. 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. 2014-06-10T14:57:18Z 2014-06-10T14:57:18Z 2014-03-05 2014-06-10 Thesis http://hdl.handle.net/10889/7774 gr Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. 0 application/pdf |
