Partial Revelation Automated Mechanism Design

摘要

In most mechanism design settings, optimal general-purpose mechanisms are not known. Thus the automated design of mechanisms tailored to specific instances of a decision scenario is an important problem. Existing techniques for automated mechanism design (AMD) require the revelation of full utility information from agents, which can be very difficult in practice. In this work, we study the automated design of mechanisms that only require partial revelation of utilities. Each agent's type space is partitioned into a finite set of partial types, and agents (should) report the partial type within which their full type lies. We provide a set of optimization routines that can be combined to address the trade-offs between the amount of communication, approximation of incentive properties, and objective value achieved by a mechanism. This allows for the automated design of partial revelation mechanisms with worst-case guarantees on incentive properties for any objective function (revenue, social welfare, etc.).