Προσεγγισιμότητα Και Επαλήθευση Προσφορών Στο Σχεδιασμό Μηχανισμών

Abstract

Στα πλαίσια του Σχεδιασμού Μηχανισμών, επαλήθευση (verification) είναι η δυνατότητα που έχει ένας μηχανισμός να ελέγχει (πιθανώς εν μέρη) αν οι δηλώσεις των παικτών είναι αληθείς. Στη βιβλιογραφία έχει μελετηθεί με ποιο τρόπο μπορεί αυτή η τεχνική να χρησιμοποιηθεί ώστε να δώσει κίνητρο στους παίκτες να δηλώσουν τις πραγματικές τους προτιμήσεις, δηλαδή να καταστήσει το μηχανισμό φιλαλήθη (truthful). Η φιλαλήθεια είναι μια πολύ επιθυμητή ιδιότητα ενός μηχανισμού αλλά ακόμα και με τη χρήση επαλήθευσης δεν μπορεί να επιτευχθεί πάντα. Στόχος μας είναι να μελετήσουμε αν η χαλάρωση της απαίτησης της φιλαλήθειας μπορεί να ξεπεράσει κάποια από τα αρνητικά αποτελέσματα στη βιβλιογραφία της επαλήθευσης. Στην παρούσα διπλωματική εργασία κάνουμε ένα βήμα προς αυτή την κατεύθυνση μελετώντας απλές μη-φιλαλήθης υλοποιήσεις συνδυαστικών δημοπρασιών (combinatorial auctions) και αξιολογώντας αυτές με τη χρήση του Τιμήματος Αναρχίας (Price of Anarchy) που εκφράζει το κατά πόσο ο μηχανισμός προσεγγίζει την απόδοση ενός αντίστοιχου φιλαλήθη μηχανισμού. Αρχικά γίνεται μια ανασκόπηση της βιβλιογραφίας πάνω στην χρήση της επαλήθευσης και στην ανάλυση του Τιμήματος Αναρχίας (PoA) με έμφαση στην προσέγγιση του Tim Roughgarden που δίνει έναν ενιαίο τρόπο υπολογισμού κάτω φραγμάτων στο PoA απλών δημοπρασιών. Καταλήγουμε με το αρνητικό αποτέλεσμα ότι η επαλήθευση δεν μπορεί να ξεπεράσει τα προαναφερθέντα κάτω φράγματα και προτείνουμε νέες γραμμές έρευνας.