Optimal bidding: a dual approach
Paper |
Carlos Pita
We propose a practical yet rigorous near-optimal bidding strategy for demand-side platforms (DSPs) that scales to thousands of advertising campaigns programmatically bidding in real-time (RTB) in billions of auctions per day. The strategy is logically derived from two different ---stylized but realistic--- constrained global profit maximization problems, so there are no ad hoc rules for pacing, pricing, etc. The approach relies on a few assumptions that we identify and analyze, providing a basis for further extensions to other kinds of problem/contract. It is expected to find a near-optimal solution by solving a convex relaxation of the original hard combinatorial problem. It is based on Lagrange duality so it has a sound, well-known, theoretical foundation. Optimal bids for first/second-price auctions can be cheaply computed in real-time given the shadow prices of the problem constraints; on the other hand, shadow prices are daily updated by a simple subgradient descent algorithm that converges logarithmically. The algorithm should be robust in the face of noisy real-life environments and of market seasonal oscillations and structural breaks. For a special case, we also offer an alternative derivation based on an intuitive continuous relaxation argument that reinforces our confidence in the general solution proposed here.