Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17126
Τίτλος: | Χρηματικά Ανταλλάξιμη Ωφέλεια σε Συνδυαστικές Δημοπρασίες |
Συγγραφείς: | Lotidis, Kyriakos Φωτάκης Δημήτριος |
Λέξεις κλειδιά: | Σχεδιασμός Μηχανισμών Συνδυαστικές Δημοπρασίες Liquid Welfare Competitive Markets Χρηματικοί Περιορισμοί |
Ημερομηνία έκδοσης: | 31-Οκτ-2018 |
Περίληψη: | Στην παρούσα διπλωματική εργασία μελετούμε φιλαλήθεις μηχανισμούς σε Συνδυαστικές Δημοπρασίες με περιορισμούς ρευστότητας (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 |
Εμφανίζεται στις συλλογές: | Διπλωματικές Εργασίες - Theses |
Αρχεία σε αυτό το τεκμήριο:
Αρχείο | Περιγραφή | Μέγεθος | Μορφότυπος | |
---|---|---|---|---|
thesis_kyriakos_lotidis.pdf | 912.12 kB | Adobe PDF | Εμφάνιση/Άνοιγμα |
Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα.