Concise Bid Optimization Strategies with Multiple Budget Constraints

Arash Asadpour (), MohammadHossein Bateni (), Kshipra Bhawalkar () and Vahab Mirrokni ()
Additional contact information
Arash Asadpour: Information, Operations & Management Sciences, NYU Stern School of Business, New York, New York 10012
MohammadHossein Bateni: Research, Google Inc., New York, New York 10011
Kshipra Bhawalkar: Research, Google Inc., Mountain View, California 94043
Vahab Mirrokni: Research, Google Inc., New York, New York 10011

Management Science, 2019, vol. 65, issue 12, 5785-5812

Abstract: A major challenge faced by marketers attempting to optimize their advertising campaigns is to deal with budget constraints. The problem is even harder in the face of multidimensional budget constraints, particularly in the presence of many decision variables involved and the interplay among the decision variables through such constraints. Concise bidding strategies help advertisers deal with this challenge by introducing fewer variables upon which to act. In this paper, we study the problem of finding optimal concise bidding strategies for advertising campaigns with multiple budget constraints. Given bid landscapes—that is, the predicted value (e.g., number of clicks) and the cost per click for any bid—that are typically provided by ad-serving systems, we optimize the value of an advertising campaign given its budget constraints. In particular, we consider bidding strategies that consist of no more than k different bids for all keywords. For constant k , we provide a polynomial-time approximation scheme to optimize the profit, whereas for arbitrary k we show how a constant-factor approximation algorithm can be obtained via a combination of solution enumeration and dependent LP rounding techniques, which can be of independent interest. In addition to being able to deal with multidimensional budget constraints, our results do not assume any specific payment scheme and can be applied on pay-per-click, pay-per-impression, or pay-per-conversion models. Also, no assumption about the concavity of value or cost functions is made. Finally, we evaluate the performance of our algorithms on real data sets in regimes with up to six-dimensional budget constraints. In the case of a single budget constraint, in which uniform bidding (currently used in practice) has a provable performance guarantee, our algorithm beats the state of the art by an increase of 1%–6% in the expected number of clicks. This is achieved by only two or three clusters in contrast with the single cluster permitted in uniform bidding. With multiple budget constraints, the gap between the performance of our algorithm and an enhanced version of uniform bidding grows to an average of 5%–6% (and as high as 35% in higher dimensions).

Keywords: internet advertising; revenue management; budget constraints; bidding strategies; uniform bidding; concise bidding (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/mnsc.2018.3207 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:65:y:2019:i:12:p:5785-5812

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().