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