When an ad pops up in your Web browser, there’s a lot going on behind the scenes. Advertisers are competing for the space in front of you in what amounts to an auction. In milliseconds, their computers have to decide how much they are willing to pay for a few seconds of your attention, while the website’s computers choose which advertisers’ bids to accept.
Over a longer term, companies like Google or Microsoft that provide the advertising platforms need to decide how to run these auctions, which ads to show and how much to charge for them. “Platforms are constantly thinking about how to improve their system,” explained Éva Tardos, the Jacob Gould Schurman Professor of Computer Science.
But, she said, they’re doing it wrong. They assume that the competitive game has settled into a state game theory researchers call a “Nash Equilibrium,” where all the players are happy with the results they’re getting and stay with their routine. Instead, she pointed out, advertisers are using sophisticated computer algorithms to analyze the market and are constantly changing their tactics.
“The thing you are trying to learn is adapting under your hand,” she said.
Throwing out the old assumption, Tardos and colleagues at the University of Virginia and Microsoft Research have proposed a method for inferring what advertisers believe an ad is worth based on the assumption that bidders have been using what computer scientists call “no-regret learning,” where a computer reviews past performance and concludes, in effect, “If we’d done it that way we’d be happier now.”
They presented their method, along with the results of applying it to a dataset from Microsoft’s Bing search engine, at the 16th ACM Conference on Economics and Computation (EC), June 15-19 in Portland, Oregon. Tardos and co-authors Denis Nekipelov, a former Cornell economics faculty member now at the University of Virginia, and Vasilis Syrgkanis, M.S. ’12, Ph.D. ’14, now at Microsoft Research, received the conference’s Best Paper Award. Coincidentally, Cornell researchers also won the Best Paper award at last year’s EC conference, and this is the university’s third such award since 2006.
Analyzing the Bing search engine dataset, the researchers focused on nine advertising accounts that changed their bid many times an hour, suggesting that the decisions were being made by computers rather than humans. Since the game is played a little differently each time, they averaged over a number of auctions and assumed that each one is a replay of the same game, finding a clue to advertisers’ value in how they adjusted their bids, on the assumption that bidding algorithms seek to minimize regret.
“Advertisers modify their bids reacting to what gets attention and what causes users to buy things,” Tardos said. “Our methods help the platforms use the bidding data to better understand their advertisers.”
Cornell has an active group of researchers working on applications of computing to economics in the Center for the Interface of Networks, Computation and Economics. Along with Tardos, the group includes economists David Easley and Larry Blume; computer scientists Lillian Lee, Robert Kleinberg and Dan Huttenlocher; information scientist Dan Cosley; communication professor Geri Gay; and sociologist Michael Macy.
This article was published by Bill Steele in the Cornell Chronicle on July 17, 2015.