Stochastic budget optimization in internet advertising

DOI10.1007/S00453-012-9614-XMaRDI QIDQ2392928zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 5 August 2013

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

internet advertisingscenario modelstochastic budget optimization

Mathematics Subject Classification ID

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

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).

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• 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
• Forward looking Nash equilibrium for keyword auction
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Parameterized approximation scheme for the multiple knapsack problem
• Scenario optimization
• Stochastic models for budget optimization in search-based advertising

Cited in

(12)

• Stochastic models for budget optimization in search-based advertising
• Optimal Budget Allocation Across Search Advertising Markets
• Concise bid optimization strategies with multiple budget constraints
• Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem
• Online Advertisement, Optimization and Stochastic Networks
• Dynamic bidding strategies in search-based advertising
• Optimal budget allocation over time for keyword ads in web portals
• scientific article; zbMATH DE number 7042405 (Why is no real title available?)
• 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)