Title: Profit Maximization for Online Advertising Demand-Side Platforms,
Abstract: We develop an optimization model and corresponding algorithm for the
management of a demand-side platform (DSP), whereby the DSP aims to maximize
its own profit while acquiring valuable impressions for its advertiser clients.
We formulate the problem of profit maximization for a DSP interacting with ad
exchanges in a real-time bidding environment in a
cost-per-click/cost-per-action pricing model. Our proposed formulation leads to
a nonconvex optimization problem due to the joint optimization over both
impression allocation and bid price decisions. We use Lagrangian relaxation to
develop a tractable convex dual problem, which, due to the properties of
second-price auctions, may be solved efficiently with subgradient methods. We
propose a two-phase solution procedure, whereby in the first phase we solve the
convex dual problem using a subgradient algorithm, and in the second phase we
use the previously computed dual solution to set bid prices and then solve a
linear optimization problem to obtain the allocation probability variables. On
several synthetic examples, we demonstrate that our proposed solution approach
leads to superior performance over a baseline method that is used in practice.