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.

Optimal stopping, prophet inequalities, and posted pricing

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’22, Alexandria, VA, USA (virtual), forthcoming
[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’21 (virtual), forthcoming
[pdf | code | BibTex]
Secretaries with Advice
Paul Dütting, Renato Paes Leme, Silvio Lattanzi, Sergei Vassilvitskii
ACM Conference on Economics and Computation, EC’21, Budapest, Hungary, forthcoming
[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’21 (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’20, Durham, NC, USA
(Journal version in SICOMP’21+)
[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’19, Phoenix, AZ, USA
(Journal version in MOR’21+)
[pdf | arXiv | BibTex]
Posted Pricing and Prophet Inequalities with Inaccurate Priors
Paul Dütting, Thomas Kesselheim
ACM Conference on Economics and Computation, EC’19, 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’17, Berkeley, CA, USA
(Journal version in SICOMP’20)
[pdf | arXiv | BibTex]
Polymatroid Prophet Inequalities
Paul Dütting, Robert Kleinberg
European Symposium on Algorithms, ESA’15, Patras, Greece, September 2015
[pdf | arXiv | BibTex]

Algorithmic contract theory

Multi-Agent Contracts
Paul Dütting, Tomer Ezra, Michal Feldman, Thomas Kesselheim
ACM Symposium on Theory of Computing, STOC’23, Orlando, FL, USA, forthcoming
[arXiv]
Combinatorial Contracts
Paul Dütting, Tomer Ezra, Michal Feldman, Thomas Kesselheim
IEEE Symposium on Foundations of Computer Science, FOCS’21, Boulder, Colorado, USA (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’21, Budapest, Hungary (virtual)
[pdf | BibTex]
The Complexity of Contracts
Paul Dütting, Tim Roughgarden, Inbal Talgam-Cohen
ACM-SIAM Symposium on Discrete Algorithms, SODA’20, Salt Lake City, UT, USA
(Journal version in SICOMP’21)
[pdf | arXiv | BibTex]
Simple versus Optimal Contracts
Paul Dütting, Tim Roughgarden, Inbal Talgam-Cohen
ACM Conference on Economics and Computation, EC’19, Phoenix, AZ, USA
[pdf | arXiv | BibTex]

Also see our STOC’22 Tutorial:
Algorithmic Contract Theory
Paul Dütting, Inbal Talgam-Cohen
Slides: Part 1 and Part 2
(Recordings coming soon)

And our EC’19 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

Economic design through machine learning

Optimal Auctions through Deep Learning
Paul Dütting, Zhe Feng, Hari Narasimhan, David C. Parkes
International Conference on Machine Learning, ICML’19, Long Beach, CA, USA
(Research highlight in CACM’21)
[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 Economics and Computation, EC’12, Valencia, Spain
[pdf | BibTex]

Two-Sided Markets

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’21, Rome, Italy (virtual)
[pdf | arXiv | BibTex]
Modularity and Greed in Double Auctions
Paul Dütting, Tim Roughgarden, Inbal Talgam-Cohen
Games and Economic Behavior, GEB, Vol. 105, 59-83, 2017
(Extended Abstract in EC’14.)
[pdf | BibTex]

Game-playing dynamics

No-regret learning and best-response dynamics

Best-Response Dynamics in Combinatorial Auctions with Item Bidding
Paul Dütting, Thomas Kesselheim
ACM-SIAM Symposium on Discrete Algorithms, SODA’17, Barcelona, Spain
[pdf | arXiv | BibTex]
Mechanisms with Unique Learnable Equilibria
Paul Dütting, Thomas Kesselheim, Eva Tardos
ACM Conference on Economics and Computation, EC’14, Palo Alto, CA, June 2014
[pdf | BibTex]

Robust mechanism and contract design

Combinatorial Contracts
Paul Dütting, Tomer Ezra, Michal Feldman, Thomas Kesselheim
Under submission
[pdf upon request]
Posted Pricing and Prophet Inequalities with Inaccurate Priors
Paul Dütting, Thomas Kesselheim
ACM Conference on Economics and Computation, EC’19, Phoenix, AZ, USA
[pdf | BibTex]
Simple versus Optimal Contracts
Paul Dütting, Tim Roughgarden, Inbal Talgam-Cohen
20th ACM Conference on Economics and Computation, EC’19, Phoenix, AZ, USA
[pdf | arXiv | BibTex]

Sponsored search and position auctions

Non-Truthful Position Auctions are More Robust to Misspecification
Paul Dütting, Felix Fischer, David C. Parkes
(Extended Abstract in EC’16)
[upon request]
Expressiveness and Robustness of First-Price Position Auctions
Paul Dütting, Felix Fischer, David C. Parkes
Mathematics of Operations Research, MOR, accepted November 2017, to appear
(Extended Abstract in EC’14.)
[pdf | BibTex]

Combinatorial auctions and double auctions

Deferred-acceptance auctions

The Performance of Deferred-Acceptance Auctions
Paul Dütting, Vasilis Gkatzelis, Tim Roughgarden
Mathematics of Operations Research, MOR, Volume 42, Issue 4, Pages 897-914, November 2017
(Extended Abstract in EC’14.)
[pdf | BibTex]
Modularity and Greed in Double Auctions
Paul Dütting, Tim Roughgarden, Inbal Talgam-Cohen
Games and Economic Behavior, GEB, Vol. 105, 59-83, 2017
(Extended Abstract in EC’14.)
[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’15, 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’15, Portland, OR, June 2015
[pdf | BibTex]

Mechanisms with restricted bidding languages

Valuation Compressions in VCG-Based Combinatorial Auctions
Paul Dütting, Monika Henzinger, Martin Starnberger
ACM Transactions on Economics and Computation, ACM TEAC, Vol. 6(2), Art. 5, October 2018
(Extended Abstract in WINE’13)
[pdf | arXiv | BibTex]
Simplicity-Expressiveness Tradeoffs in Mechanism Design
Paul Dütting, Felix Fischer, David C. Parkes
ACM Conference on Electronic Commerce, EC’11, 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
ACM Transactions on Economics and Computation, ACM TEAC, Vol. 4(1), Art. 1, December 2015
(Extended Abstract in WWW’11.)
[pdf | BibTex]
Auctions for Heterogeneous Items and Budget Limits
Paul Dütting, Monika Henzinger, Martin Starnberger
ACM Transactions on Economics and Computation, ACM TEAC, Vol. 4(1), Article 4, December 2015
(Extended Abstract in WINE’13.)
[pdf | BibTex]
Bidder Optimal Assignments for General Utilities
Paul Dütting, Monika Henzinger, Ingmar Weber
Theoretical Computer Science, TCS, Vol. 478, Pages 22–32, March 2013
(Extended Abstract in WINE’09.)
[pdf | BibTex]
Sponsored Search, Market Equilibria, and the Hungarian Method
Paul Dütting, Monika Henzinger, Ingmar Weber
Information Processing Letters, IPL, Vol. 113(3), Pages 67-73, February 2013
(Extended Abstract in STACS’10)
[pdf | BibTex]