Research map / Learning theory and algorithms / Prediction and decision losses
Addressing Bias in Online Selection with Limited Budget of Comparisons
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies the secretary problem with K groups where in-group comparisons are free and cross-group comparisons cost 1 from a budget B, proposing dynamic-threshold algorithms with asymptotic analysis and an optimal memory-less algorithm for two groups.
Problem
Online selection (secretary problem) when candidates are partitioned into groups that can only be compared within group for free, and cross-group comparisons are available only at a limited budget of costly comparisons.
Approach
Extends the multicolor secretary problem by allowing a fixed budget of costly inter-group comparisons; uses dynamic-threshold algorithms whose acceptance thresholds depend on group and remaining budget, showing a single threshold achieves near 1/e success with modest budget, and computing optimal thresholds for two groups via dynamic programming.
Key results
- Single-threshold algorithm with threshold N/e and budget B has asymptotic success probability at least (1/e)(1-(K-1)^{B+1}/(B+1)!), converging rapidly to 1/e as B grows.
- For two groups, the static double-threshold algorithm with optimized thresholds achieves success probability at least 1/e - min{1/(e(B+1)!), (4/e-1)λ(1-λ)}.
- The optimal memory-less algorithm for two groups behaves as a dynamic-threshold algorithm for large N, with thresholds computed numerically; for B=0, alpha*_0 = λexp(1/λ-2) and beta*_0 = λ.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the comparison budget B for the single-threshold algorithm | Single-threshold algorithm with threshold ⌊N/e⌋ · (K,B)-secretary problem, N → ∞ | success probability: ≥ \frac{1}{e}\left(1 - \frac{(K-1)^{B+1}}{(B+1)!} \right); converges to 1/e as B increases | Helped |
| Use different acceptance thresholds for the two groups instead of a single threshold | Two-group secretary algorithm · Two-group secretary problem, λ close to 0 or 1 | success probability | Helped |
| Use optimal DT thresholds instead of the optimal memory-less algorithm's actions | Two-group secretary algorithm · Two-group secretary problem, large N | success probability | No clear effect |
| Use the single-threshold algorithm with threshold ⌊N/e⌋ | K-group secretary problem · (K,B)-secretary problem, N → ∞ | success probability: ≥ \frac{1}{e}\left(1 - \frac{(K-1)^{B+1}}{(B+1)!} \right) | Mixed |
| Use a majority-group-only 1/e rule when one group has proportion close to 1 | K-group secretary problem · K-group secretary problem, λ_max close to 1 | success probability: \max_{k \in [K]} \lambda_k /e | Helped |
Surprising findings
- The asymptotic success probability of the single-threshold algorithm depends only on the number of groups K, not on group proportions λ_k.
Experimental setup
Metrics: success probability
Baselines: classical 1/e threshold rule multicolor secretary problem without comparisons static double-threshold algorithm
Builds on: multicolor secretary problem classical 1/e secretary rule
Closest papers by meaning
- Matchings Under Biased and Correlated Evaluations (NeurIPS 2025 · similarity 0.83)
- Centralized Selection with Preferences in the Presence of Biases (ICML 2024 · similarity 0.83)
- A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding (NeurIPS 2025 · similarity 0.82)
- Two Tickets are Better than One: Fair and Accurate Hiring Under Strategic LLM Manipulations (ICML 2025 · similarity 0.82)
- Monoculture in Matching Markets (NeurIPS 2024 · similarity 0.81)
- Online Budgeted Matching with General Bids (NeurIPS 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.