  Fair allocation of indivisible goods has attracted extensive attention over
the last two decades, yielding numerous elegant algorithmic results and
producing challenging open questions. The problem becomes much harder in the
presence of strategic agents. Ideally, one would want to design truthful
mechanisms that produce allocations with fairness guarantees. However, in the
standard setting without monetary transfers, it is generally impossible to have
truthful mechanisms that provide non-trivial fairness guarantees. Recently,
Amanatidis et al. [2021] suggested the study of mechanisms that produce fair
allocations in their equilibria. Specifically, when the agents have additive
valuation functions, the simple Round-Robin algorithm always has pure Nash
equilibria and the corresponding allocations are envy-free up to one good (EF1)
with respect to the agents' true valuation functions. Following this agenda, we
show that this outstanding property of the Round-Robin mechanism extends much
beyond the above default assumption of additivity. In particular, we prove that
for agents with cancelable valuation functions (a natural class that contains,
e.g., additive and budget-additive functions), this simple mechanism always has
equilibria and even its approximate equilibria correspond to approximately EF1
allocations with respect to the agents' true valuation functions. Further, we
show that the approximate EF1 fairness of approximate equilibria surprisingly
holds for the important class of submodular valuation functions as well, even
though exact equilibria fail to exist!
