Design and analysis of auction mechanisms: algorithms and incentives

Abstract

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. Such mechanisms have overall good revenue guarantees, but are known to provide incentives to bidders for misreporting their preferences. Current research has focused on identifying core-selecting mechanisms with minimal incentives to deviate from truth-telling, such as Minimum-Revenue Core-Selecting (MRCS) rules, or proposing truthful mechanisms whose revenue is competitive against core outcomes. Our results contribute to both of these directions. 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, the first deterministic core-competitive mechanism for binary single-parameter domains. 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, a class of auctions first studied by Vickrey. We analyze discriminatory price auctions, the natural multi-unit extension of the (non-truthful) first price auction. We consider bidders with capped-additive valuations and establish properties that capture the sources of inefficiency. We derive new lower and upper bounds on the Price of Anarchy of mixed equilibria, showing a complete characterization of inefficient equilibria and a tight upper bound for the case of two bidders. We also show that the Price of Anarchy is strictly worse for multiple bidders and we 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, where tasks are ordered according to some geographic or temporal criterion. 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, a generalization of the minimum knapsack problem. 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. The mechanism for divisible agents improves upon the known state of the art, whereas the mechanism for the multiple levels of service is the first truthful and budget-feasible mechanism that achieves a constant approximation for this setting.We conclude the dissertation with an extended discussion along with open problems and directions for future research in algorithmic mechanism design for auction environments.

Σε αυτή τη διατριβή, σχεδιάζουμε νέους αλγορίθμους για περιβάλλοντα συνδυαστικών δημοπρασιών ακολουθώντας μια διεπιστημονική προσέγγιση. Ταυτόχρονα, αναλύουμε την απόδοση υπαρχόντων πρωτοκόλλων δημοπρασιών και αναδεικνύουμε τις σχεδιαστικές αρχές εκείνες που επιτρέπουν εγγυήσεις απόδοσης.Στο πρώτο κομμάτι της διατριβής μελετάμε δύο υποδείγματα δημοπρασιών σημαντικών ως προς τις πρακτικές εφαρμογές τους: δημοπρασίες πυρήνα (core-selecting auctions) και δημοπρασίες πολλών αντιγράφων ενός αντικειμένου (multi-unit auctions). Αρχικά μελετούμε την έννοια του πυρήνα, όπως ορίστηκε από τους Ausubelκαι Milgrom. Οι μηχανισμοί αυτοί, παρά το γεγονός πως προσφέρουν συνολικά ικανοποιητικές εγγυήσεις ως προς τα έσοδα του δημοπράτη, παρέχουν κίνητρα στους πλειοδότες να μη δηλώνουν τις πραγματικές τους προτιμήσεις. Επομένως, ένα από τα κύρια ζητούμενα στην βιβλιογραφία είναι ο προσδιορισμός εκείνων των μηχανισμών πυρήνα που παρέχουν στους πλειοδότες τα ελάχιστα δυνατά τέτοια κίνητρα, όπως οι Μηχανισμοί Πυρήνα Ελαχίστων Εσόδων (MRCS), ή η εύρεση μηχανισμών που είναι φιλαλήθεις με έσοδα ανταγωνιστικά ως προς τα αποτελέσματα των μηχανισμών πυρήνα. Τα αποτελέσματά μας συνεισφέρουν ως προς αμφότερες κατευθύνσεις. Αρχικά, μελετούμε το πολύτοπο που σχηματίζει ο πυρήνας σε μεγαλύτερο βάθος και αναδεικνύουμε μερικές νέες ιδιότητες. Χρησιμοποιώντας τις ιδιότητες αυτές, προτείνουμε έναν φιλαλήθη μηχανισμό που είναι ανταγωνιστικός ως προς τα MRCS έσοδα. Ο μηχανισμός αυτός είναι ο πρώτος ντετερμινιστικός, ανταγωνιστικός προς τον πυρήνα μηχανισμός για δυαδικά περιβάλλοντα δημοπρασιών μίας παραμέτρου στη βιβλιογραφία. Ακόμη, δίνουμε μια καταφατική απάντηση στην ερώτηση που είχε τεθεί στην βιβλιογραφία σχετικά με το αν υπάρχουν μη φθίνοντες (non-decreasing) MRCS μηχανισμοί. Στη συνέχεια, επικεντρωνόμαστε στις δημοπρασίες πολλών αντιγράφων ενός αντικειμένου (multi-unit auctions), μια κλάση δημοπρασιών που μελετήθηκε πρώτη φορά από τον Vickrey. Αναλύουμε δημοπρασίες διακριτής τιμής (discriminatory price), οι οποίες αποτελούν φυσική γενίκευση των δημοπρασιών πρώτης τιμής, γνωστών για την μη φιλαλήθειά τους. Στην μελέτη μας, λαμβάνουμε υπόψη με συναρτήσεις αξίας τύπου capped-additive και αποδεικνύουμε ιδιότητες που συλλαμβάνουν τις πήγες μη αποδοτικότητας. Στη συνέχεια εξάγουμε νέα κάτω και άνω φράγματα ως προς το Τίμημα της Αναρχίας των μικτών σημείων ισορροπίας, δείχνοντας έναν πλήρη χαρακτηρισμό των μη αποδοτικών σημείων ισορροπίας καθώς και ένα ακριβές άνω φράγμα για την περίπτωση των δύο παικτών. Τέλος, δείχνουμε πως το Τίμημα της Αναρχίας είναι αυστηρά χειρότερο για την περίπτωση πολλών παικτών και παρουσιάζουμε έναν διαχωρισμό της κλάσης αυτής με την κλάση των Μπεϋζιανών σημείων ισορροπίας κατά Nash.Στο δεύτερο κομμάτι της διατριβής, μελετάμε δημοπρασίες προμηθειών (procurement auctions). Αρχικά, μελετάμε ένα πρόβλημα κάλυψης που προκύπτει σε γεωγραφικά μοντέλα αγορών πληθοπορισμού, στα οποία οι εργασίες είναι ταξινομημένες με βάση γεωγραφικά ή χρονικά κριτήρια. Σχεδιάζουμε έναν φιλαλήθη μηχανισμό που πετυχαίνει έναν φραγμένο λόγο προσέγγισης σε σχέση με το βέλτιστο κόστος του δημοπράτη, βελτιώνοντας το καλύτερο γνωστό αποτέλεσμα της βιβλιογραφίας. Για την ίδια αντικειμενική συνάρτηση, σχεδιάζουμε έναν φιλαλήθες Πλήρως Πολυωνυμικού Χρόνου Σχήμα Προσέγγισης (FPTAS) για την περίπτωση εισόδων με σταθερό αριθμό εργασιών, μια γενίκευση του προβλήματος minimum knapsack. Στη συνέχεια μελετάμε μια οικογένεια αντίστροφων δημοπρασιών στην οποία ο δημοπράτης έχει περιορισμένο προϋπολογισμό και οι πλειοδότες μπορούν να ανατεθούν να εκτελέσουν το καθήκον τους τμηματικά ή σε πολλά επίπεδα υπηρεσίας. Προτείνουμε δύο μηχανισμούς, έναν για κάθε περιβάλλον. Ο μηχανισμός για το περιβάλλον στο οποίο οι παίκτες μπορούν να προσληφθούν τμηματικά βελτιώνει την υπάρχουσα βιβλιογραφία, ενώ ο μηχανισμός για πολλαπλά επίπεδα υπηρεσίας είναι ο πρώτος γνωστός φιλαλήθης μηχανισμός με σταθερό λόγο προσέγγισης για αυτό το περιβάλλον.Ολοκληρώνουμε την διατριβή με μια εκτενή συζήτηση, καθώς και με ανοικτά προβλήματα και κατευθύνσεις για μελλοντική έρευνα στον πεδίο του σχεδιασμού μηχανισμών για περιβάλλοντα δημοπρασιών.