Complexity of Mechanism Design

Vincent Conitzer, Tuomas Sandholm

Abstract

The aggregation of conflicting preferences is a fundamental challenge in multiagent systems, primarily due to the risk of agents reporting insincere preferences to manipulate outcomes. Mechanism design addresses this by creating rules that incentivize truthfulness. This paper explores Automated Mechanism Design (AMD), where mechanisms are computationally generated for specific settings. We demonstrate that while finding an optimal deterministic mechanism is NP-complete for both dominant-strategy and Bayes-Nash implementations, allowing for randomized mechanisms renders the problem tractable via linear programming. Furthermore, randomization can improve the social objective compared to deterministic approaches.

Introduction

In multiagent environments, a central coordinator must often select an outcome—such as a resource allocation or a policy decision—based on the private preferences of various agents. The "Mechanism Design" problem arises because these agents are self-interested; they may misrepresent their true preferences if doing so leads to a more favorable outcome.

Historically, mechanism design has relied on general-purpose frameworks like the Vickrey-Clarke-Groves (VCG) mechanism. However, these frameworks often require specific conditions, such as the ability to use side payments (money) or the assumption of quasilinear utility. In many real-world scenarios, such as voting or joint planning, these conditions do not hold. This paper proposes Automated Mechanism Design (AMD): instead of seeking a universal mechanism, we use algorithms to build an optimal, manipulation-proof mechanism for the specific instance at hand.

The Complexity of Deterministic Mechanisms

The authors first investigate the computational complexity of designing deterministic mechanisms—those where a specific set of agent reports always results in a single, fixed outcome.

The study reveals that designing optimal deterministic mechanisms is computationally "hard." Specifically:

  1. Dominant-Strategy Implementation: Finding an optimal mechanism where truthtelling is the best strategy regardless of others' actions is shown to be NP-complete via a reduction from the Independent Set problem.
  2. Bayes-Nash Implementation: When agents only need to be truthful given their beliefs about others, the problem remains NP-complete, reducing from the Knapsack problem.

These results suggest that for even moderately sized problems, finding the absolute best deterministic rule is likely beyond the reach of standard algorithms.

Randomization as a Computational Catalyst

A pivotal contribution of this work is the discovery of a computational "phase transition" when moving from deterministic to randomized mechanisms. In a randomized mechanism, the result of agent reports is a probability distribution over possible outcomes.

By framing the design process as a Linear Programming (LP) problem, the authors show that randomized AMD is in P (solvable in polynomial time). The variables in this LP represent the probabilities of choosing each outcome for every possible combination of agent types. The constraints ensure "incentive compatibility"—meaning no agent gains an expected utility boost by lying.

The Uncertainty Trade-off

The paper offers a profound insight into why this works: a coordinator can overcome the computational difficulty caused by their own uncertainty (not knowing the agents' true types) by introducing uncertainty for the agents (randomized outcomes). This strategic use of randomness simplifies the optimization landscape.

Performance and the Revelation Principle

Beyond computational ease, randomization offers performance benefits. The authors prove that randomized mechanisms can achieve higher expected social welfare than any deterministic counterpart. In one provided example, a randomized approach yielded an expected welfare of 5.5, whereas the best deterministic approach was capped at 5.0.

The research also utilizes the Revelation Principle, a cornerstone of game theory. This principle states that any outcome achievable through a complex, manipulative game can also be achieved through a "direct" mechanism where agents simply report their types truthfully. This allows AMD to focus exclusively on designing truthful mechanisms without loss of generality.

Limitations and Future Directions

While AMD provides a powerful tool for custom mechanism design, it faces the "curse of dimensionality." The size of the Linear Program grows exponentially with the number of agents, as the number of possible type combinations (the input space) increases. Consequently, the current approach is most effective for systems with a small number of agents or those with highly structured preference spaces.

Future research directions include extending AMD to settings with side payments where quasilinear utility is not assumed and using AMD to discover new general principles of mechanism design by observing patterns in automatically generated solutions.

Conclusion

This work establishes the foundational complexity classes for Automated Mechanism Design. By demonstrating that randomization transforms an NP-complete optimization problem into a tractable linear program, the authors provide a viable path for designing sophisticated, truthful aggregation rules in complex multiagent systems.

Summary updated

Abstract

The aggregation of conflicting preferences is a central problem in multiagent systems. The key difficulty is that the agents may report their preferences insincerely. Mechanism design is the art of designing the rules of the game so that the agents are motivated to report their preferences truthfully and a (socially) desirable outcome is chosen. We propose an approach where a mechanism is automatically created for the preference aggregation setting at hand. This has several advantages, but the downside is that the mechanism design optimization problem needs to be solved anew each time. Focusing on settings where side payments are not possible, we show that the mechanism design problem is NP-complete for deterministic mechanisms. This holds both for dominant-strategy implementation and for Bayes-Nash implementation. We then show that if we allow randomized mechanisms, the mechanism design problem becomes tractable. In other words, the coordinator can tackle the computational complexity introduced by its uncertainty about the agents' preferences by making the agents face additional uncertainty. This comes at no loss, and in some cases at a gain, in the (social) objective.
BibTeX
@inproceedings{conitzer2002complexity,
  author = {Vincent Conitzer and Tuomas Sandholm},
  title = {{Complexity of Mechanism Design}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2002},
  url = {https://openreview.net/forum?id=f74vk5bHqM},
}
Figure