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.

Authors

• Michael Benisch Norman Sadeh
• Norman Sadeh
• Tuomas Sandholm Carnegie Mellon University, Strategy Robot, Inc. , Optimized Markets, Inc. , & Strategic Machine, Inc.

Keywords

No keywords are indexed for this paper.