Paul Dütting

Paul Dütting

Auto-generated profile, based on publicly available information

Paul Dütting

Google research

Research Focus & Metrics

Academic Career Length

12Years (2015-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
11 February 2024 in Journal of the ACM
Verified
Journal Article
Open access
PDPaul Dütting
Paul Dütting
ZFZhe Feng
Zhe Feng
HNHarikrishna Narasimhan
Harikrishna Narasimhan
DPDavid C. Parkes
David C. Parkes
SRSai Srivatsa Ravindranath
Sai Srivatsa Ravindranath
Designing an incentive compatible auction that maximizes expected revenue is an intricate task. The single-item case was resolved in a seminal piece of work by Myerson in 1981, but more than 40 years later, a full analytical understanding of the optimal design still remains elusive for settings with two or more items. In this work, we initiate the exploration of the use of tools from deep learning for the automated design of optimal auctions. We model an auction as a multi-layer neural network, frame optimal auction design as a constrained learning problem, and show how it can be solved using standard machine learning pipelines. In addition to providing generalization bounds, we present extensive experimental results, recovering essentially all known solutions that come from the theoretical analysis of optimal auction design problems and obtaining novel mechanisms for settings in which the optimal mechanism is unknown.

31 December 2024 in Foundations and Trends® in Theoretical Computer Science
Verified
Journal Article
Closed access
PDF file
PDPaul Dütting
Paul Dütting
MFMichal Feldman
Michal Feldman
ITInbal Talgam-Cohen
Inbal Talgam-Cohen
A contract is an economic tool used by a principal to incentivize one or more agents to exert effort on her behalf, by defining payments based on observable performance measures. A key challenge addressed by contracts—known in economics as moral hazard—is that, absent a properly set up contract, agents might engage in actions that are not in the principal's best interest. Another common feature of contracts is limited liability, which means that payments can go only from the principal—who has the deep pocket —to the agents. With classic applications of contract theory moving online, growing in scale, and becoming more data-driven, tools from contract theory become increasingly important for incentiveaware algorithm design. At the same time, algorithm design offers a whole new toolbox for reasoning about contracts, ranging from additional tools for studying the tradeoff between simple and optimal contracts, through a language for discussing the computational complexity of contracts in combinatorial settings, to a formalism for analyzing data-driven contracts. This survey aims to provide a computer science-friendly introduction to the basic concepts of contract theory.We give an overview of the emerging field of “algorithmic contract theory” and highlight work that showcases the potential for interaction between the two areas. We also discuss avenues for future research.

13 May 2024
Verified
Conference Paper
Open access
PDPaul Dütting
Paul Dütting
VMVahab Mirrokni
Vahab Mirrokni
RLRenato Paes Leme
Renato Paes Leme
HXHaifeng Xu
Haifeng Xu
SZSong Zuo
Song Zuo
We investigate auction mechanisms to support the emerging format of AI-generated content. We in particular study how to aggregate several LLMs in an incentive compatible manner. In this problem, the preferences of each agent over stochastically generated contents are described/encoded as an LLM. A key motivation is to design an auction format for AI-generated ad creatives to combine inputs from different advertisers. We argue that this problem, while generally falling under the umbrella of mechanism design, has several unique features. We propose a general formalism---the token auction model---for studying this problem. A key feature of this model is that it acts on a token-by-token basis and lets LLM agents influence generated contents through single dimensional bids. We first explore a robust auction design approach, in which all we assume is that agent preferences entail partial orders over outcome distributions. We formulate two natural incentive properties, and show that these are equivalent to a monotonicity condition on distribution aggregation. We also show that for such aggregation functions, it is possible to design a second-price auction, despite the absence of bidder valuation functions. We then move to designing concrete aggregation functions by focusing on specific valuation forms based on KL-divergence, a commonly used loss function in LLM. The welfare-maximizing aggregation rules turn out to be the weighted (log-space) convex combination of the target distributions from all participants. We conclude with experimental results in support of the token auction formulation.

12 November 2015
Verified
Book Chapter
Closed access
PDF file
PDPaul Dütting
Paul Dütting
RKRobert Kleinberg
Robert Kleinberg

1 January 2024 in Econometrica
Verified
Journal Article
Open access
PDPaul Dütting
Paul Dütting
MFMichal Feldman
Michal Feldman
DPDaniel Peretz
Daniel Peretz
LSLarry Samuelson
Larry Samuelson
We explore the deliberate infusion of ambiguity into the design of contracts. We show that when the agent is ambiguity‐averse and hence chooses an action that maximizes their minimum utility, the principal can strictly gain from using an ambiguous contract, and this gain can be arbitrarily high. We characterize the structure of optimal ambiguous contracts, showing that ambiguity drives optimal contracts toward simplicity. We also provide a characterization of ambiguity‐proof classes of contracts, where the principal cannot gain by infusing ambiguity. Finally, we show that when the agent can engage in mixed actions, the advantages of ambiguous contracts disappear.

1 May 2022 in Mathematics of Operations Research
Verified
Journal Article
Closed access
JCJosé Correa
José Correa
PDPaul Dütting
Paul Dütting
FFFelix Fischer
Felix Fischer
KSKevin Schewior
Kevin Schewior
A central object of study in optimal stopping theory is the single-choice prophet inequality for independent and identically distributed random variables: given a sequence of random variables [ ] drawn independently from the same distribution, the goal is to choose a stopping time τ such that for the maximum value of α and for all distributions, [ ]. What makes this problem challenging is that the decision whether [ ] may only depend on the values of the random variables [ ] and on the distribution F. For a long time, the best known bound for the problem had been [ ], but recently a tight bound of [ ] was obtained. The case where F is unknown, such that the decision whether [ ] may depend only on the values of the random variables [ ], is equally well motivated but has received much less attention. A straightforward guarantee for this case of [ ] can be derived from the well-known optimal solution to the secretary problem, where an arbitrary set of values arrive in random order and the goal is to maximize the probability of selecting the largest value. We show that this bound is in fact tight. We then investigate the case where the stopping time may additionally depend on a limited number of samples from F, and we show that, even with o(n) samples, [ ]. On the other hand, n samples allow for a significant improvement, whereas [ ] samples are equivalent to knowledge of the distribution: specifically, with n samples, [ ] and [ ], and with [ ] samples, [ ] for any [ ].