Refine
Document Type
- Article (2)
- Conference Proceeding (1)
- Contribution to a Periodical (1)
Has Fulltext
- yes (4)
Is part of the Bibliography
- no (4)
Keywords
- Algorithmic game theory (1)
- Approximation algorithms (1)
- Delegated search (1)
- Information design (1)
- Online algorithms (1)
- Principal-agent problem (1)
- Prophet Inequalities (1)
- Stochastic Probing (1)
- Testing (1)
- coupon collector problem (1)
Institute
- Informatik (4)
- Präsidium (1)
Die wahrscheinlich beste Entscheidung : wie Online-Algorithmen mit der unsicheren Zukunft rechnen
(2018)
Lohnt es sich, als Skianfänger in einem schneeunsicheren Jahr Skier zu kaufen? Oder ist es günstiger, sie zu mieten? Oft müssen wir Entscheidungen treffen, ohne genügend Informationen über die Zukunft zu haben. Das gilt in noch größerem Maße für Rechnersysteme, die große Datenmengen verarbeiten und schnelle Entscheidungen treffen müssen. Damit sie trotz einer Vielzahl von Unsicherheiten erfolgreich arbeiten können, entwickeln Informatiker OnlineAlgorithmen.
We study online secretary problems with returns in combinatorial packing domains with n candidates that arrive sequentially over time in random order. The goal is to determine a feasible packing of candidates of maximum total value. In the first variant, each candidate arrives exactly twice. All 2n arrivals occur in random order. We propose a simple 0.5‐competitive algorithm. For the online bipartite matching problem, we obtain an algorithm with ratio at least 0.5721 − o(1), and an algorithm with ratio at least 0.5459 for all n ≥ 1. We extend all algorithms and ratios to k ≥ 2 arrivals per candidate. In the second variant, there is a pool of undecided candidates. In each round, a random candidate from the pool arrives. Upon arrival a candidate can be either decided (accept/reject) or postponed. We focus on minimizing the expected number of postponements when computing an optimal solution. An expected number of Θ(n log n) is always sufficient. For bipartite matching, we can show a tight bound of O(r log n), where r is the size of the optimum matching. For matroids, we can improve this further to a tight bound of O(r′ log(n/r′)), where r′ is the minimum rank of the matroid and the dual matroid.
We study threshold testing, an elementary probing model with the goal to choose a large value out of n i.i.d. random variables. An algorithm can test each variable X_i once for some threshold t_i, and the test returns binary feedback whether X_i ≥ t_i or not. Thresholds can be chosen adaptively or non-adaptively by the algorithm. Given the results for the tests of each variable, we then select the variable with highest conditional expectation. We compare the expected value obtained by the testing algorithm with expected maximum of the variables. Threshold testing is a semi-online variant of the gambler’s problem and prophet inequalities. Indeed, the optimal performance of non-adaptive algorithms for threshold testing is governed by the standard i.i.d. prophet inequality of approximately 0.745 + o(1) as n → ∞. We show how adaptive algorithms can significantly improve upon this ratio. Our adaptive testing strategy guarantees a competitive ratio of at least 0.869 - o(1). Moreover, we show that there are distributions that admit only a constant ratio c < 1, even when n → ∞. Finally, when each box can be tested multiple times (with n tests in total), we design an algorithm that achieves a ratio of 1 - o(1).
Delegated online search
(2024)
In a delegation problem, a principal P with commitment power tries to pick one out of 𝑛 options. Each option is drawn independently from a known distribution. Instead of inspecting the options herself, P delegates the information acquisition to a rational and self-interested agent A. After inspection, A proposes one of the options, and P can accept or reject. Delegation is a classic setting in economic information design with many prominent applications, but the computational problems are only poorly understood. In this paper, we study a natural online variant of delegation, in which the agent searches through the options in an online fashion. For each option, he has to irrevocably decide if he wants to propose the current option or discard it, before seeing information on the next option(s). How can we design algorithms for P that approximate the utility of her best option in hindsight? We show that in general P can obtain a Θ(1∕𝑛)-approximation and extend this result to ratios of Θ(𝑘∕𝑛) in case (1) A has a lookahead of 𝑘 rounds, or (2) A can propose up to 𝑘 different options. We provide fine-grained bounds independent of 𝑛 based on three parameters. If the ratio of maximum and minimum utility for A is bounded by a factor 𝛼, we obtain an Ω(loglog 𝛼∕ log 𝛼)- approximation algorithm, and we show that this is best possible. Additionally, if P cannot distinguish options with the same value for herself, we show that ratios polynomial in 1∕𝛼 cannot be avoided. If there are at most 𝛽 different utility values for A, we show a Θ(1∕𝛽)-approximation. If the utilities of P and A for each option are related by a factor 𝛾, we obtain an Ω(1∕ log 𝛾)- approximation, where 𝑂(log log 𝛾∕ log 𝛾) is best possible.