The Keychain Problem: On Minimizing the Opportunity Cost of Uncertainty
Ramiro N. Deo-Campo Vuong, Robert Kleinberg, Aditya Prasad, Eric Xiao, Haifeng Xu · 2025
Read The Keychain Problem: On Minimizing the Opportunity Cost of Uncertainty by Ramiro N. Deo-Campo Vuong, Robert Kleinberg, Aditya Prasad, Eric Xiao, Haifeng Xu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-06187.txt.
Introduction
A locksmith trying keys under uncertainty inspires a new family of decision problems in a 2025 paper led by Ramiro N. Deo-Campo Vuong with four co-authors. In the Keychain Problem, each round offers only a subset of keys, one might open the lock, and a Bayesian prior rates each key. The cost counted is opportunity cost: rounds where the right key was on the chain but a different one was chosen.
The authors compute Bayes-optimal play through reductions to matching theory. With a known chain order the problem becomes maximum weight bipartite matching; with a sampled order it becomes a new laminar matching problem, then a combinatorial auction problem. Letting the locksmith choose the order makes it hard in the NP sense. The reductions also feed results for online matching.
Catalog record
| CREATOR | Ramiro N. Deo-Campo Vuong, Robert Kleinberg, Aditya Prasad, Eric Xiao, Haifeng Xu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 157 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-06187