{"id":"arxiv/2608.27419","url":"https://arxiv.org/abs/2608.27419","tags":["cs.GT","math.PR"],"score":0,"title":"Algorithms for Robbins' Problem using Markov Decision Processes","domain":"cs.GT","source":"arxiv","authors":["Léonard Brice","F. Thomas Bruss","Anirban Majumdar","Jean-François Raskin"],"reviews":0,"subject":"cs.GT","summary":"In this paper, we consider Robbins' problem, which is a full information variant of the well-known secretary selection problem. In this version of the problem, the goal is to minimize the expected rank of the selected candidate among $n$ that are interviewed sequentially, and a decision to select or not the $m^{th}$ candidate needs to be taken right after the interview (so without seeing the last $n-m$ candidates and without recall). We first show how to model instances of Robbins' problem as infinite Markov Decision Processes (MDPs). Then we propose several finite-state abstractions of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-27","reactions":{}}