  We consider the problem of fair allocation of indivisible items among $n$
agents with additive valuations, when agents have equal entitlements to the
goods, and there are no transfers. Best-of-Both-Worlds (BoBW) fairness
mechanisms aim to give all agents both an ex-ante guarantee (such as getting
the proportional share in expectation) and an ex-post guarantee. Prior BoBW
results have focused on ex-post guarantees that are based on the "up to one
item" paradigm, such as envy-free up to one item (EF1). In this work we attempt
to give every agent a high value ex-post, and specifically, a constant fraction
of his maximin share (MMS). The up to one item paradigm fails to give such a
guarantee, and it is not difficult to present examples in which previous BoBW
mechanisms give agents only a $\frac{1}{n}$ fraction of their MMS.
  Our main result is a deterministic polynomial time algorithm that computes a
distribution over allocations that is ex-ante proportional, and ex-post, every
allocation gives every agent at least his proportional share up to one item,
and more importantly, at least half of his MMS. Moreover, this last ex-post
guarantee holds even with respect to a more demanding notion of a share,
introduced in this paper, that we refer to as the truncated proportional share
(TPS). Our guarantees are nearly best possible, in the sense that one cannot
guarantee agents more than their proportional share ex-ante, and one cannot
guarantee agents more than a $\frac{n}{2n-1}$ fraction of their TPS ex-post.
