Combinatorial structure of polytopes associated to fuzzy measures

Resumen

La presente tesis doctoral está dedicada al estudio de distintas propiedades geométricas 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 Decisión a la Teoría de Juegos. El conjunto formado por todas las medidas difusas sobre un referencial tiene estructura de politopo. De la misma forma, la mayoría de las subfamilias más relevantes de medidas difusas son también politopos. Estudiar la estructura combinatoria de estos politopos surge como un problema natural que nos permite comprender mejor las propiedades de las medidas difusas asociadas. Conocer la estructura combinatoria de estos politopos también nos ayuda a desarrollar algoritmos para generar aleatoria y uniformemente puntos dentro de estos politopos. Disponer de algoritmos que nos permitan generar uniformemente en politopos asociados a medidas difusas nos permite resolver muchos problemas, entre ellos el problema de identificación que trata de estimar la medida difusa que subyace a un conjunto de datos observado. Muchos de los politopos asociados a subfamilias de medidas difusas son politopos de orden y su estructura combinatoria depende de un orden parcial (poset). De esta forma podemos transformar problemas de naturaleza geométrica en problemas de Combinatoria y Teoría del Orden. En esta tesis, empezamos introduciendo los resultados más importantes sobre posets y politopos de orden. A continuación nos centramos en el problema de generar extensiones lineales de forma aleatoria para un poset. A tal fin hemos desarrollado un método, al que hemos llamado Bottom-Up. A los posets que se les puede aplicar este método los llamamos BU-factibles. También estudiamos otro método al que llamamos método basado en ideales (Ideal-based method). Este método es más general que el Bottom-Up y es aplicable a cualquier poset. Sin embargo, su coste computacional es mucho mayor. Dentro de los posets que no son BU-factibles hay casos importantes que merecen un estudio individualizado, como es el caso de los posets de Ferrers. Los posets de Ferrers están asociados a las medidas 2-simétricas. En esta tesis estudiamos en detalle las propiedades geométricas y combinatorias de las medidas 2-simétricas. A continuación estudiamos la subfamilia de medidas 2-aditivas. Los politopos de esta subfamilia no son politopos de orden, y por tanto no podemos aplicar las técnicas que hemos desarrollado relacionadas con posets. Los juegos monótonos surgen como la versión no normalizada de las medidas difusas. En este caso estos conjuntos forman conos convexos cuya estructura también depende de un poset. A estos conos los hemos llamado conos de orden (Order Cones). En la tesis explicamos la relación existente entre conos de orden y politopos de orden. Posteriormente en la tesis estudiamos técnicas de integración para contar extensiones lineales. Estas técnicas se pueden aplicar para conocer el volumen de los politopos de orden asociados. De la misma forma permiten resolver problemas concretos de Combinatoria como el de contar el número de permutaciones 2-alternantes. Finalmente la tesis acaba con un capítulo sobre conclusiones y problemas abiertos.