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

CREATORRamiro N. Deo-Campo Vuong, Robert Kleinberg, Aditya Prasad, Eric Xiao, Haifeng Xu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE157 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-06187

Browse the full library · About the Tower of Babel