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.

随机化机制具有比确定性对应物更好的规范性质，但是随机化机制存在可验证性等问题。我们提出了通过让代理人玩游戏而不是抛硬币来解决此类机制的问题。这种游戏设计使得代理人最佳行动是随机玩，从而将 “随机性” 注入机制。这种去随机化保留了原始随机化机制的许多良好规范特性，但是提供了一种确定性且易于审核的机制。我们考虑了六个不同领域的随机化机制去随机化的三种相关方法：投票、设施选址、任务分配、学校选择、同行选择和资源分配。我们为这六个领域提出了许多具有良好规范性质的新型去随机化机制。每种机制都具有一个均匀混合策略的模块算术游戏的混合纳什均衡。除了一个混合纳什均衡外，代理人以真诚的方式报告了他们对原始问题的偏好。因此，这些去随机化方法是 “准策略证明的”。在一个领域中，我们还展示了由于去随机化而产生了新的理想规范性质。

玩游戏而非抛硬币的机制

Mechanisms that play a game, not toss a coin

We survey a burgeoning and promising new research area that considers the
online nature of many practical fair division problems. We identify wide
variety of such online fair division problems, as well as discuss new
mechanisms and normative properties that apply to this online setting. The
online nature of such fair division problems provides both opportunities and
challenges such as the possibility to develop new online mechanisms as well as
the difficulty of dealing with an uncertain future.

本篇研究论文调查了一个新兴的有前途的研究领域，这个领域考虑到许多实际的公平分配问题的在线性质。文章确定了种类繁多的这种在线公平分配问题，并讨论了适用于此在线设置的新机制和规范属性。这样的公平分配问题的在线性质提供了机会和挑战，如开发新的在线机制的可能性以及应对不确定未来的困难。