Automated Mechanism Design with a Structured Outcome Space

Previous research on automated mechanism design (proposed in UAI-02) assumed that the outcome space was flatly represented, which makes that work inapplicable if the outcome space is exponential, as it is, for example, in multi-item auctions. This paper introduces (to our knowledge) the first more concise representation for the problem, which relies on decomposing the outcome space into distinct issues. While the decomposability makes the input to the design problem polynomial, we show that it is NP-complete
(even with a single agent with only two types) to design a mechanism that maximizes one of the following objectives: 1) expected social welfare when payments are not possible, 2) a general objective function even when payments are possible, and 3) expected payments to the center (designer). We show that the NP-hardness is only weak by developing a pseudopolynomial algorithm for the former two single-agent mechanism design problems with any constant number of types. Finally, we show that when designing randomized mechanisms, we can exploit the structure of the representation and even solve the general problem in polynomial time for any constant number of agents for any growing number of types.