Mechanism design for resource allocation problems: algorithms and impossibility results

Abstract

The focus of this thesis is the study of resource allocation problems from both an algorithmic and a game theoretic point of view. In particular, we are interested in the following two areas within algorithmic game theory: 1) Fair division of indivisible items, where the goal is to produce allocations that satisfy a certain fairness criterion 2) Multi-item cost sharing problems, where the goal is to provide allocations and cost-sharing methods that achieve economic efficiency, under the constraint of covering the incurred cost. The first part of the thesis regards the domain of computational fair division where the objective is to allocate a set of indivisible resources to a set of agents, when there are no monetary transfers, and in a way that leaves everyone satisfied. We are interested in the connection between the exact and the approximate versions of several recently introduced relaxations of envy-freeness and proportionality. We establish several tight, or almost tight, results concerning the approximation quality that any of these notions guarantees for the others, providing an almost complete picture of this landscape. Moreover, we further explore these problems from a game theoretic perspective, where agents may have incentives to misreport their valuations. We initiate the study of mechanism design for this setting, by focusing on mechanisms that are truthful and provide approximation guarantees or the fairness notions, we are interested in. We explore the case of two agents and produce tight inapproximability results. By doing so, we obtain a clear separation between truthful and non truthful mechanisms in terms of the approximation guarantees that can be achieved. In the second part of the thesis, we study mechanism design for cost sharing settings, where a set of agents is interested in acquiring a set of items and there is also a central authority that decides how the items are shared. The provision of items usually creates a cost to the provider that needs to be covered. The goal is the design of mechanisms that are strategyproof, budget-balanced (i.e. the sum of the payments of the agents must cover exactly the cost of the provider) and achieve guarantees in terms of economic efficiency. We examine multi-item and general demand scenarios, motivated by participatory sensing applications, and we show that under these settings, the well known VCG mechanismcan be implemented in polynomial time. Furthermore we provide a modification of the Moulin-Shenker mechanism that works under the presence of multiple items, while we also propose a new mechanism that although non truthful, its Nash equilibria provide good guarantees regarding economic efficiency. Finally, we further explore cost-sharing methods under richer combinatorial domains, which is a far more challenging problem. We study the special case of symmetric submodular valuations, as well as the setting of general valuations, both under classes of subadditive cost functions. In both cases we provide mechanisms that are either optimal for the setting that we study, or match and even improve upon the guarantees and the properties of mechanisms that are considered the current state of the art.

Το επίκεντρο αυτής της διατριβής είναι η μελέτη προβλημάτων ανάθεσης αγαθών τόσο από την αλγοριθμική όσο και από την παίγνιο-θεωρητική πλευρά. Συγκεκριμένα, μας ενδιαφέρουν οι εξής δύο τομείς: 1) Η δίκαιη ανάθεση αδιαίρετων αγαθών, όπου ο στόχος είναι η παραγωγή αναθέσεων που ικανοποιούν ένα συγκεκριμένο κριτήριο δικαιοσύνης 2) Τα προβλήματα διαμοιρασμού κόστους πολλών αντικειμένων, όπου ο στόχος είναι η παραγωγή αναθέσεων και μεθόδων διαμοιρασμού κόστους, που επιτυγχάνουν το κριτήριο της κοινωνικής ωφέλειας, υπό τον περιορισμό της κάλυψης του κόστους.Και για τα δυο αυτά είδη προβλημάτων, παρέχουμε αλγορίθμους που επιτυγχάνουν βέλτιστους ή σχεδόν βέλτιστους προσεγγιστικούς παράγοντες ως προς τα κριτήρια που ανά περίπτωση μας ενδιαφέρουν, δίνοντας έτσι μια ολοκληρωμένη εικόνα του τι είναι δυνατό σε αυτά τα δυο πεδία.