An Algorithm for Automatically Designing Deterministic Mechanisms without Payments

Mechanism design is the art of designing the rules of the game so that a desirable outcome is reached even though the agents in the game behave selfishly. This is a difficult problem because the designer is uncertain about the agents’ preferences and the agents may lie about their preferences. Traditionally, the focus in mechanism design has been on designing mechanisms that are appropriate for a range of settings. While this approach has produced a number of famous mechanisms, much of the space of possible settings is still left uncovered. In contrast, in automated mechanismdesign (AMD), a mechanism is computed on the fly for the setting at hand—a universally applicable approach.\nIn this paper we present (to our knowledge) the first algorithm designed specifically for AMD. It is designed for the special case where there is only one type-reporting agent, the mechanism must be deterministic, and payments are not possible. The algorithm relies on an association of a particular (easy to compute) mechanism to each subset of outcomes, and a proof that one such mechanism is an optimal one—which allows us to reduce the search space to one of size 2O. We propose an admissible heuristic to use in searching over this space, and show how it can be updated efficiently from node to node. We show how to apply branch and bound DFS as well as IDA* to this search space, and show that this approach outperforms CPLEX 8.0, a general purpose solver, solidly on unstructured instances, both with and without an IR constraint. However, on our third type of instance, a bartering problem, CPLEX almost achieves the performance of our algorithm by exploiting the structure inherent in the domain.