Metraipolis › archive › dc_73e9984516da
The Pareto Secretary Problem — arXiv:2610.42101
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.42101
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T08:19:52.082Z
- SHA-256 of the archived text
bc22c59c00b7b4aed73c584a836f792a606a40581e29e0b36355bc1dcb90e8b0- Stable URL of this page
https://metraipolis.com/documento/dc_73e9984516da
How to cite
The Pareto Secretary Problem — arXiv:2610.42101 — arXiv (en), https://arxiv.org/abs/2610.42101 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_73e9984516da (Metraipolis archive dc_73e9984516da, sha256 bc22c59c00b7b4aed73c584a836f792a606a40581e29e0b36355bc1dcb90e8b0)
BibTeX
@misc{dc73e9984516da,
title = {The Pareto Secretary Problem — arXiv:2610.42101},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.42101},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_73e9984516da; sha256 bc22c59c00b7b4aed73c584a836f792a606a40581e29e0b36355bc1dcb90e8b0},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.42101. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The Pareto secretary problem asks for online selection of a Pareto-maximal observation from an i.i.d. sample: no other observation is at least as good in every coordinate and strictly better in one. For every fixed dimension $d\ge2$ and independent continuous coordinates, the optimal failure probability is of order $1/[(\log n)^{d-1}\log\log n]$, both with full information and with coordinate ranks alone. A deterministic rank rule attains the optimal leading term uniformly over the marginals. For every fixed positive definite Gaussian covariance, the same failure order holds, with a leading constant depending on the correlation matrix, and a rank-based rule attains the optimal leading failure probability without knowing the Gaussian parameters. In both models, we determine the optimal fixed cutoff and its leading failure constant; its failure probability exceeds the unrestricted optimum by a factor $\Theta_d((\log\log n)^2)$. Under arbitrary dependence, a fixed joint density with uniform marginals can instead have optimal full-information success tending to approximately $0.58$. The proof uses the scarcity of observations with very small domination probability to bound every stopping rule. A matching rule selects a currently maximal point when this probability is below a threshold that increases as time runs out. Coordinate ranks from an initial sample provide sufficiently accurate estimates to preserve the optimal leading failure probability. For singular Gaussian distributions with known correlations, we characterize the optimal failure asymptotics attainable using ranks. Singular dependence can make every observation acceptable or recover the difficulty of selecting a single best point.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Information Theory (cs.IT) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.42101 — 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-11-03T08:05:38.788Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).