Multi-stages Stackelberg inspection games
Loading...
Date
2020
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2020