Χρηματικά Ανταλλάξιμη Ωφέλεια σε Συνδυαστικές Δημοπρασίες

Abstract

Στην παρούσα διπλωματική εργασία μελετούμε φιλαλήθεις μηχανισμούς σε Συνδυαστικές Δημοπρασίες με περιορισμούς ρευστότητας (budgets). Αρχικά, παρουσιάζουμε κάποιους από τους μηχανισμούς για συνδυαστικές δημοπρασίες χωρίς budgets με χρήση demand query oracles που επιτυγχάνουν τους καλύτερους λόγους προσέγγισης μέχρι σήμερα. Αναλύοντας τα βασικά συστατικά των μηχανισμών αυτών, ερευνούμε τις προϋποθέσεις, κάτω από τις οποίες μπορούμε να επεκτείνουμε τα αποτελέσματα αυτά για το Liquid Welfare, μία μετρική μέτρησης της αποτελεσματικότητας των μηχανισμών με budget-restricted παίχτες, η οποία προτάθηκε από τους Dobzinski και Leme. Έπειτα, δείχνουμε ότι κάποια από τα πιο γνωστά αποτελέσματα μηχανισμών για τη προσέγγιση του Social Welfare με submodular παίχτες μπορούν να προσαρμοστούν για τη μετρική του Liquid Welfare. Πιο συγκεκριμένα, για τη βελτιστοποίηση του Liquid Welfare σε συνδυαστικές δημοπρασίες με submodular παίχτες, παίρνουμε ένα φιλαλήθη O(log m)-προσεγγιστικό μηχανισμό, όπου m ο αριθμός των αντικειμένων, προσαρμόζοντας το μηχανισμό των Krysta και V\"ocking. Στη συνέχεια, με βάση την ιδέα του large market assumption, παρουσιάζουμε μία νέα έννοια για ανταγωνιστικές αγορές (competitive markets) και δείχνουμε ότι σε τέτοιες αγορές, το Liquid Welfare μπορεί να προσεγγιστεί με ένα σταθερό παράγοντα. Τέλος, για το Bayesian setting, προσαρμόζοντας τα αποτελέσματα των Feldman et al., παίρνουμε έναν φιλαλήθη O(1)-προσεγγιστικό μηχανισμό για την περίπτωση που τα valuation των παιχτών παράγονται σαν ανεξάρτητα δείγματα από γνωστές κατανομές.