Dynamic Cost-Per-Action Mechanisms and Applications to Online AdvertisingH. Nazerzadeh, A. Saberi and R. VohraFlorent Garcin and Brammert Ottens{firstname.lastname}@epfl.chDecember 2008December 2008 2Outline✔Motivations✔Model✔Mechanism•Desired properties•Sufficient conditions✔Example: IID utilities✔DiscussionDecember 2008 3Motivations✔Current charging models:•Cost-per-impression•Cost-per-click✗Submit bids before observing profits✗Click fraud•Increase revenue•Hurt competitors•Think about who's the winner...December 2008 4Motivations✔Click-per-action!✗Actions hidden from the publisher✔Google Checkout (a.k.a “Google paypal”)•Free until Feb. 2008•Charge sellers 2.0% + $0.20 per transaction•Free transaction if ads on AdWordsWhat if advertisers do not use this?December 2008 5Model✔In each period t•Mechanism allocates the item to one agent.•Agent i discovers his utility uit•Agent i reports rit to the mechanism.•Mechanism determines the payment pitDecember 2008 6Mechanism: desired properties✔Individual rationality✔Incentive compatibility✔Efficiency (revenue) close to 2nd price auction✔No a-priori knowledge of utility distributionDecember 2008 7Mechanism: desired propertiesIndividual rationality✔Ex-post IR✔Asymptotically ex-ante IR∑t=1Txitrit−pit0limT ∞E[∑t=1Txitit−pit]0it=E[uit∣ui1,...,ui,t−1]December 2008 8Mechanism: desired propertiesIncentive compatibility✔Asymptotic IC => asym. Bayesian Nash equ.• : expected total profit of i if truthful• : maximum expected profit of i if not truthfulUiT −UiT oUiT UiT UiT December 2008 9Mechanism: desired propertiesEfficiency✔Efficient mechanism allocates to agent i✔Expected welfare when all agents truthful✔Asymptotically ex-ante efficientargmaxi{it}W T =E [∑t=1T∑i=1nxitit]E [∑t=1Tmaxi{it}] −W T =oW T December 2008 10Mechanism✔For t=1, 2, ...•Explore with probuniformly, at random, allocate the item to agent ipit = 0•Exploit with probrandomly allocate the item to agenti∈argmaxi{itt}pit=∑k=1t−1yikmin{ kt , ikk}−∑k= 1t−1pikt1−tpjt=0, j≠iDecember 2008 11Sufficient conditions: IR and ICTheorem 1 if for the learning algorithm, for all i and Tthen mechanism M is asymptotically ex-ante individually rational and incentive compatible.E [max1 tT{it}∑t=1Tt]=oE [∑t=1Ttit](C1)t=maxi{∣itt−it∣}December 2008 12Sufficient conditions: IR and ICSketch of proof✔Expected profit of truthful agent is at least✔Expected total error is bounded by✔Total utility by deviating from truthful strategy is bounded bylower bound on explorationOE[∑t=1Tt]Omax1tT{it}E[∑t=1Tt]1n−o1 E[∑t=1Ttit](lemma 2)December 2008 13Sufficient conditions: efficiencyTheorem 3 if for the learning algorithm, in addition to (C1), the following holdsthen mechanism M is asymptotically ex-ante efficient.E [∑t=1Tt maxi{it}] =oE[∑t=1Tmaxi{it}](C2)December 2008 14Sufficient conditions: efficiencySketch of proof✔Loss in welfare during exploration✔Mistakes during exploitation✔Start withand use C1 + C2...upper bound on explorationE[∑t=1Ttmaxi{it}]OE[∑t=1Tt]E[∑t=1Tmaxi{it}]−W T =OE[∑t=1Tttmaxi{it}]December 2008 15“I want to bid!”✔Agents have better estimate of their utilities.✔Exploitation:•Some agents bid bit•Mechanism bids for the other agents.•Item allocated to•Payments✔Theorem 1 and 3 hold.bit= itti∈argmaxibitpit=∑k=1t−1yikmin{ kt,bik}−∑k=1t−1pikDecember 2008 16Example: IID utilities✔ -greedy learning algorithm✔Satisfies all the desired properties (for )nit=∑k=1t−1xitt=min{1,nt−ln1t}itT ={∑k=1Txikrik/niT, niT00, niT=013December 2008 17Discussion✔Is CPA the solution?•Brand