"모두들 행복하게"투표 알고리즘은 무엇입니까?

Question

대다수의 득표 수와 득표 수를 바탕으로 승자를 선정하는 투표 알고리즘을 찾고 있습니다.

실생활의 예 :

우리의 회사는 시리얼 바있다. 우리는 3 가지 시리얼을위한 공간이 있습니다. 우리는 직원들이 원하는 곡물에 투표하도록 허용하고 싶습니다.

우리가 단지 (어떤 이유로 든) 1 특정 시리얼을 먹을 수있는 직원의 소수 민족이 될 수 있으며, 우리가 그들을주고 싶습니다 때문에 엄격 인기 에 따라 상위 3 우승자를 선택하지 않으

가능한 한 특별 수당 .

다음 결과가 주어지면 알고리즘이 우리에게 제공하고자하는 결과가 있습니다.

I 순위 이런 종류의 작업을 수행하는 알고리즘을 찾고 있어요. 당신이 적어도 내가 찾고있는 것의 이름을 제공 할 수 있다면 그것을 더 잘 찾을 수있는 큰 도움이 될 것입니다. :)

고마워요!

Answer 1

Hall's marriage theorem 및/또는 assignment problem의 일반화를 고려해 볼 수 있습니다. 이 패러다임에 대한

아이디어는 노드가 사람과 곡물이있는 곳 p가 c 투표하면 사람 p, 시리얼 c 사이의 가장자리로 된 그래프를 만드는 것입니다.목표는 다른 모든 곡물을 제거하는 결과 그래프가되도록 3 시리얼을 선택하는 것입니다

1. 연결 및

2. 최소/평균을 극대화 (모든 사람이 적어도 선택한 곡물 중 하나를 먹을 것이다) 각 사람의 정도는

당신은 대신 Maximum Coverage Problem으로 이것에 대해 생각할 수있는 (분/평균 행복을 극대화). 이 경우 C1,C2,...,Cm 집합이 있습니다. Ci은 시리얼 i을 좋아하는 사람들의 집합입니다. 당신이 예를 들어, 표에 나열된 순서대로 곡물 사람들을 복용, 당신은

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

이 Ci이 {1,2,...,n}의 일부가되도록 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 표를주고 원하는대로 배포하도록 허용하는 것입니다. 여러 가지 선택을 가진 사람들이 12x1 또는 6x2 또는 4x3 또는 3x4 등의 12 가지 투표를 똑같이 배포한다고 가정하면, 럭키 챠 무스가 총 10 표를 얻는 등 원하는 결과를 얻을 수 있다고 생각합니다. 점점 더. 곡물의 수가 작은 경우

Answer 3

, 당신은 구성이 대부분 "행복을 찾아서"

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

당신은 여전히 ​​문제가 있습니다 무엇을 찾는 부분 집합 덮개 문제와 폭력으로 길을 문제를 볼 수 있습니다 그러나 적절한 행복 기능을 정의하는 것. 예를 들어 우선 순위에 따라 음식을 먹는 사람의 수를 계산하는 행복감 함수를 선택할 수 있습니다. 다음으로 두 번째 우선 순위는 곡물 중 두 가지를 좋아하는 사람의 수이며 세 번째 곡물을 좋아하는 사람의 수입니다.

장점 : 행복 기능을 정의 할 수 있으면 최상의 결과를 보장합니다.

단점 : 행복 기능을 정의 할 수 있어야합니다.