Mechanisms That Play a Game, Not Toss a Coin

Toby WalshIJCAI 2024

Abstract

In mechanism design, a fundamental tension exists between determinism and fairness. While randomization is often used to achieve equitable outcomes, it introduces a "trust problem" regarding the integrity of the random source. This paper proposes a novel framework for de-randomizing social choice mechanisms by replacing external entropy with strategic competition. By having agents participate in modular arithmetic games where the unique Nash equilibrium is to play uniformly at random, we can design systems that are fair, efficient, and fully auditable. This approach is applied across various domains, including task allocation, facility location, and school choice, demonstrating that we can harvest randomness from competition rather than relying on a "black-box" coin toss.

Introduction

In the field of mechanism design—the mathematical study of voting, resource allocation, and matching—designers often face a trilemma. For many problems, such as house allocation or school matching, no deterministic rule can simultaneously satisfy fairness, efficiency, and strategy-proofness. To bypass these theoretical limits, researchers typically turn to randomization. For instance, the "Random Dictator" rule is a standard method to ensure fairness in voting by randomly selecting one participant's preference.

However, randomization introduces significant practical hurdles. If a high-stakes decision, such as matching organ donors to patients or students to schools, relies on a randomized algorithm, how can participants verify that the "coin toss" was not rigged? True randomness is notoriously difficult to generate, harder to audit post-hoc, and can introduce computational overhead. This paper explores a paradigm shift: instead of using an external source of entropy, why not let the participants generate the randomness themselves through strategic play?

The Modular Arithmetic Game

The core mechanism proposed is the Modular Arithmetic Game. In its simplest iteration, the Parity Game, two agents each select a bit (0 or 1). One agent wins if the sum of the bits is even; the other wins if it is odd. Game-theoretic analysis proves that the unique Nash equilibrium for this game is for both players to choose their bits uniformly at random. If either player deviates from this random strategy, they become exploitable by their opponent.

This concept allows for the "harvesting" of randomness from the strategic tension between agents with conflicting interests. The paper identifies three primary patterns for integrating these games into existing mechanisms:

  1. Game-first: Agents play the game to determine a "seed" (such as a priority order), which is then fed into a deterministic algorithm (e.g., School Choice).
  2. Game-last: The mechanism first generates a probability distribution over outcomes, and agents then play a game to select a specific outcome from that distribution (e.g., Resource Allocation).
  3. Game-interleaved: The game and the mechanism are played round-by-round, with each step influencing the next (e.g., Task Allocation).

Key Insights: Entropy from Competition

A primary advantage of this approach is One-Agent Robustness. In these modular games, if even a single agent plays uniformly at random, the final outcome is guaranteed to be uniform, regardless of the strategies employed by other participants. This makes the system highly resilient to manipulation or predictable patterns of behavior.

Furthermore, de-randomization can introduce desirable emergent properties. In peer selection—where a group must choose one of its members for a prize—de-randomized rules can achieve responsiveness. Unlike many deterministic rules, responsiveness ensures that every single agent possesses the power to change the outcome, increasing the perceived and actual fairness of the process. Importantly, adding these games does not necessarily compromise sincerity; in many scenarios, the optimal strategy remains to report true preferences and then play the arithmetic game randomly.

Results Across Domains

The paper demonstrates the efficacy of de-randomization through several key theoretical results:

  • Task Allocation: The de-randomized "Biased Min-Work" mechanism achieves a 7/4-approximation of the optimal makespan. This is a significant improvement over the proven 2-approximation limit for any purely deterministic mechanism.
  • Facility Location: The proposed mechanism achieves a 3/2-approximation for the maximum travel cost of an agent, matching the theoretical optimum for randomized mechanisms.
  • Auditable School Choice: By de-randomizing the tie-breaking process in the "Deferred Acceptance" algorithm, the paper provides a framework for school and medical residency matching that is fully auditable by any participant while maintaining stability.
  • Computational Tractability: For complex mechanisms like "Probabilistic Serial" allocation, the paper proves that only a polynomial number of bits are required to represent the necessary probabilities, ensuring the games remain computationally feasible.

Limitations and Future Directions

While mathematically sound, the transition from theory to practice faces certain challenges. First is the factor of human psychology. While Nash equilibria suggest agents should play randomly, human behavior in competitive games (like Rock-Paper-Scissors) can sometimes be predictable. However, the author notes that in high-stakes competitive settings, humans often approach computer-level randomness.

Second, some "Game-last" versions of mechanisms require calculating exact probabilities, which can be NP-hard for very large-scale problems. Finally, the coordination complexity required for agents to reach these equilibria in high-stakes environments remains an area for further empirical study. Future work will likely focus on the behavioral aspects of these games and the development of more computationally efficient approximations for complex distributions.

Summary updated

BibTeX
@inproceedings{walsh2024mechanisms,
  author = {Toby Walsh},
  title = {{Mechanisms That Play a Game, Not Toss a Coin}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure