Market algorithms

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 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.

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.

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.

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.

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.

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.