  Budget pacing is a popular service that has been offered by major internet
advertising platforms since their inception. Budget pacing systems seek to
optimize advertiser returns subject to budget constraints by smoothly spending
advertiser budgets. In the past few years, autobidding products that provide
real-time bidding as a service to advertisers have seen a prominent rise in
adoption. A popular autobidding strategy is value maximization subject to
return-on-spend (ROS) constraints. For historical/business reasons, the systems
that govern these two services, namely budget pacing and ROS pacing, are not
always a unified and coordinated entity that optimizes a global objective
subject to both constraints. The purpose of this work is to theoretically and
empirically compare algorithms with different degrees of coordination between
these two pacing systems.
  In particular, we compare (a) a fully-decoupled sequential algorithm that
first constructs the advertiser's ROS-pacing bid and then lowers that bid for
budget pacing; (b) a minimally-coupled min-pacing algorithm that runs these two
services independently, obtains the bid multipliers from both of them and
applies the minimum of the two multipliers as the effective multiplier; and (c)
a fully-coupled dual-based algorithm that optimally combines the dual variables
from both the systems. Our main contribution is to theoretically analyze the
min-pacing algorithm and show that it attains similar guarantees to the
fully-coupled canonical dual-based algorithm. On the other hand, we show that
the sequential algorithm, even though appealing by virtue of being fully
decoupled, could badly violate the constraints. We validate our theoretical
findings empirically by showing that the min-pacing algorithm performs almost
as well as the canonical dual-based algorithm on a semi-synthetic dataset based
on a large online advertising platform's data.

Computer Science and Game Theory