ICES: Small: Heuristic Mechanism Design

Harvard University, Cambridge MA

Investigators

Abstract

Computational mechanism design (CMD) seeks to understand how to promote desirable outcomes in multi-agent systems, despite private information, self-interest and limited computational resources. CMD finds application in many settings; e.g., in the public sector for wireless spectrum and airport landing rights, in Internet advertising, in expressive sourcing in the supply chain, in allocating resources in computational systems. A key concept is strategyproofness: the mechanism's outcome should be robust against manipulations through misreports of private information held by participants. In meeting the demands for CMD in these rich domains, we often need to bridge from the theory of economic mechanism design to the practice of deployable, computational mechanisms. The broad goal of this project is to leverage scalable, heuristic optimization algorithms, making them applicable in settings with self-interest. Rather than seeking provably optimal but possibly inapplicable mechanisms (either without complexity considerations, as in economic theory, or with worst-case complexity considerations, as is commonplace in theoretical computer science), we propose a new computational agenda. Provable guarantees are often unavailable when search algorithms are applied to real-world optimization problems. Still, heuristic search algorithms are widely employed, and find good empirical success. We seek something analogous to this for settings in which inputs are distributed to participants, each self-interested and willing to misreport inputs in order to improve the outcome in their favor. Rather than looking for optimal mechanisms amongst the class of polynomial-time algorithms, we seek to employ search algorithms with excellent empirical performance despite worst-case exponential run-time (if run-to-completion.) Specific topics of interest include: (a) automatic self-correction, to apply online sensitivity analysis to automatically correct the outcome of an algorithm, allowing the algorithm to be coupled with payments and made strategyproof; (b) metrics for approximate strategyproofness, to enable design without solving for equilibrium; and (c) automatic generation of payment rules through the use of machine learning, by imposing appropriate structure on the hypothesis space. Successful progress will provide new and fundamental methodologies with which to develop incentive-aligned mechanisms (e.g., for resource and task allocation) that enjoy excellent empirical properties and are able to scale to real-world domains. The theory of mechanism design has already provided broad societal impact, in enabling the auctioning of public resources such as wireless spectrum and power generation capacity, and in driving revenue to internet businesses by enabling efficient advertising. A new framework for heuristic mechanism design will enable a new generation of mechanisms for large-scale coordination and resource allocation amongst people, firms and organizations, with the promise of broad applications to electronic commerce (including mobile commerce), cloud computing, and across the supply chain.