Computer Science – Computer Science and Game Theory
Scientific paper
2010-01-09
Computer Science
Computer Science and Game Theory
Scientific paper
In pay-per click sponsored search auctions which are currently extensively used by search engines, the auction for a keyword involves a certain number of advertisers (say k) competing for available slots (say m) to display their ads. This auction is typically conducted for a number of rounds (say T). There are click probabilities mu_ij associated with each agent-slot pairs. The goal of the search engine is to maximize social welfare of the advertisers, that is, the sum of values of the advertisers. The search engine does not know the true values advertisers have for a click to their respective ads and also does not know the click probabilities mu_ij s. A key problem for the search engine therefore is to learn these click probabilities during the T rounds of the auction and also to ensure that the auction mechanism is truthful. Mechanisms for addressing such learning and incentives issues have recently been introduced and are aptly referred to as multi-armed-bandit (MAB) mechanisms. When m = 1, characterizations for truthful MAB mechanisms are available in the literature and it has been shown that the regret for such mechanisms will be O(T^{2/3}). In this paper, we seek to derive a characterization in the realistic but non-trivial general case when m > 1 and obtain several interesting results.
Gujar Sujit
Narahari Yadati
Sarma Akash Das
No associations
LandOfFree
Multi-Armed Bandit Mechanisms for Multi-Slot Sponsored Search Auctions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Multi-Armed Bandit Mechanisms for Multi-Slot Sponsored Search Auctions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-Armed Bandit Mechanisms for Multi-Slot Sponsored Search Auctions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-580392