Publications

Reverse chronological list of publications. By default authors are listed alphabetically. See my DBLP entry or Google Scholar profile for further details. Note that in computer science conference papers go through a rigorous reviewing process, and are the main outlet for scientific work.

Refereed conference publications

For journal publications click here

In preparation
Online Matroid Embeddings
Andres Cristi, Paul Dütting, Robert Kleinberg, Renato Paes Leme
[pdf upon request]
Online Combinatorial Auctions with Few Samples
Paul Dütting, Thomas Kesselheim, Brendan Lucier, Rebecca Reiffenhäuser, Sahil Singla
[upon request]

Under submission
The Query Complexity of Contracts
Paul Dütting, Michal Feldman, Yoav Gal-Tzur, Aviad Rubinstein
[upon request]
The Competition Complexity of Prophet Inequalities
Johannes Brustle, Jose Correa, Paul Dütting, Tomer Ezra, Michal Feldman, Victor Verdugo
[arXiv]
Selling Joint Ads: A Regret Minimization Perspective
Gagan Aggarwal, Ashwin Badanidiyuru, Paul Dütting, Federico Fusco
[pdf upon request]
Consistent Submodular Maximization
Paul Dütting, Federico Fusco, Ashkan Norouzi-Fard, Silvio Lattanzi, Morteza Zadimoghaddam
[pdf upon request]
Principal-Agent Reinforcement Learning
Dimitry Ivanov, Paul Dütting, David Parkes, Tonghan Wang, Inbal Talgam-Cohen
[pdf upon request]

Published or in press
Mechanism Design for Large Language Models
Paul Dütting, Vahab Mirrokni, Renato Paes Leme, Haifeng Xu, Song Zuo
ACM The Web Conference, WWW 2024, Singapore, forthcoming
[arXiv]
Combinatorial Contracts Beyond Gross Substitutes
Paul Dütting, Michal Feldman, Yoav Gal-Tzur
ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA
[arXiv]
Deep Contract Design via Discontinuos Networks
Tonghan Wang, Paul Dütting, Dimitry Ivanov, Inbal Talgam-Cohen, David Parkes
Conference on Neural Information Processing Systems, NeurIPS 2023, New Orleans, LA, USA
[arXiv]
Optimal No-Regret Learning for One-Sided Lipschitz Functions
Paul Dütting, Guru Guruganesh, Jon Schneider, Joshua Wang
International Conference on Machine Learning, ICML 2023, Honolulu, HI, USA
[pdf | BibTex]
Fully Dynamic Submodular Maximization over Matroids
Paul Dütting, Federico Fusco, Ashkan Norouzi-Fard, Silvio Lattanzi, Morteza Zadimoghaddam
International Conference on Machine Learning, ICML 2023, Honolulu, HI, USA
[pdf | arXiv | BibTex]
Prophet Secretary Against the Online Optimal
Paul Dütting, Alexandros Tsigonias-Dimitriadis, Evangelia Gergatsouli, Roijin Rezvan, Yifeng Teng
ACM Conference on Economics and Computation, EC 2023, London, UK
[pdf | arXiv | BibTex]
Ambiguous Contracts
Paul Dütting, Michal Feldman, Daniel Peretz
ACM Conference on Economics and Computation, EC 2023, London, UK
[pdf | arXiv | BibTex]
Bayesian Analysis of Linear Contracts
Tal Alon, Paul Dütting, Yingkai Li, Inbal Talgen-Cohen
ACM Conference on Economics and Computation, EC 2023, London, UK
[pdf | arXiv | BibTex]
Trading Prophets
Jose Correa, Andres Cristi, Paul Dütting, MohammadTaghi Hajiaghayi, Jan Olkowski, Kevin Schewior
ACM Conference on Economics and Computation, EC 2023, London, UK
[pdf | arXiv | BibTex]
Multi-Agent Contracts
Paul Dütting, Tomer Ezra, Michal Feldman, Thomas Kesselheim
ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA
[pdf | arXiv | BibTex]
Deletion Robust Submodular Maximization over Matroids
(long presentation)
Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam
International Conference on Machine Learning, ICML 2022, Baltimore, MD, USA
[pdf | arXiv | BibTex]
The Competition Complexity of Dynamic Pricing
Johannes Brustle, Jose Correa, Paul Dütting, Victor Verdugo
ACM Conference on Economics and Computation, EC 2022, Boulder, CO, USA
[pdf | BibTex]
Price Manipulability in First-Price Auctions
Johannes Brustle, Paul Dütting, Balusubramanian Sivan
ACM The Web Conference, WWW 2022, Lyon, France, forthcoming
[pdf | arXiv | BibTex]
Calibrated Click-Through Auctions
Dirk Bergemann, Paul Dütting, Renato Paes-Leme, Song Zuo
ACM The Web Conference, WWW 2022, Lyon, France, forthcoming
[pdf | arXiv | Cowles | BibTex]
Single-Sample Prophet Inequalities via Greedy-Ordered Selection
Constantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, Rebecca Reiffenhäuser
ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Alexandria, VA, USA (virtual)
[pdf | arXiv | BibTex]
Combinatorial Contracts
Paul Dütting, Tomer Ezra, Michal Feldman, Thomas Kesselheim
IEEE Symposium on Foundations of Computer Science, FOCS 2021, Boulder, CO, USA (virtual)
[pdf | arXiv | BibTex]
Fairness and Bias in Online Selection
Andres Cristi, Jose Correa, Paul Dütting, Ashkan Norouzi-Fard
International Conference on Machine Learning, ICML 2021 (virtual)
[pdf | code | BibTex]
Secretaries with Advice
Paul Dütting, Renato Paes Leme, Silvio Lattanzi, Sergei Vassilvitskii
ACM Conference on Economics and Computation, EC 2021, Budapest, Hungary (virtual)
[pdf | arXiv | BibTex]
Contracts with Private Cost per Unit-of-Effort
Tal Alon, Paul Dütting, Inbal Talgam-Cohen
ACM Conference on Economics and Computation, EC 2021, Budapest, Hungary (virtual)
[pdf | arXiv | BibTex]
Efficient Two-Sided Markets with Limited Information
Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi, Rebecca Reiffenhäuser
ACM Symposium on Theory of Computing, STOC 2021, Rome, Italy (virtual)
[pdf | arXiv | BibTex]
Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility
Jose Correa, Paul Dütting, Felix Fischer, Kevin Schewior, Bruno Ziliotto
Innovations in Theoretical Computer Science, ITCS 2021 (virtual)
[pdf | arXiv | BibTex]
An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions
Paul Dütting, Thomas Kesselheim, Brendan Lucier
IEEE Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA (virtual)
[pdf | arXiv | ACM SIGecom Exchanges | BibTex]
The Complexity of Contracts
Paul Dütting, Tim Roughgarden, Inbal Talgam-Cohen
ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA
[pdf | arXiv | BibTex]
Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution
(ACM SIGecom Best Full Paper Award)
Jose Correa, Paul Dütting, Felix Fischer, Kevin Schewior
ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA
[pdf | arXiv | BibTex]
Simple versus Optimal Contracts
Paul Dütting, Tim Roughgarden, Inbal Talgam-Cohen
ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA
[pdf | arXiv | BibTex]
Posted Pricing and Prophet Inequalities with Inaccurate Priors
Paul Dütting, Thomas Kesselheim
ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA
[pdf | BibTex]
Optimal Auctions through Deep Learning
(long presentation)
Paul Dütting, Zhe Feng, Hari Narasimhan, David C. Parkes, Sai S. Ravindranath
International Conference on Machine Learning, ICML 2019, Long Beach, CA, USA (long presentation)
[pdf | code | arXiv | BibTex]
Prophet Inequalities made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs
Paul Dütting, Michal Feldman, Thomas Kesselheim, Brendan Lucier
IEEE Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA
[pdf | arXiv | BibTex]
Best-Response Dynamics in Combinatorial Auctions with Item Bidding
Paul Dütting, Thomas Kesselheim
ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain
[pdf | arXiv | BibTex]
Truthful Outcomes from Non-Truthful Position Auctions
Paul Dütting, Felix Fischer, David C. Parkes
ACM Conference on Economics and Computation, EC 2016, Maastricht, Netherlands, July 2016
[arXiv | BibTex]
Polymatroid Prophet Inequalities
Paul Dütting, Robert Kleinberg
European Symposium on Algorithms, ESA 2015, Patras, Greece, September 2015
[pdf | arXiv | BibTex]
Algorithms as Mechanisms: The Price of Anarchy of Relax and Round
Paul Dütting, Thomas Kesselheim, Eva Tardos
ACM Conference on Economics and Computation, EC 2015, Portland, OR, June 2015
[pdf | arXiv | ACM SIGecom Exchanges | BibTex]
Algorithms against Anarchy: Understanding Non-Truthful Mechanisms
Paul Dütting, Thomas Kesselheim
ACM Conference on Economics and Computation, EC 2015, Portland, OR, June 2015
[pdf | BibTex]
The Performance of Deferred-Acceptance Auctions
Paul Dütting, Vasilis Gkatzelis, Tim Roughgarden
ACM Conference on Economics and Computation, EC 2014, Palo Alto, CA, June 2014
[pdf | BibTex]
Modularity and Greed in Double Auctions
Paul Dütting, Tim Roughgarden, Inbal Talgam-Cohen
ACM Conference on Economics and Computation, EC 2014, Palo Alto, CA, June 2014
[pdf | BibTex]
Mechanisms with Unique Learnable Equilibria
Paul Dütting, Thomas Kesselheim, Eva Tardos
ACM Conference on Economics and Computation, EC 2014, Palo Alto, CA, June 2014
[pdf | BibTex]
Expressiveness and Robustness of First-Price Position Auctions
Paul Dütting, Felix Fischer, David C. Parkes
ACM Conference on Economics and Computation, EC 2014, Palo Alto, CA, June 2014
[pdf | arXiv | BibTex]
Valuation Compressions in VCG-Based Combinatorial Auctions
Paul Dütting, Monika Henzinger, Martin Starnberger
Conference on Web and Internet Economics, WINE 2013, Cambridge, MA, December 2013
[pdf | arXiv | BibTex]
Auctions with Heterogeneous Items and Budget Limits
Paul Dütting, Monika Henzinger, Martin Starnberger
Workshop on Internet and Network Economics, WINE 2012, Liverpool, UK, December 2012
[pdf | arXiv | BibTex]
Payment Rules through Discriminant-Based Classifiers
(ACM SIGecom Best Paper Award)
Paul Dütting, Felix Fischer, Pichayut Jirapinyo, John K. Lai, Ben Lubin, David C. Parkes
ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 2012
[pdf | arXiv | code | BibTex]
Simplicity-Expressiveness Tradeoffs in Mechanism Design
Paul Dütting, Felix Fischer, David C. Parkes
ACM Conference on Electronic Commerce, EC 2011, San Jose, CA, June 2011
[pdf | arXiv | BibTex]
An Expressive Mechanism for Auctions on the Web
Paul Dütting, Monika Henzinger, Ingmar Weber
World Wide Web Conference, WWW 2011, Hyderabad, India, April 2011
[pdf | BibTex]
How Much is Your Personal Recommendation Worth?
(iBiblio Best Poster Award)
Paul Dütting, Monika Henzinger, Ingmar Weber
World Wide Web Conference, WWW 2010, Raleigh, NC, April 2010
[pdf | BibTex]
Sponsored Search, Market Equilibria, and the Hungarian Method
Paul Dütting, Monika Henzinger, Ingmar Weber
Symposium on Theoretical Aspects of Computer Science, STACS 2010, Nancy, France, March 2010
[pdf | arXiv | BibTex]
Bidder Optimal Assignments for General Utilities
Paul Dütting, Monika Henzinger, Ingmar Weber
Workshop on Internet and Network Economics, WINE 2009, Rome, Italy, December 2009
[pdf | BibTex]

Refereed journal publications

For conference publications click here

In preparation
Bayesian Analysis of Linear Contracts
Tal Alon, Paul Dütting, Yingkai Li, Inbal Talgen-Cohen
[pdf upon request]
Single-Sample Prophet Inequalities via Greedy-Ordered Selection
Constantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, Rebecca Reiffenhäuser
[pdf upon request]

Under submission
Ambiguous Contracts
Paul Dütting, Michal Feldman, Daniel Peretz, Larry Samuelson
(Submitted January 2024)
[pdf upon request]
Trading Prophets
Jose Correa, Andres Cristi, Paul Dütting, MohammadTaghi Hajiaghayi, Jan Olkowski, Kevin Schewior
(Submitted October 2023)
[pdf upon request]
Combinatorial Contracts
Paul Dütting, Tomer Ezra, Michal Feldman, Thomas Kesselheim
(Submitted October 2023)
[pdf upon request]
Fully Dynamic Submodular Maximization over Matroids
Paul Dütting, Federico Fusco, Ashkan Norouzi-Fard, Silvio Lattanzi, Morteza Zadimoghaddam
(Submitted September 2023)
[pdf upon request]
Deletion Robust Non-Monotone Submodular Maximization over Matroids
Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam
(Submitted September 2023)
[pdf upon request]
Prophet Secretary Against the Online Optimal
Paul Dütting, Alexandros Tsigonias-Dimitriadis, Evangelia Gergatsouli, Roijin Rezvan, Yifeng Teng
(Submitted August 2023)
[pdf upon request]

Revise and resubmit
Efficient Two-Sided Markets with Limited Information
Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi, Rebecca Reiffenhäuser
SIAM Journal on Computing, R&R at SICOMP, minor revision
(Revision requested January 2024, resubmitted February 2024)
[pdf upon request]
Fairness and Bias in Online Selection
Andres Cristi, Jose Correa, Paul Dütting, Ashkan Norouzi-Fard
Operations Research, R&R at OR, major revision
(Revision requested October 2023)
[pdf upon request]
Contracts with Private Cost per Unit-of-Effort
Tal Alon, Paul Dütting, Inbal Talgam-Cohen
Games and Economic Behavior, R&R at GEB, revision
(Revision requested September 2022)
[pdf upon request]

Published or in press
Optimal Auctions through Deep Learning: Advances in Differentiable Economics
Paul Dütting, Zhe Feng, Hari Narasimhan, David C. Parkes, Sai S. Ravindranath
Journal of the ACM, JACM 2023+, accepted September 2023
[pdf upon request]
The Competition Complexity of Dynamic Pricing
Johannes Brustle, Jose Correa, Paul Dütting, Victor Verdugo
Mathematics of Operations Research, MOR 2023+, forthcoming
(Accepted August 2023)
[pdf upon request]
Secretaries with Advice
Paul Dütting, Renato Paes Leme, Silvio Lattanzi, Sergei Vassilvitskii
Mathematics of Operations Research, MOR 2023+, forthcoming
(Accepted March 2023)
[pdf upon request]
Non-Truthful Position Auctions are More Robust to Misspecification
Paul Dütting, Felix Fischer, David C. Parkes
Mathematics of Operations Research, MOR 2023+, forthcoming
(Accepted February 2023)
[pdf upon request]
An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions
(Special Issue on FOCS 2020)
Paul Dütting, Thomas Kesselheim, Brendan Lucier
SIAM Journal on Computing, SICOMP’21+, forthcoming
(Accepted December 2021)
[pdf upon request]
Best-Response Dynamics in Combinatorial Auctions with Item Bidding
(Special Issue on STOC/FOCS/SODA 2016-2017)
Paul Dütting, Thomas Kesselheim
Games and Economic Behavior, GEB 2022, Vol. 134, pp. 428-448, July 2022
[pdf | BibTex]
Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution
Jose Correa, Paul Dütting, Felix Fischer, Kevin Schewior
Mathematics of Operations Research, MOR 2022, Vol. 47(2), pp. 1287-1309, May 2022
[pdf | BibTex]
Optimal Auctions through Deep Learning
(Invited Research Highlight)
Paul Dütting, Zhe Feng, Hari Narasimhan, Sai S. Ravindranath, David C.Parkes
Communications of the ACM, CACM 2021, Vol. 64(8), pp. 109-116, July 2021
[pdf | BibTex]
The Complexity of Contracts
Paul Dütting, Tim Roughgarden, Inbal Talgam-Cohen
SIAM Journal on Computing, SICOMP 2021, Vol. 50(1), pp. 211-254, January 2021
[pdf | BibTex]
Algorithms as Mechanisms: The Price of Anarchy of Relax-and-Round
Paul Dütting, Thomas Kesselheim, Eva Tardos
Mathematics of Operations Research, MOR 2021, Vol. 46(1), pp. 317-335, January 2021
[pdf | BibTex]
Prophet Inequalities made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs
Paul Dütting, Michal Feldman, Thomas Kesselheim, Brendan Lucier
SIAM Journal on Computing, SICOMP 2020, Vol. 49(3), pp. 540-582, June 2020
[pdf | BibTex]
Expressiveness and Robustness of First-Price Position Auctions
Paul Dütting, Felix Fischer, David C. Parkes
Mathematics of Operations Research, MOR 2019, Vol. 44(1), pp. 196-211, February 2019
[pdf | BibTex]
Valuation Compressions in VCG-Based Combinatorial Auctions
Paul Dütting, Monika Henzinger, Martin Starnberger
ACM Transactions on Economics and Computation, TEAC 2018, Vol. 6(2), Article 5, pp. 5:1-5:18, October 2018
[pdf | BibTex]
Modularity and Greed in Double Auctions
Paul Dütting, Tim Roughgarden, Inbal Talgam-Cohen
Games and Economic Behavior, GEB 2017, Vol. 105, pp. 59-83, September 2017
[pdf | BibTex]
The Performance of Deferred-Acceptance Auctions
Paul Dütting, Vasilis Gkatzelis, Tim Roughgarden
Mathematics of Operations Research, MOR 2017, Vol. 42(4), pp. 897-914, November 2017
[pdf | BibTex]
Auctions for Heterogeneous Items and Budget Limits
Paul Dütting, Monika Henzinger, Martin Starnberger
ACM Transactions on Economics and Computation, TEAC 2015, Vol. 4(1), Article 4, pp. 4:1-4:17, December 2015
[pdf | BibTex]
An Expressive Mechanism for Auctions on the Web
Paul Dütting, Monika Henzinger, Ingmar Weber
ACM Transactions on Economics and Computation, TEAC 2015, Vol. 4(1), Article 1, pp. 1:1-1:34, December 2015
[pdf | BibTex]
Payment Rules through Discriminant-Based Classifiers
(Special Issue on EC 2012)
Paul Dütting, Felix Fischer, Pichayut Jirapinyo, John K. Lai, Ben Lubin, David C. Parkes
ACM Transactions on Economics and Computation, TEAC 2015, Vol. 3(1), Article 5, pp. 5:1-5:41, March 2015
[pdf | BibTex]
Bidder Optimal Assignments for General Utilities
Paul Dütting, Monika Henzinger, Ingmar Weber
Theoretical Computer Science, TCS 2013, Vol. 478, pp. 22–32, March 2013
[pdf | BibTex]
Sponsored Search, Market Equilibria, and the Hungarian Method
Paul Dütting, Monika Henzinger, Ingmar Weber
Information Processing Letters, IPL 2013, Vol. 113(3), pp. 67-73, February 2013
[pdf | BibTex]
Offline File Assignments for Online Load Balancing
Paul Dütting, Monika Henzinger, Ingmar Weber
Information Processing Letters, IPL 2011, Vol.111(4), pp. 178-183, January 2011
[pdf | BibTex]

Book chapters

Machine Learning for Optimal Economic Design
Paul Dütting, Zhe Feng, Noah Golowich, David C. Parkes, Harikrishna Narasimhan, Sai S. Ravindranath
In The Future of Economic Design, Jean-François Laslier, Hervé Moulin, M. Remzi Sanver, William Z. Zwicker (eds.), Springer, Switzerland, November 2019
[pdf upon request]