Renato Paes Leme
Renato Paes Leme is a research scientist at Google New York. He is broadly interested in algorithm design, specially for problems on the interface between Economics and Computation. Some topics he is particularly excited about are: mechanism design for non-quasi-linear settings, Price of Anarchy of auctions, sequential games and applications of game-theory to ad auctions. See http://renatoppl.com/ for my personal homepage.
Research Areas
Authored Publications
Sort By
Mechanism Design for Large Language Models
Paul Duetting
Haifeng Xu
Proceedings of the ACM on Web Conference 2024, Association for Computing Machinery, New York, NY, USA, 144–155
Preview abstract
We investigate auction mechanisms for AI-generated content, focusing on applications like ad creative generation. In our model, agents' preferences over stochastically generated content are encoded as large language models (LLMs). We propose an auction format that operates on a token-by-token basis, and allows LLM agents to influence content creation through single dimensional bids. We formulate two desirable incentive properties and prove their equivalence to a monotonicity condition on output aggregation. This equivalence enables a second-price rule design, even absent explicit agent valuation functions. Our design is supported by demonstrations on a publicly available LLM.
View details
Calibrated Click-Through Auctions
Dirk Bergemann
Paul Duetting
Proceedings of the ACM Web Conference 2022, pp. 47-57
Preview abstract
We analyze the optimal information design in a click-through auction with stochastic click-through rates and known valuations per click. The auctioneer takes as given the auction rule of the click-through auction, namely the generalized second-price auction. Yet, the auctioneer can design the information flow regarding the click-through rates among the bidders. We require that the information structure to be calibrated in the learning sense. With this constraint, the auction needs to rank the ads by a product of the value and a calibrated prediction of the click-through rates. The task of designing an optimal information structure is thus reduced to the task of designing an optimal calibrated prediction.
We show that in a symmetric setting with uncertainty about the click-through rates, the optimal information structure attains both social efficiency and surplus extraction. The optimal information structure requires private (rather than public) signals to the bidders. It also requires correlated (rather than independent) signals, even when the underlying uncertainty regarding the click-through rates is independent. Beyond symmetric settings, we show that the optimal information structure requires partial information disclosure, and achieves only partial surplus extraction.
View details
Non-Excludable Dynamic Mechanism Design
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, pp. 1357-1373
Preview abstract
Dynamic mechanism design expands the scope on what type of allocation rules can be implemented and what revenue can be extracted when compared to static mechanisms. The case of excludable environments (i.e. one player can be de-allocated while keeping the allocation of the remaining players intact) is very well understood. The mechanisms in the literature don’t extend to the non-excludable environments. Two prototypical examples of such environments are: (i) public projects, where all players must have the same allocation; and (ii) non-disposable goods, where each item must be allocated to some player. We show a general mechanism that can asymptotically extract the full surplus in such environments. Moreover, we fully characterize which abstract mechanism design environments allow for full surplus extraction in the limit. Our characterization is based on the geometry of achievable utility sets – a convex set characterizing the expected utility profiles that can be implemented in a static mechanism.
View details
Preview abstract
In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in $\R^d$ and only observes the purchasing decisions of a buyer with a fixed but unknown linear valuation over the products. The regret measures the difference between the revenue the seller could have obtained knowing the buyer valuation and what can be obtained by the learning algorithm.
We give a poly-time algorithm for contextual pricing with $O(d \log \log T + d \log d)$ regret which matches the $\Omega(d \log \log T)$ lower bound up to the $d \log d$ additive factor. If we replace pricing loss by the symmetric loss, we obtain an algorithm with nearly optimal regret of $O(d \log d)$ matching the $\Omega(d)$ lower bound up to $\log d$. These algorithms are based on a novel technique of bounding the value of the Steiner polynomial of a convex region at various scales. The Steiner polynomial is a degree $d$ polynomial with intrinsic volumes as the coefficients.
We also study a generalized version of contextual search where the hidden linear function over the Euclidean space is replaced by a hidden function $f : \X \rightarrow \Y$ in a certain hypothesis class $\H$. We provide a generic algorithm with $O(d^2)$ regret where $d$ is the covering dimension of this class. This leads in particular to a $\tilde{O}(s^2)$ regret algorithm for linear contextual search if the linear function is guaranteed to be $s$-sparse. Finally we also extend our results to the noisy feedback model, where each round our feedback is flipped with a fixed probability $p < 1/2$.
View details
Secretaries with Advice
Paul Duetting
Proceedings of the 22nd ACM Conference on Economics and Computation (EC'21)(2021), pp. 409-429
Preview abstract
The secretary problem is probably the purest model of decision making under uncertainty. In this
paper we ask which advice can we give the algorithm to improve its success probability?
We propose a general model that unifies a broad range of problems: from the classic secretary problem
with no advice, to the variant where the quality of a secretary is drawn from a known distribution and
the algorithm learns each candidate’s quality quantile on arrival, to more modern ML-based versions of
advice where a binary classifier gives us noisy advice about whether or not the current secretary is the
best on the market.
Our main technique is a factor revealing LP that captures all of the problems above. We use this LP
formulation to gain structural insight into the optimal policy and present two case studies: a re-derivation
of the classic known distributions result with tools from linear programming and a tight analysis of the
noisy binary advice model.
View details
Preview abstract
In the Learning to Price setting, a seller posts prices over time with the goal of maximizing revenue while learning the buyer's valuation. This problem is very well understood when values are stationary (fixed or iid). Here we study the problem where the buyer's value is a moving target, i.e., they change over time either by a stochastic process or adversarially with bounded variation. In either case, we provide matching upper and lower bounds on the optimal revenue loss. Since the target is moving, any information learned soon becomes out-dated, which forces the algorithms to keep switching between exploring and exploiting phases.
View details
Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
Guru Prashanth Guruganesh
NeurIPS(2021)
Preview abstract
We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden $d$-dimensional value $w^*$. Every round, we are presented with a subset $\mathcal{X}_t \subseteq \mathbb{R}^d$ of possible actions. If we choose (i.e. recommend to the user) action $x_t$, we obtain utility $\langle x_t, w^* \rangle$ but only learn the identity of the best action $\arg\max_{x \in \X_t} \langle x, w^* \rangle$.
We design algorithms for this problem which achieve regret $O(d\log T)$ and $\exp(O(d \log d))$. To accomplish this, we design novel cutting-plane algorithms with low “regret” -- the total distance between the true point $w^*$ and the hyperplanes the separation oracle returns.
We also consider the variant where we are allowed to provide a list of several recommendations. In this variant, we give an algorithm with $O(d^2 \log d)$ regret and list size $\poly(d)$. Finally, we construct nearly tight algorithms for a weaker variant of this problem where the learner only learns the identity of an action that is better than the recommendation. Our results rely on new algorithmic techniques in convex geometry (including a variant of Steiner’s formula for the centroid of a convex set) which may be of independent interest.
View details
Preview abstract
We consider a setting in which bidders participate in multiple auctions run by different sellers, and optimize their bids for the \emph{aggregate} auction. We analyze this setting by formulating a game between sellers, where a seller's strategy is to pick an auction to run. Our analysis aims to shed light on the recent change in the Display Ads market landscape: here, ad exchanges (sellers) were mostly running second price auctions earlier and over time they switched to variants of the first price auction, culminating in Google's Ad Exchange moving to a first price auction in 2019. Our model and results offer an explanation for why the first price auction occurs as a natural equilibrium in such competitive markets.
View details
Preview abstract
We study optimization with an approximate zero order oracle where there is a cost c() associated
with querying the oracle with accuracy. We consider the task of reconstructing a linear function:
given a linear function f : X ⊆ R
d → [−1, 1] defined on a not-necessarily-convex set X, the goal is
to reconstruct ˆf such that |f(x) − ˆf(x)| ≤ for all x ∈ X. We show that this can be done with cost
O(d · c(/d)). The algorithm is based on a (poly-time computable) John-like theorem for simplices
instead of ellipsoids, which may be of independent interest.
This question is motivated by optimization with threshold queries, which are common in
economic applications such as pricing. With threshold queries, approximating a number up to
precision requires c() = log(1/). For this, our algorithm has cost O(d log(d/)) which matches
the Ω(d log(1/)) lower bound up to log factors
View details
Improved Approximations for Posted Price and Second-price Mechanisms
Hedyeh Beyhaghi
Negin Golrezaei
Operations Research(2020)
Preview abstract
We study the fundamental problem of selling a single indivisible good to one ofnbuyers with independentvaluations. We seek to design improved approximations to the optimal revenue achievable through two simpleand widely used mechanisms: second price auction with eager personalized reserve prices, and sequentialposted price mechanisms. Until recently, the best known approximation for both these mechanisms was 1−1e.We give improved approximations of 1−1e+0.022∼0.6543 for the sequential posted price mechanism and1−1e+0.029∼0.662 for the second price auction with eager reserve prices. We also make some progresstowards the problem of computing the optimal personalized eager reserve prices for a second price auction.
View details
