Métodos de aproximación de solucións na Teoría de Xogos

Abstract

A teoría de xogos cooperativa céntrase principalmente en analizar os seguintes dous aspectos dunha interacción multi-axente: qué coalicións se formarán e cómo será repartido o beneficio (ou custe) xerado entre os diferentes individuos involucrados. Para realizar esta distribución seguindo criterios como a xustiza ou a equidade, establécense as chamadas regras de reparto, que serán consideradas solucións dos xogos cooperativos. Sen embargo, cando o número de axentes involucrados é relativamente grande, o cómputo exacto destas solucións adoita presentar unha elevada complexidade computacional, sendo necesaria así a súa aproximación. Ao longo deste traballo, repasaremos os procesos de estimación presentados na literatura tanto para o valor de Shapley e o valor de Banzhaf, como para as súas extensións a situacións con estruturas de prioridade, o valor de Owen e o valor de Banzhaf-Owen. Ademáis, mediante a implementación en R destes algoritmos, calcularemos novas cotas de leite en Galicia ao supoñer unha redución da produción con respecto a 2015.Cooperative game theory focuses mainly on analyzing the following two aspects of a multiagent interaction: what coalitions will be formed and how the benefit (or cost) generated will be shared among the different individuals involved. For allocating according to different criteria such as justice or fairness, the so-called allocation rules are established, which will be considered solutions of the cooperative games. However, when the number of agents involved is relatively large, the exact computation of these solutions presents a high computational complexity, thus making its approximation necessary. Along this work, we will review the estimation processes presented in the literature for the Shapley value and the Banzhaf value, as well as for their extensions to situations with a priori unions, the Owen value, and the Banzhaf-Owen value. In addition, by implementing these algorithms in R, we will calculate new milk quotas in Galicia by assuming a reduction in the production with respect to 2015.