Online machine learning for bilateral trading problems

Abstract

Στα πλαίσια της παρούσας διπλωματικής εργασίας, θα ασχοληθούμε με την θεματική του «Online Learning» και τις εφαρμογές του στις «online» δημοπρασίες με διαμελάβηση. Στις μέρες μας όλες οι συναλλαγές, στις σύγχρονες ηλεκτρονικές πλατφόρμες, πραγματοποιούνται αποκλειστικά μέσω «online» δημοπρασιών σε πραγματικό χρόνο. Ο σχεδιασμός τέτοιων δημοπρασιών αλλά και η ανάλυση των ιδιοτήτων τους έχουν δώσει κίνητρο για διεξαγωγή μεγάλου όγκου ερευνών τα τελευταία χρόνια. Εστιάζοντας κυρίως στον σχεδιασμό της βέλτιστης δημοπρασίας με στόχο την μεγιστοποίηση των εσόδων του πωλητή. Συγκεκριμένα, ερευνούμε βιβλιογραφικά το πρόβλημα του «Online Learning» και παρουσιάζουμε κάποιες βασικές ιδέες και μεθόδους. Ξεκινώντας με την κατηγορία προβλημάτων «Πλήρους Πληροφορίας» με «Συμβουλή ειδικού», και «Μερικής Πληροφορίας» προβλήματα με «Κουλοχέρηδες». Με σκοπό στην συνέχεια να εμβαθύνουμε στις «online» δημοπρασίες και τις δίπλες δημοπρασίες, τις οποίες θα χρησιμοποιήσουμε παρακάτω και στο πειραματικό κομμάτι της εργασίας. Αναλυτικά, για το πειραματικό σκέλος εξετάζουμε τους αλγόριθμους που παρουσιάσαμε στην ενότητα του «Online Learning». Αρχικά επιλέγουμε τρεις «Πλήρους Πληροφορίας» αλγορίθμους, τον «Follow the Best Price» αλγόριθμο, μια τροποποιημένη εκδοχή του πρώτου την οποία αναφέρουμε ως «Follow the Best Price with Greedy sampling», και τον «Exponential Weighted Average» αλγόριθμο. Και στην συνέχεια επιλέγουμε τον «ε-Greedy» αλγόριθμο από τις «Μερικής Πληροφορίας» μεθόδους. Πραγματοποιούμε πειράματα με την χρήση των προαναφερθέντων αλγορίθμων, σε τέσσερα διαφορετικά σύνολα τιμών αγοραστών και πωλητών. Παρατηρούμε ότι σχεδόν όλοι οι αλγόριθμοι που εξετάσαμε πέτυχαν μικρά (λογαριθμικά) «Regret». Συγκρίνοντας τους αλγορίθμους μεταξύ τους, ο «Follow the Best Price» αλγόριθμος είναι ο αλγόριθμος με την καλύτερη απόδοση για τα περισσότερα σύνολα και ο «ε-Greedy» ο αλγόριθμος με την χειρότερη. Και τέλος, ο τροποποιημένος αλγόριθμος «Follow the Best Price with Greedy sampling», ξεπερνάει σε αποτελέσματα τον αρχικό «Follow the Best Price» σε μόνο ένα από τα σύνολα που εξετάστηκαν.