Multiplicative bidding in online advertising

ABSTRACT

In this paper, we initiate the study of the multiplicative bidding language adopted by major Internet search companies. In multiplicative bidding, the effective bid on a particular search auction is the product of a base bid and bid adjustments that are dependent on features of the search (for example, the geographic location of the user, or the platform on which the search is conducted). We consider the task faced by the advertiser when setting these bid adjustments, and establish a foundational optimization problem that captures the core difficulty of bidding under this language. We give matching algorithmic and approximation hardness results for this problem; these results are against an information-theoretic bound, and thus have implications on the power of the multiplicative bidding language itself. Inspired by empirical studies of search engine price data, we then codify the relevant restrictions of the problem, and give further algorithmic and hardness results. Our main technical contribution is an O(log n)-approximation for the case of multiplicative prices and monotone values. We also provide empirical validations of our problem restrictions, and test our algorithms on real data against natural benchmarks. Our experiments show that they perform favorably compare with the baseline.

References

1. AILON, N., CHARIKAR, M., AND NEWMAN, A. 2008. Aggregating inconsistent information: ranking and clustering. Journal of the ACM (JACM) 55, 5, 23.
2. ARCHAK, N., MIRROKNI, V., AND MUTHKRISHNAN, S. 2012. Budget optimization of advertising campaigns with carryover effect. In WINE.
3. Bing Ads 2014. Bing ads bid adjustments. http://advertise.bingads.microsoft. com/en-us/help-topic/how-to/moonshot concaboutadvancedbidding.htm/target-customers-with-bid-adjustments.
4. BORGS, C., CHAYES, J., ETESAMI, O., IMMORLICA, N., JAIN, K., AND MAHDIAN, M. 2007. Dynamics of bid optimization in online advertisement auctions. In WWW. 531--540.
5. CHAKRABARTY, D., ZHOU, Y., AND LUKOSE, R. 2007. Budget constrained bidding in keyword auctions and online knapsack problems. In SSA.
6. CHARLES, D. X., CHAKRABARTY, D., CHICKERING, M., DEVANUR, N. R., AND WANG, L. 2013. Budget smoothing for internet ad auctions: a game theoretic approach. In ACM Conference on Electronic Commerce. 163--180.
7. DEVANUR, N. AND HAYES, T. 2009. The adwords problem: Online keyword matching with budgeted bidders under random permutations. In EC.
8. EVENDAR, E., MANSOUR, Y., MIRROKNI, V., MUTHKIRSHNAN, S., AND NADAV, U. 2009. Bid optimization in BroadMatch ad auctions. In WWW.
9. FELDMAN, J., MUTHUKRISHNAN, S., PÄ L, M., AND STEIN, C. 2007. Budget optimization in search-based advertising auctions. In EC. ACM, 40--49.
10. GOEL, G., MIRROKNI, V., AND PAESLEME, R. 2012. Polyhedral clinching auctions and the adwords polytope. In STOC.
11. Google Support 2014. Setting bid adjustments. http://support.google.com/adwords/answer/2732132.
12. HubSpot 2013. The most important changes to google adwords in 2013. http://blog. hubspot.com/marketing/google-adwords-changes-2013-list.
13. KARANDE, C., MEHTA, A., AND SRIKANT, R. 2013. Optimizing budget constrained spend in search advertising. In WSDM. 697--706.
14. MEHTA, A., SABERI, A., VAZIRANI, U., AND VAZIRANI, V. 2007. Adwords and generalized online matching. JACM 54, 5.
15. MUTHUKRISHNAN, S., PÄL, M., AND SVITKINA, Z. 2007. Stochastic models for budget optimization in search-based advertising. In WINE.
16. RUSMEVICHIENTONG, P. AND WILLIAMSON, D. 2006. An adaptive algorithm for selecting profitable keywords for search-based advertising services. In EC. 260--269

Index Terms

• Theory of computation

  • Randomness, geometry and discrete structures