Cómo combinar una colección de preferencias ordenadas

Question

Tengo un conjunto de revisores que califican un conjunto de n objetos. Cada revisor produce de forma independiente una lista ordenada de los objetos que elige clasificar. El objetivo es producir una lista que sea la recopilación de las diversas listas ordenadas. Podemos suponer que el punto de vista de cada crítico es igual de ponderado.

Esto difiere de la mayoría de las preguntas de la lista de fusión y ordenada en que no existe un pedido global. Un revisor puede calificar A> B mientras que otro puede calificar B> A. Como se mencionó, cada objeto no necesariamente es calificado por cada revisor.

Mi idea actual es descomponer la lista de cada revisor en un conjunto de tuplas ordenadas para cada m * (m-1) * .5 pares únicos de entradas en la lista, donde m es el número de objetos clasificados. Ahora tome todas las tuplas de todos los revisores. Para una combinación dada (a, b) encuentre todas esas tuplas y tome el voto mayoritario (de los votantes) como el determinante de si un < b.

Ahora tengo un conjunto de tuplas ordenadas que representa la sabiduría de todos. ¿Pero cómo convierto estos en una lista ordenada? Puedo comenzar con un par de objetos elegidos al azar, y ordenarlos, luego agregar otro en el orden correcto, pero la salida dependerá de la que elija para comenzar. También puede haber bucles.

Agradecería cualquier idea.

Answer 1

Una solución que parece elegante y sigue haciendo lo que tiene que hacer sería convertir cada pedido en un puntaje de 1 a 0, donde 1 es el primer ítem clasificado en la lista de un revisor dado y 0 es su último (elemento inferior) y todos los elementos intermedios obtienen una puntuación de escala lineal. Entonces, si el revisor 1 clasifica solo 3 ítems, obtendría puntajes para esa lista de 1, 0.5 y 0. Luego, simplemente tome el puntaje promedio de cada ítem para generar una lista cotejada. Los lazos se pueden romper por el número de "revisiones" para un artículo (para que un artículo marcado por unanimidad como mejor por 3 revisores aparezca más alto en la lista final que un artículo unánimemente marcado como el mejor por 2 revisores, etc.)

Su requisito "El objetivo es producir una lista que sea la recopilación de las diversas listas ordenadas. Podemos suponer que el punto de vista de cada revisor se pondera por igual". definitivamente se cumple con este algoritmo simple, pero a menudo los problemas como este tienen requisitos un poco más complejos una vez que se profundiza en ellos.

Answer 2

La fusión de clasificaciones es algo no trivial. Creo que tal vez necesites tener una idea más clara de lo que quieres decir con "la compilación de las listas ordenadas", es decir, ¿qué propiedades quieres que tenga?

Vea por ejemplo estos CS course notes from Cornell. Dadas algunas propiedades razonablemente sensatas que debería tener la clasificación global, es realmente imposible crear un algoritmo que definitivamente satisfaga esas propiedades. Es posible que deba comprometerse en lo que aceptará como propiedades razonables de su clasificación global.

Answer 3

Artículos: Duke siempre Quake UT3 Duke3D de Halo

REV1: 
- Duke nukem forever 
- Duke3d 

REV2: 
- Duke3d 
- UT3 
- Quake 

REV3: 
- Duke3d 
- Duke nukem forever 

Deducción lógica:

• REV1: Duke siempre> Duke3D #
• REV1: Duke3D < Duke siempre # #
• REV2: D uke3d> UT3%
• REV2: UT3 < Duke3D%
• REV2: Duke3D> Quake %%
• REV2: Quake < Duke3D %%
• REV2: UT3> Quake %%%
• REV2: Quake < UT3 %%%
• REV3: Duke3D> Duke siempre #
• REV3: Duke siempre < Duke3D ##

más votadas:

• Duke3D 3
• Duke siempre 2
• UT3, Quake 1

Remove # que contradicen mediante la creación de pares contradiciendo y convertir a = Aceptar% que partido en pares. Agrupar con contar todo. Si hay < y = contradicciones, la verdadera es la que tiene más recuento.

filtra luego ordenados por la lógica:

• Duke3D, Duke siempre
• UT3
• Quake

Pero de selección se debe influenciado por el recuento de voto (tipo bayesiano). De esa forma, Duke3d ganaría.

de Halo no se puede colocar en cualquier lugar, ya que no es votado ...

Answer 4

El espacio del problema que está navegando es esencialmente (isomorfo a) un subconjunto de la teoría de la votación, que parte en dos papeletas y los resultados se ordenan las listas de candidatos.

que podría beneficiarse de la lectura de los siguientes:

• Condorcet Method - da un criterio útil "corrección".
• Schulze Method - proporciona un algoritmo O (n) para llegar allí.
• Voting System - le ofrece otros criterios deseables y compara diferentes enfoques.
• Borda Count - esencialmente el mismo que el currently accepted answer.
• Arrow's Impossibility Theorem - muestra por qué no puedes tener tu pastel y comértelo también.

Basado en mi conocimiento de la teoría de votación, Te daré una recomendación: si cree razonablemente que un O (n) algoritmo es viable para su conjunto particular de datos, probar el Schulze Method. De lo contrario, Borda Count es el único método listed que se ejecuta en el tiempo O (n) y toma una clasificación como entradas de boleta, así que quédese con eso.