  In online advertising markets, budget-constrained advertisers acquire ad
placements through repeated bidding in auctions on various platforms. We
present a strategy for bidding optimally in a set of auctions that may or may
not be incentive-compatible under the presence of budget constraints. Our
strategy maximizes the expected total utility across auctions while satisfying
the advertiser's budget constraints in expectation. Additionally, we
investigate the online setting where the advertiser must submit bids across
platforms while learning about other bidders' bids over time. Our algorithm has
$O(T^{3/4})$ regret under the full-information setting. Finally, we demonstrate
that our algorithms have superior cumulative regret on both synthetic and
real-world datasets of ad placement auctions, compared to existing adaptive
pacing algorithms.
