  The classic cake-cutting problem provides a model for addressing fair and
efficient allocation of a divisible, heterogeneous resource (metaphorically,
the cake) among agents with distinct preferences. Focusing on a standard
formulation of cake cutting, in which each agent must receive a contiguous
piece of the cake, this work establishes algorithmic and hardness results for
multiple fairness/efficiency measures.
  First, we consider the well-studied notion of envy-freeness and develop an
efficient algorithm that finds a cake division (with connected pieces) wherein
the envy is multiplicatively within a factor of 2+o(1). The same algorithm in
fact achieves an approximation ratio of 3+o(1) for the problem of finding cake
divisions with as large a Nash social welfare (NSW) as possible. NSW is another
standard measure of fairness and this work also establishes a connection
between envy-freeness and NSW: approximately envy-free cake divisions (with
connected pieces) always have near-optimal Nash social welfare. Furthermore, we
develop an approximation algorithm for maximizing the $\rho$-mean welfare--this
unifying objective, with different values of $\rho$, interpolates between
notions of fairness (NSW) and efficiency (average social welfare). Finally, we
complement these algorithmic results by proving that maximizing NSW (and, in
general, the $\rho$-mean welfare) is APX-hard in the cake-division context.
