Aportaciones al estudio de soluciones para juegos cooperativos

Author

Giménez Pradales, José Miguel

Director

Amer Ramon, Rafel

Tutor

Rubio i Díaz, Pere

Date of defense

2001-12-14

ISBN

846890581X

Legal Deposit

B-6820-2005



Department/Institute

Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada III

Abstract

El objetivo del trabajo consiste en la generalización y el estudio de modelos y métodos que han mostrado su eficiencia respecto a las soluciones para los juegos cooperativos propuestas por Shapley o por Banzhaf, así como el desarrollo de propiedades derivadas de su generalización. Estos y otros conceptos se extienden a una clase más amplia de soluciones para los juegos cooperativos: los semivalores. Conforme a la idea general que se ha establecido, la memoria se estructura en seis capítulos.<br/> <br/>El primer capítulo contiene una introducción a los conceptos básicos de la teoría de juegos cooperativos con utilidad transferible.<br/> <br/>El segundo capítulo aborda el estudio de los semivalores y las estructuras de coalición. Aquí se consideran familias de semivalores a partir de las cuales se forman sistemas de referencia consiguiendo, además, establecer semivalores inducidos en espacios de juegos con menor cardinal del conjunto de jugadores, con independencia del sistema de referencia escogido. Estas actuaciones permiten generalizar el proceso que lleva del valor de Shapley al valor coalicional de Owen, dando lugar al concepto de semivalor modificado para juegos con estructura de coalición. El capítulo finaliza estableciendo unas propiedades que consiguen caracterizar axiomáticamente la modificación de la solución de Banzhaf para juegos con estructura de coalición.<br/> <br/>En el tercer capítulo se emplean de modo particular técnicas y resultados provenientes del segundo con el objetivo de estudiar, desde el punto de vista de cualquier semivalor, las consecuencias de la formación de una única coalición bipersonal estable. Además de conseguir el cálculo efectivo de los resultados tanto a partir de la función característica como de la EML, este estudio consigue caracterizar diferentes semivalores en atención a su comportamiento respecto a esta situación de cooperación modificada.<br/> <br/>El cuarto capítulo se centra en otra situación de cooperación modificada: la cooperación parcial modelizada por grafos. Allí se prueba que todo semivalor cumple propiedades deseables según la formulación de Myerson (1977). También se afirma que la normalización aditiva de cualquier semivalor verifica esas mismas propiedades, resultando que normalización aditiva y cooperación parcial son conceptos ampliamente compatibles. Además, se consigue determinar qué jugadores resultan más beneficiados o más perjudicados por la supresión de una arista de un grafo de cooperación.<br/> <br/>El quinto capítulo está dedicado al potencial. Se define y estructura un concepto de potencial para cada semivalor construido de modo recurrente, en modo análogo a como Hart y Mas-Colell (1988) y Dragan (1995) introducen esos conceptos para las soluciones de Shapley y de Banzhaf, respectivamente. También se ofrece un procedimiento para calcular el potencial para cada semivalor mediante manipulaciones adecuadas de la EML. Otras nociones derivadas del potencial, como base potencial o espacio nulo, se extienden a todos los semivalores. Se resuelven problemas inversos como la determinación de los juegos que tienen una solución prefijada o la determinación del juego conocido el poder de éste y de sus juegos restringidos.<br/> <br/>El sexto capítulo trata el problema de la determinación del subespacio intersección de todos los espacios nulos por semivalores. En esta intersección se encuentran los juegos que no pueden distinguirse del nulo por ningún semivalor. Resuelto el problema anterior con la introducción de los juegos de conmutación, se consideran semivalores modificados para juegos con estructura de coalición y se busca determinar el subespacio de indistinguibles del nulo por este tipo de soluciones. Para los juegos de más de cuatro jugadores, la introducción de las estructuras de coalición consigue reducir de modo significativo la dimensión de cada subespacio de juegos indistinguibles del nulo.


The objective of the work consists of the generalization and the study of models and methods that have shown their efficiency with respect to the solutions for the cooperative games proposed by Shapley or Banzhaf, as well as the development of properties derived from its generalization. These and other concepts extend to a more ampler class of solutions for the cooperative games: the semivalues. According to the general objective that one has settled down, the memory structure in six chapters.<br/><br/>The first chapter contains an introduction to the basic concepts of the theory of cooperative games with transferable utility. <br/><br/>The second chapter undertakes the study of the semivalues and the coalition structures. Here, we consider families of semivalues obtaining reference systems for semivalues; in addition, we establish induced semivalues in spaces of games with minor cardinal of the set of players, independently of the chosen system of reference. These performances allow to generalize the process that takes of the value of Shapley to the coalition value of Owen, giving rise to the concept of modified semivalue for games with coalition structure. The chapter finalizes establishing properties that are able axiomatically to characterize the modification of the solution of Banzhaf for games with coalition structure.<br/><br/>In the third chapter it is used, of particular way, technical and results of the second with the objective of to study, from the point of view of any semivalue, the consequences of the formation of a unique stable two-person coalition. We obtain the effective calculation of the results from the function characteristic and from the EML; this study it is able to characterize different semivalues in attention from his payment with respect to this situation of modified cooperation. <br/><br/>In the fourth chapter one studies another situation of modified cooperation: the partial cooperation expressed by graphs. There, we prove that all semivalue, as allocation rule for these situations of cooperation, verify desirable properties according to the formulation of Myerson (1977). Also, one affirms that the normalization additive of any semivalue verifies those same properties; thus, normalization additive and partial cooperation are widely compatible concepts. In addition, one is able to determine what players are more benefited or more harmed by the suppression of an edge of a graph of cooperation.<br/><br/>The fifth chapter is dedicated to the potential. A concept of potential for each semivalue is defined and constructed of recurrent way, in analogous way to as Hart and Mas-Colell (1988) and Dragan (1995) introduce those concepts for the solutions of Shapley and Banzhaf, respectively. Also a procedure is offered to calculate the potential for each semivalue by means of suitable manipulations of the EML. Other notions derived from the potential, as potential basis or null space, extend to all semivalues. Inverse problems like the determination of the games that have a concrete solution or the determination of the game from the power, are solved. <br/><br/>The sixth chapter deals with the problem of the determination of the subspace intersection of all the null spaces by semivalues. In this intersection are the games that cannot be distinguished from the null game by semivalues. Solved the previous problem with the introduction of the commutation games, semivalues modified for games with coalition structure are considered and it looks for to determine the subspace of indistinguishable from the null game by this type of solutions. For games with five or more players, the introduction of coalition structures is able to reduce of significant way the dimension of each subspace of indistinguishable games from the null game.

Keywords

solucions; jocs cooperatius; separabilitat; potencial; extensió multilineal; solucions modificades; teoria dels jocs

Subjects

51 - Mathematics; 512 - Algebra; 519.1 - Combinatorial analysis. Graph theory

Knowledge Area

1200. Matemàtiques - 1201. Algebra

Documents

01Jmgp01de01.pdf

11.17Mb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)