THE DISSERTATION DEFENSE FOR THE DEGREE OF Ph.D. IN COMPUTER SCIENCE FOR
Saeed Alaei
We typically assume that the input to an algorithm is not affected by how the algorithm computes its output. However this assumption is not true when the input comes from strategic agents that have their own preferences over the possible outcomes of the algorithm. For example, consider the problem of matching a set of items to a set of agents. The problem can be cast as a weighted matching in a bipartite graph in which the weight of the edge from an agent to an item represents the valuation of the agent for that item. The input to the problem consists of the edge weights which are reported by the agents. However, a strategic agent would try to manipulate the matching outcome by misreporting her valuations in order to receive a better item (i.e., over reporting her value for the most preferred item or under reporting her value for the less preferred items). It can be shown that the weighted matching algorithm can be accompanied by a payment scheme that would incentivize the agents to report truth- fully. In this case the matching algorithm together with the payment scheme comprise a truthful mechanism. A mechanism design problem, in general, is an optimization problem where the input comes from self interested and strategic agents who may mis-report their information to manipulate the outcome in their favor. Consequently, the optimality of a mechanism is measured with respect to the true input and not the reported input. To design an optimal mechanism, without loss of generality, one can restrict attention only to truthful mechanisms, i.e., mechanisms that incentivize the agents to report truthful. Unfortunately enforcing truthfulness largely increases the computational complexity of designing optimal mechanisms, except for welfare maximizing mechanism (e.g., mechanisms whose objective is to maximize the total welfare of the agents). This increased computational complexity is due to the requirement of truthfulness. Enforcing truthfulness requires simultaneously optimizing the mechanism's outcome for all possible inputs and not just the reported input, however the number of possible input profiles grows exponentially in the number of agents.
Our main contribution is to characterize fundamental structural properties of optimization problems arising in mechanism design and to exploit them to design general frameworks and techniques for efficiently solving the underlying problems. Not only do our characterizations allow for efficient computation, they also reveal qualitative characteristics of optimal mechanisms which are important even from a non-computational standpoint. Furthermore, most of our techniques are widely applicable to optimization problems outside of mechanism design such as online algorithms or stochastic optimization.
Our frameworks can be summarized as follows. When the input to an optimization problem (e.g., a mechanism design problem) comes from independent sources (e.g., independent agents), the complexity of the problem can be exponentially reduced by (i) decomposing the problem into smaller subproblems, each one involving one input source, (ii) simultaneously optimizing the subproblems subject to certain relaxation of coupling constraints, and (iii) combining the solutions of the subproblems in a certain way to obtain an (approximately) optimal solution for the original problem.
We use our proposed framework to construct optimal or approximately optima mechanisms for several settings previously considered in the literature and to improve upon the best previously known results. We also present applications of our techniques to non-mechanism design problems such as online stochastic generalized assignment problem which itself captures online and stochastic versions of various other problems such as resource allocation and job scheduling.
Examining Committee:
Committee Chair: Dr. Samir Khuller
Dean's Representative: Dr. Lawrence Ausubel
Committee Members: Dr. Neil Spring
Dr. Mohammad Taghi Hajiaghayi
Dr. Jason Hartline