Complexity of Mechanism Design

By Vincent Conitzer, Tuomas Sandholm. Conference on Uncertainty in Artificial Intelligence, 2002

375 citations recorded by the source corpus.

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 dominantstrategy 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 the agents face additional uncertainty. This comes at no loss, and in some cases at a gain, in the (social) objective.

View Paper: https://www.semanticscholar.org/paper/9f8978d41e76eb574200e25afca9efd3651f65a7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Recommendation to Groups (2007, methodology): “, Conitzer and Sandholm [8]; Conitzer and Sandholm [9]; Sandholm [33]), methods are developed for automatically generating aggregation methods for a particular setting that (a) satisfy the constraint of being nonmanipulable (at least in that particular setting) and (b) also respect other constraints”
More than the sum of its members: challenges for group recommender systems (2004, methodology): “In an effort to create more optimal nonmanipulable mechanisms, Conitzer and Sandholm have introduced the approach of automated mechanism design ([4]; [5]): For a given setting, their method generates a mechanism which is (a) non-manipulable and (b) optimal in terms of the expected value of a given…”
Argumentation-based negotiation (2003, background): “Assuming further that participants behave according to the assumptions of rational-choice theory (Coleman, 1990), then this approach can guide the design of the interaction mechanism itself, and thus force such agents to behave in certain ways (Varian, 1995; Conitzer and Sandholm, 2002).”
Issues in Multiagent Resource Allocation (2006, background): “In this case, the allocation problem consists of selecting, each day, an admissible sequence of images that will be acquired by the satellite over the next day (and allocated to the agent).”
Computational-Mechanism Design: A Call to Arms (2003, unknown): “7,8”
A Short Introduction to Computational Social Choice (2007, methodology): “Two such cases are the large body of work on computational aspects of coalition formation [29,31,86,1], and the method of automated mechanism design [33].”
Computer-Aided Verification for Mechanism Design (2015, background): “This step proceeds fully automatically: a proof checking program verifies that the formal proof is constructed correctly.”