• Login
    View Item 
    •   etd@IISc
    • Division of Physical and Mathematical Sciences
    • Mathematics (MA)
    • View Item
    •   etd@IISc
    • Division of Physical and Mathematical Sciences
    • Mathematics (MA)
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Algorithmic and Hardness Results for Fundamental Fair-Division Problems

    View/Open
    Thesis full text (3.866Mb)
    Author
    Rathi, Nidhi
    Metadata
    Show full item record
    Abstract
    The theory of fair division addresses the fundamental problem of dividing a set of resources among the participating agents in a satisfactory or meaningfully fair manner. This thesis examines the key computational challenges that arise in various settings of fair-division problems and complements the existential (and non-constructive) guarantees and various hardness results by way of developing efficient (approximation) algorithms and identifying computationally tractable instances. • Our work in fair cake division develops several algorithmic results for allocating a divisible resource (i.e., the cake) among a set of agents in a fair/economically efficient manner. While strong existence results and various hardness results exist in this setup, we develop a polynomial-time algorithm for dividing the cake in an approximately fair and efficient manner. Furthermore, we identify an encompassing property of agents’ value densities (over the cake)—the monotone likelihood ratio property (MLRP)—that enables us to prove strong algorithmic results for various notions of fairness and (economic) efficiency. • Our work in fair rent division develops a fully polynomial-time approximation scheme (FPTAS) for dividing a set of discrete resources (the rooms) and splitting the money (rents) among agents having general utility functions (continuous, monotone decreasing, and piecewise-linear), in a fair manner. Prior to our work, efficient algorithms for finding such solutions were known only for a specific set of utility functions. We com- plement the algorithmic results by proving that the fair rent division problem (under general utilities) lies in the intersection of the complexity classes, PPAD (Polynomial Parity Arguments on Directed graphs) and PLS (Polynomial Local Search). • Our work respectively addresses fair division of rent, cake (divisible), and discrete (in- divisible) goods in a partial information setting. We show that, for all these settings and under appropriate valuations, a fair (or an approximately fair) division among n agents can be efficiently computed using only the valuations of n 1 agents. The nth (secretive) agent can make an arbitrary selection after the division has been proposed and, irrespective of her choice, the computed division will admit an overall fair allocation.
    URI
    https://etd.iisc.ac.in/handle/2005/5205
    Collections
    • Mathematics (MA) [163]

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV
     

     

    Browse

    All of etd@IIScCommunities & CollectionsTitlesAuthorsAdvisorsSubjectsBy Thesis Submission DateThis CollectionTitlesAuthorsAdvisorsSubjectsBy Thesis Submission Date

    My Account

    LoginRegister

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV