Χρηματικά ανταλλάξιμη ωφέλεια σε συνδυαστικές δημοπρασίες - Λωτίδης, Κυριάκος (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών, 2018)
Στην παρούσα διπλωματική εργασία μελετούμε φιλαλήθεις μηχανισμούς σε Συνδυ- αστικές Δημοπρασίες με budgets . Για την περίπτωση που δεν υπάρχει περιορισμός στα bud- gets , παρόλο που υπάρχει μηχανισμός που βρίσκει τη βέλτιστη λύση για το Social Welfare , η εφαρμογή του είναι υπολογιστικά αδύνατη. Συνεπώς, πρέπει να αναζητήσουμε προσεγγισ- τικούς μηχανισμούς που να εκτελούνται αποδοτικά. Στο πλαίσιο αυτό, παρουσιάζουμε ένα διαφορετικό είδος μηχανισμών, τις δημοπρασίες αυξανόμενης τιμής, και τις ιδέες των clearing prices και Walrasian Equilibrium . Επιπλέον, παρουσιάζουμε μηχανισμούς για συνδυαστικές δημοπρασίες με χρήση demand query oracles , που εμπνεύστηκαν από την ιδέα των clearing prices , και επιτυγχάνουν τους καλύτερους λόγους προσέγγισης, μέχρι σήμερα. Αναλύοντας τα βασικά συστατικά των μηχανισμών αυτών, ερευνούμε τις προϋποθέσεις, κάτω από τις οποίες μπορούμε να επεκτείνουμε τα αποτελέσματα αυτά για το Liquid Welfare , μία μετρική μέτρησης της αποτελεσματικότητας των μηχανισμών με budget-restricted παίχτες, η οποία προτάθηκε από τους Dobzinski και Leme . ́Επειτα, δείχνουμε ότι κάποια από τα πιο γνωστά αποτελέσματα μηχανισμών για τη προσέγγιση του Social Welfare με submodular (ή XOS ) παίχτες μπορούν να προσαρμοστούν για τη μετρική του 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 των παιχτών παράγονται σαν ανεξάρτητα δείγματα από γνωστές κατανομές