Producir un pedido total o parcial a partir de una relación inconsistente
Imagina que quiero construir un orden total a partir de un conjunto de elementos, $E$, pero la función de comparación produce resultados que no son deterministas. Produzco una lista de pares de elementos (e, e) mediante la aplicación repetida de la función de comparación, de modo que cada elemento del conjunto se represente al menos una vez.
¿Cómo puedo utilizar esta entrada para producir un pedido total? ¿Cuál es la clase de algoritmos que se pueden aplicar aquí?
Para mayor claridad, daré un ejemplo concreto.
¿Cuáles son las mejores coberturas para pizza?
Mi conjunto de elementos $E$ incluye algunos aderezos de pizza populares: pepperoni, queso, champiñones, piña, pimiento morrón, aceituna.
Luego, para cada uno de mis amigos, elijo subconjuntos de ingredientes de tamaño aleatorio y le pido a mi amigo que los ponga en orden de mejor a peor. Mis amigos responden diligentemente y crean la entrada para mi algoritmo:
- queso, pepperoni, aceituna
- queso, piña, champiñón, aceituna
- pimiento morrón, champiñón, aceituna
- pepperoni, queso, aceituna
- queso, pimiento
Parece que hay un orden difuso aquí (todos están de acuerdo con que las aceitunas son las peores) pero mis amigos no han llegado a un consenso sobre cuál es la mejor cobertura de pizza: queso o pepperoni. Teniendo en cuenta dónde ocurren los elementos en las entradas y con qué frecuencia ocurren, probablemente produciría un pedido como este.
- queso> pepperoni> pimiento> piña> champiñones> aceituna
Simplemente no estoy seguro de cómo formalizar esto y hacer que funcione para entradas mucho más grandes.
Creo que la solución probablemente involucre gráficos y bordes ponderados, pero no estoy lo suficientemente familiarizado con los algoritmos de gráficos para reconocer si esta es un área de estudio con nombre. Ya me encontré con la "clasificación topológica", pero eso solo funciona para gráficos acíclicos dirigidos , y estoy específicamente interesado en entradas que no pueden producir un DAG.
También noté que este problema parece similar a votar por representantes electos. ¿Es, de hecho, la misma clase de problema?
Respuestas
Es difícil decirlo sin más contexto y más modelos. Requerirá algunas suposiciones sobre cómo los resultados de la función de comparación se relacionan con el orden total deseado (oculto).
Es posible que desee el modelo Bradley-Terry-Luce . Si es así, existen muchos algoritmos estándar. Ver tambiénhttps://cs.stackexchange.com/a/85204/755.
Es posible que desee algún sistema de clasificación, como Elo, etc.
Es posible que desee un sistema de votación clasificado , como IRV, método Condorcet, recuento de Borda o cualquiera de muchos otros. Todos tienen varios defectos y compensaciones. Hay una prueba de que ningún sistema tendrá todas las propiedades que podríamos desear; vea, por ejemplo, el teorema de Arrow y el problema de la no transitividad (que incluso si cada una de las preferencias individuales de su amigo es transitiva, es decir, un orden total, entonces no hay garantía de que exista un orden global total que sea consistente con todos ellos).