MECHANISM DESIGN WITH GENERAL UTILITIES

dc.contributor.advisorKhuller, Samiren_US
dc.contributor.authorAlaei, Saeeden_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2012-10-11T06:13:10Z
dc.date.available2012-10-11T06:13:10Z
dc.date.issued2012en_US
dc.description.abstractThis thesis studies mechanism design from an optimization perspective. 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 optimal 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.en_US
dc.identifier.urihttp://hdl.handle.net/1903/13244
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pqcontrolledEconomicsen_US
dc.subject.pqcontrolledApplied mathematicsen_US
dc.subject.pquncontrolledBayesianen_US
dc.subject.pquncontrolledMechanism Designen_US
dc.subject.pquncontrolledOptimizationen_US
dc.titleMECHANISM DESIGN WITH GENERAL UTILITIESen_US
dc.typeDissertationen_US

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
Alaei_umd_0117E_13574.pdf
Size:
1.83 MB
Format:
Adobe Portable Document Format