  Geschke, Lubarsky, and Rahn in ``Choice and the Hat
Game''~\cite{choice-and-the-hat-game} generalize the classic hat game puzzle to
infinitely-many players and ask whether every model of set theory without
choice in which the optimal solution can be carried out contains either a
nonprincipal ultrafilter on $\mathbb N$ or else a Vitali set. A negative answer
is obtained here by constructing a model in which there is an optimal solution
to the hat game puzzle but no nonprincipal ultrafilter on $\mathbb N$ and no
Vitali set. This is accomplished in a more general setting, establishing that
for any Borel bipartite graph $\Gamma$ not embedding some $K_{n,\omega_1}$ and
with countable colouring number there is a model of $\mbox{ZF} + \mbox{DC}$ in
which $\Gamma$ has a $2$-colouring but there is no ultrafilter as above or
Vitali set. The same conclusion applies to the natural generalization of the
hat game to an arbitrary finite number of hat colours.
