#condorcet method

[innabesedina]

Nicolas de Condorcet

NICOLAS DE CONDORCET WAS A FRENCH PHILOSOPHER AND MATHEMATICIAN. HIS IDEAS, INCLUDING SUPPORT FOR A LIBERAL ECONOMY, FREE AND EQUAL PUBLIC INSTRUCTION, CONST...

[changwoo-hacks]

데비안의 선호 투표 해석하는 방법

데비안은 가끔 "투표"를 한다. 데비안 개발자라면 투표권이 주어지는데, 마침 2007년 리더 투표가 있었고 어제 Sam Hocevar가 당선되었다는 결과 발표가 있었다.  음 그런데 이 웹페이지를 보면 대체 무슨 소리인지 잘 알기 어렵다. 뭔가 복잡한 용어가 등장하면서 수식이 등장해서 잘 파악하기 어렵다. 나도 처음에는 상당히 생소했기에, 한번 이 글에서 데비안의 투표 방법인 Condorcet method를 설명해 보려고 한다. 투표자의 갈등 우리가 정치 활동을 하면서 하게 되는 투표는 그 방법이 아주 간단하다. 후보가 몇 개가 있으면 그 중에서 자기가 원하는 후보를 하나 찍고 가장 많은 투표를 획득한 후보가 당선/선택된다. 하지만 찬반투표가 아니라면 실제로 우리가 투표를 할 때도 흔히 고민하게 되는 다음과 같은 문제가 있다.

사표 방지 심리 - 내가 좋아하는 후보는 따로 있는데, 당선이 안 될 것 같다.  차라리 정책이 비슷하면서 당선 가능성이 있는 사람에게 표를 몰아주고 싶다.

절대적 지지 후보 없음 - 이 놈이나 저 놈이나 다 똑같다. 역시 당선 가능성 있는 사람중에 차악을 선택해야 되나?

우리 일상생활의 "한 표"의 행사라는 게 그렇게 고민덩어리이다. 내가 가진 신성한 이 표가 너무 무의미해 보인다. 결국 유행에 밀려 유력 후보를 찍을 수밖에 없고, 정치적인 성향이 분명치 않은 사람은 자기 의견을 투표로 표현하기도 어렵다. 선호 관계 투표 Condrcet method에서는 적어도 위와 같은 고민은 없다.  투표를 할 때 한 사람을 찍는 게 아니라, 여러 명의 선호 관계를 기술하는 방식이기 때문이다.  데비안의 투표 용지를 이용해 보면,

[   ] Choice 1: cwryu [   ] Choice 2: crew [   ] Choice 3: clue [   ] Choice 4: None Of The Above

투표용지는 1234 네 가지의 선택 사이의 선호 관계를 기술하게 된다.  더 선호하는 쪽에 작은 번호를 붙인다.  "2 1 3 4"를 써 넣으면 crew가 cwryu다는 좋다는 이야기이고 cwryu가 clue보다 좋다는 이야기이다.  내가 원하는 후보가 choice 1이지만 당선 가능성이 없다면 그냥 원하는 후보를 1로 쓰고 다음에 차악을 최악보다 우선적으로 선택하면 된다. 

[ 2 ] Choice 1: cwryu [ 1 ] Choice 2: crew [ 3 ] Choice 3: clue [ 4 ] Choice 4: None Of The Above

그래도 좀 나은 후보가 1번인데 2번이나 3번이나 다 똑같은 놈같으면?  Choice 1에 1번을 붙이고 2/3번에 같은 번호를 쓰면 된다.

[ 1 ] Choice 1: cwryu [ 2 ] Choice 2: crew [ 2 ] Choice 3: clue [ 3 ] Choice 4: None Of The Above

개표 왜 이렇게 써 넣어도 내 의견이 반영될 수 있는지, 개표 과정을 설명하면...  이렇게 수집된 투표는 수 많은 "A to B" 선호의 집합이라고 할 수 있다.  몇 가지 후보 중에서 후보가 A와 B 둘이라고 할 때 A를 B보다 선호하는 사람이 있을 수도 있고 B를 A보다 선호하는 사람이 있을 수 있다.  2007년 리더 투표 페이지의 beat matrix가 그 투표를 모아 놓은 것이다. 그러면 각각의 pair에 대해서 어느쪽을 선호하는 사람이 더 많은 지 생각할 수 있다. 각각의 후보를 node로 하고, 후보 A가 B보다 우세하다는 관계를 A to B의 edge로 표현하면 웹페이지에 나온 그래프가 된다.  즉 사표 방지심리를 가질 필요없이, 내가 선호하는 후보를 1번으로 기입하면 설령 그 후보가 당선권에서 멀어지더라도, 차악을 선택할 수 있고 그 표가 똑같이 반영된다.  절대적으로 선호하는 후보가 없더라도 특히 싫어하는 후보를 명시한다면 그 후보를 떨어뜨리는 정도로라도 자기 표로 의사를 표현할 수 있다. 애매한 경우 이 그래프가 이번 2007년 리더 투표처럼 한 사람이 모든 사람을 이기면 관계가 없지만 (이런 식으로 결과가 나오는 게 보통), 이 관계가 circular relation이 된다면 복잡해 진다. 이런 상황에서는 (오리지널 Condorcet method는 이 상황에 대한 해결 방법이 없지만) Schulze dropping 방법에 따라 몇 가지 기준에 따라 승자를 결정한다.  첫 번째로 선호 관계에서 얼마나 더 많은 후보를 제쳤느냐가 기준이 된다. 즉 그래프에서 outgoing edge와 incoming edge의 개수를 기준으로 승자를 결정할 수 있다.  그리고 만약에 이걸로도 결정할 수 없는 상황이 된다면, 그렇게 circular relation이 되는 관계만을 추려낸 다음에 가장 약한 (표 차이가 작은) 선호관계를  하나씩 없애서 circular 관계가 아닐 때까지 계속 한다.  예를 들어 A와 B와 C가 circular하게 선호하는 관계라면 A to B, B to C, C to A의 관계중에 가장 약한 관계를 drop한다. 그래도 동률이라면???? ... ... 우리나라 국회의원 선거처럼 나이 많은 사람이 당선되는 건가?   -_- 그 상황이 된다면 투표 알고리즘만으로는 해결할 방법이 없다.  그런 상황이 계속해서 벌어진다면, 과연 투표라는 게 인간 사회의 의사결정 방법으로 올바른 방법인지 진지하게 생각해 볼 필요가 있을 듯...