Προσεγγίσεις Της Ωφέλειας Κανονικοποιημένης Με Βάση Τη Ρευστότητα Σε Συνδυαστικές Δημοπρασίες

Abstract

Στην παρούσα Διπλωματική Εργασία μελετούμε φιλαλήθεις μηχανισμούς για Συνδυαστικές Δημοπρασίες, δημοπρασίες δηλαδή όπου διατίθενται πολλά αντικείμενα και οι παίκτες ενδιαφέρονται στο να αποκτήσουν κάποιο υποσύνολο αυτών, με τον επιπλέον περιορισμό ότι ο κάθε παίκτης έχει πλέον κάποιον κρυφό περιορισμό ρευστότητας (budget). Στόχος μας ήταν να μελετήσουμε τη συμπεριφορά μίας σχετικά πρόσφατα εισαχθείσας αντικειμενικής συνάρτηση στη διεθνή βιβλιογραφία: τη κοινωνική ωφέλεια υπό περιορισμούς ρευστότητας (Liquid Welfare). Το Liquid Welfare είναι ένα μέτρο που προτάθηκε από τους Dobzinski και Paes Leme και καταφέρνει να εξισορροπήσει την θέληση ενός παίκτη να αγοράσει ένα αντικείμενο και την ικανότητά του να το αγοράσει (λόγω των περιορισμών ρευστότητας). Για την ακρίβεια, το Liquid Welfare είναι το ελάχιστο μεταξύ της αξίας που έχει ένας παίκτης για κάποια ανάθεση αντικειμένων και του budget του παίκτη αυτού. Το ενδιαφέρον μας εστιάζεται στο να επεκτείνουμε και να βελτιώσουμε πρόσφατα αποτελέσματα της προσέγγισης που δίνει το Liquid Welfare για δημοπρασίες όπου έχουμε ένα διαιρέσιμο αγαθό και για submodular συνδυαστικές δημοπρασίες. Διαισθητικά, συνδυάζουμε ιδέες από τον γνωστό αλγόριθμο των Πολλαπλασιαστικών Συντελεστών του πεδίου της Μηχανικής Εκμάθησης, που μπορούν να παράξουν φιλαλήθεις μηχανισμούς, καθώς και ιδέες από τη δουλειά των Dobzinski και Paes Leme, οι οποίοι καταφέρνουν να σχεδιάσουν μηχανισμούς για την περίπτωση όπου έχουμε παίκτες με budgets.Για τους σκοπούς αυτής της διπλωματικής εργασίας πραγματοποιούμε εκτενή ανάλυση της σχετικής βιβλιογραφίας και παρουσιάζουμε στο τέλος τα δικά μας συμπεράσματα καθώς και προτάσεις για μελλοντική εργασία.