  Randomized mechanisms can have good normative properties compared to their
deterministic counterparts. However, randomized mechanisms are problematic in
several ways such as in their verifiability. We propose here to derandomize
such mechanisms by having agents play a game instead of tossing a coin. The
game is designed so an agent's best action is to play randomly, and this play
then injects ``randomness'' into the mechanism. This derandomization retains
many of the good normative properties of the original randomized mechanism but
gives a mechanism that is deterministic and easy, for instance, to audit. We
consider three related methods to derandomize randomized mechanism in six
different domains: voting, facility location, task allocation, school choice,
peer selection, and resource allocation. We propose a number of novel
derandomized mechanisms for these six domains with good normative properties.
Each mechanism has a mixed Nash equilibrium in which agents play a modular
arithmetic game with an uniform mixed strategy. In all but one mixed Nash
equilibrium, agents report their preferences over the original problem
sincerely. The derandomized methods are thus ``quasi-strategy proof''. In one
domain, we additionally show that a new and desirable normative property
emerges as a result of derandomization.
