Dynamic Pay-Per-Action Mechanisms and Applications to Online Advertising

We examine the problem of allocating an item repeatedly over time amongst a set of agents. The value that each agent derives from consumption of the item may vary over time. Furthermore, it is private information to the agent, and prior to consumption it may be unknown to that agent. We describe a mechanism based on a sampling-based learning algorithm that under suitable assumptions is asymptotically individually rational, asymptotically Bayesian incentive compatible, and asymptotically ex ante efficient. Our mechanism can be interpreted as a pay-per-action or pay-per-acquisition (PPA) charging scheme in online advertising. In this scheme, instead of paying per click, advertisers pay only when a user takes a specific action (e.g., purchases an item or fills out a form) on their websites.