3 Search Results for "Schoepflin, Daniel"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.86
The Secretary Problem with Predictions and a Chosen Order

Authors: Helia Karisani, Mohammadreza Daneshvaramoli, Hedyeh Beyhaghi, Mohammad Hajiesmaili, and Cameron Musco

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study a learning-augmented variant of the secretary problem, recently introduced by Fujii and Yoshida (2023). In this variant, the decision-maker has access to machine-learned predictions of candidate values in advance. The key challenge is to balance consistency and robustness: when the predictions are accurate, the algorithm should hire a near-best secretary; however, if they are inaccurate, the algorithm should still achieve a bounded competitive ratio. We consider both the standard Random Order Secretary Problem (ROSP), where candidates arrive in a uniform random order, and a more natural model in the learning-augmented setting, where the decision-maker can choose the arrival order based on the predicted candidate values. This model, which we call the Chosen Order Secretary Problem (COSP), can capture scenarios such as an interview schedule that is set by the decision-maker. We propose a novel algorithm that applies to both ROSP and COSP. Building on the approach of Fujii and Yoshida, our method switches from fully trusting predictions to a threshold-based rule when a large deviation of a prediction is observed. Importantly, unlike the algorithm of Fujii and Yoshida, our algorithm uses randomization as part of its decision logic. We show that if ε ∈ [0,1] denotes the maximum multiplicative prediction error, then for ROSP our algorithm achieves competitive ratio max {0.221, (1-ε)/(1+ε)}, improving on a previous bound of max {0.215, (1-ε)/(1+ε)} due to Fujii and Yoshida [Fujii and Yoshida, 2023]. For COSP, our algorithm achieves max {0.262, (1-ε)/(1+ε)}. This surpasses a 0.25 upper bound on the worst-case competitive ratio that applies to the approach of Fujii and Yoshida, and gets closer to the classical secretary benchmark of 1/e ≈ 0.368, which is an upper bound for any algorithm. Our result for COSP highlights the benefit of integrating predictions with arrival-order control in online decision-making.
Cite as

Helia Karisani, Mohammadreza Daneshvaramoli, Hedyeh Beyhaghi, Mohammad Hajiesmaili, and Cameron Musco. The Secretary Problem with Predictions and a Chosen Order. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 86:1-86:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{karisani_et_al:LIPIcs.ITCS.2026.86,
  author =	{Karisani, Helia and Daneshvaramoli, Mohammadreza and Beyhaghi, Hedyeh and Hajiesmaili, Mohammad and Musco, Cameron},
  title =	{{The Secretary Problem with Predictions and a Chosen Order}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{86:1--86:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.86},
  URN =		{urn:nbn:de:0030-drops-253734},
  doi =		{10.4230/LIPIcs.ITCS.2026.86},
  annote =	{Keywords: Secretary problem, learning-augmented algorithms, online algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.52
Combinatorial Pen Testing (Or Consumer Surplus of Deferred-Acceptance Auctions)

Authors: Aadityan Ganesh and Jason Hartline

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
Pen testing is the problem of selecting high-capacity resources when the only way to measure the capacity of a resource expends its capacity. We have a set of n pens with unknown amounts of ink and our goal is to select a feasible subset of pens maximizing the total ink in them. We are allowed to learn about the ink levels by writing with them, but this uses up ink that was previously in the pens. We identify optimal and near optimal pen testing algorithms by drawing analogues to auction theoretic frameworks of deferred-acceptance auctions and virtual values. Our framework allows the conversion of any near optimal deferred-acceptance mechanism into a near optimal pen testing algorithm. Moreover, these algorithms guarantee an additional overhead of at most (1+o(1)) ln n in the approximation factor to the omniscient algorithm that has access to the ink levels in the pens. We use this framework to give pen testing algorithms for various combinatorial constraints like matroid, knapsack, and general downward-closed constraints, and also for online environments.
Cite as

Aadityan Ganesh and Jason Hartline. Combinatorial Pen Testing (Or Consumer Surplus of Deferred-Acceptance Auctions). In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 52:1-52:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ganesh_et_al:LIPIcs.ITCS.2025.52,
  author =	{Ganesh, Aadityan and Hartline, Jason},
  title =	{{Combinatorial Pen Testing (Or Consumer Surplus of Deferred-Acceptance Auctions)}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{52:1--52:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.52},
  URN =		{urn:nbn:de:0030-drops-226808},
  doi =		{10.4230/LIPIcs.ITCS.2025.52},
  annote =	{Keywords: Pen testing, consumer surplus, money-burning, deferred-acceptance auctions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.49
Optimal Deterministic Clock Auctions and Beyond

Authors: Giorgos Christodoulou, Vasilis Gkatzelis, and Daniel Schoepflin

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We design and analyze deterministic and randomized clock auctions for single-parameter domains with downward-closed feasibility constraints, aiming to maximize the social welfare. Clock auctions have been shown to satisfy a list of compelling incentive properties making them a very practical solution for real-world applications, partly because they require very little reasoning from the participating bidders. However, the first results regarding the worst-case performance of deterministic clock auctions from a welfare maximization perspective indicated that they face obstacles even for a seemingly very simple family of instances, leading to a logarithmic inapproximability result; this inapproximability result is information-theoretic and holds even if the auction has unbounded computational power. In this paper we propose a deterministic clock auction that achieves a logarithmic approximation for any downward-closed set system, using black box access to a solver for the underlying optimization problem. This proves that our clock auction is optimal and that the aforementioned family of instances exactly captures the information limitations of deterministic clock auctions. We then move beyond deterministic auctions and design randomized clock auctions that achieve improved approximation guarantees for a generalization of this family of instances, suggesting that the earlier indications regarding the performance of clock auctions may have been overly pessimistic.
Cite as

Giorgos Christodoulou, Vasilis Gkatzelis, and Daniel Schoepflin. Optimal Deterministic Clock Auctions and Beyond. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 49:1-49:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.ITCS.2022.49,
  author =	{Christodoulou, Giorgos and Gkatzelis, Vasilis and Schoepflin, Daniel},
  title =	{{Optimal Deterministic Clock Auctions and Beyond}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{49:1--49:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.49},
  URN =		{urn:nbn:de:0030-drops-156453},
  doi =		{10.4230/LIPIcs.ITCS.2022.49},
  annote =	{Keywords: Auctions, Obvious Strategyproofness, Mechanism Design}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 1 2022

  • Refine by Author
  • 1 Beyhaghi, Hedyeh
  • 1 Christodoulou, Giorgos
  • 1 Daneshvaramoli, Mohammadreza
  • 1 Ganesh, Aadityan
  • 1 Gkatzelis, Vasilis
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Computational pricing and auctions
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Online algorithms
  • Show More...

  • Refine by Keyword
  • 1 Auctions
  • 1 Mechanism Design
  • 1 Obvious Strategyproofness
  • 1 Pen testing
  • 1 Secretary problem
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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