Renato Paes Leme

Research Scientist at
Google Research New York
111 8th Ave, New York, NY 10011

e-mail: renatoppl [at] google [dot] com
                renatoppl [at] renatoppl [dot] com




About me

I am research scientist at Google Research New York. I am broadly interested in algorithm design, specially for problems on the interface between Economics and Computation. Currently my main interests are: dynamic mechanism design (how to design good auctions over time for settings like internet advertisement), machine learning in economic environments (e.g. online learning for pricing and learning when feedback is given by strategic agents) and applications of convex programming to market optimization.

You can find more about me in the following links:

Working Papers

Winner-Pays-Bid Auctions Minimize Variance
P. McAfee, R. Paes Leme, B. Sivan, S. Vassilvitskii - arxiv

Online Matroid Embeddings
A. Cristi, P. Duetting, R. Kleinberg, R. Paes Leme

Ex-post Individually Rational Bayesian Persuasion
J. Zhang, R. Paes Leme, S. Zheng, Z. S. Wu - arxiv

Bayesian Conversations
R. Paes Leme, J. Schneider, S. Zheng - arxiv

Nonbossy Mechanisms: Mechanism Design Robust to Secondary Goals
R. Paes Leme, J. Schneider, H. Zhang - arxiv

Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platforms
K. Khosravi, R. Paes Leme, C. Podimata, A. Tsorvantzis - arxiv

Publications

Mechanism Design for Large Language Models
P. Duetting, R. Paes Leme, H. Xu, S. Zuo (WWW'24) - arxiv

Bernoulli Factories for Flow-Based Polytopes
R. Niazadeh, R. Paes Leme, J. Schneider - arxiv
SIAM Journal on Discrete Mathematics (SIDMA)

Are Gross Substitutes a Substitute for Submodular Valuations?
S. Dobzinski, U. Feige, M. Feldman, R. Paes Leme - arxiv
Mathematics of Operations Research (MOR)

U-Calibration: Forecasting for an Unknown Agent
R. Kleinberg, R. Paes Leme, J. Schneider, Y. Teng (COLT'23) - arxiv

Description Complexity of Regular Distributions
R. Paes Leme, B. Sivan, Y. Teng, P. Worah (EC'23) - arxiv

Eligibility Mechanisms: Auctions Meet Information Retrieval
G. Goel, R. Paes Leme, J. Schneider, D. Thompson, H. Zhang (WWW'23) - pdf
Preliminary version in the Marketplace Innovation Workshop (MIW'22)

Multiparameter Bernoulli Factories
R. Paes Leme, J. Schneider - arxiv
Annals of Applied Probability

Pricing Query Complexity of Revenue Maximization
R. Paes Leme, B. Sivan, Y. Teng, P. Worah (SODA'23) - arxiv
Prelminary version in the 2022 INFORMS Revenue Management and Pricing Workshop (RMP)

Corruption-Robust Contextual Search through Density Updates
C. Podimata, R. Paes Leme, J. Schneider (COLT'22) - arxiv

Calibrated Click-Through Auctions
D. Bergemann, P. Duetting, R. Paes Leme, S. Zuo (WWW'22) - arxiv, cowles
Preliminary version in the Marketplace Innovation Workshop (MIW'21)

Interactive Communication in Bilateral Trade
J. Mao, R. Paes Leme, K. Wang (ITCS'22) - arxiv, code

Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
S. Gollapudi, G. Guruganesh, K. Kollias, P. Manurangsi, R. Paes Leme, J. Schneider (NeurIPS'21) - arxiv

Learning to Price Against a Moving Target
R. Paes Leme, B. Sivan, Y. Teng, P. Worah (ICML'21) - arxiv

Secretaries with Advice
P. Duetting, S. Lattanzi, R. Paes Leme, S. Vassilvitskii (EC'21) - arxiv
Journal version in Mathematics of Operations Research (MOR)

Variable Decomposition for Prophet Inequalities and Optimal Ordering
A. Liu, R. Paes Leme, M. Pal, J. Schneider, B. Sivan (EC'21) - arxiv

Combinatorial Bernoulli Factories: Matchings, Flows and Other Polytopes
R. Niazadeh, R. Paes Leme, J. Schneider (STOC'21) - arxiv
Journal version in the Bernoulli Journal

Jointly Learning Prices and Product Features
E. Emamjomeh-Zadeh, R. Paes Leme, J. Schneider, B. Sivan (IJCAI'21) - pdf

Auction Design for ROI-Constrained Buyers
N. Golrezaei, I. Lobel, R. Paes Leme (WWW'21) - ssrn

Optimal Contextual Pricing and Extensions
A. Liu, R. Paes Leme, J. Schneider (SODA'21) - arxiv

Non-Excludable Dynamic Mechanism Design
S. Balseiro, V. Mirrokni, R. Paes Leme, S. Zuo (SODA'21) - ssrn

Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms
H. Beyhaghi, N. Golrezaei, R. Paes Leme, M. Pal, B. Sivan - ssrn, arxiv
Journal version in Operations Research
Previous title "Improved Approximations for Free-Order Prophets and Second-Price Auctions"

Myersonian Regression
A. Liu, R. Paes Leme, J. Schneider (NeurIPS'20) - pdf

Bandits with Adversarial Scaling
T. Lykouris, V. Mirrokni, R. Paes Leme (ICML'20) - arxiv, colab, git

Costly Zero Order Oracles
R. Paes Leme, J. Schneider (COLT'20) - pdf, link

Why Do Competitive Markets Converge to First-Price Auctions?
R. Paes Leme, B. Sivan, Y. Teng (WWW'20) - arxiv, link

Secretary Ranking with Minimal Inversions
S. Assadi, E. Balkanski, R. Paes Leme (NeurIPS'19) - arxiv, link

LP-based Approximation for Personalized Reserve Prices
M. Derakhshan, N. Golrezaei, R. Paes Leme (EC'19) - arxiv
Journal version in Management Science

Learning to Clear the Market
S. Lahaie, R. Paes Leme, W. Shen (ICML'19) - pdf

Dynamic Contracting under Positive Commitment
I. Lobel, R. Paes Leme (AAAI'19) - ssrn

Pareto Efficient Auctions with Interest Rates
G. Goel, V. Mirrokni and R. Paes Leme (AAAI'19) - pdf

Optimal Dynamic Auctions are Virtual Welfare Maximizers
V. Mirrokni, R. Paes Leme, P. Tang, S. Zuo (AAAI'19) - ssrn

Dynamic Double Auctions: Towards First Best
S. Balseiro, V. Mirrokni, R. Paes Leme, S. Zuo (SODA'19) - ssrn
Journal version in Operations Research

Contextual Pricing for Lipschitz Buyers
J. Mao, R. Paes Leme, J. Schneider (NeurIPS'18) - pdf, link

Contextual Search via Intrinsic Volumes
R. Paes Leme, J. Schneider (FOCS'18) - arxiv
Journal version in SIAM Journal on Computing (SICOMP)

Non-Clairvoyant Dynamic Mechanism Design
V. Mirrokni, R. Paes Leme, P. Tang, S. Zuo (EC'18) - journal, pdf, ssrn, slides
Journal version in Econometrica

On the Construction of Substitutes
E. Balkanski, R. Paes Leme (EC'18) - arxiv, journal
Journal version in Mathematics of Operations Research (MOR)

Stochastic Bandits Robust to Adversarial Corruptions
T. Lykouris, V. Mirrokni, R. Paes Leme (STOC'18) - arxiv

Dynamic Mechanism Design in the Field
V. Mirrokni, R. Paes Leme, R. Ren, S. Zuo (WWW'18) - ssrn
Previous title "Dynamic Second Price Auctions with Low Regret"

Gross substitutability: an algorithmic survey
R. Paes Leme - pdf (preprint), old, journal
Games and Economic Behavior (GEB)

Dynamic Revenue Sharing
S. Balseiro, M. Lin, V. Mirrokni, R. Paes Leme, S. Zuo (NIPS'17) - ssrn, link

Ego-splitting Framework: from Non-Overlapping to Overlapping Clusters
A. Epasto, S. Lattanzi and R. Paes Leme (KDD'17) - pdf, link

Tight Bounds for Approximate Caratheodory and Beyond
V. Mirrokni, R. Paes Leme, A. Vladu, S. Wong (ICML'17) - arxiv, link

Multidimensional Binary Search for Contextual Decision-Making
I. Lobel, R. Paes Leme, A. Vladu (EC'17) - arxiv, journal
Journal version in Operations Research

Dynamic Mechanisms with Martingale Utilities
S. Balseiro, V. Mirrokni, R. Paes Leme (EC'17) - ssrn, journal
Journal version in Management Science

Computing Walrasian Equilibria: Fast Algorithms and Structural Properties
R. Paes Leme, S. Wong (SODA'17) - arxiv, slides, journal
Invited to Highlights of Algorithms 2017
Journal version in Mathematical Programming Series A

Feature-Based Dynamic Pricing
M. Cohen, I. Lobel, R. Paes Leme (EC'16) - ssrn, slides, journal
Journal version in Management Science (Lead Article)
See also our letter in SIGecom Exchanges.

Where to Sell: Simulating Auctions From Learning Algorithms
H. Nazerzadeh, R. Paes Leme, A. Rostamizadeh, U. Syed (EC'16) - ssrn

Optimal dynamic mechanisms with ex-post IR via bank accounts
V. Mirrokni, R. Paes Leme, P. Tang, S. Zuo (AdAuctions'16) - arxiv
Unpublished manuscript presented in the Ad Auctions Workshop 2016.

Dynamic auctions with bank accounts
V. Mirrokni, R. Paes Leme, P. Tang, S. Zuo (IJCAI'16) - pdf

Reservation Exchange Markets for Internet Advertisings
G. Goel, S. Leonardi, V. Mirrokni A. Nikzad and R. Paes Leme (ICALP'16) - pdf
Preliminary version in the AdAuctions Workshop 2015.

A Field Guide to Personalized Reserve Prices
R. Paes Leme, M. Pal, S. Vassilvitskii (WWW'16) - arxiv

Core-competitive Auctions
G. Goel, M. R. Khani and R. Paes Leme (EC'15) - arxiv

Price Competition, Fluctuations and Welfare Guarantees
M. Babaioff, R. Paes Leme, B. Sivan (EC'15) - arxiv

Gross Substitutes and Endowed Assignment Valuations
M. Ostrovsky, R. Paes Leme - pdf, journal
Theoretical Economics (TE)

Bounding the inefficiency of outcomes in generalized second price auctions
I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, M. Kyropoulou, B. Lucier, R. Paes Leme and E. Tardos
Journal of Economic Theory (JET) - arxiv, journal
Preliminary versions of the results in FOCS'10, EC'11 and EC'11.
Previous title "On the efficiency of equilibria in generalized second price auctions".

Efficiency Guarantees in Auctions with Budgets
S. Dobzinski and R. Paes Leme (ICALP'14) - arxiv
Preliminary version in AAW'13 (AdAuctions Workshop)

On the Efficiency of the Walrasian Mechanism
M. Babaioff, B. Lucier, N. Nisan and R. Paes Leme (EC'14) - arxiv, slides

Clinching Auctions Beyond Hard Budget Constraints
G. Goel, V. Mirrokni and R. Paes Leme (EC'14) - arxiv, slides
Preliminary version in AAW'13 (AdAuctions Workshop)

Price Competition in Online Combinatorial Markets
M. Babaioff, N. Nisan and R. Paes Leme (WWW'14) - arxiv

Role of Conformity in Opinion Dynamics in Social Networks
A. Das, S. Gollapudi, A. Khan and R. Paes Leme (COSN'14)

Pricing Public Goods for Private Sale
M. Feldman, D. Kempe, B. Lucier and R. Paes Leme (EC'13) - arxiv, slides

Clinching Auctions with Online Supply
G. Goel, V. Mirrokni and R. Paes Leme (SODA'13, GEB) - arxiv, journal
Journal version in Games and Economic Behavior (GEB special issue for FOCS/STOC/SODA'13)

Design and Analysis of Sponsored Search Mechanisms
R. Paes Leme, PhD Thesis, Cornell University, Dec 2012 - pdf, code

The Dining Bidder Problem: a la russe et a la francaise
R. Paes Leme, V. Syrgkanis and E. Tardos, (SIGecom Exchanges, Vol 11-2) - link
An expository survey on item-bidding auctions from a culinary perspective

Optimal Mechanisms for Selling Information
M. Babaioff , R. Kleinberg and R. Paes Leme (EC'12) - arvix, slides

Signaling Schemes for Revenue Maximization
Y. Emek , M. Feldman , I. Gamzu , R. Paes Leme and M. Tennenholtz (EC'12, TEAC) - arxiv, slides, journal
Journal version in Transactions on Economics and Computation (TEAC)

Polyhedral Clinching Auctions and the AdWords Polytope
G. Goel, V. Mirrokni and R. Paes Leme (STOC'12, JACM) - arxiv, slides, journal
Journal version in the Journal of the Association for Computing Machinery (JACM)
Selected one of Google's Excellent Papers 2012

On Revenue in the Generalized Second Price Auction
B. Lucier, R. Paes Leme and E. Tardos (WWW'12) - pdf, pdf-full, slides
Preliminary versions of this paper appeared in AAW'11 (AdAuctions Workshop). Here for the workshop version.

Sequential Auctions and Externalities
R. Paes Leme, V. Syrgkanis and E. Tardos (SODA'12) - pdf, arxiv

The Curse of Simultaneity
R. Paes Leme, V. Syrgkanis and E. Tardos (ITCS'12) - pdf

GSP Auctions with Correlated Types
B. Lucier and R. Paes Leme (EC'11) - pdf
Preliminary version in arXiv with title "Improved Social Welfare Bounds for GSP at Equilibrium"

Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction
R. Paes Leme and E. Tardos (FOCS'10) - pdf, slides, talk
Preliminary versions of this paper appeared in AAW09 and AAW10 (AdAuctions Workshop)

A Simpler Primal-Dual Proof of Lawler's Algorithm
R. Paes Leme and D. Shmoys., Manuscript - pdf

Bayes-Nash Price of Anarchy for GSP
R. Paes Leme and E. Tardos (AdAuctions'10) - pdf, slides

Sponsored Search Equilibria for Conservative Bidders
R. Paes Leme and E. Tardos (AdAuctions'09) - pdf, slides

Symmetry-based Completion
T. Pereira, R. Paes Leme, L. Velho and T. Lewiner (GRAPP'09) - pdf

Tutorials

Gross Substitutes: Combinatorial Structure and Algorithms
R. Paes Leme, I. Talgam-Cohen (EC'18)
slides (part I), slides (part II), proposal

Learning for Revenue Optimization
R. Paes Leme, A. Munoz Medina (ALT'18) - slides

An Introduction to Bernoulli Factories
R. Paes Leme (ALGADIMAR'21) - link

Interactive Math

Torus Knots

Hyperbolic Plane

Geodesics

Conformal Maps

Laplace's equation

Langevin Dynamic

Hyperbolic LOGO



Academic Service

I currently serve as an Associate Editor of the following journals:
I served in the program committee of the following workshops and conferences:
I am a co-organizer of