Design and analysis of auction mechanisms
Authors: Τσικιρίδης Αρτέμ 
Published: May 2023

Σε αυτή τη διατριβή, σχεδιάζουμε νέους αλγορίθμους για περιβάλλοντα συνδυαστικών δημοπρασιών ακολουθώντας μια διεπιστημονική προσέγγιση. Ταυτόχρονα, αναλύουμε την απόδοση υπαρχόντων πρωτοκόλλων δημοπρασιών και αναδεικνύουμε τις σχεδιαστικές αρχές εκείνες που επιτρέπουν εγγυήσεις απόδοσης.Στο πρώτο κομμάτι της διατριβής μελετάμε δύο υποδείγματα δημοπρασιών σημαντικών ως προς τις πρακτικές εφαρμογές τους: δημοπρασίες πυρήνα (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. Στη συνέχεια μελετάμε μια οικογένεια αντίστροφων δημοπρασιών στην οποία ο δημοπράτης έχει περιορισμένο προϋπολογισμό και οι πλειοδότες μπορούν να ανατεθούν να εκτελέσουν το καθήκον τους τμηματικά ή σε πολλά επίπεδα υπηρεσίας. Προτείνουμε δύο μηχανισμούς, έναν για κάθε περιβάλλον. Ο μηχανισμός για το περιβάλλον στο οποίο οι παίκτες μπορούν να προσληφθούν τμηματικά βελτιώνει την υπάρχουσα βιβλιογραφία, ενώ ο μηχανισμός για πολλαπλά επίπεδα υπηρεσίας είναι ο πρώτος γνωστός φιλαλήθης μηχανισμός με σταθερό λόγο προσέγγισης για αυτό το περιβάλλον.Ολοκληρώνουμε την διατριβή με μια εκτενή συζήτηση, καθώς και με ανοικτά προβλήματα και κατευθύνσεις για μελλοντική έρευνα στον πεδίο του σχεδιασμού μηχανισμών για περιβάλλοντα δημοπρασιών.