Optimal Bidding: A Dual Approach

Carlos Pita
Jul 18, 2019 · 2 min read
Image for post
Image for post

ABSTRACT

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.

Read the full paper here.

jampp-engineering

Creating technology that helps mobile companies grow

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store