University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    MECHANISM DESIGN WITH GENERAL UTILITIES

    Thumbnail
    View/Open
    Alaei_umd_0117E_13574.pdf (1.830Mb)
    No. of downloads: 852

    Date
    2012
    Author
    Alaei, Saeed
    Advisor
    Khuller, Samir
    Metadata
    Show full item record
    Abstract
    This 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.
    URI
    http://hdl.handle.net/1903/13244
    Collections
    • Computer Science Theses and Dissertations
    • UMD Theses and Dissertations

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility