Where the Bidding Never Stops

Image

A multitude of tiny auctions are held each day to effectively target online ads. New research from Stanford GSB offers some simple ideas that could help optimize the bidding. | iStock/tudmeak

When you think of the ad business, you might imagine a scene out of Mad Men — wheelers and dealers in a swank Madison Avenue office, fueled by martinis and expense-account lunches. But with the ongoing shift to digital media, that world is fading fast.

Here’s how ad sales happen online: When you click onto a website, the page has some blank boxes that are set aside for ads. Instantly, those slots are posted on an ad exchange, along with data about you (which your browser dutifully hands over). An auction is held, and the winners send their ads to fill the spots. When it works right, you don’t even notice the lag.

Obviously, no person is sitting there bidding on a display ad for a single viewer. With millions of such transactions occurring every day, it’s all done by computers. That means competitive advantage should come down to who has the best algorithms. Instead of Mad Men, think A Beautiful Mind — math wizards conjuring up programs to gain a strategic edge.

Problem is, it’s not obvious which ones are the best algorithms. “There are different types of algorithms in use, and very little is known about the performance they are able to guarantee,” says Yonatan Gur, an associate professor of operations, information, and technology at Stanford Graduate School of Business.

In fact, he says, it wasn’t even clear how to think about it. “What’s the yardstick? What exactly should a good bidding algorithm do? You could look at the traffic or revenue that results from an ad campaign, but that often reflects the stream of opportunities that arose and the financial resources of the advertiser, rather than the quality of the algorithm in use.”

Now there are answers to these questions. In a new paper titled “Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium,” Gur and Santiago Balseiro of Columbia University have come up with three clear criteria for a good ad market algorithm. Then, they present a class of relatively simple algorithms that meet those criteria under typical market conditions and come very close to providing the best possible performance.

That all may sound abstract, but it’s plenty real for the companies involved. While a single ad impression might sell for a fraction of a penny, multiply that across a vast market and you’re once again in the realm of mad money. Online advertising now tops print and TV advertising by a wide margin, with sales of around $100 billion a year in the U.S. alone.

Spending Limits and Ticking Clocks

There are a number of exchanges where these auctions take place, matching viewers, advertisers, and media sites in real time for a fee on each transaction. The biggest is Google Ad Manager, formerly known as DoubleClick. (Google profits from online advertising as both a middleman and a seller of ad space on its own site.)

Gur says advertisers usually operate on these platforms with budgeted campaigns: “They’re participating in many, many auctions, so they typically have a total spend limit for a certain period of time, say, a day or a week.”

That complicates things, he explains, because your algorithm has to bid in a way that depletes the budget at the right time, near the end of the campaign. “If you finish with unused funds or burn through it too quickly, there’s a real opportunity loss. So there’s this idea of budget pacing, which is a pretty well-recognized concept now in the industry, designed to help advertisers pace their spending throughout the campaign.”

In fact, because of the difficulty of this problem and its importance to advertisers, a whole industry has sprung up to provide online bidding services, including budget pacing — essentially trading on their expertise to run the bidding for clients. Exchanges may also offer such services, often for an additional fee.

Whoever’s running the code, the campaign’s goal is to bid as efficiently as possible: getting the biggest return on the budget by winning ad slots for the most valued customers — without paying more than is necessary to win, and ensuring that the money doesn’t run out too soon.

Basically, it’s a constrained optimization problem. Not easy, but computationally doable — except for the fact that many crucial parameters are unknown to the advertiser in real time.

“You see some data on the viewer you’re bidding for, but you don’t know how valuable this opportunity is compared to one that might come along later,” Gur says. “The next viewer might be an even better fit for your brand.” Nor do you know how many other bidders there are, what their budget or strategy is, how much they value this particular viewer, what their expectations are for future opportunities, or whether you’ll face more or less competition later.

In other words, online advertisers have to balance present and future opportunities without knowing much about either. And since most of those unknowns are never revealed and constantly change, advertisers can’t easily test different approaches to see which ones perform best.

Surprisingly Simple Algorithms

To circumvent that issue, Gur and Balseiro tackled the problem theoretically. “Imagine,” Gur says, “that at the end of a campaign, you could go back and replay it with perfect hindsight — so you knew the value of every viewer and all your competitors’ bids — and you could handpick the auctions you wanted to win, given your budget.”

That would be the best-achievable outcome, and it gave the researchers a benchmark. “The question we then asked is, can you approximate that performance over time, in a fairly stable market, with an algorithm that doesn’t know all that information?” That would be their first criterion for a good bidding algorithm.

It sounds like an impossible standard. But using some nifty math, Gur and Balseiro were able to show that you actually can do that — with a surprisingly simple class of algorithms they call adaptive pacing.

The basic idea of adaptive pacing is intuitive: You start with a target expenditure rate — how much you’re willing to spend per auction — and then, depending on how you fare in each successive auction, you scale your bids up or down. If you win, you shade your next bid down. If you lose, you nudge it up. That’s essentially it.

The key, Gur says, is that advertisers learn by participating in the market. “Given the unknowns, you’re bound to lose a certain amount on each auction, compared with the optimal benchmark. But over the course of a campaign, you accumulate information. As the number of auctions goes up, you can drive the average loss down toward zero.” He calls it asymptotic optimality.

The Best of Both Worlds

Of course, that assumes stable markets. When things get bumpy, it might no longer be possible to match the best performance in hindsight. That can happen when the traffic level or competitive environment fluctuates during the campaign — for example, with the entry of a new competitor or a sudden change in the budget of an existing one.

So Gur and Balseiro proposed a second criterion: Could the algorithm guarantee the biggest possible fraction of that benchmark when market conditions suddenly change? In other words, could it ensure that no other algorithm would do better? Again, the answer was yes.

That’s important, Gur says, because advertisers often don’t know market conditions in advance. “It doesn’t hinge on correctly forecasting the market,” he says. “Whether it turns out to be stable or turbulent, adaptive pacing guarantees the best achievable performance in either case.”

Gur and Balseiro also showed that using such algorithms actually induces market stability — their third and final criterion. Specifically, in large online ad markets, if all competitors use adaptive pacing, no one has an incentive to deviate to a different strategy. In game theory, this is known as a Nash equilibrium (named, yes, for John Nash, hero of A Beautiful Mind).

Perhaps the most surprising thing is that the adaptive pacing algorithm is quite easy to implement. “It doesn’t require much technical sophistication or market knowledge,” Gur says. “You don’t need any data about competitors. It’s all based on your own wins and losses. Plus, it’s computationally simple, which matters when you’re bidding in many thousands of auctions a day.”

That’s likely to have interesting implications. Could even small advertisers now forgo the expense of ad-pacing services and do just as well on their own?

Gur won’t go quite that far. “To be clear, we’re talking in this paper about a family of algorithms that meet these criteria. Within that family, some might be marginally better than others — and in the online advertising business, margins can be crucial. But there are now clear and transparent criteria and simple, successful benchmarks against which pacing services can be compared and can demonstrate the additional value they might provide.”