Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22A Cascade Model for Externalities in Sponsored SearchD. Kempe and M. MahdianFlorent Garcin and Brammert Ottens{firstname.lastname}@epfl.chOctober 2008October 2008 2Outline✔Models•Simple cascade•Slated cascade•Position-dependent✔Allocation algorithms•Simple cascade•Slated cascade•Position-dependent✔DiscussionOctober 2008 3Simple cascadeIndependent of clicking!Ad iAd i + 1click!paipa i+1qairai=pai⋅∏j=1i−1qajclick!✔Click-through rateOctober 2008 4Slated cascade✔Constant number s of slates✔Users scan from top to bottom✔Users have different order of slatesaj,islate jqaj,i: {1,..., s }{1,... , s }October 2008 5Slated cascade✔Prob of reaching slot i, when in slate j✔Prob of moving on the next slate, when in slate j✔Prob of seeing slot (j, i)Cj ,i=∏h=1i−1qaj , hCj=∏i :aj, i≠ ⊥qaj ,iCj ,i=∑f⋅Cj , i⋅∏h=1−1 j−1ChOctober 2008 6Position-dependent✔Idea: results listed in higher positions may be more relevant✔Same as simple cascade model but✔Prob to read an ad in slot i:✔Click-through ratei12...krai=ipai⋅∏j=1i−1qajOctober 2008 7Allocation algorithmsSimple cascade1.Sort ads in decreasing order of2.Fill matrix A such that3.Optimum solution at A[1, 1]✔Running timebapa1−qaA [a ,i]=max  A [a1, i], bapaqaA [a1, i1]On log nnk October 2008 81.Ignoring small continuation probabilities2.Rounding continuation probabilities3.Enumerating over all slate probabilities4.Dynamic programming✔Running timeAllocation algorithmsSlated cascadeOnk5sOctober 2008 9✔Lemma 4.1Let the position-dependent multipliers of slate j beLet be any distribution over permutations of slates, and OPT the value of the optimum solution.For any , there is a solution of value at least such that for all non-empty slots j, we haveAllocation algorithms: slated cascadeIgnoring small probabilitiesj ,1...j , kj01−⋅OPTCj ,iOctober 2008 10✔✔By lemma 4.1, the opt. solution is decreased by at mostAllocation algorithms: slated cascadeIgnoring small probabilitiesif qas1, then qa=0⋅OPTOctober 2008 11✔Round non-zero qa to nearest power of✔Decrease the opt. solution by at mostAllocation algorithms: slated cascadeRounding continuation prob.1−k⋅OPTC={0,1,1−/k 1,... ,1−/k k log1−/k/s1}October 2008 12✔Enumerate all combination of prob✔ configurationsAllocation algorithms: slated cascadeEnumeratingCs∈CC1,...,CsOk2sOctober 2008 13✔Find solution for each configuration•Order by •S-dimensional knapsack✔Running timeAllocation algorithms: slated cascadeDynamic programmingOnk3sbapa1−qaOctober 2008 14Allocation algorithmsPosition-dependent✔Theorem 1 no longer holds!✔Algorithms•4-approximation•Quasi-poly-time approximationOctober 2008 15✔Idea: reduce to knapsack problemAllocation algorithms: position-dependent4-approximationOctober 2008 16✔Idea: same as slated cascade but•Divide slots into segments with same•Use dynamic prog✔Running timeAllocation algorithms: position-dependentQuasi-poly-time approx.On⋅2O log2k iOctober 2008 171.Removing slots with small2.Rounding position-dependent multipliers3.Rounding continuation probabilities4.Enumerating and dynamic programmingAllocation algorithms: position-dependentQuasi-poly-time approx.iOctober 2008 18✔Remove slots with✔Decrease the total value by at mostAllocation algorithms: position-dependentRemoving slots with smalliik⋅OPTOctober 2008 19✔Round remaining to the nearest power of✔Decrease the optimum by at mostAllocation algorithms: position-dependentRoundingi1−⋅OPTi{0,1,1−1,...,1−log1−/k }October 2008 20✔✔Round non-zero ca to nearest power of✔Decrease the opt. solution by at mostAllocation algorithms: position-dependentRounding continuation prob.1−k2⋅OPTC={0,1,1−/k 1,... ,1−/k k log1−/k/s1}if qas1, then qa=0October 2008 21✔Apply slated cascade algo. steps 3 and 4•Each segment is like a slate✔Enumerate all combination of prob✔Dynamic programming as beforeAllocation algorithms: position-dependentEnumerating & dyn. prog.Cs∈COctober 2008 22Discussion✔How to improve these models?•Go through all slots to move to the next slate•CTR of an ad affected by other ads✔What about GSP