Online advertisement, optimization and stochastic networks

Bo Tan, R. Srikant

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we propose a stochastic model to describe how search service providers charge client companies based on users' queries for the keywords related to these companies' ads by using certain advertisement assignment strategies. We formulate an optimization problem to maximize the long-term average revenue for the service provider under each client's long-term average budget constraint, and design an online algorithm which captures the stochastic properties of users' queries and click-through behaviors. We solve the optimization problem by making connections to scheduling problems in wireless networks, queueing theory and stochastic networks. Unlike prior models, we do not assume that the number of query arrivals is known. Due to the stochastic nature of the arrival process considered here, either temporary "free" service, i.e., service above the specified budget (which we call "overdraft") or under-utilization of the budget (which we call "underdraft") is unavoidable. We prove that our online algorithm can achieve a revenue that is within O(ε) of the optimal revenue while ensuring that the overdraft or underdraft is O(1/ε), where ε can be arbitrarily small. With a view towards practice, we also show that one can always operate strictly under the budget. Our algorithm also allows us to quantify the effect of errors in click-through rate estimation on the achieved revenue. We show that we lose at most δ over 1+δ fraction of the revenue if δ is the relative error in click-through rate estimation.

Original languageEnglish (US)
Title of host publication2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
Pages4504-4509
Number of pages6
DOIs
StatePublished - Dec 1 2011
Event2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011 - Orlando, FL, United States
Duration: Dec 12 2011Dec 15 2011

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0191-2216

Other

Other2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
CountryUnited States
CityOrlando, FL
Period12/12/1112/15/11

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'Online advertisement, optimization and stochastic networks'. Together they form a unique fingerprint.

  • Cite this

    Tan, B., & Srikant, R. (2011). Online advertisement, optimization and stochastic networks. In 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011 (pp. 4504-4509). [6161009] (Proceedings of the IEEE Conference on Decision and Control). https://doi.org/10.1109/CDC.2011.6161009