Fair Cake Division Under Monotone Likelihood Ratios

Siddharth Barman () and Nidhi Rathi ()
Additional contact information
Siddharth Barman: Department of Computer Science and Automation, Indian Institute of Science, Bangalore 560012, India
Nidhi Rathi: Department of Mathematics, Indian Institute of Science, Bangalore 560012, India

Mathematics of Operations Research, 2022, vol. 47, issue 3, 1875-1903

Abstract: This work develops algorithmic results for the classic cake-cutting problem in which a divisible, heterogeneous resource (modeled as a cake) needs to be partitioned among agents with distinct preferences. We focus on a standard formulation of cake cutting wherein each agent must receive a contiguous piece of the cake. Although multiple hardness results exist in this setup for finding fair/efficient cake divisions, we show that, if the value densities of the agents satisfy the monotone likelihood ratio property (MLRP), then strong algorithmic results hold for various notions of fairness and economic efficiency. Addressing cake-cutting instances with MLRP, first we develop an algorithm that finds cake divisions (with connected pieces) that are envy free, up to an arbitrary precision. The time complexity of our algorithm is polynomial in the number of agents and the bit complexity of an underlying Lipschitz constant. We obtain similar positive results for maximizing social, egalitarian, and Nash social welfare. Many distribution families bear MLRP. In particular, this property holds if all the value densities belong to any one of the following families: Gaussian (with the same variance), linear, Poisson, and exponential distributions, linear translations of any log-concave function. Hence, through MLRP, the current work obtains novel cake-cutting algorithms for multiple distribution families.

Keywords: Primary: 91B32; secondary: 91B14; cake cutting; monotone likelihood ratio property; envy-freeness; social welfare; Nash social welfare; egalitarian welfare (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1192 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:3:p:1875-1903

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().