  We study the problem of computing maximin share guarantees, a recently
introduced fairness notion. Given a set of $n$ agents and a set of goods, the
maximin share of a single agent is the best that she can guarantee to herself,
if she would be allowed to partition the goods in any way she prefers, into $n$
bundles, and then receive her least desirable bundle. The objective then in our
problem is to find a partition, so that each agent is guaranteed her maximin
share. In settings with indivisible goods, such allocations are not guaranteed
to exist, so we resort to approximation algorithms. Our main result is a
$2/3$-approximation, that runs in polynomial time for any number of agents.
This improves upon the algorithm of Procaccia and Wang, which also produces a
$2/3$-approximation but runs in polynomial time only for a constant number of
agents. To achieve this, we redesign certain parts of their algorithm.
Furthermore, motivated by the apparent difficulty, both theoretically and
experimentally, in finding lower bounds on the existence of approximate
solutions, we undertake a probabilistic analysis. We prove that in randomly
generated instances, with high probability there exists a maximin share
allocation. This can be seen as a justification of the experimental evidence
reported in relevant works. Finally, we provide further positive results for
two special cases that arise from previous works. The first one is the
intriguing case of $3$ agents, for which it is already known that exact maximin
share allocations do not always exist (contrary to the case of $2$ agents). We
provide a $7/8$-approximation algorithm, improving the previously known result
of $3/4$. The second case is when all item values belong to $\{0, 1, 2\}$,
extending the $\{0, 1\}$ setting studied in Bouveret and Lema\^itre. We obtain
an exact algorithm for any number of agents in this case.
