Abstract

Mechanisms (especially on the Internet) have be-gun allowing people or organizations to express richer preferences in order to provide for greater levels of overall satisfaction. In this paper, we de-velop an operational methodology for quantifying the expected gains in economic efficiency associ-ated with different forms of expressiveness.  We begin by proving that the sponsored search mech-anism (GSP) used by Google, Yahoo!, MSN, etc.can be arbitrarily inefficient. We then experimen-tally compare its efficiency to a slightly more ex-pressive variant (PGSP), which solicits an extra bid for a premium class of positions. We generate ran-dom preference distributions based on published industry knowledge.  We determine ideal strate-gies for the agents using a custom tree search tech-nique, and we also benchmark using straightfor-ward heuristic bidding strategies. The GSP’s effi-ciency 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