US008412575B2 (12) United States Patent (10) Patent No.: US 8,412,575 B2 Labio et a]. (45) Date of Patent: Apr. 2, 2013 (54) DETERMINING AND/OR MANAGING OTHER PUBLICATIONS OFFERS SUCH As BIDS FOR ADVERTISING PCT/ISN220, “Noti?cation of Transmittal of the International (75) Inventors Wilburt Labio cupenino C A (Us) Search Report and the Written Opinion of the International Searching ' sridhar R am a’sW amy cuspenino CA Authority, or the Declaration” for PCT/US06/24149 mailed Aug. 27, (US); Mark Rose, Los Altos, CA (US) 2007 (1 pg)‘ _ PCT/ISNZIO, “International Search Report” for PCT/US06/ 24149, - _ - - mailed Aug. 27, 2007 (2 pgs.). (73) Asslgnee' Google Inc" Mountaln VleW’ CA (Us) PCT/ISN237, “Written Opinion of the International Searching ( * ) Notice: Subject to any disclaimer the term ofthis Authority” for PCT/US06/24149, mailed Aug. 27, 2007 (5 pgs.). patent is extended or adjusted under 35 * -t d b - U.S.C. 154(1)) by 2313 days. C1 e y exammer (21) Appl. No.: 11/172,614 Primary Examiner * Scott D Gartland (74) Attorney, Agent, or Firm * John C. Pokotylo; Straub & (22) Filed: Jun. 30, 2005 pokotylo (65) Prior Publication Data (57) ABSTRACT US 2007/0005421 A1 Jan. 4, 2007 Offers, such as bids in an advertising network, may be deter (51) Int. Cl. mined and/or managed by accepting an ad budget and at least G06Q 30/00 (2012.01) one ad serving constraint, and then generating offer informa (52) us. Cl. .............. .. 705/14.49; 705/14.48; 705/1452 Iieh using the ad budget and the Serving eehSIraihKS) The (58) Field of Classi?cation Search ............... .. 705/142s effer may be generated byebtaininga for each efthe ad selfv See application ?le for complete search history. mg Constralnqs) a Plurahty of Polms, Whereln each P01nt includes a cost per event value and an event quantity value. (56) References Cited These points collectively de?ne a landscape. A convex land scape for each of the ad serving constraint(s) is then deter U.S. PATENT DOCUMENTS mined from the landscape(s). One or more points from at least one of the convex landscapes is then used to generate the offer 2003/0135460 A1 7/2003 Talegon _ _ 2003/0153329 A1* 8/2003 Stefan etal. ................ .. 455/456 lnfOrmaIlOIl 2004/0059655 A1* 3/2004 Seifertetal. .................. .. 705/35 2004/0107137 A1 6/2004 Skinner 2005/0065844 A1* 3/2005 Raj et al. ....................... .. 705/14 25 Claims, 9 Drawing Sheets CPC (b) A $300- P1 $2.00-- I I‘ .’ p2 .-' \q CONVEX BID $1 -°° -- : LANDSCAPE I l I l I I I I I i 0.01 0.02 0.03 0.04 0.05 CTR (e) US. Patent Apr. 2, 2013 Sheet 1 019 US 8,412,575 B2 om? rMMDOE % LomIN NM130? ow w US. Patent Apr. 2, 2013 Sheet 2 of9 US 8,412,575 B2 \\ \ owmw llllcll pzzEwzoo 205512; oZSmwwV Sm; mMMDQI oom 0mm US. Patent Apr. 2, 2013 Sheet 3 of9 US 8,412,575 B2 ( KEYWORD BID OPTIMIZER D l 40_0 ACCEPT KEYWORD AND BUDGET 410 l OBTAIN “BID w LANDSCAPE" FOR KEYWORD 420 l DETERMINE CONVEX BID LANDSCAPE FROM 430 BID LANDSCAPE l DETERMINE OPTIMAL BID STRATEGY FOR KEYWORD @440 USING CONVEX BID LANDSCAPE 450 FIGURE 4 US. Patent Apr. 2, 2013 Sheet 4 0f 9 US 8,412,575 B2 ) ( KEYWORD BID OPTIMIZER I QQQ ORDER POINTS ON CONVEX BID LANDSCAPE [V10 FROM LOWEST BID POINT TO HIGHEST ———>< FOR EACH BID POINT >\/\520 SAVE CURRENT POINT BUDGET REMAINING AFTER NO BIDDING ON ALL INCREMENTAL "RESULTS" AT CURRENT BID Y DETERMINE BID w ANOTHER 570 SPLIT FRACTION 550 I \ BID POINT NO SAVE CURRENT BID POINT, PREVIOUS BID POINT AND BID SPLIT FRACTION FIGURE 5 US. Patent Apr. 2, 2013 Sheet 5 of9 US 8,412,575 B2 655 wM. EDQE .0 a a 85 N.mo/1ow)w3;w 6w 8%. Q 956 aEm0»s9. US. Patent Apr. 2, 2013 Sheet 7 of9 US 8,412,575 B2 C MULTIPLE KEYWORD BID OPTIMIZER ) 8 0 F ACCEPT KEYWORDS AND BUDGET M805 FOR EACH KEYWORD DETERMINE CONVEX BID LANDSCAPE FOR J\ KEYWORD (AND ORDER BID POINTS ACCORDINGLY) 815 V INITIALIZE KEYWORD, KEYWORD SPEND, BID1, BID2, FRACTION, BUDGET m 820 YES ANOTHER KEYWORD \—-—-— 825 NO V 830 FOR EACH BID POINT, IN ORDER FROM LEAST EXPENSIVE INCREMENTAL SELECTION COST ENOUGH UDGET FOR ALL INCREMENTAL “RESULTS” AT CURRENT BID POINT? DETERMINE BID w RECORD BID AND AMOUNT SPL'T FRACT'ON 850 SPENT AS CURRENT l 835 N STRATEGY FOR KEYWORD 840 AND DISCARD PREVIOUS BID INFORMATION FOR RECORD KEYWORD CURRENT BID. PREVIOUS BID, BID FRACTION W855 845 ANOTHER YES AND TOTAL BID POINT AMOUNT SPENT T/ 860 FIGURE 8 US. Patent Apr. 2, 2013 Sheet 8 of9 US 8,412,575 B2 SQSOEEZ GDIINE! 3wo?EEE2z.: Em2m05.a29oo5m62l m wA?owwiémoowowkSwowwo mQm Hé 3 dim.w @5I&55500 @5IIHoS2w o N8 Aw US. Patent Apr. 2, 2013 Sheet 9 0f 9 US 8,412,575 B2 CPC (b) A $3.00-- P1 $2.00-- PL2‘ ---------- " $1.00 - P3 ________ c NVEX BID LANDSCAPE i i i 1' 1' > 0.01 0.02 0.03 0.04 0.05 CTR(C) 1000 CPC (b) A 3.00- $ P1 $2.00—- , P25’ CONVEXBID $1.00 -- ; LANDSCAPE : : a : a + 0.01 0.02 0.03 0.04 0.05 CTR(C) 1100 FIGURE 11