Multi-stages Stackelberg inspection games
| dc.contributor.advisor | Vera Andreo, Jorge | |
| dc.contributor.advisor | Guzmán Paredes, Cristóbal | |
| dc.contributor.author | Riffo Torres, Javiera Paz | |
| dc.contributor.other | Pontificia Universidad Católica de Chile. Escuela de Ingeniería | |
| dc.date.accessioned | 2020-10-23T15:42:00Z | |
| dc.date.available | 2020-10-23T15:42:00Z | |
| dc.date.issued | 2020 | |
| dc.description | Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2020 | |
| dc.description.abstract | Esta tesis estudia un juego de inspección multi-etapas líder-seguidor. En este juego, el líder es un inspector cuyas acciones son una secuencia ordenada de n nodos. Los seguidores en este juego son los nodos, cada uno de los cuales representa un operador. Al inicio del juego, el inspector se compromete a una inspección aleatoria de ruteo. Cada operador puede decidir en cualquier etapa si se prepara: si el operador se prepara, incurre en un costo independiente de la acción del inspector. Si no se prepara, incurre en un costo si el inspector lo visita. En este modelo, el objetivo del líder es maximizar la recaudación total de multas a través de las k etapas del juego. El concepto de solución que proponemos para abordar este problema es un equilibrio secuencial de Stackelberg fuerte. Esta solución se puede encontrar realizando inducción reversa. Como principales contribuciones de este trabajo, mostramos la equivalencia de la solución de inducción reversa con un programa lineal de tamaño O(n), para el caso de k = 2 etapas. Dicha reducción se alcanza mediante la aplicación del teorema de Ore en la existencia de f-factors on multi-grafos bipartitos. Los valores de las ganancias de los jugadores y la estrategia mixta del inspector se obtienen a través de un algoritmo glotón. Además, se lleva a cabo un modelo de equilibrio de Stackelberg fuerte para k etapas. Se concluye evaluando este modelo para un estudio de caso real asociado con una cadena de tiendas de restaurantes, cuyos indicadores productivos permiten entregar una ruta de visita para el inspector.Esta tesis estudia un juego de inspección multi-etapas líder-seguidor. En este juego, el líder es un inspector cuyas acciones son una secuencia ordenada de n nodos. Los seguidores en este juego son los nodos, cada uno de los cuales representa un operador. Al inicio del juego, el inspector se compromete a una inspección aleatoria de ruteo. Cada operador puede decidir en cualquier etapa si se prepara: si el operador se prepara, incurre en un costo independiente de la acción del inspector. Si no se prepara, incurre en un costo si el inspector lo visita. En este modelo, el objetivo del líder es maximizar la recaudación total de multas a través de las k etapas del juego. El concepto de solución que proponemos para abordar este problema es un equilibrio secuencial de Stackelberg fuerte. Esta solución se puede encontrar realizando inducción reversa. Como principales contribuciones de este trabajo, mostramos la equivalencia de la solución de inducción reversa con un programa lineal de tamaño O(n), para el caso de k = 2 etapas. Dicha reducción se alcanza mediante la aplicación del teorema de Ore en la existencia de f-factors on multi-grafos bipartitos. Los valores de las ganancias de los jugadores y la estrategia mixta del inspector se obtienen a través de un algoritmo glotón. Además, se lleva a cabo un modelo de equilibrio de Stackelberg fuerte para k etapas. Se concluye evaluando este modelo para un estudio de caso real asociado con una cadena de tiendas de restaurantes, cuyos indicadores productivos permiten entregar una ruta de visita para el inspector.Esta tesis estudia un juego de inspección multi-etapas líder-seguidor. En este juego, el líder es un inspector cuyas acciones son una secuencia ordenada de n nodos. Los seguidores en este juego son los nodos, cada uno de los cuales representa un operador. Al inicio del juego, el inspector se compromete a una inspección aleatoria de ruteo. Cada operador puede decidir en cualquier etapa si se prepara: si el operador se prepara, incurre en un costo independiente de la acción del inspector. Si no se prepara, incurre en un costo si el inspector lo visita. En este modelo, el objetivo del líder es maximizar la recaudación total de multas a través de las k etapas del juego. El concepto de solución que proponemos para abordar este problema es un equilibrio secuencial de Stackelberg fuerte. Esta solución se puede encontrar realizando inducción reversa. Como principales contribuciones de este trabajo, mostramos la equivalencia de la solución de inducción reversa con un programa lineal de tamaño O(n), para el caso de k = 2 etapas. Dicha reducción se alcanza mediante la aplicación del teorema de Ore en la existencia de f-factors on multi-grafos bipartitos. Los valores de las ganancias de los jugadores y la estrategia mixta del inspector se obtienen a través de un algoritmo glotón. Además, se lleva a cabo un modelo de equilibrio de Stackelberg fuerte para k etapas. Se concluye evaluando este modelo para un estudio de caso real asociado con una cadena de tiendas de restaurantes, cuyos indicadores productivos permiten entregar una ruta de visita para el inspector. | |
| dc.format.extent | x, 56 páginas | |
| dc.identifier.doi | 10.7764/tesisUC/ING/48097 | |
| dc.identifier.uri | https://doi.org/10.7764/tesisUC/ING/48097 | |
| dc.identifier.uri | https://repositorio.uc.cl/handle/11534/48097 | |
| dc.language.iso | en | |
| dc.nota.acceso | Contenido completo | |
| dc.rights | acceso abierto | |
| dc.subject.ddc | 519.7 | |
| dc.subject.dewey | Matemática física y química | es_ES |
| dc.subject.other | Programación (Matemáticas) | es_ES |
| dc.subject.other | Optimización matemática | es_ES |
| dc.title | Multi-stages Stackelberg inspection games | es_ES |
| dc.type | tesis de maestría | |
| sipa.codpersvinculados | 100240 | |
| sipa.codpersvinculados | 1041986 | |
| sipa.codpersvinculados | 232776 |