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

Combinatorial Bernoulli Factories: Matchings, Flows and Other Polytopes
R. Niazadeh, R. Paes Leme, J. Schneider - arxiv

Secretaries with Advice
P. Dutting, S. Lattanzi, R. Paes Leme, S. Vassilvitskii - arxiv

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

Improved Approximations for Free-Order Prophets and Second-Price Auctions
H. Beyhaghi, N. Golrezaei, R. Paes Leme, M. Pal, B. Sivan - arxiv

Auction Design for ROI-Constrained Buyers
N. Golrezaei, I. Lobel, R. Paes Leme - ssrn

Publications

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

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

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

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 version in Management Science.
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

Interactive Math

Torus Knots

Hyperbolic Plane

Geodesics

Conformal Maps

Laplace's equation



Academic Service

I served in the program committee of the following workshops and conferences:
Ad Auctions 2012, Ad Auctions 2013, EWSSN 2013, IJCAI 2013, EC 2013, WINE 2013, EC 2014, IJCAI 2015, EC 2015, Ad Auctions 2015, EC 2016, NetEcon 2016, Ad Auctions 2016, AAMAS 2017, EC 2017, AAMAS 2018, EC 2018, ICALP 2019, ICML 2019, EC 2019, DAI 2019, NeurIPS 2019, WINE 2019, AAAI 2010, EC 2020

I am a co-organizer of .