Optimización del espacio de búsqueda del Lema de Sperner para repartos múltiples - Díaz de Rábago Pemán, Javier

Abstract

Este trabajo estudia una estrategia para reducir el espacio de búsqueda en problemas de división justa entre tres agentes. La propuesta se inspira en aplicaciones clásicas del lema de Sperner, como el reparto de habitaciones y rentas, la división de tierras o pastel y la asignación de franjas de tiempo. En estos contextos, el principal coste práctico no suele estar en garantizar la existencia de una solución, sino en el número de consultas necesarias para hallarla.

El proyecto parte de comparaciones por pares entre tres alternativas, sintetizadas mediante el método AHP. Las preferencias resultantes se representan en un triángulo equilátero interpretado como un 2-símplex. Sobre esta base se construyen regiones geométricas individuales para cada agente, cuya superposición induce una subdivisión planar del dominio. A partir de ella se identifica una región de consenso, o de conflicto nulo, formada por las celdas en las que los tres agentes quedan asociados a alternativas distintas.

La principal aportación no consiste en resolver directamente el reparto final, sino en introducir una fase previa de preprocesado geométrico que permita acotar una zona plausible de solución. Así, una fase posterior basada en Sperner puede concentrarse en una parte mucho más pequeña del dominio inicial.

La propuesta se ha implementado en Python, con un motor geométrico propio, una interfaz interactiva en Bokeh y un módulo de simulación Monte Carlo. Los resultados muestran que la región de consenso aparece sistemáticamente y suele ocupar una fracción reducida del símplex, con un área media del 10,7 % y una mediana del 3,6 %.This thesis studies a strategy for reducing the search space in fair division problems involving three agents. The proposal is inspired by classical applications of Sperner’s lemma, such as rent division, land division, cake cutting, and time-slot allocation. In these settings, the main practical difficulty is often not proving that a fair solution exists, but minimizing the number of queries needed to find it.

The method begins with pairwise comparisons between three alternatives, aggregated using the Analytic Hierarchy Process (AHP). The resulting preferences are represented in an equilateral triangle interpreted as a 2-simplex. Within this domain, individual geometric preference regions are constructed for each agent, and their superposition induces a planar subdivision of the simplex. From this subdivision, a consensus, or zero-conflict, region is identified as the union of the cells in which the three agents are assigned to different alternatives.

The main contribution of the thesis is not to solve the final allocation problem directly, but to introduce a preliminary geometric preprocessing stage that quickly restricts the search to a plausible solution region. This allows a later Sperner-based refinement stage to focus on a much smaller portion of the original domain.

The model has been implemented in Python using a custom computational geometry engine, an interactive Bokeh interface, and a Monte Carlo simulation module. Experimental results show that the consensus region appears systematically and is usually small relative to the full simplex, with an average area close to 10.7% and a median of 3.6%. Overall, the thesis provides a practical tool for narrowing the search region before applying more expensive refinement procedures.