Combinatorial Structure of Polytopesassociated to Fuzzy Measures

Abstract

This PhD thesis is devoted to the study of geometric and combinatorial aspects of polytopes associated to fuzzy measures. Fuzzy measures are an essential tool, since they generalize the concept of probability. This greater generality allows applications to be developed in various elds, from the Decision Theory to the Game Theory. The set formed by all fuzzy measures on a referential set is a polytope. In the same way, many of the most relevant subfamilies of fuzzy measures are also polytopes. Studying the combinatorial structure of these polytopes arises as a natural problem that allows us to better understand the properties of the associated fuzzy measures. Knowing the combinatorial structure of these polytopes helps us to develop algorithms to generate points uniformly at random inside these polytopes. Generating points uniformly inside a polytope is a complex problem from both a theoretical and a computational point of view. Having algorithms that allow us to sample uniformly in polytopes associated to fuzzy measures allows us to solve many problems, among them the identi cation problem, i.e. estimate the fuzzy measure that underlies an observed data set...

La presente tesis doctoral esta dedicada al estudio de distintas propiedades geometricas y combinatorias de politopos de medidas difusas. Las medidas difusas son una herramienta esencial puesto que generalizan el concepto de probabilidad. Esta mayor generalidad permite desarrollar aplicaciones en diversos campos, desde la Teoría de la Decision a laTeoría de Juegos. El conjunto formado por todas las medidas difusas sobre un referencial tiene estructura de politopo. De la misma forma, la mayora de las subfamilias mas relevantes de medidas difusas son tambien politopos. Estudiar la estructura combinatoria de estos politopos surge como un problema natural que nos permite comprender mejor las propiedades delas medidas difusas asociadas. Conocer la estructura combinatoria de estos politopos tambien nos ayuda a desarrollar algoritmos para generar aleatoria y uniformemente puntos dentro de estos politopos. Generar puntos de forma uniforme dentro de un politopo es un problema complejo desde el punto de vista tanto teorico como computacional. Disponer de algoritmos que nos permitan generar uniformemente en politopos asociados a medidas difusas nos permite resolver muchos problemas, entre ellos el problema de identificacion que trata de estimarla medida difusa que subyace a un conjunto de datos observado...