Arrow Research search

Author name cluster

Thomas Kesselheim

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers
2 author rows

Possible papers

19

FOCS Conference 2025 Conference Paper

Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives

  • Thomas Kesselheim
  • Marco Molinaro 0001
  • Kalen Patton
  • Sahil Singla 0001

Online Set Cover and Load Balancing are central problems in online optimization, and there is a long line of work focusing on developing algorithms for these problems with convex objectives. Although we know optimal online algorithms with $\ell_{p}$-norm objectives, recent developments for general norms and convex objectives that rely on the online primal-dual framework apply only to fractional settings due to large integrality gaps. Our work focuses on directly designing integral online algorithms for Set Cover and Load Balancing with convex objectives, bypassing the convex-relaxation and the primal-dual technique. Some of the main implications of our approach are: 1) For Online Set Cover, we can extend the results of [1] for convex objectives and of [2] for symmetric norms from fractional to integral settings. 2) Our results for convex objectives and symmetric norms even apply to the Online Generalized Scheduling Problem, which generalizes both Set Cover and Load Balancing. Previous works could only handle the offline version of this problem with norm objectives [3]. 3) Our approach easily extends to settings involving disjointcomposition of norms. This allows us to recover or improve the norm-composition results of [4], [2] and extend our results to a large class of norms beyond the symmetric setting. Our approach involves first reducing these online problems to online packing problems, and to then design good approximation algorithms for the latter. To solve these packing problem, we use two key ideas. First, we decouple the global packing problem into a series of local packing problems on different machines. Second, we choose random activation thresholds for machines such that conditional on a machine being activated the expected number of jobs it covers is high compared to its cost. This approach may be of independent interest and could find applications to other online problems. Index Terms-online algorithms, set cover, load balancing

Details

FOCS Conference 2024 Conference Paper

Online Combinatorial Allocations and Auctions with Few Samples

  • Paul Dütting
  • Thomas Kesselheim
  • Brendan Lucier
  • Rebecca Reiffenhäuser
  • Sahil Singla 0001

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 aim is to immediately allocate a subset of the remaining items to maximize the total welfare, defined as the sum of bidder valuations. A long line of work has studied this problem when the bidder valuations come from known independent distributions. In particular, for submodular/XOS valuations, we know 2-competitive algorithms/mechanisms that set a fixed price for each item and the arriving bidders take their favorite subset of the remaining items given these prices. However, these algorithms traditionally presume the availability of the underlying distributions as part of the input to the algorithm. Contrary to this assumption, practical scenarios often require the learning of distributions, a task complicated by limited sample availability. This paper investigates the feasibility of achieving $O$ (1) -competitive algorithms under the realistic constraint of having access to only a limited number of samples from the underlying bidder distributions. Our first main contribution shows that a mere single sample from each bidder distribution is sufficient to yield an $O$ (1)-competitive algorithm for submodular/XOS valuations. This result leverages a novel extension of the secretary-style analysis, employing the sample to have the algorithm compete against itself. Although online, this first approach does not provide an online truthful mechanism. Our second main contribution shows that a polynomial number of samples suffices to yield a (2 + ∊) -competitive online truthful mechanism for submodular/XOS valuations and any constant ∊ > 0. This result is based on a generalization of the median-based algorithm for the single-item prophet inequality problem to combinatorial settings with multiple items.

Details

NeurIPS Conference 2024 Conference Paper

Sample Complexity of Posted Pricing for a Single Item

  • Billy Jin
  • Thomas Kesselheim
  • Will Ma
  • Sahil Singla

Selling a single item to $n$ self-interested bidders is a fundamental problem in economics, where the two objectives typically considered are welfare maximization and revenue maximization. Since the optimal auctions are often impractical and do not work for sequential bidders, posted pricing auctions, where fixed prices are set for the item for different bidders, have emerged as a practical and effective alternative. This paper investigates how many samples are needed from bidders' value distributions to find near-optimal posted prices, considering both independent and correlated bidder distributions, and welfare versus revenue maximization. We obtain matching upper and lower bounds (up to logarithmic terms) on the sample complexity for all these settings.

PDF Details DOI

STOC Conference 2024 Conference Paper

Supermodular Approximation of Norms and Applications

  • Thomas Kesselheim
  • Marco Molinaro 0001
  • Sahil Singla 0001

Many classical problems in theoretical computer science involve norms, even if implicitly; for example, both XOS functions and downward-closed sets are equivalent to some norms. The last decade has seen a lot of interest in designing algorithms beyond the standard ℓ p norms ||· || p . Despite notable advancements, many existing methods remain tailored to specific problems, leaving a broader applicability to general norms less understood. This paper investigates the intrinsic properties of ℓ p norms that facilitate their widespread use and seeks to abstract these qualities to a more general setting. We identify supermodularity —often reserved for combinatorial set functions and characterized by monotone gradients—as a defining feature beneficial for ||·|| p p . We introduce the notion of p -supermodularity for norms, asserting that a norm is p -supermodular if its p th power function exhibits supermodularity. The association of supermodularity with norms offers a new lens through which to view and construct algorithms. Our work demonstrates that for a large class of problems p -supermodularity is a sufficient criterion for developing good algorithms. This is either by reframing existing algorithms for problems like Online Load-Balancing and Bandits with Knapsacks through a supermodular lens, or by introducing novel analyses for problems such as Online Covering, Online Packing, and Stochastic Probing. Moreover, we prove that every symmetric norm can be approximated by a p -supermodular norm. Together, these recover and extend several existing results, and support p -supermodularity as a unified theoretical framework for optimization challenges centered around norm-related problems.

Details

STOC Conference 2023 Conference Paper

Multi-agent Contracts

  • Paul Dütting
  • Tomer Ezra
  • Michal Feldman
  • Thomas Kesselheim

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 heart of our model is a reward function , which maps the agent efforts to an expected reward of the principal. We seek to design computationally efficient algorithms for finding optimal (or near-optimal) linear contracts for reward functions that belong to the complement-free hierarchy. Our first main result gives constant-factor approximation algorithms for submodular and XOS reward functions, with value and demand oracles, respectively. It relies on an unconventional use of “prices” and (approximate) demand queries for selecting the set of agents that the principal should contract with, and exploits a novel scaling property of XOS functions and their marginals, which may be of independent interest. Our second main result is an Ω(√ n ) impossibility for settings with n agents and subadditive reward functions, even with demand oracle access. A striking feature of this impossibility is that it applies to subadditive functions that are constant-factor close to submodular. This presents a surprising departure from previous literature, e.g., on combinatorial auctions.

Details

FOCS Conference 2021 Conference Paper

Combinatorial Contracts

  • Paul Dütting
  • Tomer Ezra
  • Michal Feldman
  • Thomas Kesselheim

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 of a given set of unobservable actions, each of which has an associated cost. The cost of a set of actions is the sum of the costs of the individual actions, and the principal's reward as a function of the chosen actions satisfies some form of diminishing returns. The principal incentivizes the agents through a contract, based on the observed outcome. Our main results are for the case where the task delegated to the agent is a project, which can be successful or not. We show that if the success probability as a function of the set of actions is gross substitutes, then an optimal contract can be computed with polynomially many value queries, whereas if it is submodular, the optimal contract is NP-hard. All our results extend to linear contracts for higher-dimensional outcome spaces, which we show to be robustly optimal given first moment constraints. Our analysis uncovers a new property of gross substitutes functions, and reveals many interesting connections between combinatorial contracts and combinatorial auctions, where gross substitutes is known to be the frontier for efficient computation.

Details

SODA Conference 2021 Conference Paper

Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier

  • Sepehr Assadi
  • Thomas Kesselheim
  • Sahil Singla 0001

We present a computationally-efficient truthful mechanism for combinatorial auctions with subadditive bidders that achieves an O ((loglog m ) 3 )-approximation to the maximum welfare in expectation using O ( n ) demand queries; here m and n are the number of items and bidders, respectively. This breaks the longstanding logarithmic barrier for the problem dating back to the O (log m · loglog m )-approximation mechanism of Dobzinski from 2007. Along the way, we also improve and considerably simplify the state-of-the-art mechanisms for submodular bidders.

Details

FOCS Conference 2020 Conference Paper

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 alternative to classic worst-case competitive analysis, of particular importance in the design and analysis of simple (posted-price) incentive compatible mechanisms with provable approximation guarantees. A central open problem in this area concerns subadditive combinatorial auctions. Here n agents with subadditive valuation functions compete for the assignment of m items. The goal is to find an allocation of the items that maximizes the total value of the assignment. The question is whether there exists a prophet inequality for this problem that significantly beats the best known approximation factor of O(log m). We make major progress on this question by providing an O(log log m) prophet inequality. Our proof goes through a novel primal-dual approach. It is also constructive, resulting in an online policy that takes the form of static and anonymous item prices that can be computed in polynomial time given appropriate query access to the valuations. As an application of our approach, we construct a simple and incentive compatible mechanism based on posted prices that achieves an O(log log m) approximation to the optimal revenue for subadditive valuations under an item-independence assumption.

Details

SODA Conference 2018 Conference Paper

Prophet Secretary for Combinatorial Auctions and Matroids

  • Soheil Ehsani
  • MohammadTaghi Hajiaghayi
  • Thomas Kesselheim
  • Sahil Singla 0001

The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions (extends bipartite matching). Kleinberg-Weinberg [33] and Feldman et al. [17] show that for adversarial arrival order of random variables the optimal prophet inequalities give a 1/2-approximation. For many settings, however, it's conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the 1/2-approximation and obtain (1 – 1/ e )-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan [45] and Esfandiari et al. [15] who worked in the special cases where we can fully control the arrival order or when there is only a single item. Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.

Details

SODA Conference 2017 Conference Paper

Best-Response Dynamics in Combinatorial Auctions with Item Bidding

  • Paul Dütting
  • Thomas Kesselheim

In a combinatorial auction with item bidding, agents participate in multiple single-item second-price auctions at once. As some items might be substitutes, agents need to strate- gize in order to maximize their utilities. A number of results indicate that high welfare can be achieved this way, giving bounds on the welfare at equilibrium. Recently, however, criticism has been raised that equilibria are hard to compute and therefore unlikely to be attained. In this paper, we take a different perspective. We study simple best-response dynamics. That is, agents are activated one after the other and each activated agent updates his strategy myopically to a best response against the other agents’ current strategies. Often these dynamics may take exponentially long before they converge or they may not converge at all. However, as we show, convergence is not even necessary for good welfare guarantees. Given that agents’ bid updates are aggressive enough but not too aggressive, the game will remain in states of good welfare after each agent has updated his bid at least once. In more detail, we show that if agents have fractionally subadditive valuations, natural dynamics reach and remain in a state that provides a 1/3 approximation to the optimal welfare after each agent has updated his bid at least once. For subadditive valuations, we can guarantee an Ω(1/log m ) approximation in case of m items that applies after each agent has updated his bid at least once and at any point after that. The latter bound is complemented by a negative result, showing that no kind of best-response dynamics can guarantee more than a an o (log log m / log m ) fraction of the optimal social welfare.

Details

FOCS Conference 2017 Conference Paper

Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs

  • Paul Dütting
  • Michal Feldman
  • Thomas Kesselheim
  • Brendan Lucier

We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The framework establishes prophet inequalities by constructing price-based online approximation algorithms, a natural extension of threshold algorithms for settings beyond binary selection. Our analysis takes the form of an extension theorem: we derive sufficient conditions on prices when all weights are known in advance, then prove that the resulting approximation guarantees extend directly to stochastic settings. Our framework unifies and simplifies much of the existing literature on prophet inequalities and posted price mechanisms, and is used to derive new and improved results for combinatorial markets (with and without complements), multi-dimensional matroids, and sparse packing problems. Finally, we highlight a surprising connection between the smoothness framework for bounding the price of anarchy of mechanisms and our framework, and show that many smooth mechanisms can be recast as posted price mechanisms with comparable performance guarantees.

Details

STOC Conference 2014 Conference Paper

Primal beats dual on online packing LPs in the random-order model

  • Thomas Kesselheim
  • Klaus Radke
  • Andreas Tönnis
  • Berthold Vöcking

We study packing LPs in an online model where the columns are presented to the algorithm in random order. This natural problem was investigated in various recent studies motivated, e.g., by online ad allocations and yield management where rows correspond to resources and columns to requests specifying demands for resources. Our main contribution is a 1 -- O (√(log d/B))-competitive online algorithm. Here d denotes the column sparsity , i.e., the maximum number of resources that occur in a single column, and B denotes the capacity ratio B , i.e., the ratio between the capacity of a resource and the maximum demand for this resource. In other words, we achieve a (1--ε)-approximation if the capacity ratio satisfies B=Ω(logd/ε 2 ), which is known to be best-possible for any (randomized) online algorithms. Our result improves exponentially on previous work with respect to the capacity ratio. In contrast to existing results on packing LP problems, our algorithm does not use dual prices to guide the allocation of resources over time. Instead, the algorithm simply solves, for each request, a scaled version of the partially known primal program and randomly rounds the obtained fractional solution to obtain an integral allocation for this request. We show that this simple algorithmic technique is not restricted to packing LPs with large capacity ratio of order Ω(log d ), but it also yields close-to-optimal competitive ratios if the capacity ratio is bounded by a constant. In particular, we prove an upper bound on the competitive ratio of Ω( d --1/( B --1) ), for any B ≥ 2. In addition, we show that our approach can be combined with VCG payments and obtain an incentive compatible (1 -- ε)-competitive mechanism for packing LPs with B = Ω(log m /ε; 2 ), where m is the number of constraints. Finally, we apply our technique to the generalized assignment problem for which we obtain the first online algorithm with competitive ratio O (1).

Details

SODA Conference 2011 Conference Paper

A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control in the SINR Model

  • Thomas Kesselheim

In modern wireless networks devices are able to set the power for each transmission carried out. Experimental but also theoretical results indicate that such power control can improve the network capacity significantly. We study this problem in the physical interference model using SINR constraints. In the SINR capacity maximization problem, we are given n pairs of senders and receivers, located in a metric space (usually a so-called fading metric). The algorithm shall select a subset of these pairs and choose a power level for each of them with the objective of maximizing the number of simultaneous communications. This is, the selected pairs have to satisfy the SINR constraints with respect to the chosen powers. We present the first algorithm achieving a constant-factor approximation in fading metrics. The best previous results depend on further network parameters such as the ratio of the maximum and the minimum distance between a sender and its receiver. Expressed only in terms of n, they are (trivial) Ω( n ) approximations. Our algorithm still achieves an O (log n ) approximation if we only assume to have a general metric space rather than a fading metric. Furthermore, existing approaches work well together with the algorithm allowing it to be used in single-hop and multi-hop scheduling scenarios. Here, we also get polylog n approximations.

Details