March 15th 2019
Facultad de Ciencias Económicas y Empresariales | Salón de Grados
Contributions in cooperative game theory and applications
2019/03/15- 11:00h| Alejandro Saavedra Nieves, University of Vigo
The main purpose of this dissertation is to tackle several topics in cooperative game theory and its applications. In this sense, this manuscript is composed by three independent parts.
The first part is devoted to the analysis of cooperative inventory models. A multi-agent inventory problem is a situation in which several agents face individual inventory problems and agree to coordinate their orders with the objective of reducing their costs. We firstly analyse a multi-agent inventory problem with two acquisition costs. In the analysis of multi-agent inventory problems, it is usually assumed that the cost of a usual feeding ration is equal to the cost of a shortage feeding ration. However, this equality assumption is not acceptable in some cases. Secondly, we study a multi-agent inventory problem with general transportation costs. In this model, we take the case in which the variable cost per a new order is given by a general transportation cost function. In both cases, we describe the cost allocation problems that arise from a cooperative game-theoretic approach.
In the second part, we focus on analysing sequencing situations with non-linear costs. Sequencing problems describe those situations where a set of jobs has to be processed in a collection of available machines. In this class of problems, an initial order for processing the jobs is assumed and each of them has associated a specific cost function which generally depends on the time in the machine. We describe sequencing problems with exponential and logarithmic costs by processing the jobs in a single-machine. Under these new considerations, we obtain results about the optimal order and we analyse the savings obtained by rearranging the jobs using cooperative game theory.
The last part of the thesis describes the computational problems that arise in exactly calculating coalitional values when the number of involved players enlarges. Due to the interpretation of some of these coalitional values as the average of the marginal contributions, approximation methods based on sampling techniques may reduce considerably these efforts. We formally describe a variation of the procedures provided for estimating the Shapley value in the mentioned settings to approximate the Owen value of general TU-games. Finally, we provide sampling alternatives for estimating the Banzhaf-Owen value. We propose an approximation procedure based on simple random sampling without replacement and then, we also introduce an alternative estimation method to approximate the Banzhaf-Owen value based on a two-stage sampling procedure. These methodologies are theoretically analysed and their performance on several examples in the literature is also evaluated, with positive results.