Что такое алгоритм голосования «сделайте всех счастливым»?

Question

Я ищу алгоритм голосования, который выбирает победителей на основе комбинации большинства голосов и количества голосов.

Реальный пример из жизни:

Наша компания имеет бар зерновых. У нас есть место для 3 различных злаков. Мы хотим, чтобы наши сотрудники голосовали, на каких зерновых они хотят.

Мы не хотим строго выбрать лучшие 3 победителей по популярности , потому что может быть меньшинство сотрудников, которые могут есть только 1 особой каши (по любой причине), и мы хотели бы, чтобы дать им особое внимание как возможно.

Учитывая следующий результат голосования, вот результаты, которые нам хотелось бы получить от нас.

Я ищу алгоритм, который делает этот вид ранжирования. Если вы можете хотя бы указать имя того, что я ищу, это будет большой помощью, поскольку я мог бы лучше его искать. :)

Спасибо!

Answer 1

Возможно, вы захотите рассмотреть обобщения Hall's marriage theorem и/или assignment problem.

Идея этой парадигмы заключается в создании двудольного графа, где узлы люди и крупы, с ребром между человеком p и зерновых c если p проголосовали за c.Цель состоит в том, чтобы выбрать 3 злаки, такие, что график в результате удаления всех других зерновых является

1. подключен (все будут есть по крайней мере один из выбранных зерновых) и

2. максимизирует минимальное/среднее степень каждого человека (максимизирует мин/Avg счастье)

Вы могли бы вместо того, чтобы думать об этом как Maximum Coverage Problem. В этом случае у вас есть наборы C1,C2,...,Cm где Ci это набор людей, которые любят злаки i. Для вас, например, принимая злаки и людей, в порядке, указанном в таблице, у вас есть

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

Пусть n быть число людей, так что Ci является подмножеством {1,2,...,n}. Цель состоит в том, чтобы найти k множеств так, чтобы мощность объединения была максимизирована. Если существует несколько решений, выберите ту, которая минимизирует мощность пересечений (сводит к минимуму количество, на которое доминирует один человек) или максимизирует количество повторений наименее частого элемента (максимизирует счастье наименее счастливого человека).

Для этого примера наименьший k, для которого покрыты все элементы, является k=3 и дает уникальное решение C2,C3,C4.

Однако вы смотрите на это, у вас есть NP-проблема, но есть известные алгоритмы для их решения (ознакомьтесь с статьями по википедии для ссылок).

Answer 2

Нет идеальной системы голосования - см. http://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem. Были предприняты различные попытки преодолеть это, сгибая правила, в том числе http://en.wikipedia.org/wiki/Range_voting.

Идея, близкая к диапазону голосования, - дать всем 12 голосов и позволить им распространять их по своему усмотрению. Если вы предполагаете, что люди, у которых есть несколько вариантов, распределяют свои 12 голосов одинаково - 12x1 или 6x2 или 4x3 или 3x4 - тогда я думаю, что вы получите желаемый результат, а Lucky Charms получит в общей сложности 10 голосов и всего остального получая больше, чем это.

Answer 3

Если количество зерновых мало, вы можете просмотреть вашу проблему как проблему подмножество переплете и грубой силой свой путь найти то, что конфигурация дает самый «Счастливости»

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

Вы все еще есть проблемы однако, чтобы определить подходящую функцию счастья. Например, вы можете выбрать функцию счастья, которая в качестве первого приоритета вычисляет количество людей, которые могут съесть любую пищу. Затем, в качестве второго приоритета, число людей, которые любят два злаковых, а затем тех, кто любит три злака и так далее.

Плюсы: Если вы можете определить функцию счастья, это дает гарантированный наилучший результат.

Против: Вы должны уметь определить функцию счастья.