  We consider fair allocation of a set $M$ of indivisible goods to $n$
equally-entitled agents, with no monetary transfers. Every agent $i$ has a
valuation $v_i$ from some given class of valuation functions. A share $s$ is a
function that maps a pair $(v_i,n)$ to a value, with the interpretation that if
an allocation of $M$ to $n$ agents fails to give agent $i$ a bundle of value at
least equal to $s(v_i,n)$, this serves as evidence that the allocation is not
fair towards $i$. For such an interpretation to make sense, we would like the
share to be feasible, meaning that for any valuations in the class, there is an
allocation that gives every agent at least her share. The maximin share was a
natural candidate for a feasible share for additive valuations. However,
Kurokawa, Procaccia and Wang [2018] show that it is not feasible.
  We initiate a systematic study of the family of feasible shares. We say that
a share is \emph{self maximizing} if truth-telling maximizes the implied
guarantee. We show that every feasible share is dominated by some
self-maximizing and feasible share. We seek to identify those self-maximizing
feasible shares that are polynomial time computable, and offer the highest
share values. We show that a SM-dominating feasible share -- one that dominates
every self-maximizing (SM) feasible share -- does not exist for additive
valuations (and beyond). Consequently, we relax the domination property to that
of domination up to a multiplicative factor of $\rho$ (called
$\rho$-dominating). For additive valuations we present shares that are
feasible, self-maximizing and polynomial-time computable. For $n$ agents we
present such a share that is $\frac{2n}{3n-1}$-dominating. For two agents we
present such a share that is $(1 - \epsilon)$-dominating. Moreover, for these
shares we present poly-time algorithms that compute allocations that give every
agent at least her share.
