Automated mechanism design for a selfinterested designer

Often, an outcome must be chosen on the basis of the preferences reported by a group of agents. The key diculty is that the agents may re-port their preferences insincerely to make the chosen outcome more favorable to themselves. Mechanism design is the art of designing the rules of the game so that the agents are mo-tivated to report their preferences truthfully, and a desirable outcome is chosen. In a recently emerging approach proposed in UAI-02|called automated mechanism design|a mechanism is computed for the preference aggregation set-ting at hand. This has several advantages, but the downside is that the mechanism design op-timization problem needs to be solved anew each time. Unlike the earlier work on auto-mated mechanism design that studied a benev-olent designer, in this paper we study auto-mated mechanism design problems where the designer is self-interested. In this case, the cen-ter cares only about which outcome is chosen and what payments are made to it. The reason that the agents ' preferences are relevant is that the center is constrained to making each agent at least as well o as the agent would have been had it not participated in the mechanism. In this setting, we show that designing optimal de-terministic mechanisms is NP-complete in two important special cases: when the center is in-terested only in the payments made to it, and when payments are not possible and the center is interested only in the outcome chosen. We then show how allowing for randomization in the mechanism makes problems in this setting computationally easy.