  We study the problem of fairly dividing indivisible goods among a set of
agents under the fairness notion of Any Price Share (APS). APS is known to
dominate the widely studied Maximin share (MMS). Since an exact APS allocation
may not exist, the focus has traditionally been on the computation of
approximate APS allocations. Babaioff et al. studied the problem under additive
valuations, and asked (i) how large can the APS value be compared to the MMS
value? and (ii) what guarantees can one achieve beyond additive functions. We
partly answer these questions by considering valuations beyond additive, namely
submodular and XOS functions, with binary marginals.
  For the submodular functions with binary marginals, also known as matroid
rank functions (MRFs), we show that APS is exactly equal to MMS. Consequently,
we get that an exact APS allocation exists and can be computed efficiently
while maximizing the social welfare. Complementing this result, we show that it
is NP-hard to compute the APS value within a factor of 5/6 for submodular
valuations with three distinct marginals of {0, 1/2, 1}.
  We then consider binary XOS functions, which are immediate generalizations of
binary submodular functions in the complement free hierarchy. In contrast to
the MRFs setting, MMS and APS values are not equal under this case.
Nevertheless, we show that under binary XOS valuations, $MMS \leq APS \leq 2
\cdot MMS + 1$. Further, we show that this is almost the tightest bound we can
get using MMS, by giving an instance where $APS \geq 2 \cdot MMS$. The upper
bound on APS, implies a ~0.1222-approximation for APS under binary XOS
valuations. And the lower bound implies the non-existence of better than
0.5-APS even when agents have identical valuations, which is in sharp contrast
to the guaranteed existence of exact MMS allocation when agent valuations are
identical.
