WINE 2009

The WINE conf as usual slipped into the fading days of 2009. For me, it started with Andrei Broder's tutorial on Sunday. (Alas, I missed Nikhil's and Tim's tutorials on Saturday). At the basic level, there is a "mapping":
(user queries, context, content of web pages) \rightarrow (suitable ads or creatives),that is a challenge in Internet Ads, and Andrei's tutorial was a flourishing, flowing view of this mapping, mainly as a Information Retrieval (IR) task. Some specific topics beyond the tf-idf like measures and precision-recall curves included (a) looking at ads -- creatives/URLs/bid phrases -- as documents for IR, (b) using taxonomy to capture context for content match, (c) graphical ad selection by looking at this mapping as a recommendation function, (d) bandit variations with taxonomy for new ads, and (e) classification, in particular for rare queries, across multiple languages. These ideas are published in a slew of papers in WWW, KDD, SIGIR confs. Andrei's audience showed an yearning for novelty, and he indulged them with describing challenges in mobile ads, ads over IPTV, VDP newspapers etc. He mentioned the Webscope program to share data with academia, including some data on mapped (query, ad) pairs.

On Monday, I gave a talk on my AdX model for Ad exchanges. It is difficult to communicate how the many decisions you make every week ultimately determines the overall system that audience get to see, and users get to play. I chose to talk about 3 technical results, one each on auction, online optimization and crypto, so people get a little bit of new things in their area of expertise, and a little peek into new things in other areas. I had a bunch of questions over the following two days.

• Why not sell bulk impressions? AdX trades on individual impressions. More sophisticated instruments -- like bulk impressions, futures, derivatives, whatever -- may get traded on top of this primitive.
  
• Why do we need AdX, and why will traders come to AdX? Publishers come for liquidity and better prices. Peyton Young, ever sharp, asked one question over dinner: what is the information that goes from AdX to ad networks. Advertisers come to AdX to potentially influence ad experience across multiple websites easily.
  
• Aren't there complex pathways from advertisers to AdX via multiple interacting ad networks? Yes. In some exchanges like RightMedia, these relationships are endogenized and leads to sophisticated graph problems to determine suitable bids for each impression. In the AdX model, these are exogenized so we can focus on the game theory between AdX and ad networks, or between AdXs.
• How to deal with currency changes? This is not a question of $s vs Euros, but as marketplaces get sophisticated, parties have many different payment schemes (pay per impressions, clicks, conversions, or pay flat fee or for bulk etc), these have to compiled down to per-impression bid in AdX, and this involves taking some statistical risk; it is a nice open problem how to manage this risk. Finally,
  
• Why do you work on AdX and why not work on exchanges in general instead of ad exchanges? It sounds silly, but I want to change the display ads business, and I think AdX will change the display ads business to make it more transparent, robust. In Applied Algorithms research, you have to believe in a goal beyond the theorems.
  

On Tuesday, Peyton Young gave a very interesting talk on adaptive learning rules in complex systems of agents. As an aside, he like many Economists is a swingman, being able to talk macro, micro, math, policy and everything else with insight. His talk was a series of "experiments" in which agents have a state comprising a benchmark of what they did and an aspiration function, and based on choosing to experiment, can change their benchmark. In one version, agents experiment based on mood in an interactive trial and error way. In yet another version, agents have logit response to neighbors' actions (a la some of Larry Blume's work). He showed the connection between these rules and well-known games from weakly acyclic games to interdependent games and spatial potential games. In each case, under some mild conditions, the Nash equilibrium is in some amount of experimentation. I really liked the spirit of this talk, and would have liked to see more, perhaps connection to the bandit literature.

Algorithms Day at Google, NYC

Google NY folks organized an Algorithms Research day following STOC and invited a bunch of STOC attendees. Vahab orchestrated the day, and from what I could see, the team of Nitish, MohammadHossein, Silvio and Jon helped out, may be others too, behind the scenes where I couldnt see. The team did a great job!

Eva Tardos, our newest Godel winner, started the day and talked about sequential auction. Bidders know order of auctions.  v_i(A_i) for items A_i for i. n bidders, m items. Goal: social welfare. Agents strategic. Solution concept: subgame perfect eq (for each subgame history). They looked at PoA of complete as well as incomplete information case.  The talk had an interesting example (Dining Bidders) that showed some of the nuances, and had one nontrivial bidding strategy (and its variant for analysis): each player draws  a random sample of value from others values and uses that to strategize. Costas and Moses asked what value distributions challenge the analysis and how the PoA of 3 is affected by the distribution. I asked, if the order of auctions can be determined and how that affects PoA.

Eyal Manor, the Engg Director for Ad Exchange (AdX), spoke next.  Q & A was the key, this was clearly an opportunity for researchers to get answers from a key person in AdX.  Bobby asked, why push bids for each impression sold, why not let ad networks push bids in a flexible way in small bulks. Eyal's answer was,  real time strategies seem important to AdX players.  Someone asked, there is information asymmetry, can AdX equalize the information available to all parties. Eyal answered that AdX did not own all the information in the ecosystem, publishers and other players do, and their data is private or secret. Eva asked, is BlueKai a pain in AdX operations? Eyal said they were good partners. Eva pointed out that Economics says what data should be shared: platforms should share, buyers should not have to share. Again, the issue is data is owned by many parties. Moses asked, what data are not shared. Eyal gave the example of someone day bought a ticket, bank login etc.

Alfred, VP of Google Research, spoke via video. He used the occasion to let folks know that Google was providing some space for Cornell's operations in NY, which is good news for Academia. Alfred couldnt resist posing some technical  challenges: we dont understand fairness of auctions to individual users; we have complex auctioning systems and very sophisticated distributed systems, how do we quantity and control risk?

There were several other talks during the day (bobby, gagan, mohammad, andrew mcgregor, et al) which I am unable to summarize here. Vahab gave an excellent overview of research in Google NY and provided pointers to folks who were experts in different projects. Towards the end, Mukund spoke about some interesting problems with interpreting sales data, and our other new Godel Prize winner Tim spoke about simple and optimal auctions.

Prabhakar called me an old timer, and I felt like one, slightly out of touch with it all. I ran the first of such meetings in 2009 after SODA, and it is great to see the continuing tradition. It was also good to catch up with Sanjeev, Stefano, Sampath, Seffi and others, that is just the S's.

Ad Exchange (AdX) Update

Well, it has been a year+ since DoubleClick Ad Exchange launched. Here is an update: it made the top 10 for 2010 digital hotlist. Others on the list include facebook, twitter, zynga, iPad... Understandably, AdX is down in the list in this great company (just made the 10th). Go AdX! Here is the entry:

Advertisers are abandoning traditional buying models on the Web in favor of buying specific audiences all over the Internet using a wealth of data. Nearly every ad agency worth its salt has established a trading desk to purchase this highly targeted ad inventory at scale in real time. Ad exchanges are at the heart of this macro trend, with Google's DoubleClick Ad Exchange having emerged as the clear leader. The exchange, which rolled out last fall, trades inventory from 50-plus ad networks that represent thousands of Web publishers large and small. Naturally, individual publishers also come to the exchange to directly unload leftover avails. Per Google, those publishers enjoy prices for their ad space that are an average of 130 percent higher than those achieved by ad networks. As inventory becomes more abundant across the Web, the importance of exchanges will only expand. Google's competition in the space will grow too, as independent exchanges like OpenX gain traction.

• Hundreds of thousands of advertisers
• Number of transactions tripled over past year
• Average CPM lift of 136 percent compared with standard ad inventory, per Google research

Congratulations to the team. Here is a link to all my previous posts on AdX.

Visiting Columbia IEOR Dept

Researchers of interest to us are hidden in many depts in a typical university (CS, IS, OR, Business, EE, whatever), some even 100 city blocks uptown. I visited the Industrial Engineering and Operations Research dept at Columbia U, and presented an hour long talk on Ad Exchanges. I bring a CS/Algorithms perspective to problems, but the researchers in OR/Stochastic optimization have different perspective that will be particularly useful for problems in AdX and I look forward to learning from them.

• Nicolas Stier: Spoke about nonlinear optimization with complements and relationship to transportation systems; endogenizing smooth cost functions a la Klemperer's work on supply function equilibria; principle agents problem and contract theory for employer-employee relationship; models for net neutrality.
  
• Mariana Olvera, Assaf Zeevi and Ciamac C. Moallemi, over lunch. Relative sizes of display markets.
  
• Santiago Balseiro: Stochastic control modeling of AdX optimization problems.
  
• Mariana Olvera: Stochastic recursion and explanations for power law distribution of PageRank based on indegrees. Mariana noticed that short ads are repeated sometimes to fill in long slots, ad scheduling can do better.
  
• Vineet Goyal: Stochastic versions of query optimization problems. Electricity markets.
  
• Chris Wiggins: Applied mathematician, physicist, machine learner, computational biologist and more. Among other things, we managed to catch up on Mark Hansen's sabbatical at NY Times R&D and art installations.
• Jay Sethuraman: Reminisced about a SODA talk long time ago on combinatorial approach to computing determinants.
• Garud Iyengar: He pointed out that AdX standardizes the goods that are traded in spot auctions, and we discussed how to standardize goods to trade in futures market and pricing challenges.
  
• Garud Iyengar and Victoria Stodden ( a CS PhD + law, combining sparse approximation and legal/policy aspects of data, both of great interest to me): Dinner conversation on challenges with NSF's new data sharing policy.
  

Full day even without meeting my CS colleagues.

Data Science and Online Ads: Panel in NYCE 2014

Thanks to Arash Asadpour, Mohammad Hossein Bateni and Alex Slivkins for organizing the 2014 NY Area CS and Econ (NYCE) day in NY.   I will let the organizers blog about the day, it was a superb program.

I organized a panel on Data Science in Online ads. The panelist are stars and represented a constellation of perspectives in this complex ecosystem.

• Matt Curcio is from Neustar (via Aggregate Knowledge). He builds and supports a neutral data platform for advertisers to gather and analyze ads data. He is remarkably broad, using data streaming to data privacy in this work. He spoke about the challenge of getting data scientists to collaborate, no matter the company they worked. 
• Chris Wiggins is now the Chief Data Scientist at NY Times. He spoke about data products at NYT and estimating Long Term Value (LTV) of users. He also talked about placing house ads as an example of reenforcement learning. 
• Aparna Pappu runs AdX at Google. She focused on AdX and described the goal of fair transfer of value from advertiser to publishers. She mentioned many specific data issues: there are gaps in their data since they dont observe all online events; data viz is hard; there is asymmetry of info since advertisers may know about users than any specific publisher; AdX can not share data equally with all parties; and finally, she spoke about great diversity of data they have so it is hard to find natural segmentations of publishers and advertisers. 
• Paul Barford is now the Chief Scientist at Comscore, Inc following their acquisition of his Mdot. He described his consulting experience at BIM which is a publisher network that led him to the problem of detecting fraud clicks. He said, when systems are complex and there is money involved, there are bad actors, ie, fraud is a problem. Further, he quoted that data science starts with measurement and it is hard to gather data from ads platforms. 
• Neal Richter is now the CTO at Rubicon Project. He spoke about how ads sales is changing into being automatic, and a challenge in petabytes of analyses he does with 200B transactions a day is to make the analyses and conclusions explainable to others including biz folks. 
• Catherine Williams is Head of Data Sciences at AppNexus. She described AppNexus as the largest independent (non FB/GOOG) programmatic media co. and not involved with PII. AppNexus has a performance marketplace which is nice. She spoke about the challenge of suitable incentives for various types of content and stretched us to consider freedom of speech issues when we emphasize one type of content over the others. 
• Claudia Perlich is Chief Scientist at Dstillery. She spoke about the predictive modeling and machine learning challenges in prospecting for ad targets. In particular she pointed out that it is not as much about predicting if you will buy X as it is to convince/convert you to buy X. She quipped that from their lat/long data of users, 30% os US population travels above the speed of sound! She also talked about how not to look at artificial metrics to improve in ad platforms, and the challenges of getting performance data from networks. 
• Jon Krohn is a Data Scientist in the orbit of Omnicom, a large media company. He started with the observation that you need data to spend money well, and went to the board to draw the ``river of money'' from advertisers to agencies and media companies like his, to eventually publishers, with $s dwindling along the way with 20--30 hands that touch the transaction. 

I summarized their presentations. Discussions ensued:

• Costis Maglaras asked, is the ad market going to be like DJ with small transaction cost or like Christies with XX% cut? Goods in ads are ephermeral, valued differently by different parties and cant be retraded, so not clear financial analogies apply. 
• Vahab Mirrokni asked, is the ad market converging to reservations/allocation or auctions? Catherine mentioned that platforms like AppNexus are supporting many different types of markets from reservations to private packages/deals to RTB and performance. 
• I asked if large distributed ML package that searches automatically over models and parameters will suffice for ad business. No, because information is not complete, players may not be rational, not single objective optimization, signal is weak, moving targets, etc. 
• I asked why more of microeconomic concepts didnt penetrate ad markets, like substitutable goods. This is because publishers dont think their inventory is substitutable, and there are handcuffs around who owns data and privacy isseus, so data permissions dont let this info be usable. Paul Barford said Comscore is an exception of data and he was willing to work with academics on data access. 

I now have the formula for a great panel: recruit great professionals, let them go, and sit back. I enjoyed the panel immensely. I hope researchers connect with the folks above, there is a lot we can gain. It was good to sneak into NY academic scene, if only briefly. 

Google Updates

Google announced on Thursday in their earnings call that: "In addition to the $5 billion run rate for display, Google reported that its DoubleClick ad exchange had 130% growth in spending year-over-year. One driver of display growth was marketer interest in buying for specific audience categories -- such as hybrid-car buyers or adventure travelers -- which the technology now can target, according to SVP-Advertising Susan Wojcicki." So AdX is growing.

I have been playing with interactive graphing built into Google search. I enjoy typing in functions like sin(1/x)+x^2 = in the box and playing with the graph, zooming, reading off values, etc. (sometimes you see a little message at the bottom, if the function is not plotted correctly and an explanation why).

WWW 2010

The WWW Conf will take place in a week. On Friday Apr 30th at 1-2.30 PM, I will give an Industry Track talk on Google Ad Exchange (AdX). Actually I lie: the talk will be given by Scott Spencer, Eyal Manor and I. Scott will talk about the Business, Eyal about the Engineering, and I, about the Research. Of course, Scott can easily talk about the research, and Eyal about the business, but we had to divide the task in some way. I am quite excited about this three-faceted talk. So, I hope those of you who find themselves in Raleigh, NC, on Friday will show up for the talk (the Industry track program is not on the webpage yet).

Ashish, Srikant and I area-chaired Internet Monetization track and have to thank the PC members (and of course the many anonymous referees) who helped tremendously: Deepak Agarwal, Moshe Babaioff, Maria-Florina Balcan, Nicole Immorlica, David Parkes, Diane Tang, Kamal Jain, William Walsh, Michael Wellman, Vahab S. Mirrokni, Alessandro Acquisti, Sharad Goel, Tim Roughgarden, John Chuang, Byron Ellis, Rob Luenberger, and Matt Richardson.

Ad Exchanges Revisited

My research on Ad Exchanges has continued, but I have been quiet on blogging about the business. Here are some updates.

• It has been more than a year since the launch of the DoubleClick Ad Exchange. It seems to be doing well. See the presentation here for stats. Of relevance to research: "in January of last year the real time buys on DoubleClick’s AdExchange represented just 8 percent of the total. By January of this year, that figure was 64 percent." So, many research problems with real time bidding are now important, from optimizing call out, to understanding the game theory, arbitrage and others.

• Individual publishers are building private ad exchanges around their own inventory. CBS Interactive, Forbes.com, NBC Universal (universal audience platform), Weather.com (channel 5) and Turner Broadcasting Systems. "For publishers, setting up exchanges has several advantages: they cut out the middlemen and they allow the publishers greater control over consumer data." Check out NY Times article. This means there is a lot of research to be done on inventory optimization, understanding the dynamics of advertisers automatically choosing across publishers and so on.
  

Hooray for AdX research!

EC & WSA

I went underground for past two weeks, preparing for my tutorial on ad exchanges at EC. I will put the slides online as soon as I write up some of the new results, but meanwhile the older papers are here. There were like 70+ people in the audience Monday morning. In the first half, I described my AdX model. It is a block diagram with a sequence of 7 operations, and immediately I knew the audience just wanted to get past it and see theorems/results. But diagrams like that hide the nuances of the many decisions one makes in building a system and I took some time to point out to the audience some of these decisions. Then the audience got lively and started poking at the design and after a prolonged back-and-forth, I felt comfortable that the audience had an appreciation for the model and the underlying system. The second half was mainly research results, some old, some new. Tuomas Sandholm, David Parkes and others during after the tutorial had many questions.

In the afternoon on Monday, Aranyak and Vahab spoke about ad allocation problems. These are variants of bipartite matching problems from online to budgeted, stochastic or whatever. Aranyak spoke about online Adwords problem and discussed throttling and quality scores which are difficult areas to theorize, but with deliberate speak, Aranyak managed it. (Puzzle: algorithms to maximize avg value of items in the knapsack.) In a conflict of styles, Vahab who went next, took bigger bites and larger chunks of problems, more focused on social network and display ads problems.

Tuesday was the workshop on sponsored search auctions. Michael Ostrovsky spoke about setting reserve prices in Yahoo!. The discussion for or against reserve prices has swung around a few times, and Michael's work showed, via live experiments at Yahoo! that revenue can be optimized by tweaking reserve prices. He claimed 9-digit $s improvement and there was a lot of debate about this among the audience later. Preston McAfee spoke about Yahoo! as a large publisher network that had to decide how to split its ad impression among various sold contracts as well as when to go to an ad exchange for the spot market. This was the talk I was looking forward to most since it was closest to my interest, and Preston has a good sense of humor ("it is bad when the audience not only looks at the watch, but starts shaking it in disbelief"). Preston basically chose to talk about his paper on representative allocations; many questions still linger in audiences' mind about whether this is a suitable allocation, is it really appropriate to price them by spot market outcome and others (that came up during my tutorial when I discussed this paper), but Preston said Yahoo! uses these ideas.

Tim is always a pleasure to listen: he spoke about all auctions that have VCG equilibriums for sponsored search. John Hegeman gave one of the most interesting talks in the workshop on ad auctions at facebook, including their choice of VCG (not GSP). Susan Athey gave an insightful talk on detailed modeling and understanding sponsored search including price elasticity.

Some important discussions:

• Moshe Tennenholtz, who has been on all sides of the aisle from academia to startups and corporate labs, is a real thinker. Among other things we discussed: how much research/academia does Apple, the company of innovation as most would boast, support?
  
• Chris Dellarocas who has done some very interesting work with reputation mechanisms, asked what parts of sponsored search research could (should) Academia contribute, and is not in the realm of only corporate research.
  

EC + STOC + CCC + Wkshps: collision of many overlapping communities. I could not sample all of the fare.

AdX: Industry view

Here is a whitepaper on Ad Exchanges, that gives an industry view:

• Getting Real: Ad Exchanges, RTB and the Future of Online Advertising, by desilva+phillips, LLC.

The whitepaper does a nice job of laying out the landscape and explores some tricky topics of competition. Here is a set of blog-responses to the above: Darren Harmen, lookery, Ad Exchanger, Etc.

Btw, I will giving an Industry Track talk at the WWW 2010 conference on Ad Exchanges, Friday Apr 30, 1--2.30 PM. Any pointers, papers, etc. welcome. This talk will be about the design decisions in the product, engineering challenges, algorithmic and game-theoretic research issues, and finally, a discussion of the ecosystem (I dislike that word!) around Ad Exchanges.