Proponemos una rigurosa y a la vez práctica estrategia casi-óptima para oferentes (DSPs, o demand-side platforms) en el mercado de subastas en tiempo real (RTB) que escala a miles de campañas publicitarias ofertando programáticamente en miles de millones de subastas por día.

La estrategia se deriva lógicamente a partir de dos tipos de problemas - estilizados pero realistas - de optimización global restringida , sin ninguna regla ad-hoc para la estimación de precios, ritmo de ofertas, etc. El enfoque requiere unos pocos supuestos que identificamos y analizamos, los cuales proveen la base para futuras extensiones a otros tipos de problemas/contratos. Con este método, se espera encontrar una solución casi-óptima resolviendo una relajación convexa del complejo problema combinatorio original. Está basado en la dualidad Lagrangiana, la cual le da un fundamento teórico sólido y bien conocido. Las ofertas óptimas para subasta de primer y segundo precio pueden computarse rápidamente en tiempo real dados los precios sombra de cada restricción a los problemas; por su parte los precios sombra se actualizan diariamente mediante un algoritmo de descenso de subgradiente que converge logarítmicamente. Se espera que el algoritmo sea robusto aún en condiciones reales "ruidosas", a oscilaciones estacionales de mercado y quiebres estructurales.

Para un caso especial, ofrecemos también una derivación alternativa basada en un intuitivo argumento de relajación continua que refuerza nuestra confianza en la solución general aquí propuesta.

Este trabajo se presentó por primera vez en el Taller de Tecnología Publicitaria (AdTech) de KDD 2019.

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.

This paper was first presented at the AdTech Workshop of KDD 2019.