  Budget-management systems are one of the key components of modern auction
markets. Internet advertising platforms typically offer advertisers the
possibility to pace the rate at which their budget is depleted, through
budget-pacing mechanisms. We focus on multiplicative pacing mechanisms in an
online setting in which a bidder is repeatedly confronted with a series of
advertising opportunities. After collecting bids, each item is then allocated
through a single-item, second-price auction. If there were no budgetary
constraints, bidding truthfully would be an optimal choice for the advertiser.
However, since their budget is limited, the advertiser may want to shade their
bid downwards in order to preserve their budget for future opportunities, and
to spread expenditures evenly over time. The literature on online pacing
problems mostly focuses on the setting in which the bidder optimizes an
additive separable objective, such as the total click-through rate or the
revenue of the allocation. In many settings, however, bidders may also care
about other objectives which oftentimes are non-separable, and therefore not
amenable to traditional online learning techniques. Building on recent work, we
study the frequent case in which advertisers seek to reach a certain
distribution of impressions over a target population of users. We introduce a
novel regularizer to achieve this desideratum, and show how to integrate it
into an online mirror descent scheme attaining the optimal order of sub-linear
regret compared to the optimal allocation in hindsight when inputs are drawn
independently, from an unknown distribution. Moreover, we show that our
approach can easily be incorporated in standard existing pacing systems that
are not usually built for this objective. The effectiveness of our algorithm in
internet advertising applications is confirmed by numerical experiments on
real-world data.

Computer Science and Game Theory