Conference Report: Workshop on Internet and Network Economics (WINE) 2012

Posted by Vahab Mirrokni, Research Scientist, Google Research New York

Google regularly participates in the WINE conference: Workshop on Internet & Network Economics. WINE’12 just happened last week in Liverpool, UK, where there is a strong economics and computation group. WINE provides a forum for researchers across various disciplines to examine interesting algorithmic and economic problems of mutual interest that have emerged from the Internet over the past decade. For Google, the exchange of ideas at this selective workshop has resulted in innovation and improvements in algorithms and economic auctions, such as our display ad allocation.

Googlers co-authored three papers this year; here’s a synopsis of each, as well as some highlights from invited talks at the conference:

Budget Optimization for Online Campaigns with Positive Carryover Effects
This paper first argues that ad impressions may have some long-term impact on user behaviour, and refers to an older WWW ’10 paper. Based on this motivation, the paper presents a scalable budget optimization algorithm for online advertising campaigns in the presence of Markov user behavior. In such settings, showing an ad to a user may change their actions in the future through a Markov model, and the probability of conversion for the ad does not only depend on the last ad shown, but also on earlier user activities. The main purpose of the paper is to give a simpler algorithm to solve a constrained Markov Decision Process, and confirms this easier solution via simulations on some advertising data sets. The paper was written when Nikolay Archak, a PhD student at NYU business school, was an intern with the New York market algorithms research team.

On Fixed-Price Marketing for Goods with Positive Network Externalities
This paper presents an approximation algorithm for marketing “networked goods” and services that exhibit positive network externalities - for example, is the buyer's value for the goods or service influenced positively by other buyers owning the goods or using the service? Such positive network externalities arise in many products like operating systems or smartphone services. While most of previous research is concerned with influence maximization, this paper attempts to identify a revenue maximizing marketing strategy for such networked goods, as follows: The seller selects a set (S) of buyers and gives them the goods for free, then sets a fixed per-unit price (p), at which other consumers can buy the item. The strategy is consistent with practice and is easy to implement. The authors use ideas from non-negative submodular maximization to find the optimal revenue maximizing fixed-price marketing strategy.

The AND-OR game: Equilibrium Characterization
Yishay Mansour, former Visiting Faculty in Google New York, presented the results; he first argued that the existence and uniqueness of market equilibria is only known for markets with divisible goods and concave or convex utilities. Then he described a simple market AND-OR game for divisible goods. To my surprise, he showed a class of mixed strategies are basically the unique set of randomized equilibria for this market (up to minor changes in the outcome). At the end, Yishay challenged the audience to give such characterization for more general markets with indivisible goods.

Kamal Jain of Ebay Research gave an interesting talk about mechanism design problems, inspired by application in companies like Ebay and Google. In one part, Kamal proposed "coopetitive ad auctions" for settings in which the auctioneer runs an auction among buyers who may cooperate with some advertisers, and at the same time compete with others for sealing advertising slots. He gave context around "product ads"; for example, a retailer like Best Buy may cooperate with a manufacturer like HP to put out a product ad for an HP computer sold at Best Buy. Kamal argued that if the cooperation is not an explicit part of the auction, an advertiser may implicitly end up competing with itself, thus decreasing the social welfare. By making the cooperation an explicit part of the auction, he was able to design a mechanism with better social welfare and revenue properties, compared to both first-price and second-price auctions. Kamal also discussed optimal mechanisms for intermediaries, and “surplus auctions” to avoid cyclic bidding behavior resulted from running naive variants of first-price auctions in repeated settings.

David Parkes of Harvard University discussed techniques to combine mechanism design with machine learning or heuristic search algorithms. At one point David discussed how to implement a branch-and-bound search algorithm in a way that results in a "monotone" allocation rule, so that if we implement a VCG-type allocation and pricing rule based on this allocation algorithm, the resulting mechanism becomes truthful. David also presented ways to compute a set of prices for any allocation, respecting incentive compatibility constraints as much as possible. Both of these topics appeared in ACM EC 2012 papers that he had co-authored.

At the business meeting, there was a proposal to change the title of the conference from “workshop” to “conference” or “symposium” to reflect its fully peer-reviewed and archival nature, keeping the same acronym of WINE. (Changing the title to “Symposium on the Web, Internet, and Network Economics” was rejected: SWINE!) WINE 2013 will be held at Harvard University in Boston, MA, and we look forward to reconnecting with fellow researchers in the field and continuing to nurture new developments and research topics.

Google Correlate expands to 49 additional countries

Posted by Matt Mohebbi, Software Engineer

In May of this year we launched Google Correlate on Google Labs. This system enables a correlation search between a user-provided time series and millions of time series of Google search traffic. Since our initial launch, we've graduated to Google Trends and we've seen a number of great applications of Correlate in several domains, including economics (consumer spending, unemployment rate and housing inventory), sociology and meteorology. The correspondence of gas prices and search activity for fuel efficient cars was even briefly discussed in a Fox News presidential debate and NPR recently covered correlations related to political commentators.

Health has always been an area of particular interest to our team (Matt Mohebbi, Julia Kodysh, Rob Schonberger and Dan Vanderkam). Correlate was inspired by Google Flu Trends and many of us worked on both systems. So we were very excited when the BioSense division at the CDC published a page which shows correlations between some of their national trends in patient diagnosis activity and Google search activity. With just three years of weekly data, relevant search terms are surfaced. For example, the time series for bloody nose surfaces "bloody snot" and "blood in snot".

While these terms shouldn't come as a surprise, there are others which are more interesting, including searches related to static electricity, dry skin, and red cheeks. Of course, correlation is not causation but we hope that Correlate can be used as a method for researchers to generate new hypotheses with their data.

To help researchers outside the United States, we're pleased to announce support for 49 additional countries in Google Correlate. It's now possible to see correlations like "snorkeling" in Australia, "cherry blossoms" in Japan , and "beer garden" in Germany. We look forward to seeing what new correlations researchers can find with this data!

Reading tea leaves in the tourism industry: A Case Study in the Gulf Oil Spill

Posted by Hyunyoung Choi and Paul Liu, Senior Economists

A few years ago, our in-house economists, Hal Varian and Hyunyoung Choi, demonstrated how to “predict the present” with monthly visitor arrivals to Hong Kong. We took this idea further to see if search queries could predict the future. If users start to research their travel plans some weeks or months in advance, then intuitively shouldn’t we be able to extend "predicting the present" into "predicting the future?" We decided to test it out by focusing on a region whose tourism was recently severely impacted: Florida’s gulf coast.

With the travel industry still in the midst of recovering from a deep recession, the Gulf Oil spill had the potential to do significant economic damage. Our case study on the Gulf Oil spill helped find useful insight into people’s future travel plans to Florida; in fact, we found that travel search queries actually were good predictors for trips to Florida, and destinations within Florida, about 4 weeks later.

The results we saw surprised us. Google Insights for Search suggested that at least with respect to hotel bookings (using data from Smith Travel Research, Inc.), the aggregate effect of the oil spill was modest on Florida travel, since travelers tended to shift their destinations from the affected regions on the west coast to the east coast or central regions of Florida. In particular, hotel bookings for affected areas along the Gulf coast were 4.25% less than predicted, and unaffected areas along the Atlantic coast were 4.89% greater than predicted.

You can read the full case study here or try your own hand at predicting the future!