Mechanisms That Play a Game, Not Toss a Coin

Mechanisms That Play a Game, Not Toss a Coin

Toby Walsh

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 3005-3013. https://doi.org/10.24963/ijcai.2024/333

Randomized mechanisms can have good normative properties compared to their deterministic counter-parts. However, randomized mechanisms are problematic in several ways such as in their verifiability. We propose here to de-randomize such mechanisms by having agents play a game instead of tossing a coin. The game is designed so agents play randomly, and this play injects “randomness” into the mechanism. Surprisingly this de-randomization 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 general purpose methods to de-randomize mechanisms, and apply these to six different domains: voting, facility location, task allocation, school choice, peer selection, and resource allocation. We propose a number of novel de-randomized mechanisms for these six domains with good normative properties (such as equilibria in which agents sincerely report preferences over the original problem). In one domain, we additionally show that a new and desirable normative property emerges as a result of de-randomization.property emerges as a result of de-randomization.
Keywords:
Game Theory and Economic Paradigms: GTEP: Mechanism design
Agent-based and Multi-agent Systems: MAS: Resource allocation
Game Theory and Economic Paradigms: GTEP: Computational social choice
Game Theory and Economic Paradigms: GTEP: Fair division