Computer Science – Computer Science and Game Theory
Scientific paper
2006-11-15
Computer Science
Computer Science and Game Theory
29 pages, work was presented at a) Second Workshop on Sponsored Search Auctions, Ann Arbor, MI b) INFORMS Annual Meeting, Pitt
Scientific paper
We present a number of models for the adword auctions used for pricing advertising slots on search engines such as Google, Yahoo! etc. We begin with a general problem formulation which allows the privately known valuation per click to be a function of both the identity of the advertiser and the slot. We present a compact characterization of the set of all deterministic incentive compatible direct mechanisms for this model. This new characterization allows us to conclude that there are incentive compatible mechanisms for this auction with a multi-dimensional type-space that are {\em not} affine maximizers. Next, we discuss two interesting special cases: slot independent valuation and slot independent valuation up to a privately known slot and zero thereafter. For both of these special cases, we characterize revenue maximizing and efficiency maximizing mechanisms and show that these mechanisms can be computed with a worst case computational complexity $O(n^2m^2)$ and $O(n^2m^3)$ respectively, where $n$ is number of bidders and $m$ is number of slots. Next, we characterize optimal rank based allocation rules and propose a new mechanism that we call the customized rank based allocation. We report the results of a numerical study that compare the revenue and efficiency of the proposed mechanisms. The numerical results suggest that customized rank-based allocation rule is significantly superior to the rank-based allocation rules.
Iyengar Garud
Kumar Anuj
No associations
LandOfFree
Characterizing Optimal Adword 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 Characterizing Optimal Adword Auctions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Characterizing Optimal Adword Auctions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-54863