On minimum cost spanning tree problems and games with coalition structure

Zusammenfassung

La tesis constituye una aportación a la Teoría de Juegos Cooperativa, En particular se centra en los problemas de árboles de mínimo coste, y los juegos de utilidad transferible (TU) con estructura coalicional. Además introduce una nueva clase de problemas que reciben el nombre de problemas de árboles de mínimo coste con estructura coalicional. Los problemas de árboles de mínimo coste modelizan situaciones en las que un grupo de agentes, situados en distintos puntos geográficos quieren un determinado recurso que es proporcionado por un único proveedor o fuente. Las conexiones entre los distintos agentes y entre ellos y la fuente llevan asociado un coste de conexión. En este tipo de problemas existe un planificador que se encarga de construir el árbol que conecta a todos los agentes a la fuente a coste mínimo y de repartir el coste asociado al mismo entre dichos agentes mediante una regla de asignación de costes. En el Capítulo 1 de la tesis se introduce una nueva propiedad para este contexto, No Advantageous Merging. Dicha propiedad implica que ningún grupo de agentes tenga incentivos a unirse a priori, asumiendo el coste de conexión entre ellos y presentarse de este modo al planificador para ser tratados como un único agente. Se prueba que la regla que asigna a cada agente su coste de conexión directa en el árbol de mínimo coste (Bird, 1976) verifica esta propiedad y se proporciona una caracterización de dicha regla utilizando No Advantageous Merging. La segunda parte de la tesis se dedica la estudio de los juegos TU donde los agentes se presentan formando coaliciones. Se trata de repartir un beneficio entre las coaliciones y entre los agentes dentro de cada coalición. Dicho reparto se hará a través de un valor coalicional. Vidal-Puga (2006) define un nuevo valor para este conteto en el que se tiene en cuenta el tamaño de cada coalición a la hora de repartir el beneficio entre los agentes. En el Capítulo 2 de esta tesis se proporciona una caracterización de dicho valor utilizando propiedades estándares en la literatura (como eficiencia, linealidad, independencia de coaliciones nulas y contribuciones equilibradas entre jugadores de la misma coalición) y otras introducidas en dicho capítulo, tales como coordinación (que indica que cambios internos dentro de una coalición que no afectan a ljuego entre coaliciones no influyen en el pago final del resto de jugadores) y reparti igualitario en juegos de unanimidad (que indica que si la unanimidad es necesaria para obtener un beneficio, todos los agentes han de recibir el mismo pago independientemente de cuál sea la estructura coalicional). Además, en este capítulo se presentan sendas caracterizaciones de otros valores conocidos en la literatura como son el valor de Owen (1977) y el valor de Levy and McLean (1989) con pesos dados por el tamaño de las coaliciones. En el Capítulo 3 de la tesis se extiende el valor presentado por Vidal-Puga (2006) a juegos TU con estructura de niveles, que son juegos TU con una secuencia de estructuras coalicionales. Además se presenta una nueva propiedad para este contexto que recibe el nombre de contribuciones equilibradas per cápita, que segura que para cualquier par de coaliciones de un determinado nivel que pertenecen a la misma coalición a partir del siguiente nivel, el cambio en el pago per cápita de los jugadores de una de las coaliciones si la otra abandona el juego ha de ser igual para ambas. En este capítulo se presenta una caracterización del nuevo valor introducido con las propiedades de eficiencia y esta nueva propiedad de contribuciones equilibradas per cápita. En la última parte de la tesis se definen los llamados problemas de árboles de mínimo coste con estructura coalicional. A menudo, cuando los agentes quieren conectarse a una fuente común de agua, estos están situados en distintas ciudades o villas. En términos de la matriz de costes esto significa que el coste de conexión directa entre dos agentes de la misma ciudad es más pequeño que entre agentes de ciudades diferentes, si bien el modelo clásico de problemas de árboles de mínimo coste puede modelizar esta situación, lo primero es que ignora este hecho. En el Capítulo 4 de la tesis se define una nueva clase de problemas que introducen dicha información en el modelo. El objetivo principal en este tipo de problemas que introducen dicha información en el modelo. El objetivo principal en este tipo de problemas es construir el árbol de mínimo coste y repartir el coste asociado al mismo entre todos los agentes. En este capítulo se presenta una regla como la única para este contexto que verifica una serie de propiedades. Dicha spropiedades son las siguientes: monotonía en la población sobre coaliciones y monotonía en la población sobre agentes de la misma coalición (ambas con la filosofía de la entrada de jugadores nuevos en el problema no debe suponer un empeoramiento de la sociedad inicial), simetría entre coaliciones y simetría entre agentes de la misma coalición (que indican que agentes simétricos respecto a la matriz de costes han de pagar la misma cantidad para disponer del recurso) y aditividad restringida (que asegura que bajo ciertas restricciones la regla ha de ser aditiva en la matriz de costes). Los resultados presentados en este capítulo son generalizaciones de la regla presentada por Bergantiños y Vidal-Puga (Journal of Economic Theory, 2007a) y la caracterización de la misma desarrollada en Bergantiños y Vidal-Puga (2007b). En el Capítulo 5 se demuestra que la regla introducida en el Capítulo 4 coincide con el valor de Owen de un juego TU particular asociado al problema de árboles de mínimo coste con estructura coalicional.