# Exploration via design and the cost of uncertainty in keyword auctions - Computer Science > Computer Science and Game Theory

Exploration via design and the cost of uncertainty in keyword auctions - Computer Science > Computer Science and Game Theory - Download this document for free, or read online. Document in PDF available to download.

Abstract: We present a deterministic exploration mechanism for sponsored searchauctions, which enables the auctioneer to learn the relevance scores ofadvertisers, and allows advertisers to estimate the true value of clicksgenerated at the auction site. This exploratory mechanism deviates onlyminimally from the mechanism being currently used by Google and Yahoo! in thesense that it retains the same pricing rule, similar ranking scheme, as wellas, similar mathematical structure of payoffs. In particular, the estimationsof the relevance scores and true-values are achieved by providing a chance tolower ranked advertisers to obtain better slots. This allows the search engineto potentially test a new pool of advertisers, and correspondingly, enables newadvertisers to estimate the value of clicks-leads generated via the auction.Both these quantities are unknown a priori, and their knowledge is necessaryfor the auction to operate efficiently. We show that such an exploration policycan be incorporated without any significant loss in revenue for the auctioneer.We compare the revenue of the new mechanism to that of the standard mechanismat their corresponding symmetric Nash equilibria and compute the cost ofuncertainty, which is defined as the relative loss in expected revenue perimpression. We also bound the loss in efficiency, as well as, in userexperience due to exploration, under the same solution concept i.e. SNE. Thusthe proposed exploration mechanism learns the relevance scores whileincorporating the incentive constraints from the advertisers who are selfishand are trying to maximize their own profits, and therefore, the exploration isessentially achieved via mechanism design. We also discuss variations of thenew mechanism such as truthful implementations.

Author: ** Sudhir Kumar Singh, Vwani P. Roychowdhury, Milan BradonjiÄ‡, Behnam A. Rezaei**

Source: https://arxiv.org/