Contributions in cooperative game theory and applications

Abstract

The analysis of situations of multi-agent cooperation has received much attention in recent years. The study of these is based on the determination of the optimal policy for the involved agents in each scenario, which, from an economic point of view, has to reduce the joint costs. Game theory is the discipline distributing the associated benefits/costs among the cooperating agents. According to this, there are multiple situations to be analyzed, among others, centralized inventory problems or sequencing problems.

First, new multi-agent inventory situations in which costs for product storage are not considered are studied. Nagarajan and Sosic (2008), Dror and Hartman (2011) or Fiestras-Janeiro et al. (2012) are some references in inventory problems. Authors study situations where a group of agents, who face individual inventory problems, cooperate to joint new orders of product. The determination of their sizes and their frequency bases the study. Once the optimal policy is obtained, the associated cost games are analyzed. From a theoretical point of view, the compliance of certain properties of interest will be studied, as well as the definition of distribution rules for the costs generated.

The study of cooperative multi-agent models is completed with the analysis of a new sequencing situation in the processing of jobs by a machine. In a generic way, the existence of several independent jobs to be performed sequentially in a single machine is assumed. The main goal is to determine the optimal order of the processing in order to minimize the overall costs. Curiel et al. (1989) and Borm et al. (2002), among many others, analyze this class of problems. In particular, this work analyzes situations such as those described in which the cost of processing a job is an exponential or logarithmic function of its completion time. Fixed an initial order for the jobs, the resulting profit from the reordering of the job in their processing are analyzed. So, a savings game arises that will be studied from a game theoretical approach.

Cooperative Game Theory is based on the formation of coalitions of agents which cooperate. The objective consists in the definition of values for sharing the costs / benefits by cooperation of the agents involved. Among others, the value of Shapley or the value of Banzhaf are two of the well-known mechanisms in the literature. They were extended to situations with a priori union systems for the agents and so, it appears the Owen value and the Banzhaf-Owen value, respectively.

Finally, statistical procedures are proposed for the estimation of values. In those cases in which the number of agents involved is large, since that the direct calculation is computationally difficult, several authors propose methods for estimating them by sampling. Maleki (2015) and Castro et al. (2009) define mechanisms based on simple random sampling in order to obtain an estimation of the Shapley value of a TU game. Bachrach et al. (2010) proposes analogous procedures for the estimation of Banzhaf value. They extend their proposals to the games with a priori unions, focusing on the estimation of the Owen value and the Banzhaf-Owen value. In these cases, aspects such as the estimation error is studied and its application is illustrated on different known examples.

El análisis de situaciones de cooperación multi-agente ha experimentado un gran incremento en los últimos años. El estudio de las mismas se basa en la determinación de la política óptima a seguir por los agentes involucrados en cada escenario lo que, desde un punto de vista económico, debe reducir los costes conjuntos. La teoría de juegos es la disciplina que permite distribuir los beneficios/costes asociados entre los agentes que cooperan. De acuerdo con esto, son múltiples las situaciones que pueden ser analizadas destacando, entre otros, los problemas de inventario centralizados o los problemas de secuenciación.

En primer lugar, se analizan nuevas situaciones de inventario multi-agente para las que no se consideran costes por almacenamiento de producto. Nagarajan y Sosic (2008), Dror y Hartman (2011) o Fiestras-Janeiro et al. (2012) son algunas referencias en problemas de inventario. Estos autores estudian situaciones en las que un conjunto de agentes, que se enfrentan a problemas de inventario individuales, cooperan para realizar pedidos de producto de manera conjunta. La determinación de sus tamaños y la frecuencia de los mismos fundamentan el estudio. Determinada la política óptima a seguir, los juegos de costes asociados a los problemas planteados son analizados. Desde un punto de vista teórico, se estudiará el cumplimiento de ciertas propiedades de interés, así como la definición de reglas de reparto para los costes generados.

El estudio de modelos cooperativos multi-agente se completa con el análisis de una nueva situación de secuenciación en el procesado de tareas por una máquina. De forma genérica, se asume la existencia de varias tareas independientes a realizar de manera secuencial en una única máquina. El objetivo fundamental pasa por determinar el orden óptimo de su procesado con el fin de minimizar los costes globales. Curiel et al. (1989) y Borm et al. (2002), entre muchos otros, analizan problemas de esta clase. En particular, en este trabajo se analizan situaciones como las descritas en las que el coste de procesado de una tarea es una función exponencial o logarítmica de su tiempo de finalización. Fijado un orden inicial para las tareas, se analizan los beneficios resultantes de la reordenación de las tareas para su procesado. Con esto, surge un juego de ahorro asociado que será estudiado desde el punto de vista de la teoría de juegos.

La teoría de los juegos cooperativos se basa en la formación de coaliciones de agentes que actúan de manera coordinada. Uno de sus objetivos pasa por la definición de valores para el reparto de los costes/beneficios resultantes de dicha cooperación entre los agentes involucrados. Entre ellos, el valor de Shapley o el valor de Banzhaf figuran como dos de los mecanismos más conocidos en la literatura para este fin. Su extensión a situaciones con sistemas de uniones a priori para los agentes ha permitido la definición del valor de Owen y del valor de Banzhaf-Owen, respectivamente.

Por último, se proponen procedimientos estadísticos para la estimación de valores. En aquellos casos en los que el número de agentes involucrados es elevado, dado que su cálculo directo resulta computacionalmente más difícil, varios autores proponen métodos para su estimación por muestreo. Maleki (2015) y Castro et al. (2009) definen mecanismos basados en el muestreo aleatorio simple para obtener una estimación del valor de Shapley de un juego TU. Bachrach et al. (2010) propone procedimientos análogos para la estimación del valor de Banzhaf. Se extienden sus propuestas al caso de valores con uniones a priori, centrándonos en el valor de Owen y el valor de Banzhaf-Owen. En estos casos, se estudian cuestiones tales como el error cometido en la estimación, ilustrando su aplicación sobre diferentes ejemplos conocidos.

A análise de situacións de cooperación multi-axente experimentou un gran incremento nos últimos anos. O estudo das mesmas baséase na determinación da política óptima a seguir polos axentes involucrados en cada escenario o que, dende un punto de vista económico, debe reducir os costes conxuntos. A teoría de xogos é a disciplina que permite distribuir los beneficios/costes asociados entre os axentes que cooperan. Dacordo con esto, son múltiples as situacións que poden ser analizadas destacando, entre outros, os problemas de inventario centralizados ou os problemas de secuenciación.

En primeiro lugar, analízanse novas situacións de inventario multi-axente para as que non se consideran costes por almacenamento de produto. Nagarajan e Sosic (2008), Dror e Hartman (2011) ou Fiestras-Janeiro et al. (2012) son algunhas referencias en problemas de inventario. Estos autores estudan situacións nas que un conxunto de axentes, que se enfrentan a problemas de inventario individuais, cooperan para realizar pedidos de produto de maneira conxunta. A determinación dos seus tamaños e a frecuencia dos mesmos fundamentan o estudo. Determinada a política óptima a seguir, os xogos de costes asociados ós problemas plantexados son analizados. Dende un punto de vista teórico, estudiarase o cumplimento de certas propiedades de interese, así como a definición de regras de reparto para os costes xerados.

O estudo de modelos cooperativos multi-axente complétase coa análise dunha nova situación de secuenciación no procesado de tarefas por unha máquina. De forma xenérica, asúmese a existencia de varias tarefas independentes a realizar de maneira secuencial nunha única máquina. O obxectivo fundamental pasa por determinar a orde óptima do seu procesado co fin de minimizar os costes globales. Curiel et al. (1989) e Borm et al. (2002), entre moitos outros, analizan problemas desta clase. En particular, neste traballo analízanse situacións como as descritas nas que o coste de procesado dunha tarefa é unha función exponencial ou logarítmica do seu tempo de finalización. Fixado unha orde inicial para as tarefas, analízanse os beneficios resultantes da reordenación das tarefas para o seu procesado. Con esto, surxe un xogo de aforro asociado que será estudado dende o punto de vista da teoría de xogos.

A teoría dos xogos cooperativos baséase na formación de coalicións de axentes que actúan de maneira coordinada. Un dos obxectivos pasa pola definición de valores para o reparto dos costes/beneficios resultantes de dita cooperación entre os axentes involucrados. Entre eles, o valor de Shapley ou o valor de Banzhaf figuran como dous dos mecanismos máis coñecidos na literatura para este fin. A súa extensión a situacións con sistemas de unións a priori para os axentes permitiu a definición do valor de Owen e do valor de Banzhaf-Owen, respectivamente.

Por último, propóñense procedementos estatísticos para a estimación de valores. Naqueles casos nos que o número de axentes involucrados é elevado, dado que o seu cálculo directo resulta computacionalmente máis difícil, varios autores propoñen métodos para a súa estimación por mostraxe. Maleki (2015) e Castro et al. (2009) definen mecanismos baseados na mostraxe aleatoria simple para obter unha estimación do valor de Shapley dun xogo TU. Bachrach et al. (2010) propoñen procedementos análogos para a estimación do valor de Banzhaf. Exténdense as súas propostas ó caso de valores con unións a priori, centrándonos no valor de Owen e o valor de Banzhaf-Owen. Nestos casos, estúdanse cuestións tales como o erro cometido na estimación, ilustrando a súa aplicación sobre diferentes exemplos coñecidos.