Algorithmic and mechanism design aspects of problems with limited -or no - payments

Abstract

The most notable distinction between algorithm design and mechanism design is the notion of truthfulness. Typically, one of the goals of the mechanism designer is to ensure that the agents participating in the mechanism will not have any incentive to misreport their private information. Towards this goal, the payments made to the agents by the mechanism are crucial. However, there is an abundance of scenarios in microeconomics where the payments are restricted (e.g., via budget constraints) or even completely undesirable. This thesis focuses on two such problems that are indicative of the challenges that arise when the payments are limited or absent. In particular, fair division of indivisible items and reverse auctions with hard budget constraints are studied, both from the game-theoretic and the algorithmic point of view. In the first part of the thesis, we study the problem of computing allocations with maximin share guarantees, a recently introduced fairness notion. Given a set of agents and a set of goods, the objective is to find a partition so that each agent is guaranteed an approximation of his maximin share. Our main algorithmic result is a 2/3-approximation algorithm, that runs in polynomial time for any number of agents and items. Furthermore, we undertake a probabilistic analysis and provide a theoretical justification of the experimental evidence reported in the literature indicating that better approximations almost always exist.From the mechanism design point of view, this is a setting where no monetary transfers are allowed. Even for two agents and a few items, the problem becomes strictly harder than its algorithmic counterpart, and the limitations imposed by truthfulness on the approximability of the problem become apparent. We focus on the case of two players and our main result is a complete characterization of truthful mechanisms that allocate all the items. Applying this result, we derive several consequences on the design of mechanisms with fairness guarantees, such as maximin share fairness and envy-freeness up to one item.In the second part of the thesis, we study a family of reverse auctions with a budget constraint. The general algorithmic problem is to purchase a set of resources, which come at a cost, so as not to exceed a given budget and at the same time maximize a given valuation function. This framework captures the budgeted version of several well-known optimization problems, and when the resources are owned by strategic agents the goal is to design truthful and budget-feasible mechanisms.We obtain mechanisms with significantly improved approximation ratios for several subclasses of submodular valuation functions, like coverage functions and cut functions. We then provide a general scheme for designing deterministic and randomized mechanisms for a subclass of XOS problems which contains problems whose feasible set forms an independence system. Some representative problems include, among others, finding maximum weighted matchings and maximum weighted matroid members. For most of the above, only randomized mechanisms with very high approximation ratios were known prior to our results. A purely algorithmic byproduct of our work is a polynomial-time 2e/(e-1)-approximation algorithm for symmetric submodular maximization subject to a budget constraint. This is the best known factor achieved by a deterministic algorithm assuming only a value oracle for the objective function.

Η πιο αξιοσημείωτη διάκριση μεταξύ της σχεδίασης αλγορίθμων και της σχεδίασης μηχανισμών είναι η έννοια της φιλαλήθειας (truthfulness). Κατά κανόνα, ένας από τους στόχους του σχεδιαστή μηχανισμών είναι να εξασφαλίσει ότι οι παίκτες που συμμετέχουν στον μηχανισμό δεν έχουν κανένα κίνητρο να παραποιήσουν το κομμάτι της εισόδου που αποτελεί προσωπική τους πληροφορία. Για την επίτευξη του στόχου αυτού, οι πληρωμές που πραγματοποιούνται στους παίκτες από τον μηχανισμό είναι κρίσιμες. Ωστόσο, υπάρχουν πολλά σενάρια στη μικροοικονομική θεωρία όπου οι πληρωμές είναι περιορισμένες (π.χ., λόγω ύπαρξης προϋπολογισμού) ή ακόμη και εντελώς ανεπιθύμητες. Η παρούσα διδακτορική διατριβή επικεντρώνεται σε δύο τέτοια προβλήματα που είναι ενδεικτικά των προκλήσεων που προκύπτουν όταν οι πληρωμές είναι περιορισμένες ή απουσιάζουν. Συγκεκριμένα, μελετάται ο δίκαιος διαμοιρασμός μη διαιρετών αντικειμένων και οι αντίστροφες δημοπρασίες με αυστηρούς περιορισμούς προϋπολογισμού, τόσο από την παιγνιοθεωρητική όσο και από την αλγοριθμική σκοπιά. Στο πρώτο μέρος της διατριβής, μελετάμε το πρόβλημα του υπολογισμού διανομών μη διαιρετών αγαθών, οι οποίες παρέχουν εγγυήσεις ως προς τα μεγιστοελάχιστα μερίδια (maximin shares) των παικτών, μια πρόσφατα ορισμένη έννοια δικαιότητας. Δεδομένου ενός συνόλου παικτών και ενός συνόλου αγαθών, ο στόχος είναι να βρεθεί μια διανομή που να εγγυάται σε κάθε παίκτη μια προσέγγιση του μεγιστοελαχίστου μεριδίου του. Το κύριο αλγοριθμικό αποτέλεσμά μας είναι ένας 2/3-προσεγγιστικός αλγόριθμος, ο οποίος τρέχει σε πολυωνυμικό χρόνο για οποιονδήποτε αριθμό παικτών και αγαθών. Επιπλέον, επιχειρούμε μια πιθανοτική ανάλυση και παρέχουμε μια θεωρητική αιτιολόγηση των πειραματικών δεδομένων που αναφέρονται στη σχετική βιβλιογραφία και που υποδεικνύουν ότι υπάρχουν σχεδόν πάντα καλύτερες προσεγγίσεις.Από τη σκοπιά της σχεδίασης μηχανισμών, αυτό είναι ένα περιβάλλον στο οποίο δεν επιτρέπονται πληρωμές. Ακόμη και για δύο παίκτες και λίγα αγαθά, το πρόβλημα είναι αυστηρά δυσκολότερο από το αντίστοιχο αλγοριθμικό και γίνονται προφανείς οι περιορισμοί που επιβάλλει η φιλαλήθεια στην προσεγγισιμότητα του προβλήματος. Εστιάζουμε στην περίπτωση των δύο παικτών και το κύριο αποτέλεσμά μας είναι ένας πλήρης χαρακτηρισμός των φιλαληθών μηχανισμών που κατανέμουν όλα τα αγαθά. Ο χαρακτηρισμός αυτός έχει άμεσες συνέπειες στο σχεδιασμό μηχανισμών με εγγυήσεις δικαιότητας, όπως η δικαιότητα μεγιστοελαχίστου μεριδίου (maximin share fairness) και η απουσία φθόνου εξαιρουμένου το πολύ ενός αντικειμένου (envy-freeness up to one item). Στο δεύτερο μέρος της διατριβής, μελετάμε μια οικογένεια αντίστροφων δημοπρασιών με περιορισμένο προϋπολογισμό. Το γενικότερο αλγοριθμικό πρόβλημα είναι να αγοράσουμε ένα σύνολο πόρων, καθένας από τους οποίους έχει κάποιο κόστος, έτσι ώστε να μην υπερβούμε έναν δεδομένο προϋπολογισμό και ταυτόχρονα να μεγιστοποιήσουμε μια δεδομένη συνάρτηση αποτίμησης. Αυτό το πλαίσιο περιλαμβάνει τις παραλλαγές πολλών γνωστών προβλημάτων βελτιστοποίησης όπου έχει προστεθεί και ένας περιορισμός προϋπολογισμού. Όταν οι πόροι ανήκουν σε στρατηγικούς παίκτες, ο στόχος είναι να σχεδιαστούν φιλαλήθεις μηχανισμοί που δεν παραβιάζουν τον προϋπολογισμό.Παίρνουμε μηχανισμούς με σημαντικά βελτιωμένους λόγους προσέγγισης για αρκετές υποκατηγορίες υπομετρικών (submodular) συναρτήσεων, όπως οι συναρτήσεις κάλυψης (coverage functions) και οι συναρτήσεις κοπής (cut functions). Στη συνέχεια παρέχουμε ένα γενικό σχήμα για τον σχεδιασμό ντετερμινιστικών και τυχαιοποιημένων μηχανισμών για μια υποκλάση των XOS συναρτήσεων που περιέχει προβλήματα των οποίων το σύνολο εφικτών λύσεων σχηματίζει ένα σύστημα ανεξαρτησίας. Ορισμένα αντιπροσωπευτικά προβλήματα είναι, μεταξύ άλλων, η εύρεση μέγιστων σταθμισμένων ταιριασμάτων (maximum weighted matchings) και μέγιστων σταθμισμένων μελών μητροειδών (maximum weighted matroid members). Για τα περισσότερα από τα παραπάνω, πριν από τα αποτελέσματά μας, ήταν γνωστοί μόνο τυχαιοποιημένοι μηχανισμοί με πολύ υψηλούς λόγους προσέγγισης. Ένα καθαρά αλγοριθμικό υποπροϊόν της δουλειάς μας είναι ένας πολυωνυμικός 2e/(e-1)-προσεγγιστικός αλγόριθμος για το πρόβλημα της μεγιστοποίησης συμμετρικών υπομετρικών συναρτήσεων υπό περιορισμό προϋπολογισμού. Πρόκειται για τον καλύτερο γνωστό λόγο προσέγγισης που επιτυγχάνεται από ντετερμινιστικό αλγόριθμο, υποθέτοντας μόνο κλήσεις σε ένα μαντείο για την αντικειμενική συνάρτηση.