¿Qué es el algoritmo de votación "hacer que todos estén felices"?

Question

Estoy buscando un algoritmo de votación que elija a los ganadores según la combinación de la mayoría de los votos y el número de votos.

ejemplo de la vida real:

Nuestra empresa cuenta con una barra de cereal. Tenemos espacio para 3 cereales diferentes. Nosotros queremos permitirles a nuestros empleados votar sobre los cereales que desean.

Nos no queremos recoger estrictamente los 3 primeros ganadores en base a su popularidad porque puede haber una minoría de empleados que sólo pueden comer 1 cereales en particular (por cualquier razón) y nos gustaría darles asignación especial como sea posible.

Dado el siguiente resultado de votación, aquí están los resultados que nos gustaría que el algoritmo nos dé.

Busco un algoritmo que hace este tipo de clasificación. Si al menos puede proporcionar el nombre de lo que estoy buscando, sería una gran ayuda ya que podría buscarlo mejor. :)

Gracias!

Answer 1

Es posible que desee considerar las generalizaciones de Hall's marriage theorem y/o assignment problem.

La idea de este paradigmas es crear un grafo bipartito, donde los nodos son personas y cereales, con un borde entre la persona y el cereal pc si p votaron por c.El objetivo es seleccionar 3 cereales de tal manera que la gráfica resultante de la eliminación de todos los otros cereales es

1. conectado (todo el mundo va a comer al menos uno de los cereales seleccionados), y

2. maximiza el mínimo/promedio grado de cada persona (maximiza la felicidad min/promedio)

Se podría en cambio pensar en esto como un Maximum Coverage Problem. En este caso, tiene conjuntos C1,C2,...,Cm donde Ci es el conjunto de personas a las que les gusta el cereal i. Por ejemplo que, teniendo los cereales y las personas en el orden indicado en la tabla, usted tiene

C1 = {1,5} 
C2 = {2} 
C3 = {1,4,5} 
C4 = {3,5} 

Vamos n ser el número de personas, por lo que Ci es un subconjunto de {1,2,...,n}. El objetivo es encontrar k conjuntos de modo que la cardinalidad de la unión se maximiza. Si existen soluciones múltiples, elija la que minimice la cardinalidad de las intersecciones (minimice la cantidad que domina una persona) o maximice la cantidad de veces que se repite el elemento menos frecuente (maximiza la felicidad de la persona menos feliz).

Para este ejemplo, hay más pequeño k para los que están cubiertos todos los elementos es k=3 y le da la solución única C2,C3,C4.

Sin embargo lo miras, tienes un problema NP, pero hay algoritmos conocidos para resolverlos (ver los artículos de la wikipedia para referencias).

Answer 2

No hay un sistema de votación perfecto - ver http://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem. Ha habido varios intentos de superar esto doblando las reglas, incluyendo http://en.wikipedia.org/wiki/Range_voting.

Una idea cercana al rango de votación es darles a todos 12 votos y permitirles distribuirlos como lo deseen. Mirando tu ejemplo, si asumes que las personas que tienen múltiples opciones distribuyen sus 12 votos por igual (12x1 o 6x2 o 4x3 o 3x4), entonces creo que obtienes el resultado deseado, con Lucky Charms obteniendo un total de 10 votos y todo lo demás obteniendo más que esto.

Answer 3

Si el número de los cereales es pequeño, se puede ver el problema como un problema subconjunto de la cubierta y la fuerza bruta su camino para encontrar qué configuración proporciona la "felicidad" más

var max_happyness = -INF 
for every subset {c1, c2, c3} of C: 
    max_hapyness = max(max_happyness, happyness(i1,i2,i3)) 

Usted todavía tiene el problema de definir una función de felicidad adecuada sin embargo. Por ejemplo, puede elegir una función de felicidad que, como primera prioridad, calcule el número de personas que pueden comer cualquier alimento. Luego, como segunda prioridad, la cantidad de personas a las que les gustan dos de los cereales, luego a los que les gustan los tres cereales y así sucesivamente.

Pros: Si puede definir una función de felicidad, esto le garantiza el mejor resultado.

Contras: Debe poder definir una función de felicidad.