Paul Dütting

JMLR Journal 2025 Journal Article

Deletion Robust Non-Monotone Submodular Maximization over Matroids

• Paul Dütting
• Federico Fusco
• Silvio Lattanzi
• Ashkan Norouzi-Fard
• Morteza Zadimoghaddam

We study the deletion robust version of submodular maximization under matroid constraints. The goal is to extract a small-size summary of the data set that contains a high-value independent set even after an adversary deletes some elements. We present constant-factor approximation algorithms, whose space complexity depends on the rank $k$ of the matroid, the number $d$ of deleted elements, and the input precision $\varepsilon$. In the centralized setting we present a $(4.494+O(\varepsilon))$-approximation algorithm with summary size $O( \frac{k+d}{\varepsilon^2}\log \frac{k}{\varepsilon})$ that improves to a $(3.582+O(\varepsilon))$-approximation with $O(k + \frac{d}{\varepsilon^2}\log \frac{k}{\varepsilon})$ summary size when the objective is monotone. In the streaming setting we provide a $(9.294 + O(\varepsilon))$-approximation algorithm with summary size and memory $O(k + \frac{d}{\varepsilon^2}\log \frac{k}{\varepsilon})$; the approximation factor is then improved to $(5.582+O(\varepsilon))$ in the monotone case. [abs] [ pdf ][ bib ] &copy JMLR 2025. ( edit, beta )

IJCAI Conference 2025 Conference Paper

Mechanism Design for Large Language Models (Extended Abstract)

• Paul Dütting
• Vahab Mirrokni
• Renato Paes Leme
• Haifeng Xu
• Song Zuo

We investigate auction mechanisms for AI-generated content, focusing on applications like ad creative generation. In our model, agents' preferences over stochastically generated content are encoded as large language models (LLMs). We propose an auction format that operates on a token-by-token basis, and allows LLM agents to influence content creation through single dimensional bids. We formulate two desirable incentive properties and prove their equivalence to a monotonicity condition on output aggregation. This equivalence enables a second-price rule design, even absent explicit agent valuation functions. Our design is supported by demonstrations on a publicly available LLM.

SODA Conference 2025 Conference Paper

Multi-Agent Combinatorial Contracts

• Paul Dütting
• Tomer Ezra
• Michal Feldman
• Thomas Kesselheim

FOCS Conference 2025 Conference Paper

Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade

• Simone Di Gregorio 0001
• Paul Dütting
• Federico Fusco 0001
• Chris Schwiegelshohn

Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. We study this problem from the perspective of a broker, in a regret minimization framework. At each time step, a new seller and buyer arrive, and the broker has to propose a mechanism that is incentivecompatible and individually rational, with the goal of maximizing profit. We propose a learning algorithm that guarantees a nearly tight regret in the stochastic setting when seller and buyer valuations are drawn i. i. d. from a fixed and possibly correlated unknown distribution. We further show that it is impossible to achieve sublinear regret in the non-stationary scenario where valuations are generated upfront by an adversary. Our ambitious benchmark for these results is the best incentive-compatible and individually rational mechanism. This separates us from previous works on efficiency maximization in bilateral trade, where the benchmark is a single number: the best fixed price in hindsight. A particular challenge we face is that uniform convergence for all mechanisms’ profits is impossible. We overcome this difficulty via a careful chaining analysis that proves convergence for a provably near-optimal mechanism at (essentially) optimal rate. We further showcase the broader applicability of our techniques by providing nearly optimal results for the joint ads problem.

STOC Conference 2025 Conference Paper

The Cost of Consistency: Submodular Maximization with Constant Recourse

• Paul Dütting
• Federico Fusco 0001
• Silvio Lattanzi
• Ashkan Norouzi-Fard
• Ola Svensson
• Morteza Zadimoghaddam

SODA Conference 2024 Conference Paper

Combinatorial Contracts Beyond Gross Substitutes

• Paul Dütting
• Michal Feldman
• Yoav Gal Tzur

We study the combinatorial contracting problem of Dütting et al. [13], in which a principal seeks to incentivize an agent to take a set of costly actions. In their model, there is a binary outcome (the agent can succeed or fail), and the success probability and the costs depend on the set of actions taken. The optimal contract is linear, paying the agent an α fraction of the reward. For gross substitutes (GS) rewards and additive costs, they give a poly-time algorithm for finding the optimal contract. They use the properties of GS functions to argue that there are poly-many “critical values” of α, and that one can iterate through all of them efficiently in order to find the optimal contract. In this work we study to which extent GS rewards and additive costs constitute a tractability frontier for combinatorial contracts. We present an algorithm that for any rewards and costs, enumerates all critical values, with poly-many demand queries (in the number of critical values). This implies the tractability of the optimal contract for any setting with poly-many critical values and efficient demand oracle. A direct corollary is a poly-time algorithm for the optimal contract in settings with supermodular rewards and submodular costs. We also study a natural class of matching-based instances with XOS rewards and additive costs. While the demand problem for this setting is tractable, we show that it admits an super-polynomial number of critical values. On the positive side, we present (pseudo-) polynomial-time algorithms for two natural special cases of this setting. Our work unveils a profound connection to sensitivity analysis, and designates matching-based instances as a crucial focal point for gaining a deeper understanding of combinatorial contract settings. * Accepted as a “soft merge” with Deo-Campo Vuong, Dughmi, Patel, and Prasad [12]. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 866132), by the Israel Science Foundation (grant number 317/17), by an Amazon Research Award, and by the NSF-BSF (grant number 2020788). The full version of the paper can be accessed at https: //arxiv. org/pdf/2309. 10766. pdf

ICML Conference 2024 Conference Paper

Consistent Submodular Maximization

• Paul Dütting
• Federico Fusco 0001
• Silvio Lattanzi
• Ashkan Norouzi-Fard
• Morteza Zadimoghaddam

Maximizing monotone submodular functions under cardinality constraints is a classic optimization task with several applications in data mining and machine learning. In this paper, we study this problem in a dynamic environment with consistency constraints: elements arrive in a streaming fashion, and the goal is maintaining a constant approximation to the optimal solution while having a stable solution (i. e. , the number of changes between two consecutive solutions is bounded). In this setting, we provide algorithms with different trade-offs between consistency and approximation quality. We also complement our theoretical results with an experimental analysis showing the effectiveness of our algorithms in real-world instances.

FOCS Conference 2024 Conference Paper

Online Combinatorial Allocations and Auctions with Few Samples

• Paul Dütting
• Thomas Kesselheim
• Brendan Lucier
• Rebecca Reiffenhäuser
• Sahil Singla 0001

In online combinatorial allocations/auctions, $n$ bidders sequentially arrive, each with a combinatorial valuation (such as submodular/XOS) over subsets of $m$ indivisible items. The aim is to immediately allocate a subset of the remaining items to maximize the total welfare, defined as the sum of bidder valuations. A long line of work has studied this problem when the bidder valuations come from known independent distributions. In particular, for submodular/XOS valuations, we know 2-competitive algorithms/mechanisms that set a fixed price for each item and the arriving bidders take their favorite subset of the remaining items given these prices. However, these algorithms traditionally presume the availability of the underlying distributions as part of the input to the algorithm. Contrary to this assumption, practical scenarios often require the learning of distributions, a task complicated by limited sample availability. This paper investigates the feasibility of achieving $O$ (1) -competitive algorithms under the realistic constraint of having access to only a limited number of samples from the underlying bidder distributions. Our first main contribution shows that a mere single sample from each bidder distribution is sufficient to yield an $O$ (1)-competitive algorithm for submodular/XOS valuations. This result leverages a novel extension of the secretary-style analysis, employing the sample to have the algorithm compete against itself. Although online, this first approach does not provide an online truthful mechanism. Our second main contribution shows that a polynomial number of samples suffices to yield a (2 + ∊) -competitive online truthful mechanism for submodular/XOS valuations and any constant ∊ > 0. This result is based on a generalization of the median-based algorithm for the single-item prophet inequality problem to combinatorial settings with multiple items.

ICML Conference 2023 Conference Paper

Fully Dynamic Submodular Maximization over Matroids

• Paul Dütting
• Federico Fusco 0001
• Silvio Lattanzi
• Ashkan Norouzi-Fard
• Morteza Zadimoghaddam

Maximizing monotone submodular functions under a matroid constraint is a classic algorithmic problem with multiple applications in data mining and machine learning. We study this classic problem in the fully dynamic setting, where elements can be both inserted and deleted in real-time. Our main result is a randomized algorithm that maintains an efficient data structure with an $\tilde{O}(k^2)$ amortized update time (in the number of additions and deletions) and yields a $4$-approximate solution, where $k$ is the rank of the matroid.

STOC Conference 2023 Conference Paper

Multi-agent Contracts

• Paul Dütting
• Tomer Ezra
• Michal Feldman
• Thomas Kesselheim

We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the heart of our model is a reward function , which maps the agent efforts to an expected reward of the principal. We seek to design computationally efficient algorithms for finding optimal (or near-optimal) linear contracts for reward functions that belong to the complement-free hierarchy. Our first main result gives constant-factor approximation algorithms for submodular and XOS reward functions, with value and demand oracles, respectively. It relies on an unconventional use of “prices” and (approximate) demand queries for selecting the set of agents that the principal should contract with, and exploits a novel scaling property of XOS functions and their marginals, which may be of independent interest. Our second main result is an Ω(√ n ) impossibility for settings with n agents and subadditive reward functions, even with demand oracle access. A striking feature of this impossibility is that it applies to subadditive functions that are constant-factor close to submodular. This presents a surprising departure from previous literature, e.g., on combinatorial auctions.

ICML Conference 2023 Conference Paper

Optimal No-Regret Learning for One-Sided Lipschitz Functions

• Paul Dütting
• Guru Guruganesh
• Jon Schneider
• Joshua R. Wang

Inspired by applications in pricing and contract design, we study the maximization of one-sided Lipschitz functions, which only provide the (weaker) guarantee that they do not grow too quickly in one direction. We show that it is possible to learn a maximizer for such a function while incurring $O(\log \log T)$ total regret (with a universal constant independent of the number of discontinuities / complexity of the function). This regret bound is asymptotically optimal in $T$ due to a lower bound of Kleinberg and Leighton. By applying this algorithm, we show that one can sell digital goods to multiple buyers and learn the optimal linear contract in the principal-agent setting while incurring at most $O(\log \log T)$ regret.

ICML Conference 2022 Conference Paper

Deletion Robust Submodular Maximization over Matroids

• Paul Dütting
• Federico Fusco 0001
• Silvio Lattanzi
• Ashkan Norouzi-Fard
• Morteza Zadimoghaddam

Maximizing a monotone submodular function is a fundamental task in machine learning. In this paper we study the deletion robust version of the problem under the classic matroids constraint. Here the goal is to extract a small size summary of the dataset that contains a high value independent set even after an adversary deleted some elements. We present constant-factor approximation algorithms, whose space complexity depends on the rank $k$ of the matroid and the number $d$ of deleted elements. In the centralized setting we present a $(3. 582+O(\varepsilon))$-approximation algorithm with summary size $O(k + \frac{d}{\eps^2}\log \frac{k}{\eps})$. In the streaming setting we provide a $(5. 582+O(\varepsilon))$-approximation algorithm with summary size and memory $O(k + \frac{d}{\eps^2}\log \frac{k}{\eps})$. We complement our theoretical results with an in-depth experimental analysis showing the effectiveness of our algorithms on real-world datasets.

SODA Conference 2022 Conference Paper

Single-Sample Prophet Inequalities via Greedy-Ordered Selection

• Constantine Caramanis
• Paul Dütting
• Matthew Faw
• Federico Fusco 0001
• Philip Lazos
• Stefano Leonardi 0001
• Orestis Papadigenopoulos
• Emmanouil Pountourakis

FOCS Conference 2021 Conference Paper

Combinatorial Contracts

• Paul Dütting
• Tomer Ezra
• Michal Feldman
• Thomas Kesselheim

We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take any subset of a given set of unobservable actions, each of which has an associated cost. The cost of a set of actions is the sum of the costs of the individual actions, and the principal's reward as a function of the chosen actions satisfies some form of diminishing returns. The principal incentivizes the agents through a contract, based on the observed outcome. Our main results are for the case where the task delegated to the agent is a project, which can be successful or not. We show that if the success probability as a function of the set of actions is gross substitutes, then an optimal contract can be computed with polynomially many value queries, whereas if it is submodular, the optimal contract is NP-hard. All our results extend to linear contracts for higher-dimensional outcome spaces, which we show to be robustly optimal given first moment constraints. Our analysis uncovers a new property of gross substitutes functions, and reveals many interesting connections between combinatorial contracts and combinatorial auctions, where gross substitutes is known to be the frontier for efficient computation.

STOC Conference 2021 Conference Paper

Efficient two-sided markets with limited information

• Paul Dütting
• Federico Fusco 0001
• Philip Lazos
• Stefano Leonardi 0001
• Rebecca Reiffenhäuser

ICML Conference 2021 Conference Paper

Fairness and Bias in Online Selection

• José Correa 0001
• Andrés Cristi
• Paul Dütting
• Ashkan Norouzi-Fard

There is growing awareness and concern about fairness in machine learning and algorithm design. This is particularly true in online selection problems where decisions are often biased, for example, when assessing credit risks or hiring staff. We address the issues of fairness and bias in online selection by introducing multi-color versions of the classic secretary and prophet problem. Interestingly, existing algorithms for these problems are either very unfair or very inefficient, so we develop optimal fair algorithms for these new problems and provide tight bounds on their competitiveness. We validate our theoretical findings on real-world data.

FOCS Conference 2020 Conference Paper

An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions

• Paul Dütting
• Thomas Kesselheim
• Brendan Lucier

Prophet inequalities compare the expected performance of an online algorithm for a stochastic optimization problem to the expected optimal solution in hindsight. They are a major alternative to classic worst-case competitive analysis, of particular importance in the design and analysis of simple (posted-price) incentive compatible mechanisms with provable approximation guarantees. A central open problem in this area concerns subadditive combinatorial auctions. Here n agents with subadditive valuation functions compete for the assignment of m items. The goal is to find an allocation of the items that maximizes the total value of the assignment. The question is whether there exists a prophet inequality for this problem that significantly beats the best known approximation factor of O(log m). We make major progress on this question by providing an O(log log m) prophet inequality. Our proof goes through a novel primal-dual approach. It is also constructive, resulting in an online policy that takes the form of static and anonymous item prices that can be computed in polynomial time given appropriate query access to the valuations. As an application of our approach, we construct a simple and incentive compatible mechanism based on posted prices that achieves an O(log log m) approximation to the optimal revenue for subadditive valuations under an item-independence assumption.

SODA Conference 2020 Conference Paper

The Complexity of Contracts

• Paul Dütting
• Tim Roughgarden
• Inbal Talgam-Cohen

ICML Conference 2019 Conference Paper

Optimal Auctions through Deep Learning

• Paul Dütting
• Zhe Feng 0004
• Harikrishna Narasimhan
• David C. Parkes
• 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. Even after 30-40 years of intense research the problem remains unsolved for seemingly simple multi-bidder, multi-item settings. 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 pipelines. We prove generalization bounds and present extensive experiments, recovering essentially all known analytical solutions for multi-item settings, and obtaining novel mechanisms for settings in which the optimal mechanism is unknown.

SODA Conference 2017 Conference Paper

Best-Response Dynamics in Combinatorial Auctions with Item Bidding

• Paul Dütting
• Thomas Kesselheim

In a combinatorial auction with item bidding, agents participate in multiple single-item second-price auctions at once. As some items might be substitutes, agents need to strate- gize in order to maximize their utilities. A number of results indicate that high welfare can be achieved this way, giving bounds on the welfare at equilibrium. Recently, however, criticism has been raised that equilibria are hard to compute and therefore unlikely to be attained. In this paper, we take a different perspective. We study simple best-response dynamics. That is, agents are activated one after the other and each activated agent updates his strategy myopically to a best response against the other agents’ current strategies. Often these dynamics may take exponentially long before they converge or they may not converge at all. However, as we show, convergence is not even necessary for good welfare guarantees. Given that agents’ bid updates are aggressive enough but not too aggressive, the game will remain in states of good welfare after each agent has updated his bid at least once. In more detail, we show that if agents have fractionally subadditive valuations, natural dynamics reach and remain in a state that provides a 1/3 approximation to the optimal welfare after each agent has updated his bid at least once. For subadditive valuations, we can guarantee an Ω(1/log m ) approximation in case of m items that applies after each agent has updated his bid at least once and at any point after that. The latter bound is complemented by a negative result, showing that no kind of best-response dynamics can guarantee more than a an o (log log m / log m ) fraction of the optimal social welfare.

FOCS Conference 2017 Conference Paper

Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs

• Paul Dütting
• Michal Feldman
• Thomas Kesselheim
• Brendan Lucier

We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The framework establishes prophet inequalities by constructing price-based online approximation algorithms, a natural extension of threshold algorithms for settings beyond binary selection. Our analysis takes the form of an extension theorem: we derive sufficient conditions on prices when all weights are known in advance, then prove that the resulting approximation guarantees extend directly to stochastic settings. Our framework unifies and simplifies much of the existing literature on prophet inequalities and posted price mechanisms, and is used to derive new and improved results for combinatorial markets (with and without complements), multi-dimensional matroids, and sparse packing problems. Finally, we highlight a surprising connection between the smoothness framework for bounding the price of anarchy of mechanisms and our framework, and show that many smooth mechanisms can be recast as posted price mechanisms with comparable performance guarantees.

TCS Journal 2013 Journal Article

Bidder optimal assignments for general utilities

• Paul Dütting
• Monika Henzinger
• Ingmar Weber

We study the problem of matching bidders to items where each bidder i has general, strictly monotonic utility functions u i, j ( p j ) expressing his utility of being matched to item j at price p j. For this setting we prove that a bidder optimal outcome always exists, even when the utility functions are non-linear and non-continuous. We give sufficient conditions under which every mechanism that finds a bidder optimal outcome is incentive compatible. We also give a mechanism that finds a bidder optimal outcome if the conditions for incentive compatibility are satisfied. The running time of this mechanism is exponential in the number of items, but polynomial in the number of bidders.