1/2 - Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations

Chandra Chekuri, Pooja Kulkarni, Rucha Kulkarni, Ruta Mehta

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We study fair distribution of a collection of m indivisible goods among a group of n agents, using the widely recognized fairness principles of Maximin Share (MMS) and Any Price Share (APS). These principles have undergone thorough investigation within the context of additive valuations. We explore these notions for valuations that extend beyond additivity. First, we study approximate MMS under the separable (piecewise-linear) concave (SPLC) valuations, an important class generalizing additive, where the best known factor was 1/3-MMS. We show that 1/2-MMS allocation exists and can be computed in polynomial time, significantly improving the state-of-the-art. We note that SPLC valuations introduce an elevated level of intricacy in contrast to additive. For instance, the MMS value of an agent can be as high as her value for the entire set of items. Additionally, the equilibrium computation problem, which is polynomial-time for additive valuations, becomes intractable for SPLC. We use a relax-and-round paradigm that goes through competitive equilibrium and LP relaxation. Our result extends to give (symmetric) 1/2-APS, a stronger guarantee than MMS. APS is a stronger notion that generalizes MMS by allowing agents with arbitrary entitlements. We study the approximation of APS under submodular valuation functions. We design and analyze a simple greedy algorithm using concave extensions of submodular functions. We prove that the algorithm gives a 1/3-APS allocation which matches the best-known factor. Concave extensions are hard to compute in polynomial time and are, therefore, generally not used in approximation algorithms. Our approach shows a way to utilize it within analysis (while bypassing its computation), and hence might be of independent interest.

Original languageEnglish (US)
Title of host publicationAAAI-24 Technical Tracks 9
EditorsMichael Wooldridge, Jennifer Dy, Sriraam Natarajan
PublisherAssociation for the Advancement of Artificial Intelligence
Number of pages8
ISBN (Electronic)1577358872, 9781577358879
StatePublished - Mar 25 2024
Event38th AAAI Conference on Artificial Intelligence, AAAI 2024 - Vancouver, Canada
Duration: Feb 20 2024Feb 27 2024

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468


Conference38th AAAI Conference on Artificial Intelligence, AAAI 2024


  • GTEP: Fair Division
  • GTEP: Auctions and Market-Based Systems

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of '1/2 - Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations'. Together they form a unique fingerprint.

Cite this