Tata Institute of Fundamental Research
Fair Cake Division
STCS Student Seminar
Speaker:
Nidhi Rathi (IISc Bangalore)
Organiser:
Prabhat Kumar Jha
Date:
Friday, 16 Apr 2021, 17:15 to 18:15
Venue:
(Scan to add to calendar)
Abstract:
The theory of Fair Division addresses the fundamental problem of allocating goods among agents with equal entitlements but distinct preferences. The classic cake-cutting problem provides a model for addressing fair and efficient allocation of a divisible, heterogeneous resource (metaphorically, the cake) among agents with varied preferences. Classic results of Stromquist (1980) and Su (1999) show that envy-free (fair) cake divisions (with contiguous pieces) are guaranteed to exist under mild conditions. These strong existential results follow from fixed-point theorems and stand without an algorithmic counterpart.
In this talk, I will present two of the recent results that complements the existential (and non-constructive) guarantees and various hardness results either by developing polynomial-time approximation algorithms or by identifying computationally tractable instances for fair cake division. Our work identifies a broad class of cake division instances that essentially admits a polynomial time algorithm for computing fair and efficient allocations. In particular, our algorithmic result holds when (all) agents' valuations are induced either by linear translations of any log-concave function, Gaussian, exponential, linear, or binomial distributions.
Joint work with Siddharth Barman, Eshwar Ram Arunchaleswaran and Rachitesh Kumar.
https://arxiv.org/abs/2006.00481
https://arxiv.org/abs/1907.11019
Zoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
| Speaker: | Nidhi Rathi (IISc Bangalore) |
| Organiser: | Prabhat Kumar Jha |
| Date: | Friday, 16 Apr 2021, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
The theory of Fair Division addresses the fundamental problem of allocating goods among agents with equal entitlements but distinct preferences. The classic cake-cutting problem provides a model for addressing fair and efficient allocation of a divisible, heterogeneous resource (metaphorically, the cake) among agents with varied preferences. Classic results of Stromquist (1980) and Su (1999) show that envy-free (fair) cake divisions (with contiguous pieces) are guaranteed to exist under mild conditions. These strong existential results follow from fixed-point theorems and stand without an algorithmic counterpart.
In this talk, I will present two of the recent results that complements the existential (and non-constructive) guarantees and various hardness results either by developing polynomial-time approximation algorithms or by identifying computationally tractable instances for fair cake division. Our work identifies a broad class of cake division instances that essentially admits a polynomial time algorithm for computing fair and efficient allocations. In particular, our algorithmic result holds when (all) agents' valuations are induced either by linear translations of any log-concave function, Gaussian, exponential, linear, or binomial distributions.
Joint work with Siddharth Barman, Eshwar Ram Arunchaleswaran and Rachitesh Kumar.
https://arxiv.org/abs/2006.00481
https://arxiv.org/abs/1907.11019
Zoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
In this talk, I will present two of the recent results that complements the existential (and non-constructive) guarantees and various hardness results either by developing polynomial-time approximation algorithms or by identifying computationally tractable instances for fair cake division. Our work identifies a broad class of cake division instances that essentially admits a polynomial time algorithm for computing fair and efficient allocations. In particular, our algorithmic result holds when (all) agents' valuations are induced either by linear translations of any log-concave function, Gaussian, exponential, linear, or binomial distributions.
Joint work with Siddharth Barman, Eshwar Ram Arunchaleswaran and Rachitesh Kumar.
https://arxiv.org/abs/2006.00481
https://arxiv.org/abs/1907.11019
Zoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09