Learning reserve prices in online repeated reverse auctions

Abstract

Στην παρούσα διατριβή εμπνεόμαστε από την εργασία των Roughgarden και Wang [1], και εξετάζουμε το πρόβλημα του υπολογισμού reserve prices σε ακολουθίες αντίστροφων δημοπρασιών Vickrey για πολλαπλά αντικείμενα ιδίου τύπου. Ασχολούμαστε με δύο βασικά σενάρια αυτής της κατηγορίας προβλημάτων. Τον υπολογισμό non-anonymous reserve prices, όπου κάθε πλειοδότης λαμβάνει ένα μοναδικό reserve price, και τον υπολογισμό ενός reserve price που ισχύει για όλους τους πλειοδότες. Τα reserve prices που υπολογίζουμε και στις δύο περιπτώσεις αφορούν το σύνολο των αντικειμένων που αγοράζει κάθε bidder. Για το πρώτο σενάριο, παρουσιάζουμε έναν offline αλγόριθμο που επιτυγχάνει θεωρητικό ανώτατο όριο 2 για την αναλογία μεταξύ του «κέρδους» που επιτυγχάνει η βέλτιστη λύση και του κέρδους που εξασφαλίζει ο αλγόριθμός μας, και τον επεκτείνουμε σε online περιβάλλον χρησιμοποιώντας τον αλγόριθμο Follow the Perturbed Leader (FTPL). Για το δεύτερο σενάριο, προτείνουμε έναν offline αλγόριθμο που επιτυγχάνει ανώτατο όριο n για την αναλογία μεταξύ του «κέρδους» που επιτυγχάνει η βέλτιστη λύση και του κέρδους που εξασφαλίζει ο αλγόριθμός μας και τον προσαρμόζουμε σε online περιβάλλον χρησιμοποιώντας το πλαίσιο Multiplicative Weights Update (MWU). Μέσω πειραμάτων αξιολογούμε την απόδοση των αλγορίθμων, χρησιμοποιώντας μετρικές όπως το μέσο ημερήσιο surplus (κέρδος) και το μέσο ημερήσιο regret. Τα bids για κάθε bidder στα πειράματα μας δημιουργούνται με χρήση ενός autoregressive model, ώστε να κάνουμε καλύτερη προσομοίωση ρεαλιστικών συνθηκών δημοπρασιών. Τα αποτελέσματά μας αποκαλύπτουν ότι η λύση που χρησιμοποιεί εξατομικευμένα reserve prices υπερέχουν σε απόδοση έναντι εκείνων που χρησιμοποιούν μία ενιαία τιμή reserve price, όσον αφορά το surplus και το regret. Επίσης, δείχνουμε τη σημαντική επίδραση της ρύθμισης παραμέτρων στην απόδοση αυτών των αλγορίθμων, υπογραμμίζοντας την ευελιξία των μεθόδων μας σε διαφορετικά περιβάλλοντα δημοπρασιών. Επιπλέον, αναπτύξαμε μια τροποποιημένη έκδοση του FTPL, με την ονομασία FTPL-GLPD, η οποία ενσωματώνει δυναμικά ιστορικά δεδομένα, επιτυγχάνοντας καλύτερη απόδοση στις περισσότερες περιπτώσεις των πειραμάτων μας. Η παρούσα εργασία παρέχει ένα πλαίσιο για τον υπολογισμό reserve prices σε δημοπρασίες, ενώ ταυτόχρονα παρουσιάζει και τη σύγκριση μεταξύ ενός αλγορίθμου που υπολογίζει ένα reserve price για κάθε bidder και ενός αλγορίθμου που υπολογίζει ένα reserve price καθολικά για όλους τους bidders.