University of Patras
Υπολογιστικά ζητήματα σε στρατηγικά παίγνια και διαδικασίες κοινωνικής επιλογής
Abstract
dc:descriptionIn 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.
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 2014
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Kyropoulou, Maria
- Κυροπούλου, Μαρία
Subjects
dc:subject × 20- Δημοπρασίες χρηματοδοτούμενης αναζήτησης
- Ανάλυση καταστάσεων ισορροπίας
- Τίμημα της αναρχίας
- Μοντέλο μερικής πληροφόρησης
- Γενικευμένος μηχανισμός δεύτερης τιμής
- Σχεδιασμός βέλτιστης δημοπρασίας
- Ντετερμινιστικοί μηχανισμοί δημοπρασίας
- Μοντέλο συσχετιζόμενων αξιών
- Sponsored search auction design
- Equilibrium analysis
- Price of anarchy
- Incomplete information games
- Generalized second price auction
- Optimal auction design
- Deterministic auctions
- Correlated valuations
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/35138