Our mission is to analyze, design, and deliver economically and computationally efficient marketplaces across Google.
About the team
Our research in auction theory, mechanism design, and advanced algorithms serves to improve Ads and other market-based products.
Team focus summaries
Auction optimization for ad exchanges
As part of the display ads eco-system, advertising exchanges provide many challenging optimization and algorithmic mechanism design problems. Examples of such research areas include auction design in the presence of supply chain of auctioneers, optimal competition between reservation, spot markets and reserve price optimization.
Display ads research
Display ads eco-system provides a great platform for a variety of research problems in online stochastic optimization and computational economics. Examples of such areas are robust online allocation problems, and optimal contract design in display advertising.
Dynamic mechanism design via bank accounts
The bulk of online ads are sold via repeated auctions. Instead of optimizing these auctions separately per auction, one can design stateful (dynamic) pricing and allocation strategies that may optimize these auctions together. While dynamic mechanism design has been an active research area, most of the existing mechanisms are either too computationally complex, or rely too much on forecasting of the future auctions. We have designed a new family of dynamic mechanisms, called bank account mechanisms, and showed their effectiveness in designing oblivious dynamic mechanisms that can be implemented without relying on forecasting the future.
Mechanism design with budgets
Budget constraints are a central issue in online advertising. While designing efficient mechanisms with good incentive properties is a well understood question for unbudgeted settings, it is only understood with budgets for very simple settings. In this line of work, we develop efficient mechanisms in settings with budgets for more sophisticated settings that occur in internet advertisement, such as online settings and polyhedral constraints.
Online stochastic matching
All online advertising systems employ online ad selection algorithms satisfying various global constraints and optimizing different objectives. In this regard, we have developed new cutting-edge algorithms for online stochastic matching, budgeted allocation, and more general variants of the problem, called submodular welfare maximization.
Optimizing advertiser campaigns
Advertisers must constantly optimize their campaigns to keep up with changes in their goals, resources and the market itself. To help, Google provides bid automation tools, as well as suggestions for targeting, bid and budget changes. We have studied algorithmic questions in this area to improve these tools and suggestions.
Pricing via online learning
Each ad impression is unique in its combinations of features, which makes it challenging to price them accurately. We develop robust online learning algorithms that can cope with unpredictable supply of ads and that balance the conflicting objectives of learning and earning in online pricing.
Many of the applications of machine learning are in environments that are game theoretic in nature, i.e., they involve multiple self-interested agents whose actions affect the data points that the machine learning algorithm observes, and who are affected by the outcome selected by the underlying optimization algorithm. The main challenge of learning in such game theoretic environments is to develop the underlying optimization algorithms that encourage agents to behave truthfully, resulting in a correct outcome.
Some of our publications
Econometrica, vol. 88(5) (2020), pp. 1939-1963
Seventh International Conference on Learning Representations (ICLR) (2019)
Web and Internet Economics 2019
Web and Internet Economics 2019
Thirty-third Conference on Neural Information Processing Systems (2019) (to appear)
Advances in Neural Information Processing Systems (2019), pp. 1579-1587
SIAM Journal on Computing, vol. 47(3) (2018), pp. 1056-1086
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, ?114-122
ACM Conference on Economics and Computation (EC) (2014)
STOC, ACM (2012), pp. 107-122
Foundations and Trends in Theoretical Computer Science, vol. 8 (4) (2013), pp. 265-368
Symposium on Foundations of Computer Science (FOCS), IEEE (2012)
Symposium on the Foundations of Computer Science (FOCS) (2009)
Proceedings of the 10th ACM Conference on Electronic Commerce (2009)