Google Research Blog
The latest news from Research at Google
Conference Report: Workshop on Internet and Network Economics (WINE) 2012
Wednesday, December 19, 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
Tuesday, January 03, 2012
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
Thursday, March 24, 2011
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!
Labels
accessibility
ACL
ACM
Acoustic Modeling
Adaptive Data Analysis
ads
adsense
adwords
Africa
AI
Algorithms
Android
Android Wear
API
App Engine
App Inventor
April Fools
Art
Audio
Australia
Automatic Speech Recognition
Awards
Cantonese
Chemistry
China
Chrome
Cloud Computing
Collaboration
Computational Imaging
Computational Photography
Computer Science
Computer Vision
conference
conferences
Conservation
correlate
Course Builder
crowd-sourcing
CVPR
Data Center
Data Discovery
data science
datasets
Deep Learning
DeepDream
DeepMind
distributed systems
Diversity
Earth Engine
economics
Education
Electronic Commerce and Algorithms
electronics
EMEA
EMNLP
Encryption
entities
Entity Salience
Environment
Europe
Exacycle
Expander
Faculty Institute
Faculty Summit
Flu Trends
Fusion Tables
gamification
Gmail
Google Books
Google Brain
Google Cloud Platform
Google Docs
Google Drive
Google Genomics
Google Maps
Google Photos
Google Play Apps
Google Science Fair
Google Sheets
Google Translate
Google Trips
Google Voice Search
Google+
Government
grants
Graph
Graph Mining
Hardware
HCI
Health
High Dynamic Range Imaging
ICLR
ICML
ICSE
Image Annotation
Image Classification
Image Processing
Inbox
Information Retrieval
internationalization
Internet of Things
Interspeech
IPython
Journalism
jsm
jsm2011
K-12
KDD
Klingon
Korean
Labs
Linear Optimization
localization
Low-Light Photography
Machine Hearing
Machine Intelligence
Machine Learning
Machine Perception
Machine Translation
Magenta
MapReduce
market algorithms
Market Research
Mixed Reality
ML
MOOC
Moore's Law
Multimodal Learning
NAACL
Natural Language Processing
Natural Language Understanding
Network Management
Networks
Neural Networks
Nexus
Ngram
NIPS
NLP
On-device Learning
open source
operating systems
Optical Character Recognition
optimization
osdi
osdi10
patents
ph.d. fellowship
PhD Fellowship
PhotoScan
PiLab
Pixel
Policy
Professional Development
Proposals
Public Data Explorer
publication
Publications
Quantum Computing
renewable energy
Research
Research Awards
resource optimization
Robotics
schema.org
Search
search ads
Security and Privacy
Semi-supervised Learning
SIGCOMM
SIGMOD
Site Reliability Engineering
Social Networks
Software
Speech
Speech Recognition
statistics
Structured Data
Style Transfer
Supervised Learning
Systems
TensorFlow
TPU
Translate
trends
TTS
TV
UI
University Relations
UNIX
User Experience
video
Video Analysis
Virtual Reality
Vision Research
Visiting Faculty
Visualization
VLDB
Voice Search
Wiki
wikipedia
WWW
YouTube
Archive
2017
May
Apr
Mar
Feb
Jan
2016
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2015
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2014
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2013
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2012
Dec
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2011
Dec
Nov
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2010
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2009
Dec
Nov
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan
2008
Dec
Nov
Oct
Sep
Jul
May
Apr
Mar
Feb
2007
Oct
Sep
Aug
Jul
Jun
Feb
2006
Dec
Nov
Sep
Aug
Jul
Jun
Apr
Mar
Feb
Feed
Google
on
Follow @googleresearch
Give us feedback in our
Product Forums
.