Fundamentos del Reparto de Tartas: El Teorema de Lyapunov y extensiones

Abstract

RESUMEN: Este manuscrito se dedica a establecer los Fundamentos Matemáticos del Problema de Reparto de Tartas, un Problema de Asignación de Recursos estático. El problema, que se remonta a Banach, demanda un “método” para distribuir una tarta entre n agentes. La operación elemental es “Cut & Choose”: alguien corta varios trozos de la tarta y, posteriormente, los agentes eligen algunos de esos trozo conforme a sus preferencias y gusto personales. Las preferencias de los agentes son dadas por distribuciones de probabilidad sobre la tarta. El antecesor de este problema es un resultado cl asico debido a A. Lyapunov: El rango de una lista de n distribuciones de probabilidad es un subconjunto convexo y compacto de Rn. En el Capítulo 1, mostramos una demostración completa y detallada de este Teorema, siguiendo (y completando) una demostración de P. Halmos de 1947. El teorema de Lyapunov no basta para nuestro problema. En 1951, A. Dvoretzky, A. Wald y J. Wolfowitz probaron una extensión más profunda: El conjunto de las matrices dadas como esperanzas de particiones de la unidad medibles y finitas con respecto a una lista fija de distribuciones de probabilidad es un conjunto compacto y convexo. M as a un, este conjunto coincide con el conjunto de la matrices de medidas de particiones del conjunto con respecto a la misma lista fijada de distribuciones de probabilidad. En el Capítulo 2, mostramos una versión detallada de su demostración y, en la Sección 2.6, aportamos algún material original, basado en reflexiones personales sobre este Teorema: Introducimos un operador (re-estructuración), estudiamos el estabilizador del conjunto de DWW, probamos que se trata de un monoide convexo y compacto y mostramos como un reparto perfecto (proporcional, libre de envidia, justo y exacto) puede obtenerse realizando n “cortes convexos”. Estas ideas solo conducen a trozos que son conjuntos medibles. Como, usualmente, los conjuntos medibles no son constructibles, estos trozos de tarta difícilmente pueden ser descritos a los agentes. En 1987, N. Alon demostró que existe un reparto perfecto de la tarta I = [0; 1] de tal modo que cada trozo es una unión finita de intervalos y, por tanto, constructible (un conjunto semi-algebraico). Se trata de un Teorema existencial y la prueba original tiene algunos puntos dudosos que también hemos corregido para mostrar una prueba completa y detallada en el Capítulo 3. El manuscrito se completa con varios Apéndices como ayuda al lector: El Apéndice A muestra algunas notaciones básicas y resultados conocidos usados a lo largo del manuscrito, el Apéndice B muestra versiones cortas de los métodos de reparto de tartas más famosos y el Apéndice C muestra un par de imágenes del artículo de Lyapunov.

ABSTRACT: This manuscript is devoted to establish the Mathematical Foundations of the Problem of Cutting Cakes, a static Resource Allocation Problem. This Problem, which goes back to Banach, asks for a “method” to distribute a cake among n agents. The elementary operation is “Cut & Choose”: someone cuts several pieces of cake and, then, agents choose some of these pieces, according to their personal preference and taste. Agents preferences are given by probability distributions on the cake. The ancestor of this problem is a classical result due to A. Lyapunov: The range of a list of n probability distributions is a convex and compact subset of Rn. In Chapter 1, we exhibit a complete and detailed proof of this Theorem, following (and fulfilling) a proof by P. Halmos of 1947. Lyapunov's Theorem does not suffice to our problem. In 1951, A. Dvoretzky, A. Wald and J. Wolfowitz proved a deeper extension: The set of matrices of expectations of finite measurable partitions of the unit with respect to a fixed list of probability distributions is convex and compact. Moreover, this set agrees with the set of matrices of measures of finite partitions of the set with respect to the same list of fixed probability distributions. In Chapter 2, we exhibit a complete and detailed version of their proof and, in Section 2.6, we add some original material, based on personal reflections on this result: we introduce an operator (restructure), we study the stabilizer of the DWW set, we prove that it is a convex and compact monoid and we exhibit how a perfect (proportional, envy free, fair and exact) partition may be achieved just using n \convex cuts". These ideas lead to pieces which are measurable sets. As, usually, measurable sets are not constructible, these pieces of cake can hardly be described to the agents. In 1987, N. Alon proved that there exists a perfect partition of the cake I = [0; 1] in such a way that each piece is a finite union of intervals and, hence, constructible (a semi-algebraic set). This is an existential Theorem and the original proof had some flows that we have also fixed to exhibit a complete and detailed proof in Chapter 3. The manuscript is completed with several Appendices to help the reader: Appendix A recalls some basic notations and well-known facts used along the manuscript, Appendix B shows short versions of some famous Cutting Cake pseudo-algorithms and Appendix C shows a couple of images of Lyapunov's paper.