Accession Number:

ADA478308

Title:

Characterizing Optimal Adword Auctions

Descriptive Note:

Technical rept., version 3

Corporate Author:

COLUMBIA UNIV NEW YORK DEPT OF INDUSTRIAL ENGINEERING AND OPERATIONS RESEARCH

Personal Author(s):

Report Date:

2006-11-14

Pagination or Media Count:

30.0

Abstract:

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 multidimensional type-space that are 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 On2m2 and On2m3 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.

Subject Categories:

  • Economics and Cost Analysis
  • Statistics and Probability
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE