Aplicaciones de juegos cooperativos en grafos de colores

Abstract

En este trabajo estudiamos dos situaciones distintas, pero a la vez muy parecidas. En el primer problema nos encontraremos con tres satélites que deben alcanzar seis zonas diferentes. Todos los satélites son análogos en costes y beneficios, pero saturan la capacidad de satélites que caben en una órbita. Creamos por tanto un grafo de colores, un color por cada satélite, que se une a las distintas zonas que son capaces de alcanzar. Creamos a su vez un valor basado en Myerson y en los grafos de colores para medir la importancia de cada satélite en función de las zonas que alcanza en el grafo de colores. En este caso no hay resultados sorprendentes ya que eliminamos una satélite que alcanza menos zonas que los otros dos. Debemos saber que el valor de Myerson también depende de la distribución de las zonas en el grafo. En el segundo problema nos encontraremos en una galería de arte la cual debe ser vigilada durante las veinticuatro horas que tiene el día. Para ello dispondremos de tres sistemas de cámaras de seguridad distintos. Todos los sistemas, como en el caso anterior, los consideraremos análogos en costes y beneficios. La galería dispone de un presupuesto limitado, con el cual solo se pueden adquirir dos de los tres sistemas que se disponen. Creamos por tanto un grafo de colores, un color por cada sistema, que se une a las paredes que vigilan. Nuevamente se define un valor basado en Myerson y en los grafos de colores para medir la importancia de cada sistema de cámara de seguridad en función de las paredes que vigila en el grafo de colores. Aunque de nuevo los resultados no son sorprendentes, ya que eliminamos el sistema azul, el sistema que menos paredes es capaz de vigilar, debemos saber que el valor de Myerson también depende de la distribución de las paredes en la habitación, es decir, en el grafo.

In this thesis we study two different situations, but at the same time they are quite similar. In the first case, we will find the next problem, three satellites which must reach six different areas. All satellites are analogous in costs and benefits, but they saturate the capacity of the orbit. We create a graph of colors, a color for each satellite, which links the different areas they can reach. We also create a value based on Myerson and the color graphs to measure the importance of each satellite based on the number of areas that they can reach in the color graph. In our case there are no surprising results since we eliminate a satellite that reaches the least number of areas. We must know that the value also depends on the position of the areas in the color graph. In the second case we face the art gallery problem, where all the walls must be secure, for this we will dispose of three security camera systems, all of them are analogous in costs and benefits, but the art gallery has limited budget, the main reason why they must choose two of the three different systems. We create a graph of colors, a color for each camera system, which secure the different walls of art gallery. We also create a value based on Myerson and the color graphs to measure the importance of each security camera system based on the number of walls that they can secure in the color graph Again, the result is not surprising due to the system that is eliminated is the blue one which secure the least number of walls. We must know that the Myerson´s value apart of the number of walls it secures, it also depends of the position of the walls in the graph