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.
Market Algorithms and Optimization Meeting
Wednesday, January 28, 2009
Posted by
Vahab S. Mirrokni and Muthu Muthukrishnan
Google auctions ads, and enables a market with millions of advertisers and users. This market presents a unique opportunity to test and refine economic principles as applied to a very large number of interacting, self-interested parties with a myriad of objectives. Researchers in economics, computer science, operations research, marketing and business are increasingly involved in defining, understanding and influencing this market.
On January 7th, a group of computer science researchers from Google and various universities formed a workshop to discuss key research directions in this area, specifically "Market Algorithms and Optimization." Corinna Cortes (Head, Google Research, NY) and
Alfred
Spector
(VP of Research, Google) gave short talks about research groups in Google, academic collaborations, and research awards. The morning session comprised talks by Google researchers including Noam Nisan, Jon Feldman, Vahab Mirrokni, Yishay Mansour, and Muthu Muthukrishnan. These talks explored the following topics and key issues:
Role of budgets. Identify suitable properties of mechanisms for repeated auctions in the presence of budgets.
Truthfulness is impossible
, and may not be the suitable property.
Advertisers' bidding strategies. While bidding equally on all keywords has certain
desirable properties
, identify other bidding strategies if advertisers want to maximize different utility functions and use
rich bidding features
.
Dynamics of ad games. Understand dynamics of sophisticated advertiser bidder strategies under various ad allocation rules. For proportional allocation rules, the dynamics of simple bidder strategies are described
here
.
Online Reservations. Design suitable mechanisms for selling ad inventory in the future rather than on the spot. Models and methods for what happens when reservations can not be honored are explored in
WWW08
,
WINE08
, and
SODA09
papers.
The research presented in these talks can be found at the Google
publications site
. Some general research directions and open problems in ad auctions are
here
.
The post-lunch (sushi included of course) session comprised talks by researchers from academia.
Bobby Kleinberg
(Cornell) went first and took the audience far into projective geometry in an attempt to understand equilibria resulting from a sequence of selfish behavior of players using specific learning algorithms.
Silvio Micali
(MIT) described how difficult it was to model or propose mechanisms in presence of collusions, and then went on to show how to correctly
design such mechanisms for combinatorial auctions
.
Kamesh Munagala
(Duke Univ.) and
Anna Karlin
( U. Wash) discussed algorithmic problems related to ad auctions, including
how to run auctions
in presence of advertisers with mixed utilities and tight remnant budgets. Other participants --
Richard Cole
(NYU),
Amos Fiat
(Tel Aviv),
Uri Feige
(Weizmann),
Michel Goemans
(MIT),
Anupam Gupta
(CMU),
Nicole Immorlica
(Northwestern),
Michael Rabin
(Harvard), and
Eva Tardos
(Cornell) -- kept it lively with questions and discussions.
Part of what makes Google ad systems exciting is the challenges they pose and overcome, and yet others in the horizon. It is remarkable how some of the fundamental problems Google ad systems grapple with are also some of the hardest research problems in the community of Market Algorithms. Joint Google and Academia meetings like this help researchers begin to attack these problems, and may be a model for research collaborations in 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
.