Research Topics
In algorithmic theory, our goal is to understand algorithms and the quality of the solutions they produce by using appropriate mathematical models and to show statements via rigorous proofs. A central theme in my research is to find out to what extent algorithms can solve optimization problems despite certain uncertainties or when this is impossible. I mostly focus on resource allocation problems. Concrete examples of such resources could be items in an online store, seats in airplanes, slots in online advertisement and the like. My aim is to abstract from these concrete examples and to understand the underlying principles. In this sense, we are dealing with abstract items, which are to be allocated among agents.
I focus on two types of uncertainty: (a) Decisions must be made continuously before the entire input is known. (b) It is private information from strategically acting agents. These two variants of uncertainty go hand in hand: In the case of strategic agents, it is common practice to approach them one after the other and make decisions sequentially. This way, it is much easier to set incentives appropriately.
Combinatorial Markets
One key application is combinatorial markets: In many realistic scenarios, there are complex relations between items that can be allocated to an agent. The items might be complements or substitutes. For example, when booking a hotel room, a traveler will usually only be interested in a reservation for a number of consecutive nights and not be satisfied for a shorter period of time. At the same time, they will not have additional value from multiple rooms for the same night.
Existence (and Computation) of Good Prices: Prophet Inequalities
A prevalent and particularly appealing way to coordinate such combinatorial markets is by setting prices. But is it enough to define a price for every item? Or can much better results be obtained by bundling items, maybe giving discounts for larger sets? And how can we compute good prices efficiently?
Selected Publications
- Simplified Prophet Inequalities for Combinatorial Auctions
Alexander Braun and Thomas Kesselheim
SOSA, 2023, 381–389
arXiv preprint
- Truthful Mechanisms for Two-Sided Markets via Prophet Inequalities
Alexander Braun and Thomas Kesselheim
EC, 2021, 202–203
arXiv preprint
- An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions
Paul Dütting, Thomas Kesselheim, and Brendan Lucier
FOCS, 2020, 306–317
arXiv preprint
- Prophet Secretary for Combinatorial Auctions and Matroids
Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla
SODA, 2018, 700–714
arXiv preprint
- Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs
Paul Duetting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier
FOCS, 2017, 540–551
arXiv preprint
Learning Prices
It is a standard assumption that probability distributions of buyer valuations are known when defining prices. Usually, one argues that one can infer this knowledge based on previous observations. However, how should we use previous observations? How many samples do we need? What happens if we are in repeated settings, where our observations to be used tomorrow are influenced by our decisions today?
Selected Publications
- Sample Complexity of Posted Pricing for a Single Item
Billy Jin, Thomas Kesselheim, Will Ma, and Sahil Singla
NeurIPS, 2024, to appear
arXiv preprint
- Online Combinatorial Allocations and Auctions with Few Samples
Paul Dütting, Thomas Kesselheim, Brendan Lucier, Rebecca Reiffenhäuser, and Sahil Singla
FOCS, 2024, to appear
arXiv preprint
- Bandit Algorithms for Prophet Inequality and Pandora’s Box
Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, and Yifan Wang
SODA, 2024, 462–500
arXiv preprint
- Posted Pricing and Prophet Inequalities with Inaccurate Priors
Paul Dütting and Thomas Kesselheim
EC, 2019, 111–129
Mechanism Design
In other, more complex settings, simply setting prices cannot lead to good outcomes. For these settings, we design mechanisms, which are still incentive compatible, meaning that agents have no advantage from strategically misreporting their valuations.
Selected Publications
- Truthful Mechanisms for Two-Sided Markets via Prophet Inequalities
Alexander Braun and Thomas Kesselheim
EC, 2021, 202–203
arXiv preprint
- Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier
Sepehr Assadi, Thomas Kesselheim, and Sahil Singla
SODA, 2021, 653–661
arXiv preprint
Decision Making under Uncertainty
In my research I also consider other problems of decision making under uncertainty beyond combinatorial markets. In the following, they are presented in three different clusters. However, there are very interesting and important connections between these clusters.
Online Algorithms for Norm Objectives
Consider the following typical load balancing problem appearing in scheduling: There are jobs that need to be assigned to machines processing the jobs. A typical objective is the makespan, which is the load of the highest loaded machine. We generalize this objective to arbitary norms and give algorithmic techniques for online algorithms, which assign these jobs one after the other.
Selected Publications
- Supermodular Approximation of Norms and Applications
Thomas Kesselheim, Marco Molinaro, and Sahil Singla
STOC, 2024, 1841–1852
arXiv preprint
- Online and Bandit Algorithms Beyond ℓp Norms
Thomas Kesselheim, Marco Molinaro, and Sahil Singla
SODA, 2023, 1566–1593
arXiv preprint
Random-Order Arrivals
A very interesting assumption to make is that the input to an online algorithm arrives in random order. That is, a hypothetical adversary can choose the optimization instance but not the order in which it is revealed. A prototypical example is the Secretary Problem, which has been studied for more than 50 years. More recently, we have extended this perspective to combinatorial settings and we have studied settings with weaker assumptions such as a random permutation that is not uniformly drawn. The interesting aspect is that one can try to infer from the observations what the future sequence will be like despite the fact that of course the exact same requests will not reappear.
Selected Publications
- Knapsack Secretary with Bursty Adversary
Thomas Kesselheim and Marco Molinaro
ICALP, 2020, 72:1–72:15
arXiv preprint
- How to Hire Secretaries with Stochastic Departures
Thomas Kesselheim, Alexandros Psomas, and Shai Vardi
WINE, 2019, 343
arXiv preprint
- Secretary Problems with Non-Uniform Arrival Order
Thomas Kesselheim, Robert D Kleinberg, and Rad Niazadeh
STOC, 2015, 879–888
arXiv preprint
- Primal beats dual on online packing LPs in the random-order model
Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking
STOC, 2014, 303–312
arXiv preprint
Online Learning/Bandit Algorithms
In online learning problems, one has to learn while making decisions. A particularly relevant case are bandit problems, in which one only gets to know how good the decisions were one actually made and not the alternatives. This leads to explore-exploit tradeoffs. In my research, I consider such problems with constraints across time steps (like in Bandits with Knapsacks) or with more complex stochastic optimization problems (like Pandora’s Box).
Selected Publications
- Bandit Algorithms for Prophet Inequality and Pandora’s Box
Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, and Yifan Wang
SODA, 2024, 462–500
arXiv preprint
- Online Learning with Vector Costs and Bandits with Knapsacks
Thomas Kesselheim and Sahil Singla
COLT, 2020, 2286–2305
arXiv preprint
Computing Optimal Contracts
Another related but different application scenario is to incentive agents to work. Again, one has to cope with the fact that certain information is private. Most importantly, my coauthors and I have studied settings of moral hazard, in which the actions chosen by agents cannot be observed directly. Therefore, one has to design (and compute) a contract, which ensures that it is in the agents’ individual best interest to take the actions the decision maker intends them to take.
Selected Publications
- Multi-Agent Combinatorial Contracts
Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim
SODA, 2025, to appear
arXiv preprint
- Multi-agent Contracts
Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim
STOC, 2023, 1311–1324
arXiv preprint
- Combinatorial Contracts
Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim
FOCS, 2021, 815–826
arXiv preprint