Βιβλιοθήκη ΟΠΑ - Ψηφιακό Αποθετήριο

ΠΥΞΙΔΑ Ιδρυματικό Αποθετήριο
και Ψηφιακή Βιβλιοθήκη

Όνομα χρήστη
Κωδικός πρόσβασης

Συλλογές :	Ιδρυματικό Αποθετήριο ΟΠΑ / AUEB Institutional Repository Σχολή Επιστημών και Τεχνολογίας της Πληροφορίας / School of Informatics Τμήμα Πληροφορικής / Department of Informatics Διδακτορικές διατριβές / PhD Theses

Τίτλος :	Design and analysis of auction mechanisms: algorithms and incentives

Εναλλακτικός τίτλος :	Σχεδιασμός και ανάλυση μηχανισμών δημοπρασιών: αλγόριθμοι και κίνητρα

Δημιουργός :	Τσικιρίδης, Αρτέμ Tsikiridis, Artem

Συντελεστής :	Markakis, Evangelos (Επιβλέπων καθηγητής) Dimakis, Antonios (Εξεταστής) Karagiannis, Ioannis (Εξεταστής) Sgouritsa, Alkmini (Εξεταστής) Stamoulis, Georgios (Εξεταστής) Pagourtzis, Aris (Εξεταστής) Fotakis, Dimitris (Εξεταστής) Athens University of Economics and Business, Department of Informatics (Degree granting institution)

Τύπος :	Text

Φυσική περιγραφή :	180p.

Γλώσσα :	en

Αναγνωριστικό :	http://www.pyxida.aueb.gr/index.php?op=view_object&object_id=10560

Περίληψη :	Σε αυτή τη διατριβή, σχεδιάζουμε νέους αλγορίθμους για περιβάλλοντα συνδυαστικών δημοπρασιών ακολουθώντας μια διεπιστημονική προσέγγιση. Ταυτόχρονα, αναλύουμε την απόδοση υπαρχόντων πρωτοκόλλων δημοπρασιών και αναδεικνύουμε τις σχεδιαστικές αρχές εκείνες που επιτρέπουν εγγυήσεις απόδοσης.Στο πρώτο κομμάτι της διατριβής μελετάμε δύο υποδείγματα δημοπρασιών σημαντικών ως προς τις πρακτικές εφαρμογές τους: δημοπρασίες πυρήνα (core-selecting auctions) και δημοπρασίες πολλών αντιγράφων ενός αντικειμένου (multi-unit auctions). Αρχικά μελετούμε την έννοια του πυρήνα, όπως ορίστηκε από τους Ausubel και Milgrom. Μελετούμε το πολύτοπο που σχηματίζει ο πυρήνας σε μεγαλύτερο βάθος και αναδεικνύουμε μερικές νέες ιδιότητες. Χρησιμοποιώντας τις ιδιότητες αυτές, προτείνουμε έναν φιλαλήθη μηχανισμό που είναι ανταγωνιστικός ως προς τα MRCS έσοδα. Ο μηχανισμός αυτός είναι ο πρώτος ντετερμινιστικός, ανταγωνιστικός προς τον πυρήνα μηχανισμός για δυαδικά περιβάλλοντα δημοπρασιών μίας παραμέτρου στη βιβλιογραφία. Ακόμη, δίνουμε μια καταφατική απάντηση στην ερώτηση που είχε τεθεί στην βιβλιογραφία σχετικά με το αν υπάρχουν μη φθίνοντες (non-decreasing) MRCS μηχανισμοί. Στη συνέχεια, επικεντρωνόμαστε στις δημοπρασίες πολλών αντιγράφων ενός αντικειμένου (multi-unit auctions). Αναλύουμε δημοπρασίες διακριτής τιμής (discriminatory price), οι οποίες αποτελούν φυσική γενίκευση των δημοπρασιών πρώτης τιμής. Εξάγουμε νέα κάτω και άνω φράγματα ως προς το Τίμημα της Αναρχίας των μικτών σημείων ισορροπίας. Επιπλέον, παρουσιάζουμε έναν διαχωρισμό της κλάσης αυτής με την κλάση των Μπεϋζιανών σημείων ισορροπίας κατά Nash.Στο δεύτερο κομμάτι της διατριβής, μελετάμε δημοπρασίες προμηθειών (procurement auctions). Αρχικά, μελετάμε ένα πρόβλημα κάλυψης που προκύπτει σε γεωγραφικά μοντέλα αγορών πληθοπορισμού. Σχεδιάζουμε έναν φιλαλήθη μηχανισμό που πετυχαίνει έναν φραγμένο λόγο προσέγγισης σε σχέση με το βέλτιστο κόστος του δημοπράτη, βελτιώνοντας το καλύτερο γνωστό αποτέλεσμα της βιβλιογραφίας. Για την ίδια αντικειμενική συνάρτηση, σχεδιάζουμε έναν φιλαλήθες Πλήρως Πολυωνυμικού Χρόνου Σχήμα Προσέγγισης (FPTAS) για την περίπτωση εισόδων με σταθερό αριθμό εργασιών. Στη συνέχεια μελετάμε μια οικογένεια αντίστροφων δημοπρασιών στην οποία ο δημοπράτης έχει περιορισμένο προϋπολογισμό και οι πλειοδότες μπορούν να ανατεθούν να εκτελέσουν το καθήκον τους τμηματικά ή σε πολλά επίπεδα υπηρεσίας. Προτείνουμε δύο μηχανισμούς, έναν για κάθε περιβάλλον. In this dissertation, we propose novel algorithms for combinatorial auction environments using an interdisciplinary approach. At the same time, we also analyze the performance of existing auction protocols and highlight design principles that allow for provable performance guarantees.In the first part of the thesis we study two forward auction paradigms with practical significance: core-selecting mechanisms and multi-unit auctions. We begin with the notion of core-selecting mechanisms, as introduced by Ausubel and Milgrom. We study the core polytope in more depth and provide new properties and insights that are of independent interest. Utilizing these properties, we then propose a truthful mechanism that is competitive against the MRCS benchmark. We also answer an open question from the literature, of whether there exist MRCS non-decreasing mechanisms, in the affirmative. Next, we shift our attention to multi-unit auctions. We analyze discriminatory price auctions, the natural multi-unit extension of the (non-truthful) first price auction. We derive new lower and upper bounds on the Price of Anarchy of mixed equilibria. We also exhibit a separation result for Bayes Nash equilibria.In the second part of this dissertation, we study procurement auctions. Firstly, we study a covering problem motivated by spatial models in crowdsourcing markets. We propose a truthful mechanism that achieves a bounded approximation guarantee w.r.t. the optimal cost, improving upon the state of the art. For the same objective, we propose a truthful fully polynomial-time approximation scheme (FPTAS) for the case of inputs with a constant number of tasks. We then focus on the class of budget-feasible procurement auctions, in which agents can provide their service to the auctioneer fractionally or in many levels. We propose two mechanisms, one for each setting.

Περίληψη :

Σε αυτή τη διατριβή, σχεδιάζουμε νέους αλγορίθμους για περιβάλλοντα συνδυαστικών δημοπρασιών ακολουθώντας μια διεπιστημονική προσέγγιση. Ταυτόχρονα, αναλύουμε την απόδοση υπαρχόντων πρωτοκόλλων δημοπρασιών και αναδεικνύουμε τις σχεδιαστικές αρχές εκείνες που επιτρέπουν εγγυήσεις απόδοσης.Στο πρώτο κομμάτι της διατριβής μελετάμε δύο υποδείγματα δημοπρασιών σημαντικών ως προς τις πρακτικές εφαρμογές τους: δημοπρασίες πυρήνα (core-selecting auctions) και δημοπρασίες πολλών αντιγράφων ενός αντικειμένου (multi-unit auctions). Αρχικά μελετούμε την έννοια του πυρήνα, όπως ορίστηκε από τους Ausubel και Milgrom. Μελετούμε το πολύτοπο που σχηματίζει ο πυρήνας σε μεγαλύτερο βάθος και αναδεικνύουμε μερικές νέες ιδιότητες. Χρησιμοποιώντας τις ιδιότητες αυτές, προτείνουμε έναν φιλαλήθη μηχανισμό που είναι ανταγωνιστικός ως προς τα MRCS έσοδα. Ο μηχανισμός αυτός είναι ο πρώτος ντετερμινιστικός, ανταγωνιστικός προς τον πυρήνα μηχανισμός για δυαδικά περιβάλλοντα δημοπρασιών μίας παραμέτρου στη βιβλιογραφία. Ακόμη, δίνουμε μια καταφατική απάντηση στην ερώτηση που είχε τεθεί στην βιβλιογραφία σχετικά με το αν υπάρχουν μη φθίνοντες (non-decreasing) MRCS μηχανισμοί. Στη συνέχεια, επικεντρωνόμαστε στις δημοπρασίες πολλών αντιγράφων ενός αντικειμένου (multi-unit auctions). Αναλύουμε δημοπρασίες διακριτής τιμής (discriminatory price), οι οποίες αποτελούν φυσική γενίκευση των δημοπρασιών πρώτης τιμής. Εξάγουμε νέα κάτω και άνω φράγματα ως προς το Τίμημα της Αναρχίας των μικτών σημείων ισορροπίας. Επιπλέον, παρουσιάζουμε έναν διαχωρισμό της κλάσης αυτής με την κλάση των Μπεϋζιανών σημείων ισορροπίας κατά Nash.Στο δεύτερο κομμάτι της διατριβής, μελετάμε δημοπρασίες προμηθειών (procurement auctions). Αρχικά, μελετάμε ένα πρόβλημα κάλυψης που προκύπτει σε γεωγραφικά μοντέλα αγορών πληθοπορισμού. Σχεδιάζουμε έναν φιλαλήθη μηχανισμό που πετυχαίνει έναν φραγμένο λόγο προσέγγισης σε σχέση με το βέλτιστο κόστος του δημοπράτη, βελτιώνοντας το καλύτερο γνωστό αποτέλεσμα της βιβλιογραφίας. Για την ίδια αντικειμενική συνάρτηση, σχεδιάζουμε έναν φιλαλήθες Πλήρως Πολυωνυμικού Χρόνου Σχήμα Προσέγγισης (FPTAS) για την περίπτωση εισόδων με σταθερό αριθμό εργασιών. Στη συνέχεια μελετάμε μια οικογένεια αντίστροφων δημοπρασιών στην οποία ο δημοπράτης έχει περιορισμένο προϋπολογισμό και οι πλειοδότες μπορούν να ανατεθούν να εκτελέσουν το καθήκον τους τμηματικά ή σε πολλά επίπεδα υπηρεσίας. Προτείνουμε δύο μηχανισμούς, έναν για κάθε περιβάλλον.
In this dissertation, we propose novel algorithms for combinatorial auction environments using an interdisciplinary approach. At the same time, we also analyze the performance of existing auction protocols and highlight design principles that allow for provable performance guarantees.In the first part of the thesis we study two forward auction paradigms with practical significance: core-selecting mechanisms and multi-unit auctions. We begin with the notion of core-selecting mechanisms, as introduced by Ausubel and Milgrom. We study the core polytope in more depth and provide new properties and insights that are of independent interest. Utilizing these properties, we then propose a truthful mechanism that is competitive against the MRCS benchmark. We also answer an open question from the literature, of whether there exist MRCS non-decreasing mechanisms, in the affirmative. Next, we shift our attention to multi-unit auctions. We analyze discriminatory price auctions, the natural multi-unit extension of the (non-truthful) first price auction. We derive new lower and upper bounds on the Price of Anarchy of mixed equilibria. We also exhibit a separation result for Bayes Nash equilibria.In the second part of this dissertation, we study procurement auctions. Firstly, we study a covering problem motivated by spatial models in crowdsourcing markets. We propose a truthful mechanism that achieves a bounded approximation guarantee w.r.t. the optimal cost, improving upon the state of the art. For the same objective, we propose a truthful fully polynomial-time approximation scheme (FPTAS) for the case of inputs with a constant number of tasks. We then focus on the class of budget-feasible procurement auctions, in which agents can provide their service to the auctioneer fractionally or in many levels. We propose two mechanisms, one for each setting.

Λέξη κλειδί :	Σχεδιασμός μηχανισμών Αλγόριθμοι Αλγοριθμική θεωρία παιγνίων Mechanism design Algorithms Algorithmic game theory

Διαθέσιμο από :	2023-05-25 15:55:14

Ημερομηνία έκδοσης :	22-05-2023

Ημερομηνία κατάθεσης :	2023-05-25 15:55:14

Δικαιώματα χρήσης :	Free access

Άδεια χρήσης :

Αρχείο: Tsikiridis_2023.pdf

Τύπος: application/pdf

Είσοδος