Search Results

Documents authored by Kesselheim, Thomas

Document
DOI: 10.4230/LIPIcs.ESA.2021.22
Asymptotically Optimal Welfare of Posted Pricing for Multiple Items with MHR Distributions

Authors: Alexander Braun, Matthias Buttkus, and Thomas Kesselheim

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We consider the problem of posting prices for unit-demand buyers if all n buyers have identically distributed valuations drawn from a distribution with monotone hazard rate. We show that even with multiple items asymptotically optimal welfare can be guaranteed. Our main results apply to the case that either a buyer’s value for different items are independent or that they are perfectly correlated. We give mechanisms using dynamic prices that obtain a 1 - Θ (1/(log n))-fraction of the optimal social welfare in expectation. Furthermore, we devise mechanisms that only use static item prices and are 1 - Θ ((log log log n)/(log n))-competitive compared to the optimal social welfare. As we show, both guarantees are asymptotically optimal, even for a single item and exponential distributions.
Cite as

Alexander Braun, Matthias Buttkus, and Thomas Kesselheim. Asymptotically Optimal Welfare of Posted Pricing for Multiple Items with MHR Distributions. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{braun_et_al:LIPIcs.ESA.2021.22,
  author =	{Braun, Alexander and Buttkus, Matthias and Kesselheim, Thomas},
  title =	{{Asymptotically Optimal Welfare of Posted Pricing for Multiple Items with MHR Distributions}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.22},
  URN =		{urn:nbn:de:0030-drops-146038},
  doi =		{10.4230/LIPIcs.ESA.2021.22},
  annote =	{Keywords: Prophet Inequalities, Monotone Hazard Rate, Competitive Analysis, Posted Prices, Combinatorial Auctions, Matching}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.72
Knapsack Secretary with Bursty Adversary

Authors: Thomas Kesselheim and Marco Molinaro

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
The random-order or secretary model is one of the most popular beyond-worst case model for online algorithms. While this model avoids the pessimism of the traditional adversarial model, in practice we cannot expect the input to be presented in perfectly random order. This has motivated research on best of both worlds (algorithms with good performance on both purely stochastic and purely adversarial inputs), or even better, on inputs that are a mix of both stochastic and adversarial parts. Unfortunately the latter seems much harder to achieve and very few results of this type are known. Towards advancing our understanding of designing such robust algorithms, we propose a random-order model with bursts of adversarial time steps. The assumption of burstiness of unexpected patterns is reasonable in many contexts, since changes (e.g. spike in a demand for a good) are often triggered by a common external event. We then consider the Knapsack Secretary problem in this model: there is a knapsack of size k (e.g., available quantity of a good), and in each of the n time steps an item comes with its value and size in [0,1] and the algorithm needs to make an irrevocable decision whether to accept or reject the item. We design an algorithm that gives an approximation of 1 - Õ(Γ/k) when the adversarial time steps can be covered by Γ ≥ √k intervals of size Õ(n/k). In particular, setting Γ = √k gives a (1 - O((ln² k)/√k))-approximation that is resistant to up to a (ln k)/√k-fraction of the items being adversarial, which is almost optimal even in the absence of adversarial items. Also, setting Γ = Ω̃(k) gives a constant approximation that is resistant to up to a constant fraction of items being adversarial. While the algorithm is a simple "primal" one it does not possess the crucial symmetry properties exploited in the traditional analyses. The strategy of our analysis is more robust and significantly different from previous ones, and we hope it can be useful for other beyond-worst-case models.
Cite as

Thomas Kesselheim and Marco Molinaro. Knapsack Secretary with Bursty Adversary. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 72:1-72:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kesselheim_et_al:LIPIcs.ICALP.2020.72,
  author =	{Kesselheim, Thomas and Molinaro, Marco},
  title =	{{Knapsack Secretary with Bursty Adversary}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{72:1--72:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.72},
  URN =		{urn:nbn:de:0030-drops-124798},
  doi =		{10.4230/LIPIcs.ICALP.2020.72},
  annote =	{Keywords: Beyond worst-case, secretary problem, random order, online algorithms, knapsack}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.155
Price of Anarchy for Mechanisms with Risk-Averse Agents

Authors: Thomas Kesselheim and Bojana Kodric

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We study the price of anarchy of mechanisms in the presence of risk-averse agents. Previous work has focused on agents with quasilinear utilities, possibly with a budget. Our model subsumes this as a special case but also captures that agents might be less sensitive to payments than in the risk-neutral model. We show that many positive price-of-anarchy results proved in the smoothness framework continue to hold in the more general risk-averse setting. A sufficient condition is that agents can never end up with negative quasilinear utility after playing an undominated strategy. This is true, e.g., for first-price and second-price auctions. For all-pay auctions, similar results do not hold: We show that there are Bayes-Nash equilibria with arbitrarily bad social welfare compared to the optimum.
Cite as

Thomas Kesselheim and Bojana Kodric. Price of Anarchy for Mechanisms with Risk-Averse Agents. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 155:1-155:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kesselheim_et_al:LIPIcs.ICALP.2018.155,
  author =	{Kesselheim, Thomas and Kodric, Bojana},
  title =	{{Price of Anarchy for Mechanisms with Risk-Averse Agents}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{155:1--155:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.155},
  URN =		{urn:nbn:de:0030-drops-91599},
  doi =		{10.4230/LIPIcs.ICALP.2018.155},
  annote =	{Keywords: Mechanism Design, Price of Anarchy, Risk Aversion, Smoothness}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.16
Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints

Authors: Thomas Kesselheim and Andreas Tönnis

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
We study various generalizations of the secretary problem with submodular objective functions. Generally, a set of requests is revealed step-by-step to an algorithm in random order. For each request, one option has to be selected so as to maximize a monotone submodular function while ensuring feasibility. For our results, we assume that we are given an offline algorithm computing an alpha-approximation for the respective problem. This way, we separate computational limitations from the ones due to the online nature. When only focusing on the online aspect, we can assume alpha = 1. In the submodular secretary problem, feasibility constraints are cardinality constraints, or equivalently, sets are feasible if and only if they are independent sets of a k-uniform matroid. That is, out of a randomly ordered stream of entities, one has to select a subset of size k. For this problem, we present a 0.31alpha-competitive algorithm for all k, which asymptotically reaches competitive ratio alpha/e for large k. In submodular secretary matching, one side of a bipartite graph is revealed online. Upon arrival, each node has to be matched permanently to an offline node or discarded irrevocably. We give a 0.207alpha-competitive algorithm. This also covers the problem, in which sets of entities are feasible if and only if they are independent with respect to a transversal matroid. In both cases, we improve over previously best known competitive ratios, using a generalization of the algorithm for the classic secretary problem. Furthermore, we give an O(alpha d^(-2/(B-1)))-competitive algorithm for submodular function maximization subject to linear packing constraints. Here, d is the column sparsity, that is the maximal number of none-zero entries in a column of the constraint matrix, and B is the minimal capacity of the constraints. Notably, this bound is independent of the total number of constraints. We improve the algorithm to be O(alpha d^(-1/(B-1)))-competitive if both d and B are known to the algorithm beforehand.
Cite as

Thomas Kesselheim and Andreas Tönnis. Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kesselheim_et_al:LIPIcs.APPROX-RANDOM.2017.16,
  author =	{Kesselheim, Thomas and T\"{o}nnis, Andreas},
  title =	{{Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{16:1--16:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.16},
  URN =		{urn:nbn:de:0030-drops-75657},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.16},
  annote =	{Keywords: Secretary Problem, Online Algorithms, Submodular Maximization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.54
Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions

Authors: Thomas Kesselheim and Andreas Tönnis

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
The Temp Secretary Problem was recently introduced by [Fiat et al., ESA 2015]. It is a generalization of the Secretary Problem, in which commitments are temporary for a fixed duration. We present a simple online algorithm with improved performance guarantees for cases already considered by [Fiat et al., ESA 2015] and give competitive ratios for new generalizations of the problem. In the classical setting, where candidates have identical contract durations gamma << 1 and we are allowed to hire up to B candidates simultaneously, our algorithm is (1/2) - O(sqrt{gamma})-competitive. For large B, the bound improves to 1 - O(1/sqrt{B}) - O(sqrt{gamma}). Furthermore we generalize the problem from cardinality constraints towards general packing constraints. We achieve a competitive ratio of 1 - O(sqrt{(1+log(d) + log(B))/B}) - O(sqrt{gamma}), where d is the sparsity of the constraint matrix and B is generalized to the capacity ratio of linear constraints. Additionally we extend the problem towards arbitrary hiring durations. Our algorithmic approach is a relaxation that aggregates all temporal constraints into a non-temporal constraint. Then we apply a linear scaling algorithm that, on every arrival, computes a tentative solution on the input that is known up to this point. This tentative solution uses the non-temporal, relaxed constraints scaled down linearly by the amount of time that has already passed.
Cite as

Thomas Kesselheim and Andreas Tönnis. Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kesselheim_et_al:LIPIcs.ESA.2016.54,
  author =	{Kesselheim, Thomas and T\"{o}nnis, Andreas},
  title =	{{Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{54:1--54:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.54},
  URN =		{urn:nbn:de:0030-drops-63966},
  doi =		{10.4230/LIPIcs.ESA.2016.54},
  annote =	{Keywords: Secretary Problem, Online Algorithms, Scheduling Problems}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact