Online Mechanisms

A dynamic Vickrey–Clarke–Groves mechanism that is efficient and Bayes–Nash incentive compatible is defined and truthful auctions are presented for domains with expiring items and limited-supply items.

Abstract

Online mechanisms extend the methods of mechanism design to dynamic environments with multiple agents and private information. Decisions must be made as information about types is revealed online and without knowledge of the future, in the sense of online algorithms. We first consider single-valued preference domains and characterize the space of decision policies that can be truthfully implemented in a dominant strategy equilibrium. Working in a model-free environment, we present truthful auctions for domains with expiring items and limited-supply items. Turning to a more general preference domain, and assuming the existence of a probabilistic model for agent types, we define a dynamic Vickrey–Clarke–Groves mechanism that is efficient and Bayes–Nash incentive compatible. We close with some thoughts about future research directions in this area.