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.
Third Market Algorithms and Optimization Workshop at Google NYC
Friday, June 15, 2012
Posted by Nitish Korula and Vahab Mirrokni, Google Research, New York
There are fascinating algorithmic and game theoretic challenges in designing both Google’s internal systems and our core products facing hundreds of millions of users. For example, both Google AdWords and the
Ad Exchange
run billions of auctions a day; showing the perfect ad to every user requires simple mechanisms to align incentives while simultaneously optimizing efficiency and revenue.
We think that research in these areas benefits from close cooperation between academia and industry. To this end, last week we held the
Third Market Algorithms and Optimization Workshop at Google
, immediately after
STOC 2012
. We invited several leading academics in these fields to meet with researchers and engineers at Google for a day of talks and discussions.
As a recent winner of the Godel prize,
Éva Tardos
from Cornell led off with a discussion of how to achieve efficiency in sequential auctions where bidders arrive and depart one at a time instead of all bidding simultaneously.
Eyal Manor, Google engineering director for the Ad Exchange, gave an overview of the design and functioning of the exchange. This was an opportunity to have questions answered by the absolute expert, and the participants took full advantage of it!
Costis Daskalakis
and
Pablo Azar
from MIT and
Tim Roughgarden
from Stanford talked about different aspects of Optimal Auctions in Bayesian Settings. Costis talked about efficient implementation of optimal auctions in a class of combinatorial auctions. Both Tim and Pablo discussed optimal auctions in Bayesian settings with limited information. Tim, our other Godel prize winner, promoted the idea of designing simple auction rules that are independent of the distributions of buyers’ valuations, and Pablo presented optimal auction rules using only the mean and standard deviation of buyers’ valuations.
Bobby Kleinberg
from Cornell and
Gagan Goel
from Google NYC presented recent work on pricing with budget constraints. Bobby’s talk was about procurement auctions where the auctioneer acts as a buyer with a budget constraining her procurements. Gagan, on the other hand, discussed Pareto-optimal ascending auctions where the auctioneer is selling to budget-constrained buyers. This has direct applications in Google AdWords auctions as advertisers aim to increase performance while staying within budget constraints.
With our mission of organizing all the world’s information, Google needs superior algorithmic techniques to analyze extremely large data sets. We had two talks on new algorithmic ideas for Big Data. From academia,
Andrew McGregor
gave an introduction to the new field of graph sketching. Though a graph on n nodes is O(n^2)-dimensional, Andy described how to find interesting properties of the graph (such as connectivity, approximate Minimum Spanning Trees, etc.) using only O(n polylog(n)) bits of information. These algorithms were based on clever use of the homomorphic properties of random projections of the graph’s
adjacency matrix
. In the next talk,
Mohammad Mahdian
from Google MTV explained a new model for evolving data; even a ‘simple’ problem like sorting becomes interesting when the order of elements changes over time. Mohammad showed that even if element swaps occur at the same rate as comparisons, one can compute an ordering with
Kendall-Tau distance
O(n ln ln n) from the true ordering at any time, very close to the optimal Ω(n).
Later,
Mukund Sundararajan
from Google MTV discussed algorithmic problems in interpreting and presenting sales data to advertisers. He challenged us to design flexible human-friendly optimization algorithms that can be adopted and tuned by humans. Toward the end of the workshop,
Varun Gupta
, Google NYC postdoctoral researcher, gave a short presentation about the use of primal-dual techniques for online stochastic bin packing with application in assigning jobs to data centers.
We also discussed some of the main activities in the algorithms research group in New York, like the use of primal-dual techniques in online stochastic display ad allocation at Google and large-scale graph mining techniques based on
MapReduce
and
Pregel
.
Corinna Cortes
, Director of Research in New York, and
Alfred Spector
, VP of Research and Special Projects, gave short speeches. Corinna talked about our statistics, machine learning, and NLP research groups in New York, and Alfred challenged us to design mechanisms to take into account fairness in allocations and pricing. For more details, see the
blog post
by our colleague,
‘Muthu’ Muthukrishnan
.
Part of what makes Google a fascinating place to work is the wealth of algorithmic and economic research challenges posed by Google advertising and large-scale data analysis systems. These challenges define research directions for the computer science and economics research communities. Workshops like this and our weekly research seminars help us continue collaborations between Google and academia. We hope to post videos of this workshop shortly, and look forward to organizing many more such events in the future.
Games, auctions and beyond
Wednesday, March 16, 2011
Posted by Yossi Matias, Senior Director, Head of Israel R&D Center
In an effort to advance the understanding of market algorithms and Internet economics, Google has launched an academic research initiative focused on the underlying aspects of online auctions, pricing, game-theoretic strategies, and information exchange. Twenty professors from three leading Israeli academic institutions - the
Hebrew University
,
Tel Aviv University
and the
Technion
- will receive a Google grant to conduct research for three years.
In the past two decades, we have seen the Internet grow from a scientific network to an economic force that positively affects the global economy. E-commerce, online advertising, social networks and other new online business models present fascinating research questions and topics of study that can have a profound impact on society.
Consider online advertising, which is based on principles from algorithmic game theory and online auctions. The Internet has enabled advertising that is more segmented and measurable, making it more efficient than traditional advertising channels, such as newspaper classifieds, radio spots, and television commercials. These measurements have led to better pricing models, which are based on online real-time auctions. The original Internet auctions were designed by the industry, based on basic economic principles which have been known and appreciated for forty years.
As the Internet grows, online advertising is becoming more sophisticated, with developments such as ad-exchanges, advertising agencies which specialize in online markets, and new analytic tools. Optimizing value for advertisers and publishers in this new environment may benefit from a better understanding of the strategies and dynamics behind online auctions, the main driving tool of Internet advertising.
These grants will foster collaboration and interdisciplinary research by bringing together world renowned computer scientists, engineers, economists and game theorists to analyze complex online auctions and markets. Together, they will help bring this area of study into mainstream academic scientific research, ultimately advancing the field to the benefit of the industry at large.
The professors who received research grants include:
Hebrew University: Danny Dolev, Jeffrey S. Rosenschein, Noam Nisan (
Computer Science and Engineering
); Liad Blumrosen, Alex Gershkov, Eyal Winter (
Economics
); Michal Feldman and Ilan Kremer (
Business
). The last six are also members of the
Center for the Study of Rationality
.
Tel Aviv University: Yossi Azar, Amos Fiat, Haim Kaplan, and Yishay Mansour (
Computer Science
); Zvika Neeman (
Economics
); Ehud Lehrer and Eilon Solan (
Mathematics
); and Gal Oestreicher (
Business
).
Technion: Seffi Naor (
Computer Science
); Ron Lavi (
Industrial Engineering
); Shie Mannor and Ariel Orda (
Electrical Engineering
).
In addition to providing the funds, Google will offer support by inviting the researchers to seminars, workshops, faculty summits and brainstorming events. The results of this research will be published for the benefit of the Internet industry as a whole, and will contribute to the evolving discipline of market algorithms.
Labels
accessibility
ACL
ACM
Acoustic Modeling
Adaptive Data Analysis
ads
adsense
adwords
Africa
Android
API
App Engine
App Inventor
April Fools
Audio
Australia
Automatic Speech Recognition
Awards
Cantonese
China
Chrome
Cloud Computing
Collaboration
Computational Photography
Computer Science
Computer Vision
conference
conferences
Conservation
correlate
Course Builder
crowd-sourcing
CVPR
Data Center
data science
datasets
Deep Learning
distributed systems
Diversity
Earth Engine
economics
Education
Electronic Commerce and Algorithms
EMEA
EMNLP
Encryption
entities
Entity Salience
Environment
Exacycle
Faculty Institute
Faculty Summit
Flu Trends
Fusion Tables
gamification
Genomics
Gmail
Google Books
Google Drive
Google Science Fair
Google Sheets
Google Translate
Google Voice Search
Google+
Government
grants
HCI
Health
High Dynamic Range Imaging
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
Machine Hearing
Machine Intelligence
Machine Learning
Machine Translation
MapReduce
market algorithms
Market Research
ML
MOOC
NAACL
Natural Language Processing
Natural Language Understanding
Network Management
Networks
Neural Networks
Ngram
NIPS
NLP
open source
operating systems
Optical Character Recognition
optimization
osdi
osdi10
patents
ph.d. fellowship
PiLab
Policy
Professional Development
Public Data Explorer
publication
Publications
Quantum Computing
renewable energy
Research
Research Awards
resource optimization
Search
search ads
Security and Privacy
SIGCOMM
SIGMOD
Site Reliability Engineering
Software
Speech
Speech Recognition
statistics
Structured Data
Systems
TensorFlow
Translate
trends
TTS
TV
UI
University Relations
UNIX
User Experience
video
Vision Research
Visiting Faculty
Visualization
VLDB
Voice Search
Wiki
wikipedia
WWW
YouTube
Archive
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
Follow @googleresearch
Give us feedback in our
Product Forums
.
