PhD Proposal: Algorithms for Finding Fair Allocations

Talk
Alireza Farhadi
Time: 
12.19.2018 16:00 to 18:00
Location: 

AVW 3258

The theory of fairness provides formal notions of fairness and mechanisms for achieving fairness in the allocation of items. Since 1948, when Hugo Steinhaus introduced the fair division, fairness has attracted an extensive attention in both computer science and economics. In this proposal, we continue this line of research and propose various results on the fair allocations of both divisible and indivisible items.In the allocation of divisible items, we study the problem of fairly allocating an undesirable item, called chore, among several players. We inspect this problem using two well-studied notions of fairness. First, we consider the envy-freeness which is the most prominent notion of fairness. It has been an open problem whether a bounded protocol can achieve envy-freeness in the allocation of a chore. We positively answer to this long-standing open problem, by providing the first discrete and bounded envy-free protocol for the chore division problem. We also study the same problem using the proportionality notion of fairness and provide an asymptotically tight lower bound for the proportional chore division.In the allocation of indivisible items, we consider the fair allocation of organs (e.g. kidneys). Transplant of an organ from a living donor is possible if the recipient (patient) happens to be medically compatible with his/her donor. This is not always the case, however, we can overcome this problem by exchanging organs between donor/patient pairs. The compatibility between a donor and a patient can be determined based on the medical characteristics, however, it is not accurate and before a transplant, a more accurate medical test should take place. We model this problem as finding a matching in stochastic graphs, and we design an approximation algorithm that requires a few number of medical tests. We also consider the allocation of indivisible items when players have unequal entitlements. We propose a natural adaptation of proportionality to this setting, and based on our notion of fairness, we provide an approximation guarantee for this problem.

Examining Committee:

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