Mostrar el registro sencillo del ítem

Profesor guíadc.contributor.advisorSoto San Martín, José
Autordc.contributor.authorValdevenito Werner, Felipe Andrés
Profesor colaboradordc.contributor.otherKiwi Krauskopf, Marcos
Profesor colaboradordc.contributor.otherVerdugo Silva, Víctor
Fecha ingresodc.date.accessioned2024-04-30T21:04:39Z
Fecha disponibledc.date.available2024-04-30T21:04:39Z
Fecha de publicacióndc.date.issued2023
Identificadordc.identifier.other10.58011/xmgc-qr44
Identificadordc.identifier.urihttps://repositorio.uchile.cl/handle/2250/198349
Resumendc.description.abstractExaminamos 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.es_ES
Patrocinadordc.description.sponsorshipCMM ANID BASAL FB210005, FONDECYT REGULAR 1181180 y FONDECYT REGULAR 1231669es_ES
Idiomadc.language.isoeses_ES
Publicadordc.publisherUniversidad de Chilees_ES
Tipo de licenciadc.rightsAttribution-NonCommercial-NoDerivs 3.0 United States*
Link a Licenciadc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/us/*
Títulodc.titleProblema de la secretaria simple y matroidal con consejos ordinaleses_ES
Tipo de documentodc.typeTesises_ES
dc.description.versiondc.description.versionVersión original del autores_ES
dcterms.accessRightsdcterms.accessRightsAcceso abiertoes_ES
Catalogadoruchile.catalogadorgmmes_ES
Departamentouchile.departamentoDepartamento de Ingeniería Matemáticaes_ES
Facultaduchile.facultadFacultad de Ciencias Físicas y Matemáticases_ES
uchile.titulacionuchile.titulacionDoble Titulaciónes_ES
uchile.carrerauchile.carreraIngeniería Civil Matemáticaes_ES
uchile.gradoacademicouchile.gradoacademicoMagisteres_ES
uchile.notadetesisuchile.notadetesisTesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadases_ES
uchile.notadetesisuchile.notadetesisMemoria para optar al título de Ingeniero Civil Matemático


Descargar archivo

Icon

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem

Attribution-NonCommercial-NoDerivs 3.0 United States
Excepto si se señala otra cosa, la licencia del ítem se describe como Attribution-NonCommercial-NoDerivs 3.0 United States