By Topic

Publications sorted by topic. 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.

Prophet inequalities, secretary problems, and posted pricing

Online Combinatorial Allocation and Auctions with Few Samples
Paul Dütting, Thomas Kesselheim, Brendan Lucier, Rebecca Reiffenhäuser, Sahil Singla
IEEE Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, forthcoming
[upon request]
The Competition Complexity of Prophet Inequalities
Johannes Brustle, Jose Correa, Paul Dütting, Tomer Ezra, Michal Feldman, Victor Verdugo
ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA
[upon request]
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
(Journal version R&R at MOR)
[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
(Journal version R&R at OR)
[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
(Journal version in MOR 2024+, forthcoming)
[pdf | BibTex]
Single-Sample Prophet Inequalities via Greedy-Ordered Selection
Constantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardo, Orestis Papadigenopoulos, Emmanouil Pountourakis, Rebecca Reiffenhäuser
ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Alexandria, VA, USA (virtual)
(Journal version under submission)
[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)
(Journal version R&R at OR)
[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
(Journal version in MOR 2024)
[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
(Journal version in SICOMP 2021+, forthcoming)
[pdf | arXiv | ACM SIGecom Exchanges | 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
(Journal version in MOR 2022)
[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]
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
(Journal version in SICOMP 2020)
[pdf | arXiv | BibTex]
Polymatroid Prophet Inequalities
Paul Dütting, Robert Kleinberg
European Symposium on Algorithms, ESA 2015, Patras, Greece, September 2015
[pdf | arXiv | BibTex]

Summer Schools:

Max-Planck ADFOCS 2024 Summer School:
Prophet Inequalities
Paul Dütting
Slides: Part 1, Part 2, Part 3, Part 4

Algorithmic contract theory

The Query Complexity of Contracts
Paul Dütting, Michal Feldman, Yoav Gal-Tzur, Aviad Rubinstein
[upon request]
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]
Ambiguous Contracts
Paul Dütting, Michal Feldman, Daniel Peretz
ACM Conference on Economics and Computation, EC 2023, London, UK
(Journal Version with Larry Samuelson in ECMA 2024+, forthcoming)
[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
(Journal version with title “Approximation Guarantees of Linear Contracts Under Uncertainty” in preparation)
[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, forthcoming
[arXiv]
Combinatorial Contracts
Paul Dütting, Tomer Ezra, Michal Feldman, Thomas Kesselheim
IEEE Symposium on Foundations of Computer Science, FOCS 2021, Boulder, Colorado, USA (virtual)
(Journal version under submission)
[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)
(Journal version R&R at GEB)
[pdf | 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
(Journal version in SICOMP 2021)
[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]

Survey talks and tutorials:

HALG 2024 Survey Talk:
Algorithmic Contract Theory
Paul Dütting
Slides: slides

STOC 2022 Tutorial:
Algorithmic Contract Theory
Paul Dütting, Inbal Talgam-Cohen
Slides: Part 1 and Part 2
Recording: Video

EC 2019 Tutorial:
Contract Theory: A New Frontier for AGT
Paul Dütting, Inbal Talgam-Cohen
Slides: Part 1 and Part 2
Recordings: Part 1 and Part 2

Machine learning for economic design, differentiable economics, automated mechanism design

Deep Contract Design via Discontinuos Piecewise-Affine Neural 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 Auctions through Deep Learning
Paul Dütting, Zhe Feng, Hari Narasimhan, David C. Parkes
International Conference on Machine Learning, ICML 2019, Long Beach, CA, USA
(Journal version in JACM 2024)
(Research highlight in CACM 2021)
[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 Economics and Computation, EC 2012, Valencia, Spain
(Journal Version in TEAC 2015)
[pdf | BibTex]

Two-sided markets, double auctions, bilateral trade

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)
(Journal version R&R in SICOMP)
[pdf | arXiv | 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, USA
(Journal version in GEB 2017)
[pdf | BibTex]

Submodular maximization

Consistent Submodular Maximization
Paul Dütting, Federico Fusco, Ashkan Norouzi-Fard, Silvio Lattanzi, Morteza Zadimoghaddam
International Conference on Machine Learning, ICML 2024, Vienna, Austria
[upon request]
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
(Journal version R&R at TALG)
[pdf | arXiv | BibTex]
Deletion Robust Submodular Maximization over Matroids
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]

Game-playing dynamics, no-regret learning, correlated equilibria

Selling Joint Ads: A Regret Minimization Perspective
Gagan Aggarwal, Ashwin Bananidiyuru, Paul Dütting, Federico Fusco
ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA
[upon request]
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]
Best-Response Dynamics in Combinatorial Auctions with Item Bidding
Paul Dütting, Thomas Kesselheim
ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain
(Journal Version in GEB 2022)
[pdf | arXiv | 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]

Combinatorial auctions, deferred-acceptance auctions

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 2014o
(Journal version in MOR 2017.)
[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
(Journal version in GEB 2017)
[pdf | BibTex]

Price of anarchy in mechanisms

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]
(Journal version in MOR 2021)
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]

Simplified mechanisms, mechanisms with restricted bidding languages

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
(Journal version in TEAC 2018)
[pdf | arXiv | 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]

Mechanisms for non-linear utilities and budget constraints

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
(Journal version in TEAC 2015)
[pdf | 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
(Journal version in TEAC 2015)
[pdf | arXiv | 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
(Journal version in IPL 2013)
[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
(Journal version in TCS 2013)
[pdf | BibTex]