  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. Further, 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 current 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 might be of independent
interest.
