6 papers
Online Multi-Agent Contracts
Paul Dütting, Michal Feldman, Yoav Gal-Tzur +1
We introduce and study an online variant of the multi-agent contract model. In our model, agents arrive one-by-one and are active with a certain probability. Upon arrival of agent…
Graphic Matroid Secretary without the Graph
Paul Dütting, Renato Paes Leme, Martin Pál +1
The matroid secretary problem (MSP) is one of the cleanest, and most captivating open problems in online algorithms. The famous MSP conjecture stipulates that there exists a consta…
Online Matroid Embeddings
Andrés Cristi, Paul Dütting, Robert Kleinberg +2
We introduce the notion of an online matroid embedding, which is an algorithm for mapping an unknown matroid that is revealed in an online fashion to a larger-but-known matroid. We…
Multi-Agent Combinatorial Contracts
Paul Duetting, Tomer Ezra, Michal Feldman +1
Combinatorial contracts are emerging as a key paradigm in algorithmic contract design, paralleling the role of combinatorial auctions in algorithmic mechanism design. In this paper…
Mechanism Design for Large Language Models
Paul Duetting, Vahab Mirrokni, Renato Paes Leme +2
We investigate auction mechanisms for AI-generated content, focusing on applications like ad creative generation. In our model, agents' preferences over stochastically generated co…
Combinatorial Contracts Beyond Gross Substitutes
Paul Dütting, Michal Feldman, Yoav Gal Tzur
We study the combinatorial contracting problem of Dütting et al. [FOCS '21], in which a principal seeks to incentivize an agent to take a set of costly actions. In their model, the…