Academic literature on the topic 'Juego de Stackelberg'

<p align="center"><strong>ABSTRACT</strong><strong></strong></p><p>This paper investigates the selection of the bargaining agenda in a unionized industry with decentralized negotiations for different competition modes. The firms choose the agenda (right-to-manage, RTM, <em>versus</em> efficient bargaining, EB), considering alternative timing of the bargaining game in the case of mixed duopoly. In fact, the EB (RTM) firm can be either Stackelberg wage follower (leader) or Stackelberg output leader (follower). A two-stage game is developed in which the typology as well as the timing of the negotiations is endogenous. It is shown that, in pure strategies, no equilibria arise for a wide set of the parameters’ space while RTM appears as the unique equilibrium agenda for a different combination of the parameters; moreover, multiple, asymmetric equilibria emerge in a limited area of the parameters’ space. These results are in sharp contrast to the received literature in which EB can arise as an industry bargaining institution in equilibrium.</p><p align="center"> </p><p align="center">UN ENFOQUE DE TEORÍA DE JUEGOS PARA LA SELECCIÓN DE LA AGENDA DE NEGOCIACIÓN DEL OLIGOPOLIO SINDICAL</p><p align="center"><strong> </strong><strong>RESUMEN</strong></p>Este artículo investiga la selección de la agenda de negociación en una industria sindicalizada con negociaciones descentralizadas para diferentes modos de competencia. Las empresas eligen la agenda (negociación con derecho de administrar, NDA, frente a negociación eficiente, NE) considerando casos alternativos de la sucesión de eventos en el juego de negociación con duopolio mixto. De hecho, la empresa NE (NDA) puede ser seguidora de salarios Stackelberg (líder) o líder de cantidades Stackelberg (seguidora). Se desarrolla un juego de dos etapas en el que la tipología y el momento de las negociaciones son endógenos. Se muestra que en estrategias puras no surgen equilibrios para un amplio conjunto del espacio de los parámetros, mientras que NDA aparece como la agenda de equilibrio única para una combinación diferente de los parámetros; además, los equilibrios múltiples y asimétricos emergen en un área limitada del espacio de los parámetros. Estos resultados contrastan con la literatura existente, en la que NE puede surgir como una institución de negociación de la industria en equilibrio.

Esta investigación analiza, estima y compara modelos microeconométricos de interacción estratégica aplicados a la oferta laboral de los hogares en México. En tanto que la posibilidad de decisiones descentralizadas al interior del hogar proporciona el ímpetu para un marco de teoría de juegos, los modelos estimados se basan en el supuesto de que las variables observadas representan el resultado de un juego discreto estático. Los modelos son estimados con datos de la Encuesta Nacional sobre Niveles de Vida de los Hogares 2002 (ENNViH). La estimación por máxima verosimilitud, basada en los conceptos de equilibrio no cooperativo de Nash y Stackelberg, se probó factible y los resultados producidos son plausibles. Los principales resultados sugieren la dependencia recíproca de las decisiones individuales al interior del hogar.

Los modelos de competencia de Stackelberg agrupan a una gran familia de problemas de decisión económicos provenientes de la Teoría de Juego, en los que el objetivo principal es encontrar las estrategias óptimas entre un par de competidores teniendo en cuenta una jerarquía entre ellos. Aunque estos modelos han sido abordados ampliamente a lo largo de los últimos años, es importante destacar que muy pocos trabajos tratan escenarios con incertidumbre, especialmente aquellos que varían en el tiempo. En este sentido, la presente investigación aborda estos escenarios y propone un método computacional basado en técnicas metaheurísticas que resuelve de manera eficiente modelos de competencia de Stackelberg dinámicos. Los experimentos computacionales desarrollados sugieren que el enfoque propuesto resulta efectivo para problemas de esta naturaleza.

El objetivo de este artículo consiste en modelar las estrategias utilizadas por las Afore para retener el mayor número de afiliados con diferentes rangos de ingreso en un esquema de competencia por costos. Para tal efecto simulamos un juego estático no cooperativo de dos etapas, en el que se formaliza la competencia establecida por las M ≥ 1 administradoras líderes y las N seguidoras en un equilibrio generalizado de Nash-Cournot-Stackelberg (EGNCS). Los resultados indican que: i) la competencia entre las Afore es heterogénea por segmentos de salarios; ii) mientras que en rangos intermedios de salarios el EGNCS es adecuado para explicar el comportamiento de las Afore, en los rangos extremos la conjetura más razonable es que los agentes actúan como competidores por precios —salarios bajos— o como oligopolistas con un liderazgo no basado en cantidades y precios —salarios altos—, y iii) no es posible asegurar que, en una estructura de competencia como la que prevalece en las Afore, un mayor número de competidores redunde siempre en un mayor beneficio para los afiliados

Los modelos de Juegos de Stackelberg engloban una importante familia de problemas de la Teoría de Juegos, que encuentra aplicaciones directas en economía. El principal objetivo es encontrar un equilibrio óptimo entre las decisiones que pueden tomar dos actores que se relacionan jerárquicamente. En general estos modelos son complejos de resolver dada su estructura jerárquica, y la frecuente aparición en estos de funciones objetivos o restricciones intratables analíticamente. Otra causa de dicha complejidad es la existencia de incertidumbre, particularmente debido a la variabilidad en el tiempo de las condiciones del mercado, estrategias de los competidores, entre otras. Un análisis de la literatura relacionada muestra muy pocos trabajos abordando estos problemas de optimización no estacionarios. En este sentido, la presente investigación propone una técnica meta-heurística auto-adaptativa para resolver modelos de Juegos de Stackelberg no estacionarios. Los resultados experimentales obtenidos muestran una mejoría significativa sobre un método existente.

Magíster en Gestión de Operaciones<br>El objetivo principal de este trabajo es proporcionar un algoritmo que resuelve instancias de gran tamaño para problemas de juegos de seguridad de Stackelberg con un énfasis en reducir el número de recursos necesarios requeridos para calcular dicha solución. Para ello se utilizan los principios de generación de columnas para desarrollar un algoritmo que procede mediante la resolución de un problema más pequeño (menor número de restricciones). Entonces, de forma iterativa, añadimos restricciones hasta que el problema llega a las condiciones de parada definidas. Básicamente, partimos de un problema secundario del original con dos jugadores que juegan a la seguridad y cuentan con un espacio de estrategia limitado, ya que este considera sólo un número limitado de restricciones. Iterativamente, verificamos si algún jugador le gustaría cambiar su estrategia con el fin de incrementar sus utilidades, añadimos la estrategia candidata y resolvemos una vez más. Esto sugiere un método de descomposición que es capaz de estimar el conjunto mínimo de restricciones a tener en cuenta con el fin de encontrar también la solución óptima para el problema global. En el transcurso de nuestros estudios identificamos que el proceso de iteración no siempre encuentra la solución óptima para el problema global. Luego, proporcionamos un análisis y caracterización de la estructura de las funciones de utilidad para ambos jugadores con el fín comprender más la dinámica de los jugadores e identificar las situaciones en las que la solución óptima global efectivamente es encontrada. Más tarde, se presenta una implementación que incluye datos del mundo real a través de una red en el centro de Santiago, Chile. Las recompensas se calcularon teniendo en cuenta el promedio histórico robado en cada lugar y un valor estimado de la falta de voluntad de ir a la cárcel para efectos de los asaltantes. Finalmente, comparamos nuestro algoritmo con los demás ya la literatura en escenarios similares. Mostramos que nuestros métodos nos permiten ofrecer de manera eficiente soluciones razonables para los problemas de seguridad en tamaño del mundo real. Además comparamos nuestros resultados con los resultados utilizando la metodología estándar de resolución de problemas lineales y mostramos que se pueden reducir ampliamente la necesidad de recursos computacionales y en algunos casos, el tiempo de ejecución para llegar a la solución.

Doctor en Sistemas de Ingeniería<br>En esta tesis presentamos contribuciones algorítmicas y de modelación para Juegos de Stackelberg para problemas de gran tamaño. Juegos de Stackelberg es un tipo de juego en el que un jugador, llamado líder, utiliza una estrategia y luego el otro jugador, llamado seguidor, observa esta estrategia y juega una mejor respuesta. En el contexto de seguridad, el lider se le denomina defensor, y al seguidor se le denomina atacante. En el Capítulo 1, presentamos una situación en donde el defensor tiene que emparejar recursos para poder desarrollar labores de patrullaje. En este caso, el conjunto de estrategias puras es de tamaño exponencial. Presentamos una formulación en programación lineal entera mixta con un número polinomial de variables y un número exponencial de restricciones que pueden ser separadas en tiempo polinomial. Además, se diseñó un método de sampleo para recuperar estrategias implementables para el defensor. Por otra parte, mostramos un caso de estudio basado en el patrullaje fronterizo de Carabineros de Chile. Finalmente mostramos que nuestro modelo con el generación de cortes funciona considerablemente mejor que cualquier modelo en la literatura. En el Capítulo 2, se muestra una manera de escalar un algoritmo basado en Aprendizaje de M\'aquinas, realizando multiples capas de clusters de territorios en donde en cada cluster el algoritmo resuelve en tiempos razonables. En el Capítulo 3 se realiza un estudio sobre existencia de estrategias estacionarias que formen equilibrios de estrategias fuertes. Se detecta una familia de instancias en las cuales algoritmos de programación dinámica pueden encuentran el único equilibrio de Stackelberg fuerte. En este caso, se demuestra que Iteración de políticas y de valores convergen a los únicos valores de equilibrio. Se muestra vía contraejemplo que no siempre programación dinámica puede encontrar equilibrios de Stackelberg en estrategias estacionarias. Computacionalmente se encuentra que la estructura de juegos de seguridad presentara características que hace aplicable la teoría de operadores para encontrar equilibrios de Stackelberg. Finalmente se estudian formulaciones basadas en programación matemática para calcular equilibrios de Stackelberg. Finalmente, en el Capítulo 4 mostramos un juego dinámico, en donde un agente central tiene como objetivo la sobreexplotación de agua en el contexto agrícola, controlando los costos marginales de extracción que enfrentan los agricultores. Modelamos esta situación como un juego estocástico en donde se busca un equilibrio de Stackelberg en donde el líder es la agencia central, y los seguidores son los agricultores. Computacionalmente se encuentra que se pueden alcanzar mejores niveles de agua en el estado estacionario controlando los costos marginales a través de las tasas de descuento del líder, aunque los agricultures sean miopes. Finalmente, nosotros proponemos una formulación de programación robusta para incluir incertidumbre en nuestros modelos.<br>Este trabajo ha sido parcialmente financiado por CONICYT

Magíster en Gestión de Operaciones<br>Uno de los desafíos importantes que enfrenta un grupo de defensores corresponde a su coordinación con el objetivo de poder brindar una mayor protección al sistema que defienden. En este trabajo, se estudia el desarrollo de algoritmos eficientes y garantías de optimalidad para un modelo de juego de seguridad de Stackelberg que resuelve la coordinación de múltiples recursos defensivos descentralizados. Este modelo asume la presencia de incertidumbre en las acciones efectuadas por cada recurso defensor y la ausencia de comunicación entre ellos. En específico, el modelo de juego de seguridad de este trabajo consiste en resolver un número pequeño de problemas de programación lineal, que se pueden resolver mediante un esquema de generación de columnas. El subproblema de dicha generación de columnas corresponde a la resolución de un problema de decisión markoviana descentralizado. Estos problemas de decisión markoviana descentralizados son de difícil solución; sin embargo, es posible resolver estos subproblemas mediante heurísticas, dando como resultado un enfoque capaz de obtener soluciones subóptimas para el modelo de juego de seguridad. Se presentan diversas heurísticas para la resolución de dicho subproblema, y se realiza un estudio para evaluar su uso dentro del esquema de generación de columnas. Este estudio consiste en la simulación de instancias de prueba aleatorias para evaluar el desempeño, tanto en el valor del resultado obtenido como en el tiempo de resolución de cada heurística. Se presenta una cota para el valor óptimo de un problema de decisión markoviana descentralizado que se obtiene al resolver un problema de optimización entero relacionado. Nuestros estudios computacionales muestran que esta cota es menor a un 10% del valor óptimo. Se presentan además, variantes del enfoque de generación de columnas, buscando reducir los tiempos de solución sin sacrificar calidad de la respuesta. Estos enfoques también están basados en generación de columnas y otorgan una solución subóptima al problema planteado. Con el objetivo de evaluar el comportamiento de los enfoques presentados, se recurre a la simulación de instancias aleatorias y una instancia inspirada en parte de la red de metro de Santiago. Además, con el objetivo de poder evaluar las soluciones subóptimas otorgadas por dichos enfoques, se desarrolla un método que permite obtener garantías para la solución del problema de generación de columnas. En específico, el algoritmo desarrollado permite resolver el problema de patrullar descentralizadamente una red conformada por 16 estaciones de metro, durante 12 períodos de tiempo y utilizando 6 recursos. Esta solución se obtiene, en promedio, en un tiempo de 400 [s] y con una garantía del 20%.<br>Este trabajo ha sido parcialmente financiado por CONICYT-PCHA/Magíster Nacional/2015 - 22152053 Powered@NLHPC: Esta investigación fue parcialmente apoyada por la infraestructura de supercómputo del NLHPC (ECM-02)

Magíster en Gestión de Operaciones<br>Las agencias de seguridad alrededor del mundo enfrentan el reto de proteger objetivos sensibles, tales como aeropuertos, puertos u otras infraestructuras críticas. Para ello, toman acciones preventivas y asignan recursos de defensa a patrullar un objetivo. El problema es que, por lo general, los recursos a su disposición son limitados y la cantidad de objetivos a defender puede llegar a ser muy grande, por lo que la labor de asignación de recursos puede llegar a ser muy compleja y costosa en términos computacionales. Para enfrentar este problema, un enfoque es utilizar técnicas de teoría de juegos para captar el razonamiento entre el defensor y los atacantes o criminales, específicamente se usan los Juegos de Seguridad de Stackelberg, ó SSG por sus siglas en inglés. Los SSGs son parte esencial de varias aplicaciones actualmente en uso por diversas agencias de seguridad en Estados Unidos y su éxito ha generado que el interés por estos aumente, por lo que muchos autores han dado diversas contribuciones sobre este tema. Sin embargo, uno de los puntos que aún es un tema abierto de estudio es la escalabilidad de las formulaciones, ya que los modelos existentes tienen un bajo desempeño cuando el número de tipos de atacantes es grande, lo que resulta inadecuado para problemas complejos del mundo real. Una instancia cualquiera de SSG tiene muchas posibles formulaciones, este trabajo de tesis estudia tres: (SSMG), (DOBSS-SSG) y (MIP-SSG). Estas formulaciones son equivalentes entre sí, que tienen diferencias en términos de tamaño y fortaleza, lo que hace que no sea evidente cúal es la de mejor desempeño, pero todas resuelven el problema, en ámbitos con múltiples tipos de atacantes, aprovechando la estructura propia de los juegos de seguridad donde la utilidad de los jugadores depende solamente de si el objetivo atacado esta protegido o no, logrando de esta manera una representación compacta y acelerando los tiempos de ejecución. Este trabajo describe y analiza cada una de estas formulaciones comparándolas tanto desde el punto de vista de modelación como computacional. En el aspecto de modelación se muestra el efecto de incorporar una representación logarítmica de las las variables enteras y el efecto de restringir el espacio de soluciones. En el aspecto computacional, el enfoque esta en el rendimiento, en términos del tiempo de ejecución requerido para hallar una solución, sobre un conjunto amplio de instancias, poniendo énfasis en escalar tanto el número de tipos de atacantes como el número de objetivos a defender. Se compara las formulaciones entre sí y se detalla las ventajas de estas sobre las formulaciones presentes en la literatura.

Ingeniero Civil Industrial<br>Ingeniero Civil Mecánico<br>Muchas empresas poseen numerosos equipos mecánicos que son ocupados en sus procesos productivos, donde el mantenimiento de ellos es realizado por equipos de técnicos propios llevando también los costos y la derivación de las capacidades y habilidades. Otras firmas, consideran la estrategia de externalizar ciertos procesos, relacionados o no, con el negocio que está abocada la empresa, delegando a terceras entidades la realización de estas. La externalización es normada por medio de contratos que clarifican deberes y obligaciones de las partes. En Chile la externalización u outsourcing en mantenimiento de activos fijos es una de las actividades estratégicas más recurridas, además de ser una de las mejor evaluadas (Menéndez [11]). Las fallas de los equipos son hechos aleatorios por lo que no pueden ser previstos y que afectan la producción de la empresa. Estas son modeladas probabilísticamente en relación a la política de mantenimiento, aquí mantenimiento perfecto. El tiempo en que los equipos están no operativos siendo intervenidos también afectan la producción. Desde la perspectiva del proveedor del servicio juegan a favor la cantidad de intervenciones correctivas y preventivas que realice, marginalizando por cada una de ellas, juega en contra, por concepto de multa, el tiempo excesivo en que los equipos no son devueltos operativos al cliente. Estas constituyen los beneficios para el cliente y desutilidad para el proveedor. En esta memoria se determinarán los precios que caracterizan a los contratos, tanto de la intervención preventiva como de la correctiva. Esto se logrará mediante la teoría de juegos como un problema principal-agente, donde el principal es el cliente, con alto poder de negociación y el proveedor será el agente con escaso poder en relación a una estrategia, sea esta: mantenimiento correctivo, preventivo (intervención por edad y por bloque de tiempo).

The present doctoral thesis has been realized in accordance with the research line of Economy and Regulation in Telecommunications under the doctoral programme in Telecommunications of Universitat Politècnica de València. It has been developed on the basis of various research projects, especially the "Cooperation and Opportunity for Wireless Heterogeneous Networks Project" (TIN2010-21378-C02-02), which acted as my funding agent and the "S2EuNet-Security Project" . Mobile communications have undergone notable growth from their beginning up to the present day regarding devices and bandwidth available. Service providers have now to take the challenge of such increase. New technologies are being implemented to address the challenge and all of them belong to the world of mobile communications. This thesis will focus on the solutions provided by heterogeneous nets (HetNets) and, more speci¿cally, we will look at the Small Cells technology. It is starting to be widely deployed lately and allows for a visible increase in network capacity and a resulting enhancement in availability and coverage on the user side. Abundant research has proved that the integration of these technologies within markets is technically feasible. A marketing model is however still necessary which is able to prove its economic viability. A business model was laid out where a provider sets out to deploy small cells technology and stands as an incumbent service provider. The Theory of Games was used for the analysis of such models as it allows an insight of the decisions in equilibrium when entering into a competition among themselves and try the decisions of users need to be predicted. In this way we will manage to know the effect of such decisions over the pro¿ts of all the agents in the model. A clear picture will be thus obtained of the advantages of the implementation of the new technology in the market as well as of its effects over the incumbent service providers. This thesis intends to be a contribution towards the implementation of new technologies in the market of mobile technologies through the analysis of the competence between new service providers of Small Cells and an incumbent service providers along with the behaviour of the users of mobile communications. The result show that: users get a better service, the SSP pro¿ts are guaranteed and the entrance of the SSP improves the user comfort and social welfare.<br>Esta tesis se ha creado en el marco de la línea de investigación de Economía y Regulación de las Telecomunicaciones del programa de doctorado de Telecomunicaciones de la Universitat Politècnica de València, y se ha desarrollado en diferentes proyectos de investigación, en especial, el proyecto de "Cooperación yOportunismo enRedesde Acceso Inalámbricas y Heterogéneas" (TIN2010-21378-C02-02) y el proyecto S2EuNet-Security (FP7PEOPLE-2009- IRSES, 247083). Desde sus inicios las comunicaciones móviles han experimentado un gran crecimiento, tanto de dispositivos móviles como de cantidad de ancho de banda demandado, lo que ha provocado que los proveedores se encuentren con el desafío de hacer frente a este crecimiento. Para ello, se están implementando diferentes técnicas y tecnologías que se integran con el modeloactualdecomunicacionesmóviles.Enestatesisnoscentraremosenla solución que aportan las redes heterogéneas, especialmente en la tecnología de Small cells que se desplegado rápidamente en los últimos años y permite incrementar la capacidad de la red, así como obtener mejor disponibilidad y cobertura para los usuarios, pero falta un modelo de negocio claro donde se muestre su viabilidad económica. En esta tesis se plantea un modelo de negocio para un proveedor de servicio que despliega small cells y que compite como el proveedor de servicios incumbente. Para el análisis de este modelo se ha utilizado la Teoría de Juegos la cual ha permitido conocer las decisiones en equilibrio que toman los proveedores de servicio cuando compiten entre sí, así como las decisiones en equilibrio de los usuarios; de esta manera se ha obtenido el efecto de estas decisiones sobre los bene¿cios de todos los agentes del modelo y se han identi¿cado las ventajas y los inconvenientes que tiene la implementación de una nueva tecnología en el mercado. Esta tesis pretende ser una contribución al estudio de implementación de nuevas tecnologías en el mercado de comunicaciones móviles, más concretamente planteando modelos económicos que estudien su viabilidad a través del análisis de la competencia entre un nuevo proveedor se servicio de Small cells y el proveedor de servicio existente, y el comportamiento de los usuarios de comunicaciones móviles. Los resultados obtenidos muestran que los usuarios obtienen una mejor utilidad , el SSP siempre tiene unos bene¿cios garantizados, el MSP se ve obligado a competir y sus bene¿cios se ven perjudicados, además que la entrada del SSP mejora el bienestar de los usuarios y el bienestar social.<br>Aquesta tesi s'ha creat en el marc de la línia de recerca d'Economia i Regulació de les Telecomunicacions del programa de doctorat de Telecomunicacions de la Universitat Politècnica de València, i s'ha desenvolupat en diferents projectes de recerca, especialment, el projecte de Çooperació i Oportunisme en Xarxes d'Accés Sense ¿ls i Heterogènies"(TIN2010-21378-C02-02) i el projecte S2EuNet-Security (FP7PEOPLE-2009- IRSES, 247083). Des dels seus inicis les comunicacions mòbils han experimentat un gran creixement, tant de dispositius mòbils com de quantitat d'amplada de banda demandada, la qual cosa ha provocat que els proveïdors es troben amb el desa¿amentdeferfrontaaquestcreixement.Peraaixò,s'estanimplementant diferents tècniques i tecnologies que s'integren amb el model actual de comunicacions mòbils. En aquesta tesi ens centrarem en la solució que aporten les xarxes heterogènies, especialment a la tecnologia de Small cells que s'ha desplegat ràpidament en els últims anys i permet incrementar la capacitat de la xarxa, així com obtenir millor disponibilitat i cobertura per als usuaris, però falta un model de negoci clar on es mostre la seua viabilitat econòmica. En aquesta tesi es planteja un model de negoci per a un proveïdor de servei que desplega Small cells i que competeix com el proveïdor de serveis incumbent. Per a l'anàlisi d'aquest model s'ha utilitzat la Teoria de Jocs la qual ha permès conéixer les decisions en equilibri que prenen els proveïdors de servei quan competeixen entre si, així com les decisions en equilibri dels usuaris; d'aquesta manera s'ha obtingut l'efecte d'aquestes decisions sobre els bene¿cis de tots els agents del model i s'han identi¿cat els avantatges i els inconvenients que té la implementació d'una nova tecnologia al mercat. Aquesta tesi pretén ser una contribució a l'estudi d'implementació de noves tecnologies al mercat de comunicacions mòbils, més concretament plantejant models econòmics que estudien la seua viabilitat a través de l'anàlisi de la competència entre un nou proveïdor se servei de Small cells i el proveïdor de servei existent, i el comportament dels usuaris de comunicacions mòbils. Els resultats obtinguts mostren que els usuaris obtenen una millor utilitat, el SSP sempre té uns bene¿cis garantits, el MSP es veu obligat a competir i els seus bene¿cis es veuen perjudicats, a més que l'entrada del SSP millora el benestar dels usuaris i el benestar social.<br>Romero Chavarro, JC. (2017). Contribución al modelado y al análisis mediante Teoría de Juegos de la competencia entre operadores móviles en escenarios con tecnología "small cell" [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/85681<br>TESIS

Magíster en Gestión de Operaciones<br>Ingeniero Civil Matemático<br>El problema de la evasión del pago del pasaje en el transporte público es transversal a distintos sistemas de transporte a lo largo del mundo, causando pérdidas a las empresas operadoras y al Estado. Ya que la instalación de barreras físicas y torniquetes no siempre es posible o deseable, diversos sistemas recurren al control del pago del pasaje a bordo. En esta tesis se modela el fenómeno de la evasión como un juego de Stackelberg sobre un grafo dirigido en el que interactúan dos jugadores: un inspector (el líder) y un evasor (el seguidor). Para controlar la evasión, el líder se ubica aleatoriamente sobre a lo más un arco de la red. Para ello, su estrategia consiste en fijar una distribución de probabilidad de inspección sobre los arcos del grafo. El seguidor, quien desea viajar entre dos nodos fijos sin pagar el pasaje, reacciona escogiendo como estrategia un camino, y lo recorre de manera que si atraviesa el arco donde se encuentra el inspector, deberá pagar una multa antes de continuar su viaje. Dependiendo de su comportamiento después de pagar la multa, se hace la distinción entre un seguidor no adaptativo, que continúa su viaje por el camino escogido previamente sin modificar su ruta, y uno adaptativo, que continúa su trayecto a través de un camino mínimo con respecto a las distancias. Dada una distribución de probabilidad de inspección, los tiempos de viaje y el valor de la multa, el objetivo del seguidor es encontrar un camino de costo esperado mínimo. Mientras que para el seguidor no adaptativo este problema se reduce a encontrar un camino mínimo con respecto a una versión modificada de las distancias, la pregunta por la complejidad del problema del seguidor adaptativo queda abierta. En esta tesis se diseñan algoritmos pseudopolinomiales para este último problema en grafos acíclicos y en grafos generales, además de un algoritmo fuertemente polinomial en grafos generales para el caso en que la distribución de inspección es uniforme sobre los arcos. Por último, se presenta un esquema de aproximación a tiempo totalmente polinomial (FPTAS) en grafos generales, y se amplía un resultado previo de Correa et al., donde se muestra que el cuociente entre los valores óptimos de los problemas no adaptativo y adaptativo es a lo más 4/3, mostrando un ejemplo donde la cota es ajustada. El líder, por su parte, es modelado de acuerdo a dos variantes. En la primera de ellas, su objetivo es maximizar el costo esperado del seguidor. Se prueba que cuando el seguidor es no adaptativo, este problema se puede resolver en tiempo polinomial, mientras que para el seguidor adaptativo se diseña un FPTAS. En la segunda variante, el líder busca maximizar el valor esperado de la multa recolectada. En el caso del seguidor no adaptativo, se demuestra que el problema de decisión asociado es NP-completo, mientras que para el seguidor adaptativo la pregunta por la complejidad se deja abierta.