Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/2462| Uso de la teoría de juegos para modelar el problema de asignación de guardaespaldas Using game theory to model the bodyguard allocation problem | |
| Daniel Brubeck Salcedo | |
| Jose Alberto Fernandez Zepeda | |
| Acceso Abierto | |
| Atribución | |
| Teoría de juegos,Problema de asignación de guardaespaldas,Sistemas distribuidos | |
| En este trabajo se estudia el problema de asignación de guardaespaldas (PAG) desde la perspectiva de la teoría de juegos. Este problema lo propuso Fajardo-Delgado et al. (2010) y consiste en construir un árbol de esparcimiento en grafos conectados donde se presentan dos tipos de nodos: blancos y negros; los nodos blancos buscan minimizar su distancia a la raíz mientras que los nodos negros buscan maximizarla. Una solución del PAG es un árbol en el que se cumple una condición de equilibrio y se maximiza el beneficio social. En este trabajo se analizan los distintos tipos principales de juegos que existen en la literatura y se clasifica el juego del PAG con base en sus características. Una característica importante del juego del PAG, es que puede tener más de una configuración que satisface una condición de equilibrio y en el que no todas ellas maximizan el beneficio social. Así, en este trabajo se proponen seis variantes del juego que buscan mejorar la calidad de los equilibrios encontrados. Cuatro de estas variantes, consisten en la implementación de las estrategias: voraz, ε-voraz, anti-voraz e IA-voraz. La diferencia entre estas estrategias radica en el mecanismo de decisión empleado por cada nodo. Otra variante es la implementación de un nuevo calendarizador denominado anti-voraz; este calendarizador está diseñado para trabajar en conjunto con la estrategia anti-voraz y su objetivo es minimizar los cambios en el beneficio social del sistema. Los resultados experimentales muestran que la estrategia anti-voraz bajo este calendarizador incrementa de forma significativa la calidad del equilibrio encontrado para el enfoque cooperativo. La última variante del juego, consiste en una nueva función de preferencias que utiliza el pago promedio obtenido en el tiempo con el fin de que los nodos sean más “precavidos” al evaluar sus opciones durante el juego. Por otro lado, Fajardo-Delgado et al. (2010) también proponen el algoritmo CBAP para encontrar soluciones aproximadas para el PAG. Este algoritmo garantiza una condición de equilibrio para el PAG que no necesariamente maximiza el beneficio social. En este trabajo, se diseña la técnica de especulación; esta técnica se diseña para el enfoque cooperativo y permite romper de forma segura un equilibrio encontrado por el algoritmo CBAP. Se roponen cuatro variantes para el algoritmo CBAP que implementan la técnica de especulación. Las variantes se diferencian en la cantidad de información que utilizan y las reglas empleadas para realizar movimientos de especulación. Se demuestra que estas variantes siempre terminan con una configuración que satisface una condición de equilibrio y que los beneficios sociales de estos equilibrios son iguales o mejores que los obtenidos por el algoritmo CBAP. Asimismo, se demuestra que las variantes propuestas mantienen el orden de complejidad temporal del algoritmo CBAP. Finalmente, se presentan resultados experimentales donde se comparan las variantes propuestas del juego del PAG y las variantes del algoritmos CBAP. In this thesis, we study the bodyguard allocation problem (BAP) from a game theory perspective. This problem was proposed by Fajardo-Delgado et al. (2010) and its objective is to build a spanning tree in a connected graph in which there are two types of nodes: white and black. The white nodes seek to minimize their distance to the root while black nodes seek to maximize it. A solution of the BAP is a tree which satisfies a condition of equilibrium and maximizes social welfare. In this work, we analyze the main types of games that exist in literature and classify the BAP game based on its characteristics. An important feature of the BAP game is that it has more than one configuration that satisfies a condition of equilibrium, and not all of them maximize social welfare. Thus, in this thesis we propose six variants of the game which seeks to improve the quality of the equilibrium found by a previous existing algorithm. Four of these variants consist on the following strategies: greedy, ε-greedy, anti-greedy and RS-greedy. The difference between these strategies lies in the decision mechanism used by each node. Another variant is the implementation of a new scheduler called anti-greedy. We designed this scheduler to work with the anti-greedy strategy and its objective is to minimize changes in the social welfare of the system. Experimental results show that the anti-greedy strategy enhances the quality of the equilibrium found for the cooperative approach when it works in conjunction with this scheduler. The last variant of the proposed game is a new preference function that uses the average payment over time giving “cautious” behavior to the nodes when evaluating their options during the game. On the other hand, Fajardo-Delgado et al. (2010) propose the CBAP algorithm to find approximate solutions for the BAP. This algorithm guarantees to finish with an equilibrium condition for the BAP, but it does not necessarily maximize social welfare. In this thesis, we design a new technique called the speculation technique, this technique works for the cooperative approach and it allows the algorithm to break safely the equilibrium found by the CBAP algorithm. We propose four variants of the CBAP algorithm that implement the speculation technique. The variants differ in the amount of information and the rules used in order to make speculation moves. We show that these variants always end with a configuration that satisfies a condition of equilibrium and the social welfare of these equilibria are equal to or better than those obtained by the CBAP algorithm. We also show that these variants maintain the time complexity of the CBAP algorithm. Finally, we present experimental results that compare the proposed variants of the BAP game and the variants of the CBAP. | |
| CICESE | |
| 2011 | |
| Tesis de maestría | |
| Español | |
| Brubeck Salcedo, D.2011.Uso de la teoría de juegos para modelar el problema de asignación de guardaespaldas.Tesis de Maestría en Ciencias.Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.136 pp. | |
| TECNOLOGÍA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| 187881.pdf | 4.68 MB | Adobe PDF | Visualizar/Abrir |