Dublin Core
Title
Multi-stages Stackelberg inspection games
Subject
519.7
Matemática física y química
Programación (Matemáticas)
Optimización matemática
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2020
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.
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.
Creator
Riffo Torres, Javiera Paz
Date
2020-10-23T15:42:00Z
2020-10-23T15:42:00Z
2020
Contributor
Vera Andreo, Jorge
Guzmán Paredes, Cristóbal
Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Rights
acceso abierto
Format
x, 56 páginas
application/pdf
Language
en
Type
tesis de maestría
Identifier
10.7764/tesisUC/ING/48097
https://doi.org/10.7764/tesisUC/ING/48097
https://repositorio.uc.cl/handle/11534/48097