# 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