On Multiple Round Sponsored Search Auctions with Budgets

Details On Multiple Round Sponsored Search Auctions with Budgets On Multiple Round Sponsored Search Auctions with Budgets

2011-12-29

arxiv.org/abs/1112.6361v1

Computer Science

Computer Science and Game Theory

28 pages

Scientific paper

In a sponsored search auction the advertisement slots on a search result page are generally ordered by click-through rate. Bidders have a valuation, which is usually assumed to be linear in the click-through rate, a budget constraint, and receive at most one slot per search result page (round). We study multi-round sponsored search auctions, where the different rounds are linked through the budget constraints of the bidders and the valuation of a bidder for all rounds is the sum of the valuations for the individual rounds. All mechanisms published so far either study one-round sponsored search auctions or the setting where every round has only one slot and all slots have the same click-through rate, which is identical to a multi-item auction. This paper contains the following three results: (1) We give the first mechanism for the multi-round sponsored search problem where different slots have different click-through rates. Our mechanism is incentive compatible in expectation, individually rational in expectation, Pareto optimal in expectation, and also ex-post Pareto optimal for each realized outcome. (2) Additionally we study the combinatorial setting, where each bidder is only interested in a subset of the rounds. We give a deterministic, incentive compatible, individually rational, and Pareto optimal mechanism for the setting where all slots have the same click-through rate. (3) We present an impossibility result for auctions where bidders have diminishing marginal valuations. Specifically, we show that even for the multi-unit (one slot per round) setting there is no incentive compatible, individually rational, and Pareto optimal mechanism for private diminishing marginal valuations and public budgets.

Affiliated with

Also associated with

No associations

Rating

On Multiple Round Sponsored Search Auctions with Budgets 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 On Multiple Round Sponsored Search Auctions with Budgets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Multiple Round Sponsored Search Auctions with Budgets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-728675