Metraipolis › archive › dc_113be62dcedf

Secretary Problems with Interactive Ordinal Queries — arXiv:2609.19016

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.19016
License (as archived): CC0-1.0
Archived: 2026-10-15T17:09:23.807Z
SHA-256 of the archived text: be1792ecb8aca25b1a43cf06581a07fafa22bbc679756703eec33477ee7b2c18
Stable URL of this page: https://metraipolis.com/documento/dc_113be62dcedf

How to cite

Secretary Problems with Interactive Ordinal Queries — arXiv:2609.19016 — arXiv (en), https://arxiv.org/abs/2609.19016 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_113be62dcedf (Metraipolis archive dc_113be62dcedf, sha256 be1792ecb8aca25b1a43cf06581a07fafa22bbc679756703eec33477ee7b2c18)

BibTeX

@misc{dc113be62dcedf,
  title = {Secretary Problems with Interactive Ordinal Queries — arXiv:2609.19016},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.19016},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_113be62dcedf; sha256 be1792ecb8aca25b1a43cf06581a07fafa22bbc679756703eec33477ee7b2c18},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19016. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study secretary problems in which the online algorithm can ask a reliable oracle a limited number of ordinal queries about unseen elements. Values are revealed only when elements arrive, and all accept/reject decisions are irrevocable. The oracle never reveals numerical values; it only answers questions defined relative to the information already observed by the algorithm. We first consider the single-choice secretary problem. A query returns the number of unseen elements whose value exceeds the current record. We analyze random order, adversarial order, and two sample-based adversarial orders, with no queries, one query, and unlimited queries. We obtain tight bounds for all variants except one. In adversarial order, queries do not improve over the trivial $1/n$ guarantee. In random order, one query improves the optimal success probability from $1/e$ to $0.4477\ldots$, and unlimited queries achieve the optimal value $1/2$. In the sample-based models, one query already yields the tight value $1/e$ against an online adversary, while unlimited queries give the exact value $(20\sqrt{10}-29)/81$ against an offline adversary. The remaining one-query offline-adversarial case is left open, and we give two partial upper bounds for it. We also extend the model to the matroid secretary problem, where we study two ordinal query interfaces. A simple query identifies the unseen elements that would individually improve the current optimum on the observed set, while a complete query gives a finer ordinal partition of the unseen elements by weight relative to that optimum. Under sample-based online adversarial order, a single simple query yields a $1/4$ probability-competitive algorithm, and a complete query improves this to the optimal $1/e$. Finally, with unlimited complete queries in the random-order model, we achieve the optimal $1/2$ probability-competitive ratio.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.19016 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T16:17:15.276Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).