  We consider allocating indivisible goods with provable fairness guarantees
that are satisfied regardless of which bundle of items each agent receives.
Symmetrical allocations of this type are known to exist for divisible
resources, such as consensus splitting of a cake into parts, each having equal
value for all agents, ensuring that in any allocation of the cake slices, no
agent would envy another. For indivisible goods, one analogous concept relaxes
envy freeness to guarantee the existence of an allocation in which any bundle
is worth as much as any other, up to the value of a bounded number of items
from the other bundle. Previous work has studied the number of items that need
to be removed. In this paper, we improve upon these bounds for the specific
setting in which the number of bundles equals the number of agents.
  Concretely, we develop the theory of symmetrically envy free up to one good,
or symEF1, allocations. We prove that a symEF1 allocation exists if the
vertices of a related graph can be partitioned (colored) into as many
independent sets as there are agents. This sufficient condition always holds
for two agents, and for agents that have identical, disjoint, or binary
valuations. We further prove conditions under which exponentially-many distinct
symEF1 allocations exist. Finally, we perform computational experiments to
study the incidence of symEF1 allocations as a function of the number of agents
and items when valuations are drawn uniformly at random.
