Resultados en el modelo Prophet Secretary y modelos relacionados

Abstract

En el modelo Prophet Secretary Matching con agentes, consideramos un hiper-grafo G = (V, E), d´onde las hiper-aristas son de orden a lo m´as k, con k un entero positivo. Un conjunto finito de agentes se presentan uno a uno en orden uniformemente aleatorio y un algoritmo asigna, ya sea una ´unica arista de E, o bien, ninguna arista, a cada agente, en el momento en que este se presenta. El conjunto de aristas asignadas a agentes debe formar un matching en G. Al momento de presentarse, cada agente revela para cada arista de E un valor(real positivo) asociado a esta, provenientes de una distribuci´on de probabilidad sobre todas las valuaciones posibles de aristas. Con esto, el algoritmo busca hacer asignaciones tal que la suma de valores que cada agente da a la arista que le fue asignada sea lo m´as grande posible. Una de las dificultades del problema recae en el hecho de que, al inicio del proceso, el algoritmo solo conoce la distribuci´on de probabilidad de cada agente,y su valuaci´on efectiva de las aristas solo es revelada en el momento en que este se presenta. En esta memoria nos enfocamos en estudiar cotas superiores sobre la competitividad m´axima que puede tener cualquier algoritmo bajo distintas condiciones sobre G. El primer caso que estudiamos es para G general y mostramos una cota superior O(log(k) k ) para todo algoritmo. El segundo es cu´ando G posee un solo elemento. En este caso presentamos un nuevo m´etodo para calcular cotas superiores, que llamamos “m´etodo continuo”, y lo utilizamos para obtener 2 cotas superiores ya conocidas. Por ´ultimo presentamos un nuevo modelo que llamamos “modelo no-show” en el que cada agente tiene una probabilidad de no presentarse nunca al proceso, y establecemos cotas superiores en este modelo para k = 1 y k = 2.