Stochastic budget optimization in internet advertising

DOI10.1007/S00453-012-9614-XzbMATH Open1275.68037arXiv1001.2735OpenAlexW1658377931MaRDI QIDQ2392928FDOQ2392928

Authors: Yanyan Li 

Publication date: 5 August 2013

Published in: Algorithmica (Search for Journal in Brave)

Abstract: Internet advertising is a sophisticated game in which the many advertisers "play" to optimize their return on investment. There are many "targets" for the advertisements, and each "target" has a collection of games with a potentially different set of players involved. In this paper, we study the problem of how advertisers allocate their budget across these "targets". In particular, we focus on formulating their best response strategy as an optimization problem. Advertisers have a set of keywords ("targets") and some stochastic information about the future, namely a probability distribution over scenarios of cost vs click combinations. This summarizes the potential states of the world assuming that the strategies of other players are fixed. Then, the best response can be abstracted as stochastic budget optimization problems to figure out how to spread a given budget across these keywords to maximize the expected number of clicks. We present the first known non-trivial poly-logarithmic approximation for these problems as well as the first known hardness results of getting better than logarithmic approximation ratios in the various parameters involved. We also identify several special cases of these problems of practical interest, such as with fixed number of scenarios or with polynomial-sized parameters related to cost, which are solvable either in polynomial time or with improved approximation ratios. Stochastic budget optimization with scenarios has sophisticated technical structure. Our approximation and hardness results come from relating these problems to a special type of (0/1, bipartite) quadratic programs inherent in them. Our research answers some open problems raised by the authors in (Stochastic Models for Budget Optimization in Search-Based Advertising, Algorithmica, 58 (4), 1022-1044, 2010).

Full work available at URL: https://arxiv.org/abs/1001.2735

Recommendations

• Stochastic models for budget optimization in search-based advertising
• Online Advertisement, Optimization and Stochastic Networks
• Stochastic optimal budget decision for advertising considering uncertain sales responses
• Optimal Budget Allocation Across Search Advertising Markets
• Online joint bid/daily budget optimization of Internet advertising campaigns
• Optimal keyword bids in search-based advertising with stochastic advertisement positions
• scientific article; zbMATH DE number 7042405
• Online allocation and display ads optimization with surplus supply

zbMATH Keywords

internet advertisingscenario modelstochastic budget optimization

Mathematics Subject Classification ID

Stochastic programming (90C15) Marketing, advertising (90B60) Experimental studies (91A90) Internet topics (68M11)

Cites Work

• Title not available (Why is that?)
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• Approximating the Cut-Norm via Grothendieck's Inequality
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Fast Approximation Algorithms for Knapsack Problems
• Title not available (Why is that?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Title not available (Why is that?)
• Scenario optimization
• Parameterized approximation scheme for the multiple knapsack problem
• Stochastic models for budget optimization in search-based advertising
• Forward looking Nash equilibrium for keyword auction

Cited In (10)

• Stochastic models for budget optimization in search-based advertising
• Optimal Budget Allocation Across Search Advertising Markets
• Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem
• Online Advertisement, Optimization and Stochastic Networks
• Optimal budget allocation over time for keyword ads in web portals
• Title not available (Why is that?)
• Dynamic budget allocation for social media advertising campaigns: optimization and learning
• Stochastic optimal budget decision for advertising considering uncertain sales responses
• Nonparametric advertising budget allocation with inventory constraint
• Adaptivity in the stochastic blackjack knapsack problem

This page was built for publication: Stochastic budget optimization in internet advertising

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2392928)