11 citations · 48 across the 34 of their papers we have counts for
42 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…
Online Algorithms via Minimax and Posterior Matching
Thomas Kesselheim, Marco Molinaro, Kalen Patton +1
Competitive analysis is central to the study of online algorithms, but upper bounds are often highly problem-specific. We develop a more unifying methodology via the minimax viewpo…
Black-Box Lifting and Robustness Theorems for Multi-Agent Contracts
Paul Dütting, Tomer Ezra, Michal Feldman +1
Multi-agent contract design has largely evaluated contracts through the lens of pure Nash equilibria (PNE). This focus, however, is not without loss: In general, the principal can…
Prophet and Secretary at the Same Time
Gregory Kehne, Thomas Kesselheim
Many online problems are studied in stochastic settings for which inputs are samples from a known distribution, given in advance, or from an unknown distribution. Such distribution…
An Efficient Algorithm for Minimizing Ordered Norms in Fractional Load Balancing
Daniel Blankenburg, Antonia Ellerbrock, Thomas Kesselheim +1
We study the problem of minimizing an ordered norm of a load vector (indexed by a set of resources), where a finite number of customers contribute to the load of each r…
Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives
Thomas Kesselheim, Marco Molinaro, Kalen Patton +1
Online Set Cover and Load Balancing are central problems in online optimization, and there is a long line of work on developing algorithms for these problems with convex objectives…
Contextual Learning for Stochastic Optimization
Anna Heuser, Thomas Kesselheim
Motivated by stochastic optimization, we introduce the problem of learning from samples of contextual value distributions. A contextual value distribution can be understood as a fa…
Online Combinatorial Allocations and Auctions with Few Samples
Paul Dütting, Thomas Kesselheim, Brendan Lucier +2
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 a…
Supermodular Approximation of Norms and Applications
Thomas Kesselheim, Marco Molinaro, Sahil Singla
Many classical problems in theoretical computer science involve norm, even if implicitly; for example, both XOS functions and downward-closed sets are equivalent to some norms. The…
Approximating Optimum Online for Capacitated Resource Allocation
Alexander Braun, Thomas Kesselheim, Tristan Pollner +1
We study online capacitated resource allocation, a natural generalization of online stochastic max-weight bipartite matching. This problem is motivated by ride-sharing and Internet…
Sample Complexity of Posted Pricing for a Single Item
Billy Jin, Thomas Kesselheim, Will Ma +1
Selling a single item to self-interested buyers is a fundamental problem in economics, where the two objectives typically considered are welfare maximization and revenue maximi…
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…
Bandit Algorithms for Prophet Inequality and Pandora's Box
Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla +1
The Prophet Inequality and Pandora's Box problems are fundamental stochastic problem with applications in Mechanism Design, Online Algorithms, Stochastic Optimization, Optimal Stop…
Multi-Agent Contracts
Paul Duetting, Tomer Ezra, Michal Feldman +1
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 h…
Simplified Prophet Inequalities for Combinatorial Auctions
Alexander Braun, Thomas Kesselheim
We consider prophet inequalities for XOS and MPH- combinatorial auctions and give a simplified proof for the existence of static and anonymous item prices which recover the stat…
Online and Bandit Algorithms Beyond Norms
Thomas Kesselheim, Marco Molinaro, Sahil Singla
Vector norms play a fundamental role in computer science and optimization, so there is an ongoing effort to generalize existing algorithms to settings beyond and $\el…
Combinatorial Contracts
Paul Duetting, Tomer Ezra, Michal Feldman +1
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 o…
Asymptotically Optimal Welfare of Posted Pricing for Multiple Items with MHR Distributions
Alexander Braun, Matthias Buttkus, Thomas Kesselheim
We consider the problem of posting prices for unit-demand buyers if all buyers have identically distributed valuations drawn from a distribution with monotone hazard rate. We s…
Truthful Mechanisms for Two-Sided Markets via Prophet Inequalities
Alexander Braun, Thomas Kesselheim
We design novel mechanisms for welfare-maximization in two-sided markets. That is, there are buyers willing to purchase items and sellers holding items initially, both acting ratio…
Online Learning with Vector Costs and Bandits with Knapsacks
Thomas Kesselheim, Sahil Singla
We introduce online learning with vector costs (\OLVCp) where in each time step , we need to play an action that incurs an unknown vec…
Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier
Sepehr Assadi, Thomas Kesselheim, Sahil Singla
We present a computationally-efficient truthful mechanism for combinatorial auctions with subadditive bidders that achieves an -approximation to the maximum w…
Knapsack Secretary with Bursty Adversary
Thomas Kesselheim, Marco Molinaro
The random-order or secretary model is one of the most popular beyond-worst case model for online algorithms. While it avoids the pessimism of the traditional adversarial model, in…
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 a…
How to Hire Secretaries with Stochastic Departures
Thomas Kesselheim, Alexandros Psomas, Shai Vardi
We study a generalization of the secretary problem, where decisions do not have to be made immediately upon candidates' arrivals. After arriving, each candidate stays in the system…