Sébastien Lahaie
Sébastien Lahaie is a research scientist in the Market Algorithms group at Google Research, NYC. He received his PhD in Computer Science from Harvard in 2007 and was previously a researcher at Yahoo and Microsoft Research. His research focuses on computational aspects of market design, with applications to sponsored search and display advertising. He is interested in designing market algorithms that scale well and properly anticipate user behavior. Other interests include preference modeling and elicitation, combinatorial auctions, and prediction markets.
Research Areas
Authored Publications
Sort By
Integer Programming for Generalized Causal Bootstrap Designs
Adel Javanmard
Nick Doudchenko
Proceedings of the 42 nd International Conference on Machine Learning (2025)
Preview abstract
In experimental causal inference, we distinguish between two sources of uncertainty: design uncertainty, due to the treatment assignment mechanism, and sampling uncertainty, when the sample is drawn from a super-population. This distinction matters in settings with small fixed samples and heterogeneous treatment effects, as in geographical experiments. The standard bootstrap procedure most often used by practitioners primarily estimates sampling uncertainty, and the causal bootstrap procedure, which accounts for design uncertainty, was developed for the completely randomized design and the difference-in-means estimator, whereas non-standard designs and estimators are often used in these low-power regimes. We address this gap by proposing an integer program which computes numerically the worst-case copula used as an input to the causal bootstrap method, in a wide range of settings. Specifically, we prove the asymptotic validity of our approach for unconfounded, conditionally unconfounded,
and individualistic with bounded confoundedness assignments, as well as generalizing to any linear-in-treatment and quadratic-in-treatment estimators. We demonstrate the refined confidence intervals achieved through simulations of small geographical experiments.
View details
Preview abstract
Building on the linear programming approach to competitive equilibrium pricing, we develop a general method for constructing iterative auctions that achieve Vickrey-Clarke-Groves (VCG) outcomes. We show how to transform a linear program characterizing competitive equilibrium prices into one that characterizes universal competitive equilibrium (UCE) prices, which elicit precisely the information needed to compute VCG payments. By applying a primal-dual algorithm to these transformed programs, we derive iterative auctions that maintain a single price path, eliminating the overhead and incentive problems associated with multiple price paths used solely for payment calculations. We demonstrate the versatility of our method by developing novel UCE auctions for multi-unit settings and deriving an iterative UCE variant of the Product-Mix auction. The resulting auctions combine the transparency of iterative price discovery with the efficiency and incentive properties of the VCG mechanism.
View details
Synthetic Design: An Optimization Approach to Experimental Design with Synthetic Controls
Guido Imbens
Jann Spiess
Khashayar Khosravi
Miles Lubin
Nick Doudchenko
35th Conference on Neural Information Processing Systems (NeurIPS 2021) (2021)
Preview abstract
We investigate the optimal design of experimental studies that have pre-treatment outcome data available. The average treatment effect is estimated as the difference between the weighted average outcomes of the treated and control units. A number of commonly used approaches fit this formulation, including the difference-in-means estimator and a variety of synthetic-control techniques. We propose several methods for choosing the set of treated units in conjunction with the weights. Observing the NP-hardness of the problem, we introduce a mixed-integer programming formulation which selects both the treatment and control sets and unit weightings. We prove that these proposed approaches lead to qualitatively different experimental units being selected for treatment. We use simulations based on publicly available data from the US Bureau of Labor Statistics that show improvements in terms of mean squared error and statistical power when compared to simple and commonly used alternatives such as randomized trials.
View details
Revenue-Incentive Tradeoffs in Dynamic Reserve Pricing
International Conference on Machine Learning (2021), pp. 2601-2610
Preview abstract
Online advertisements are primarily sold via repeated auctions with reserve prices. In this paper, we study how to set reserves to boost revenue based on the historical bids of strategic buyers, while controlling the impact of such a policy on the incentive compatibility of the repeated auctions. Adopting an incentive compatibility metric which quantifies the incentives to shade bids, we propose a novel class of reserve pricing policies and provide analytical tradeoffs between their revenue performance and bid-shading incentives. The policies are inspired by the exponential mechanism from the literature on differential privacy, but our study uncovers mechanisms with significantly better revenue-incentive tradeoffs than the exponential mechanism in practice. We further empirically evaluate the tradeoffs on synthetic data as well as ad auction data from a major ad exchange to verify and support our theoretical findings.
View details
Robust Pricing in Dynamic Mechanism Design
International Conference on Machine Learning (2020), pp. 2494-2503
Preview abstract
Motivated by the repeated sale of online ads via auctions, optimal pricing in repeated auctions has attracted a large body of research. While dynamic mechanisms offer powerful techniques to improve on both revenue and efficiency by optimizing auctions across different items, their reliance on exact distributional information of buyers’ valuations (present and future) limits their use in practice. In this paper, we propose robust dynamic mechanism design. We develop a new framework to design dynamic mechanisms that are robust to both estimation errors in value distributions and strategic behavior. We apply the framework in learning environments, leading to the first policy that achieves provably low regret against the optimal dynamic mechanism in contextual auctions, where the dynamic benchmark has full and accurate distributional information.
View details
A Data-Driven Metric of Incentive Compatibility
Proceedings of The Web Conference (2020), pp. 1796-1806
Preview abstract
An incentive-compatible auction incentivizes buyers to truthfully reveal their private valuations. However, many ad auction mechanisms deployed in practice are not incentive-compatible, such as first-price auctions (for display advertising) and the generalized second-price auction (for search advertising). We introduce a new metric to quantify incentive compatibility in both static and dynamic environments. Our metric is data-driven and can be computed directly through black-box auction simulations without relying on reference mechanisms or complicated optimizations. We provide interpretable characterizations of our metric and prove that it is monotone in auction parameters for several mechanisms used in practice, such as soft floors and dynamic reserve prices. We empirically evaluate our metric on ad auction data from a major ad exchange and a major search engine to demonstrate its broad applicability in practice.
View details
Testing Dynamic Incentive Compatibility in Display Ad Auctions
Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (2019), pp. 1616-1624
Preview abstract
The question of transparency has become a key point of contention between buyers and sellers of display advertising space: ads are allocated via complex, black-box auction systems whose mechanics can be difficult to model let alone optimize against. Motivated by this concern, this paper takes the perspective of a single advertiser and develops statistical tests to confirm whether an underlying auction mechanism is dynamically incentive compatible (IC), so that truthful bidding in each individual auction and across time is an optimal strategy. The most general notion of dynamic-IC presumes that the seller knows how buyers discount future surplus, which is questionable in practice. We characterize dynamic mechanisms that are dynamic-IC for all possible discounting factors according to two intuitive conditions: the mechanism should be IC at each stage in the usual sense, and expected present utility (under truthful bidding) should be independent of past bids. The conditions motivate two separate experiments based on bid perturbations that can be run simultaneously on the same impression traffic. We provide a novel statistical test of stage-IC along with a test for utility-independence that can detect lags in how the seller uses past bid information. We evaluate our tests on display ad data from a major ad exchange and show how they can accurately uncover evidence of first- or second-price auctions coupled with dynamic reserve prices, among other types of dynamic mechanisms.
View details
A Robust Non-Clairvoyant Dynamic Mechanism for Contextual Auctions
Advances in Neural Information Processing Systems (2019), pp. 8657-8667
Preview abstract
Dynamic mechanisms offer powerful techniques to improve on both revenue and efficiency by linking sequential auctions using state information, but these techniques rely on exact distributional information of the buyers’ valuations (present and future), which limits their use in learning settings. In this paper, we consider the problem of contextual auctions where the seller gradually learns a model of the buyer's valuation as a function of the context (e.g., item features) and seeks a pricing policy that optimizes revenue. Building on the concept of a bank account mechanism---a special class of dynamic mechanisms that is known to be revenue-optimal---we develop a non-clairvoyant dynamic mechanism that is robust to both estimation errors in the buyer's value distribution and strategic behavior on the part of the buyer. We then tailor its structure to achieve a policy with provably low regret against a constant approximation of the optimal dynamic mechanism in contextual auctions. Our result substantially improves on previous results that only provide revenue guarantees against static benchmarks.
View details
Preferred Deals in General Environments
Proceedings of the 28th International Joint Conference on Artificial Intelligence (2019), pp. 231-237
Preview abstract
A preferred deal is a special contract for selling impressions of display ad inventory. By accepting a deal, a buyer agrees to buy a minimum amount of impressions at a fixed price per impression, and is granted priority access to the impressions before they are sent to an open auction on an ad exchange. We consider the problem of designing preferred deals (inventory, price, quantity) in the presence of general convex constraints, including budget constraints, and propose an approximation algorithm to maximize the revenue obtained from the deals. We then evaluate our algorithm using auction data from a major advertising exchange and our empirical results show that the algorithm achieves around 95% of the optimal revenue.
View details
Testing Incentive Compatibility in Display Ad Auctions
Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018
Preview abstract
Consider a buyer participating in a repeated auction, such as those
prevalent in display advertising. How would she test whether the
auction is incentive compatible? To bid effectively, she is
interested in whether the auction is single-shot incentive
compatible---a pure second-price auction, with fixed reserve
price---and also dynamically incentive compatible---her bids
are not used to set future reserve prices. In this work we develop
tests based on simple bid perturbations that a buyer can use to
answer these questions, with a focus on dynamic incentive
compatibility.
There are many potential A/B testing setups that one could use, but
we find that many natural experimental designs are, in fact, flawed.
For instance, we show that additive perturbations can lead to paradoxical results,
where higher bids lead to lower optimal reserve prices. We precisely
characterize this phenomenon and show that reserve prices are only
guaranteed to be monotone for distributions satisfying the Monotone
Hazard Rate (MHR) property. The experimenter must also decide how to split traffic to apply
systematic perturbations. It is tempting to have this split be
randomized, but we demonstrate empirically that unless the perturbations are
aligned with the partitions used by the seller to compute
reserve prices, the results are guaranteed to be inconclusive.
We validate our results with experiments on real display auction
data and show that a buyer can quantify both single-shot and dynamic
incentive compatibility even under realistic conditions where only
the cost of the impression is observed (as opposed to the exact
reserve price). We analyze the cost of running such experiments,
exposing trade-offs between test accuracy, cost, and underlying
market dynamics.
View details
