  We study fair allocation of indivisible goods among agents with additive
valuations. We obtain novel approximation guarantees for three of the strongest
fairness notions in discrete fair division, namely envy-free up to the removal
of any positively-valued good (EFx), pairwise maximin shares (PMMS), and
envy-free up to the transfer of any positively-valued good (tEFx). Our
approximation guarantees are in terms of an instance-dependent parameter
$\gamma \in (0,1]$ that upper bounds, for each indivisible good in the given
instance, the multiplicative range of nonzero values for the good across the
agents.
  First, we consider allocations wherein, between any pair of agents and up to
the removal of any positively-valued good, the envy is multiplicatively
bounded. Specifically, the current work develops a polynomial-time algorithm
that computes a $\left(
\frac{2\gamma}{\sqrt{5+4\gamma}-1}\right)$-approximately EFx allocation for any
given fair division instance with range parameter $\gamma \in (0,1]$. For
instances with $\gamma \geq 0.511$, the obtained approximation guarantee for
EFx surpasses the previously best-known approximation bound of $(\phi-1)
\approx 0.618$, here $\phi$ denotes the golden ratio.
  Furthermore, for $\gamma \in (0,1]$, we develop a polynomial-time algorithm
for finding allocations wherein the PMMS requirement is satisfied, between
every pair of agents, within a multiplicative factor of $\frac{5}{6} \gamma$.
En route to this result, we obtain novel existential and computational
guarantees for $\frac{5}{6}$-approximately PMMS allocations under restricted
additive valuations.
  Finally, we develop an algorithm that efficiently computes a
$2\gamma$-approximately tEFx allocation. Specifically, we obtain existence and
efficient computation of exact tEFx allocations for all instances with $\gamma
\in [0.5, 1]$.

Computer Science and Game Theory