PhD Proposal: Fairness Guarantees for Allocation Problems

Fair division problems have been vastly studied in the past 60 years. This line of research was initiated by the work of Steinhaus in 1948 in which the author introduced the cake cutting problem as follows: given a heterogeneous cake and a set of agents with different valuation functions, the goal is to find a fair allocation of the cake to the agents. In order to study this problem, several notions of fairness are proposed, the most famous of which are proportionality and envy-freeness, introduced by Steinhaus in 1948 and Foley in 1967. The fair allocation problems have been studied in both divisible and indivisible settings.For the divisible setting, we explore the "Chore Division Problem". The chore division problem is the problem of fairly dividing an object deemed undesirable among a number of agents. The object is possibly heterogeneous, and hence agents may have different valuations for different parts of the object. Chore division was first introduced by Gardner in 1970s, and is the dual problem of the celebrated cake cutting problem. In this proposal, we consider the first discrete and bounded envy-free chore division protocol for any number of agents.For the indivisible setting, we use the maximin share paradigm introduced by Budish as a measure of fairness. We improve current results on this measure of fairness in the additive setting and generalize our results for submodular, fractionally subadditive, as well as subadditive settings. We also consider the fair allocation of indivisible goods with different entitlements and address their applications in finding a criterion for identifying (Il)legal Market schemes.

Examining Committee:

Chair: Dr. MohammadTaghi Hajiaghayi Dept. rep: Dr. John Dickerson Members: Dr. David Mount