Please use this identifier to cite or link to this item:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17126
Title: | Χρηματικά Ανταλλάξιμη Ωφέλεια σε Συνδυαστικές Δημοπρασίες |
Authors: | Lotidis, Kyriakos Φωτάκης Δημήτριος |
Keywords: | Σχεδιασμός Μηχανισμών Συνδυαστικές Δημοπρασίες Liquid Welfare Competitive Markets Χρηματικοί Περιορισμοί |
Issue Date: | 31-Oct-2018 |
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 των παιχτών παράγονται σαν ανεξάρτητα δείγματα από γνωστές κατανομές. |
URI: | http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17126 |
Appears in Collections: | Διπλωματικές Εργασίες - Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
thesis_kyriakos_lotidis.pdf | 912.12 kB | Adobe PDF | View/Open |
Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.