The Pareto Secretary Problem
Abstract
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≥2 and independent continuous coordinates, the optimal failure probability is of order 1/[(log n)d−1loglog 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 Θd((loglog 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.
Related
- Asymptotic Rounding Laws for Optimal Thresholds in Secretary Problems
- New Pareto Z-eigenvalue localization theorems for tensors with applications
- Pareto optimality under nondegeneracy at infinity
- Convergence-Aware Pareto Selection of Covariate Scaling Transformations for Markov Deterioration Hazard Models: Evidence from Bridge Inspection Data
- Full asymptotics for the parabolic Anderson model with Pareto potential in the heaviest-tailed regime
BibTeX
@misc{cristi2026pareto,
title = {{The Pareto Secretary Problem}},
author = {Andrés Cristi and Yilin Kong and Jiechen Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.42101},
eprint = {2610.42101},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.42101},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Pareto Secretary Problem
AU - Andrés Cristi
AU - Yilin Kong
AU - Jiechen Zhang
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.42101
UR - https://arxiv.org/abs/2610.42101
AB - 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≥2 and independent continuous coordinates, the optimal failure probability is of order 1/[(log n)^d−1loglog 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 Θ_d((loglog 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.
ER -