Incentive-centered design of money-free mechanisms

Abstract

This thesis serves as a step toward a better understanding of how to design fair and efficient multiagent resource allocation systems by bringing the incentives of the participating agents to the center of the design process. As the quality of these systems critically depends on the ways in which the participants interact with each other and with the system, an ill-designed set of incentives can lead to severe inefficiencies. The special focus of this work is on the problems that arise when the use of monetary exchanges between the system and the participants is prohibited. This is a common restriction that substantially complicates the designer’s task; we nevertheless provide a sequence of positive results in the form of mechanisms that maximize efficiency or fairness despite the possibly self-interested behavior of the participating agents. The first part of this work is a contribution to the literature on approximate mechanism design without money. Given a set of divisible resources, our goal is to design a mechanism that allocates them among the agents. The main complication here is due to the fact that the agents’ preferences over different allocations may not be known to the system. Therefore, the mechanism needs to be designed in such a way that it is in the best interest of every agent to report the truth about her preferences; since monetary rewards and penalties cannot be used in order to elicit the truth, a much more delicate regulation of the resource allocation is necessary. The second part of this work concerns the design of money-free resource allocation mechanisms for decentralized multiagent systems. As the world has become increasingly interconnected, such systems are using more and more resources that are geographically dispersed; to provide scalability in these systems, the mechanisms need to be decentralized. That is, the allocation decisions for any given resource should not assume global information regarding the system’s resources or participants. We approach this restriction by using coordination mechanisms: simple resource allocation policies, each of which controls only one of the resources and uses only local information regarding the state of the system.

Αυτή η διατριβή προσφέρει ένα βήμα προς την καλύτερη κατανόηση μεθόδων σχεδιασμού δίκαιων και αποτελεσματικών συστημάτων κατανομής πόρων μεταξύ πολλαπλών πρακτόρων, φέρνοντας τα κίνητρα των πρακτόρων αυτών στο επίκεντρο της διαδικασίας σχεδιασμού. Καθώς η ποιότητα αυτών των συστημάτων εξαρτάται σε μεγάλο βαθμό από τους τρόπους με τους οποίους οι συμμετέχοντες αλληλεπιδρούν μεταξύ τους και με το σύστημα, ένα εσφαλμένα σχεδιασμένο σύνολο κινήτρων μπορεί να οδηγήσει σε μεγάλη αναποτελεσματικότητα. Η εστίαση αυτής της εργασίας είναι στα προβλήματα που προκύπτουν όταν απαγορεύεται η χρήση νομισματικών ανταλλαγών μεταξύ του συστήματος και των συμμετεχόντων. Αυτός είναι ένας κοινός περιορισμός που περιπλέκει σε μεγάλο βαθμό το έργο του σχεδιαστή. Ωστόσο, παρέχουμε μια σειρά θετικών αποτελεσμάτων με τη μορφή μηχανισμών που μεγιστοποιούν την αποτελεσματικότητα ή τη δικαιοσύνη παρά την πιθανώς ιδιοτελή συμπεριφορά των συμμετεχόντων παραγόντων. Το πρώτο μέρος αυτής της εργασίας είναι μια συνεισφορά στη βιβλιογραφία του σχεδιασμού προσεγγιστικών μηχανισμών χωρίς χρήματα. Δεδομένου ενός συνόλου πόρων, στόχος μας είναι να σχεδιάσουμε έναν μηχανισμό που τους κατανέμει μεταξύ των πρακτόρων. Η κύρια περιπλοκή εδώ οφείλεται στο γεγονός ότι οι προτιμήσεις των πρακτόρων έναντι διαφορετικών κατανομών ενδέχεται να μην είναι γνωστές στο σύστημα. Επομένως, ο μηχανισμός πρέπει να σχεδιαστεί με τέτοιο τρόπο ώστε να είναι προς το συμφέρον του κάθε πράκτορα να αναφέρει την αλήθεια σχετικά με τις προτιμήσεις του. Δεδομένου ότι δεν μπορούν να χρησιμοποιηθούν χρηματικές ανταμοιβές και ποινές για να αποκαλυφθεί η αλήθεια, είναι απαραίτητη μια πολύ πιο λεπτή ρύθμιση της κατανομής των πόρων. Το δεύτερο μέρος αυτής της εργασίας αφορά το σχεδιασμό μηχανισμών κατανομής πόρων χωρίς χρήματα για κατανεμημένα συστήματα πολλών πρακτόρων. Καθώς ο κόσμος γίνεται όλο και πιο διασυνδεδεμένος, τέτοια συστήματα χρησιμοποιούν όλο και περισσότερους πόρους που είναι γεωγραφικά διασκορπισμένοι· Για να μπορούν να κλιμακωθούν αυτά τα συστήματα, οι μηχανισμοί πρέπει να είναι αποκεντρωμένοι. Δηλαδή, οι αποφάσεις κατανομής για οποιονδήποτε δεδομένο πόρο δεν πρέπει να προϋποθέτουν κεντρική πληροφόρηση σχετικά με τους διαθέσιμους πόρους ή σχετικά με τους πράκτορες που συμμετέχουν στο σύστημα. Στη διατριβή αυτή πετυχαίνουμε αυτόν τον περιορισμό χρησιμοποιώντας κατανεμημένους μηχανισμούς συντονισμού: απλές πολιτικές κατανομής πόρων, καθεμία από τις οποίες ελέγχει μόνο έναν από τους πόρους και χρησιμοποιεί μόνο τοπικές πληροφορίες σχετικά με την κατάσταση του συστήματος.