  We study the problem of fair allocation for indivisible goods. We use the the
maxmin share paradigm introduced by Budish as a measure for fairness. Procaccia
and Wang (EC'14) were first to investigate this fundamental problem in the
additive setting. In contrast to what real-world experiments suggest, they show
that a maxmin guarantee (1-MMS allocation) is not always possible even when the
number of agents is limited to 3. While the existence of an approximation
solution (e.g. a $1/2$-MMS allocation) is quite straightforward, improving the
guarantee becomes subtler for larger constants. Procaccia provide a proof for
existence of a $2/3$-MMS allocation and leave the question open for better
guarantees.
  Our main contribution is an answer to the above question. We improve the
result of [Procaccia and Wang] to a $3/4$ factor in the additive setting. The
main idea for our $3/4$-MMS allocation method is clustering the agents. To this
end, we introduce three notions and techniques, namely reducibility, matching
allocation, and cycle-envy-freeness, and prove the approximation guarantee of
our algorithm via non-trivial applications of these techniques. Our analysis
involves coloring and double counting arguments that might be of independent
interest.
  One major shortcoming of the current studies on fair allocation is the
additivity assumption on the valuations. We alleviate this by extending our
results to the case of submodular, fractionally subadditive, and subadditive
settings. More precisely, we give constant approximation guarantees for
submodular and XOS agents, and a logarithmic approximation for the case of
subadditive agents. Furthermore, we complement our results by providing close
upper bounds for each class of valuation functions. Finally, we present
algorithms to find such allocations for additive, submodular, and XOS settings
in polynomial time.
