An Algorithm for Automatically Designing Deterministic Mechanisms without Payments

Vincent Conitzer · Tüomas Sandholm

29 citations0/0 files stored

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Auction Theory and Applications Game Theory and Voting Systems Multi-Agent Systems and Negotiation

Abstract

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 selﬁshly. This is a difﬁcult 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 ﬂy for the setting at hand—a universally applicable approach.\nIn this paper we present (to our knowledge) the ﬁrst algorithm designed speciﬁcally 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 efﬁciently 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.