Methodology for Designing Reasonably Expressive Mechanisms with Application to Ad Auctions

Mechanisms (especially on the Internet) have begun allowing people or organizations to express richer preferences in order to provide for greater levels of overall satisfaction. In this paper, we develop an operational methodology for quantifying the expected gains in economic efficiency associated with different forms of expressiveness. We begin by proving that the sponsored search mechanism (GSP) used by Google, Yahoo!, MSN, etc. can be arbitrarily inefficient. We then experimentally compare its efficiency to a slightly more expressive variant (PGSP), which solicits an extra bid for a premium class of positions. We generate random preference distributions based on published industry knowledge. We determine ideal strategies for the agents using a custom tree search technique, and we also benchmark using straightforward heuristic bidding strategies. The GSP's efficiency loss is greatest in the practical case where some advertisers ("brand advertisers") prefer top positions while others ("value advertisers") prefer middle positions, and that loss can be dramatic. It is also worst when agents have small profit margins. While the PGSP is only slightly more expressive (and thus not much more cumbersome), it removes almost all of the efficiency loss in all of the settings we study.

Michael Benisch, Norman Sadeh, Tuomas Sandholm