Partial Revelation Automated Mechanism Design

Maxim Binshtok
Department of Computer Science
Ben-Gurion University
email: maximbi@cs.bgu.ac.il

Ronen I. Brafman
Department of Computer Science
Ben-Gurion University
email: brafman@cs.bgu.ac.il

Soloman E. Shimony
Department of Computer Science
Ben-Gurion University
email: shimony@cs.bgu.ac.il

Ajay Martin
Department of Computer Science
Stanford University
email: ajaym@cs.stanford.edu

Craig Boutilier
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: cebly@cs.toronto.edu

Abstract
Various tasks in decision making and decision support require selecting a preferred subset of items from a given set of feasible items. Recent work in this area considered methods for specifying such preferences based on the attribute values of individual elements within the set. Of these, the approach of (Brafman et al. 2006) appears to be the most general. In this paper, we consider the problem of computing an optimal subset given such a specification. The problem is shown to be NP-hard in the general case, necessitating heuristic search methods. We consider two algorithm classes for this problem: direct set construction, and implicit enumeration as solutions to appropriate CSPs. New algorithms are presented in each class and compared empirically against previous results.

To appear, AAAI-2007

Return to List of Papers