Problema de la secretaria simple y matroidal con consejos ordinales

Abstract

Examinamos variaciones del Problema de la Secretaria Simple (con una sola selecci´on) y del Problema de la Secretaria Matroidal en un nuevo escenario, en el cual el tomador de decisiones (el jugador) puede solicitar uno (o m´as) bits de informaci´on ordinal de los candidatos antes de que lleguen. Espec´ıficamente, cada candidato tiene informaci´on privada (su “peso”) que es revelada al momento que el candidato llega. Como es usual, el jugador debe decidir irrevocablemente si seleccionar al candidato o no despu´es de este paso. Adicionalmente, consideramos modelos en los que el jugador puede realizar preguntas ordinales binarias a los candidatos que a´un no han llegado, y los candidatos pueden responder bas´andose solo en su propia informaci´on privada m´as la informaci´on p´ublicamente disponible hasta el momento. Llamamos a esta informaci´on adicional consejo ordinal. Por ejemplo, el jugador puede preguntar a cada candidato que a´un no llega si su peso oculto es mayor que todos los pesos de candidatos que ya han llegado, pero no le puede preguntar si su peso es el mayor de la lista completa. En la versi´on del problema con ´unica selecci´on, el objetivo es seleccionar al candidato de mayor peso de la lista. Consideramos diferentes maneras en que los candidatos llegan, tales como en orden aleatorio, en orden adversarial, o con una muestra aleatoria de candidatos que se revelan de antemano. En el ´ultimo caso, el jugador decide la cantidad de candidatos incluidos en la muestra, y el resto de los candidatos llegan en un orden elegido por un adversario ya sea antes o despu´es de la realizaci´on de la muestra. Exploramos el impacto de variar la cantidad de consejos ordinales que se pueden solicitar, considerando los casos en que se puede consultar cero, una o ilimitadas veces. Presentamos algoritmos que alcanzan competitividades ´optimas para casi todos los escenarios considerados. Finalmente, investigamos la versi´on matroidal del problema, en la cual los candidatos son elementos de una matroide conocida, y el jugador solo puede seleccionar elementos incrementalmente tal que se forme un conjunto independiente de la matroide. Notablemente, probamos que incluso una sola ronda de consejos ordinales es suficiente para alcanzar competitividades constantes (independientes del rango de la matroide) si se dispone de una muestra aleatoria. Tambi´en presentamos algoritmos con competitividades ´optimas para varios de los escenarios presentados.