The Trading Agent Competition’s Ad Auctions (TAC/AA) game, a tournament where computer science students and researchers craft programs (called ‘agents’) to battle each other in a simulated auction environment similar to the one which search engine marketers deal with on a daily basis, was held last week at the Association of Computing Machinery (ACM) conference on Electronic Commerce at Harvard University in Cambridge, MA. (A previous post, ‘Wish Brown Luck at the Trading Agent Competition‘ reviewed the rules and provided some background information.) Though geared heavily toward academics, the conference did attract attendees from a limited number of corporate and government entities, including Google, Microsoft, Facebook, Yahoo!, the Federal Reserve Bank of New York and, of course, The Search Agency.
This year’s competition hosted 11 teams from universities around the world, including some who participated in 2009’s inaugural Ad Auctions tournament, like Wayne State University and the University of Zagreb (Croatia), and some new entrants, like Tel-Aviv University (Israel) and the Nanyang Technological University (Singapore).
Congratulations are in order for all of the tournament’s participants (a full list of whom can be found at the TAC/AA website run by the Swedish Institute of Computer Science), but especially for this year’s champion agent, TacTex, designed by Dr. David Pardoe of the University of Texas. Second place was won by Schlemazl, designed by a team from Brown University. Perhaps the most surprising finish was the third-place position taken by Mertacor, designed by Andreas Symeonidis of the Aristotle University of Thessaloniki (Greece). Though Mertacor didn’t even make the final round in the 2009 tournament, in a nail-biting finish this year it jumped into second place in the 82nd game (out of 88 total), before losing that position to Brown’s agent with just two games left before the end of the tournament.
“Our second-place finish [over Mertacor] had no statistical significance at all,” Brown team member Jordan Berg demurred immediately after the tournament on the bus ride to a reception at Microsoft’s New England Research & Development (NERD) Center’s building overlooking the Charles River. “A few games before the end, they were in second place. At the end we were in second place. If there were a few more games…” he said, pausing to shrug his shoulders, “…eh, who knows?”
Though the basic rules of the competition were largely unchanged from 2009’s inaugural Ad Auctions tournament, the designers at the University of Michigan, including Professor Mike Wellman, and Dr. Patrick Jordan (now of Yahoo! Labs, but who helped develop the game while a graduate student there) made some notable modifications. “The participants in the 2009 tournament created some very clever strategies,” Dr. Jordan explained, “exploiting information in ways we did not anticipate.”
One change, made at the suggestion of Professor Amy Greenwald of Brown University, was that the agents now receive only an approximate value of the average position of their competitors’ ads, rather than an exact value. “Amy’s reasoning was that this more closely models the real-world ad auctions problem,” explained Brown team member and Prof. Greenwald’s graduate student, Eric Sodomka, “you may be able to perform some searches to get a rough idea of your opponents’ average positions, but you don’t receive this information precisely.”
Another notable modification was the use of higher reserve scores. In 2009’s competition, the simulated search engine set a very low minimum (or ‘reserve’) bid which an advertiser was required to supply to be able to participate in a given ad auction. But part of Dr. Jordan’s Ph.D. thesis showed that the search engine could get a much higher revenue for itself by using moderate reserve scores. (In effect, with the higher reserve scores, the search engine took more money for itself that otherwise would have become profit for the advertisers.)
One result was that almost all of the agents saw their 60-day profit levels fall significantly from the 2009 tournament to 2010’s. For example TacTex, Dr. Pardoe’s champion agent, averaged about $79,000 profit in 2009 but saw its average profit cut to about $58,000 in 2010. Schlemazl, the second-place finisher, went from about $75,000 to $53,000. Even Mertacor, which was eliminated in the semi-finals in 2009 when it earned about $62,000 in profit, won third place with about $52,000 in 2010. (The biggest exception to this trend was the CrocodileAgent, designed primarily by Master’s degree student Irena Siranovic of the University of Zagreb, which averaged only $34,000 in profit in 2009 but about $48,000 in 2010, for a 6th-place finish.)
Perhaps what was most surprising about the Ad Agent competition, both in 2009 and 2010, was how close the finishers were to each other given their diversity of approaches to this problem. The CrocodileAgent team’s advisor, Professor Vedran Podobnik, explained that the newer version of their agent focuses much more on the conversion rate (the ratio of the number of conversions and clicks), the distribution capacity of the advertisers (an upper limit on the number of conversions an advertiser can fill before beginning to receive a penalty to the conversion rate), and on daily spending limits. Dr. Pardoe’s agent uses the information given about the average position of each advertiser’s ad to determine when each agent entered and exited the daily bidding, among other things. QuakTac, a 2009 entrant from the University of Pennsylvania, relied on ‘bid shading’, the practice of bidding a certain amount below one’s true value-per-click in order to help guarantee profit. And Brown’s agent used a mixture of the ‘multi-choice knapsack problem’ (MCKP) algorithm and rules-based approaches. “Patrick Jordan, Michael Wellman, and the rest of the Michigan team deserve much credit,” Eric Sodomka of Brown University said,” for making a game that has produced what seems to be a wide variety of viable strategies to the ad auctions problem.”
So I asked David Pardoe, who will soon finish the work for his Ph.D. degree, since over the past 8 years he’s won half of the bidding agent competitions he’s entered, including both of the TAC Ad Auction tournaments, “What are you going to do now, go to Disneyland?”
“Yeah,” he answered skeptically, slowly bobbing his head, “I’m job hunting. I’m looking for a job.”
Tags | trading agent competition