- Maximin Share Guarantees via Limited Cost-Sensitive Sharing
- Project Year:
2025
- REU Student (s):
Martin Cerny | Charles University
| Hana Salavcova | Charles University (Prague, Czech Republic)
- Student 1 Institution:
Charles University (Prague, Czech Republic)
- Student 2 Institution:
Charles University (Prague, Czech Republic)
- Project Mentor:
Arpita Biswas
- Project Mentor Area:
Computer Science
- Project Abstract:
We study the problem of fairly allocating indivisible goods when limited sharing is allowed, that is, each good may be allocated to up to k agents, while incurring a cost for sharing. While classic maximin share (MMS) allocations may not exist in many instances, we show that allowing such controlled sharing can restore fairness guarantees that are otherwise unattainable in some scenarios. We additionally propose the Sharing Maximin Share (SMMS), a natural extension of MMS to the k-sharing setting. We show the impossibility of the universal existence of an SMMS guarantee in the k-sharing setting. We further design an algorithm that guarantees a (1 - C)(k - 1)-approximate MMS allocation, where C is the maximum cost of sharing a good. Notably, when (1 - C)(k - 1) ≥ 1, our algorithm recovers an exact MMS allocation. Finally, we establish a connection between SMMS and constrained MMS (CMMS), yielding approximation guarantees for SMMS via existing CMMS results.
