애로의 불가능성 정리(Arrow's impossibility theorem)
후보가 셋 이상이고 유권자가 유한히 많을(둘 이상일) 때 개인들의 순위를 모아 사회의 순위를 내는 규칙이 어떤 순위 조합에도 답하고, 만장일치를 존중하고, 두 후보의 사회적 순서를 그 두 후보에 대한 개인들의 순서만으로 정한다면, 그 규칙은 한 사람의 순위를 그대로 따르는 독재뿐이다(케네스 애로, 1951).
세 사람이 후보 A, B, C에 순위를 매겼습니다. 첫째는 A > B > C, 둘째는 B > C > A, 셋째는 C > A > B입니다. 두 후보씩 다수결로 겨루면 A가 B를, B가 C를, C가 A를 2 대 1로 이깁니다. 개인은 모두 앞뒤가 맞는 순위를 적었는데 다수결로 모은 결과는 돌고 돕니다. 1785년 프랑스의 콩도르세 후작이 적어 둔 이 현상을 콩도르세의 역설(Condorcet paradox)이라 합니다. 1951년 미국의 경제학자 케네스 애로는 이것이 다수결만의 결함이 아니라, 순위를 모으는 모든 규칙이 피할 수 없는 일임을 증명했습니다.
애로는 규칙에 네 가지를 요구했습니다. (1) 사람들이 어떤 순위를 적어 내든 답을 낸다. (2) 답은 모든 후보를 앞뒤가 맞게 줄 세운 순위다(A > B, B > C이면 A > C). (3) 모두가 A를 B보다 좋아하면 사회도 그렇다(만장일치 또는 파레토 조건(Pareto condition)). (4) 사회가 A와 B 중 누구를 앞에 두는지는 사람들이 A와 B 사이의 순서를 어떻게 적었는지에만 달려 있다(무관한 후보로부터의 독립(independence of irrelevant alternatives), 흔히 IIA). 정리는 후보가 셋 이상이고 사람 수가 유한할 때, 이 넷을 모두 지키는 규칙에는 반드시 독재자, 곧 언제나 자기 순위가 그대로 사회의 순위가 되는 사람이 있다는 것입니다. 흔한 규칙들은 하나씩 어깁니다. 둘씩 겨루는 다수결은 위처럼 (2)를, 1위 표만 세는 최다득표(plurality voting)와 순위에 점수를 주는 보르다 점수(Borda count)는 (4)를 어깁니다. 누구도 A와 B 사이의 순서를 바꾸지 않았는데 C의 자리만 옮겨서 A와 B의 결과가 뒤집히는 경우가 생기는 것입니다. 예를 들어 세 사람이 A > B > C, 두 사람이 B > A > C라고 적으면, 보르다 점수(1위 2점, 2위 1점)로 A가 8점, B가 7점입니다. 뒤의 두 사람이 C만 A 위로 올려 B > C > A라고 적으면, A–B 순서를 바꾼 사람이 없는데도 A 6점, B 7점으로 뒤집힙니다.
증명의 핵심을 따라가 봅시다. 네 조건을 지키는 규칙이 있다고 가정하고, 다섯 사람이 모두 B를 꼴찌에 둔 투표에서 출발해 한 사람씩 차례로 B를 맨 위로 올립니다. 사람들의 A와 C 사이 순서는 아무렇게나 두어도 됩니다. 조건들이 사회의 순위를 어디까지 강제하는지를 단계마다 봅니다. 규칙의 속은 모르니 B가 사회에서 뛰어오르는 사람이 몇 번째인지도 모릅니다. 그 사람을
둘째 단계의 주장, 곧 모든 사람이 B를 맨 위나 맨 아래에 두면 사회도 B를 맨 위나 맨 아래에 둔다는 것은 이렇게 보입니다. 사회가 A > B > C처럼 B를 가운데 두었다고 합시다. 이제 사람마다 C를 A 바로 위로 옮깁니다. B가 맨 위나 맨 아래인 사람에게 이 옮김은 A–B, B–C 순서를 바꾸지 않으니 (4)에 따라 사회는 여전히 A > B, B > C이고, 이행성(transitivity)으로 A > C여야 합니다. 그런데 이제 모든 사람이 C를 A보다 좋아하니 (3)에 따라 C > A입니다. 모순입니다. 이 뼈대는 2005년 경제학자 존 지나코플로스가 정리한 짧은 증명을 따른 것입니다. 마지막 단계의 논법을 다른 후보 쌍에 되풀이하면, 그 중추적인 사람이 모든 쌍의 순서를 정하는 독재자라는 결론에 이릅니다.
흔한 오해는 이 정리가 민주적인 투표가 불가능하다는 뜻이라는 것입니다. 정리가 말하는 것은 순위만 받아서 순위를 내는 규칙이 어떤 순위 조합에서나 네 조건을 한꺼번에 지킬 수는 없다는 것이고, 실제 선거 규칙은 어느 조건을 언제 양보할지를 고르는 일이라는 것입니다. 조건을 늦추면 불가능이 사라지기도 합니다. 후보가 둘이면 다수결이 모든 조건을 지키고, 사람들의 선호가 한 줄 위의 봉우리 하나 꼴이면(1948년 던컨 블랙) 사람 수가 홀수일 때 둘씩 겨루는 다수결에 순환이 생기지 않습니다. 각자 가장 좋아하는 자리를 줄 위에 늘어놓았을 때 그 중앙값(median)에 있는 사람이 가장 좋아하는 후보가 다른 모든 후보를 이깁니다. 순위 대신 점수를 적게 하는 방식(승인 투표, 점수 투표)은 애로의 틀 밖에 있어서 이 정리가 적용되지 않지만, 대신 다른 약점을 따로 따져야 합니다. 비슷한 결과로, 1973년 앨런 기바드와 1975년 마크 새터스웨이트는 당선자를 하나 정하는 규칙에서 당선될 수 있는 후보가 셋 이상이면, 독재가 아닌 어떤 규칙에서도 거짓 순위를 적어 내는 편이 이득인 경우가 있음을 보였습니다.
이어지는 곳. 조건 (4)는 'C를 움직이는 모든 변화에 대해 A–B 판정이 불변'이라는 요구이고, 증명은 이 불변성들이 서로 부딪히게 만드는 것입니다. B를 한 사람씩 올리다 보면 어딘가에서 결과가 뒤집힌다는 단계는 사잇값 정리의 이산판처럼 생겼습니다. 사람과 병원을 짝짓는 안정 매칭(stable matching)에도 비슷한 불가능성이 있어서, 안정적인 짝을 찾는 어떤 방법도 양쪽 모두에게 솔직함이 최선이도록 만들 수는 없습니다(앨빈 로스, 1982). 순위를 정하는 일이 가능한 순서, 곧 순열(permutation) 가운데 하나를 고르는 일이라는 점에서 이 정리는 조합론(combinatorics)의 결과이기도 합니다.