우리는 거대한 사회를 이루며 살아 갑니다. 그 속에는 다양한 군상들이 존재하죠. 모든 사회 구성원들의 성격이나 가치관이 같을리 만무하므로 사회는 여러 요인에 의해 갈등이 발생할 수밖에 없습니다. 왕정이나 독재 하에서는 결국 절대 권력을 가진 사람이나 집단이 모든 의사 결정을 담당할 것이므로 (바람직하지는 않지만) 갈등을 효율적으로 해소할 수 있습니다. 하지만 우리나라를 포함한 많은 국가들이 채택하고 있는 민주주의 체제에서는 갈등을 합리적으로 해소하여 사회적 합일을 이루는 방안을 마련해야 합니다. 과연 어떻게 하면 될까요?
안타깝게도 합리적인 조건을 모두 만족하면서 사회적인 합치를 이루는 방법은 존재하지 않습니다. 이는 저명한 경제학자인 케네스 애로우(Kenneth Arrow)에 의해 증명이 되었는데요. 이번 포스트에서는 그의 불가능성 정리에 대해서 알아 보겠습니다.
저는 컴퓨터 과학도입니다. 따라서 경제학이나 정치 과학 분야의 지식의 폭이 좁습니다. 다만 요즘 경제학, 특히, 후생 경제학 분야에서 활용되는 컴퓨터 과학에 대해 공부하고 있습니다. 그 와중에 애로우의 불가능성 정리에 대해서 알게 되었습니다. 애초에 불가능하므로 컴퓨터로 해결할 '건덕지'도 없어서 컴퓨터 과학과는 큰 관련이 없어 보이나 그 자체로 흥미로운 주제라고 생각하여 정리해 봅니다. 혹여나 글에 오류가 있는 경우에는 알려 주시면 감사하겠습니다.
문제 모델
수학을 비롯한, 컴퓨터 과학, 경제학 등 대부분의 학문은 복잡한 현상을 특정 모델로 단순화시키는 것에서부터 시작합니다. 이번에는 우리 사회를 다음과 같은 모델로 표현해 보겠습니다. 총 \(n\) 명의 구성원이 있습니다. 아무 순서대로 각각에게 구성원 \(1\)부터 구성원 \(n\)이라고 이름을 붙이겠습니다. 이 사회에서 어떤 쟁점이 발생했고 이에 대해 총 \(m\) 개의 후보가 대안으로 제시되었다고 합시다. 아무 순서대로 각 대안 후보들을 후보 \(1\)부터 후보 \(m\)이라고 부르겠습니다.
각 구성원 \(i\)는 모든 후보를 일렬로 세운 선호 리스트를 가집니다. 즉, 임의의 서로 다른 두 후보에 대해 둘 중 하나는 반드시 더 좋아해야 하며, 만약 후보 \(a\)보다 후보 \(b\)를 좋아하고 후보 \(b\)보다 후보 \(c\)를 좋아하면 후보 \(a\)보다 후보 \(c\)를 반드시 좋아해야 합니다. 수학적인 표현을 쓰자면, 구성원의 선호 리스트는 후보들의 순열(permutation)로 볼 수 있습니다.
간단히 나타내기 위해, 만약 구성원 \(i\)가 후보 \(a\)보다 후보 \(b\)를 좋아하면, \[ a \prec_i b \]라고 표현하겠습니다. 반대로 후보 \(b\)보다 후보 \(a\)를 좋아하는 것은 \[ a \succ_i b \]로 적겠습니다. 후보들의 모든 순열을 모아 놓은 집합을 \(\Pi\)라고 했을 때, 아래에서는 \(\prec_i \in \Pi \)를 구성원 \(i\)의 선호 리스트 자체로 부르기도 합니다.
우리가 해야 할 일은 모든 구성원으로부터 각자의 선호 리스트를 받은 다음 '합리적'인 조건들을 만족하면서 모든 후보를 일렬로 나열하는 것입니다. 만족해야 하는 조건들은 다음 절에서 알아 보겠습니다. 수학 기호로 이를 나타내어 보면, 구성원들의 선호 리스트를 입력으로 받고 후보들의 나열 하나를 출력하는 어떤 함수 \(f : \Pi^n \to \Pi \)에 대해 \[ \prec \;= f(\prec_1, \cdots, \prec_n) \]이라고 하면, 우리의 목표는 \( \prec \)가 다음 절에서 기술할 조건들을 모두 만족하도록 만드는 것입니다. 이때, \(f\)와 같은 함수를 우리는 사회 후생 함수(social welfare function)라고 부릅니다. 또, 함수의 결과인 \(\prec\)는 사회적으로 합의된 선호라고 부르겠습니다. 참고로 '사회 후생 함수'는 널리 통용되는 표현입니다만, '사회적으로 합의된 선호'는 제가 적당히 지은 것입니다.
사회 후생 함수의 조건
이번 절에서는 사회 후생 함수가 갖추어야 할 합리적인 조건들에 대해서 알아 보겠습니다. 총 세 가지의 조건이 있으며, 각각 다음과 같습니다.
- 만장일치성(unanimity)
- 관계 없는 대안으로부터의 독립성(independence of irrelevant alternatives)
- 비독재성(non-dictatorship)
만장일치성
임의의 두 후보 \(a\)와 \(b\)에 대해, 만약 모든 구성원이 \(a\)보다 \(b\)를 더 좋아한다면 사회적 합의도 \(a\)보다 \(b\)를 더 좋아하는 방향으로 이루어지는 것이 합리적입니다. 만장일치성은 이를 나타냅니다. 다시 말하자면, 모든 만약 구성원 \(i\)가 \( a \prec_i b \)를 갖는다면, 사회적으로 합의된 선호에서도 \( a \prec b \)를 만족해야 합니다.
관계 없는 대안으로부터의 독립성
개인적으로는 이 조건이 가장 이해하기 어려운 조건이 아닌가 싶습니다. 처음에 저는 이 조건이랑 만장일치성이랑 헷갈렸습니다. (사실 제가 읽은 책 자체가 좀 난해하게 적힌 것 같습니다.) 여러 다른 자료를 참조한 끝에 이 조건이 무엇인지 정확히 이해할 수 있었습니다.
이 조건을 이해하기 위해서는 두 가지 상황을 고려해야 합니다. 첫 번째 상황에서는 각 구성원 \(i\)가 \( \prec_i \)를 선호 리스트로 가지며, 두 번째 상황에서는 \( \prec'_i \)를 선호 리스트로 갖습니다. 첫 번째 상황일 때 사회적으로 합의된 선호를 \( \prec \), 두 번째 상황일 때 사회적으로 합의된 선호를 \( \prec' \)이라고 하겠습니다.
이제 임의의 두 후보 \(a\)와 \(b\)에 대해서, 모든 구성원 \(i\)에 대해 만약 \( a \prec_i b \)이면 \( a \prec'_i b \)이고, 반대로 만약 \( a \succ_i b \)이면 \( a \succ_i b \)라고 합시다. 다시 말해, 두 상황 모두에서 모든 구성원의 선호 리스트에서 \(a\)와 \(b\)의 상대적인 위치가 동일한 상태를 뜻합니다. 그렇다면 비록 \(a\)나 \(b\)가 아닌 후보들 때문에 \( \prec_i \)와 \( \prec'_i \)가 같지 않을 수는 있겠지만, 최소한 \(a\)와 \(b\)에 대해서 만큼은 \(a\)를 좋아하든 \(b\)를 좋아하든 모든 구성원이 상대적으로 동일한 선호를 가지므로, 첫 번째 상황일 때 합의된 선호 \(\prec\)에서의 \(a\)와 \(b\)의 상대적인 위치는 두 번째 상황일 때 합의된 선호 \(\prec'\)에서의 상대적인 위치와 동일해야 합리적입니다. 다시 말해, \(a \prec b\)라면 \( a \prec' b \)이고, \( a \succ b \)라면 \( a \succ' b \)를 만족해야 합니다. 이 성질을 관계 없는 대안으로부터의 독립성이라고 부릅니다.
약간은 복잡하지만, 아래와 같이 수학 기호를 사용하면 간결히 표현할 수 있습니다.
\[ \forall i \; ( a \prec_i b \iff a \prec'_i b) \Longrightarrow ( a \prec b \iff a \prec' b )\]
비독재성
독재는 민주주의의 근간을 훼손하는 일입니다. 민주주의를 채택하는 많은 나라에서는 이를 방지하기 위한 다양한 방책을 마련해 놓습니다. 그러니 우리 모델에서도 당연히 독재를 지양해야 마땅합니다. 독재자는 다음과 같이 정의할 수 있습니다. 만약 다른 구성원들이 어떤 선호 리스트를 써서 내든 사회적으로 합의된 선호가 항상 어떤 구성원 \(i\)의 선호 리스트와 동일하다면, 우리는 해당 구성원 \(i\)를 독재자라고 말합니다. 다시 말해, 임의의 \( \prec_1, \cdots, \prec_n \)에 대해, \[ f( \prec_1, \cdots, \prec_i, \cdots, \prec_n ) = \prec_i \]라면 구성원 \(i\)는 독재자입니다. 사회 후생 함수가 비독재성을 만족한다는 의미는 모든 구성원이 독재자가 아니라는 의미입니다.
애로우의 불가능성 정리
이것으로 사회 후생 함수가 갖추어야 할 조건들에 대해서 모두 알아 보았습니다. 위 조건들이 합리적이라는 점은 모두가 동의하시리라 생각합니다. 따라서 모두 만족시키는 것이 가장 바람직한 일이겠지요. 하지만 슬프게도 이는 불가능합니다. 그리고 이 결과가 바로 이번 포스트의 주제인 애로우의 불가능성 정리입니다.
정리 1. 애로우의 불가능성 정리
후보가 세 개 이상일 때, 어떤 사회 후생 함수가 만장일치성과 관계 없는 대안으로부터의 독립성을 만족하면 반드시 독재자가 존재한다.
참고로 후보가 둘이라면 조건을 모두 만족하는 사회 후생 함수가 존재합니다. 한번 생각해 보세요!
증명
만장일치성과 관계 없는 대안으로부터의 독립성을 만족하는 임의의 사회 후생 함수를 가정하겠습니다. 만약 이 함수에 독재자가 있으면 증명이 완료됩니다. 증명은 총 세 단계로 구성됩니다. 첫 번째는 만약 모든 구성원이 어떤 후보 \(a\)를 가장 좋아하거나 가장 싫어하면 사회적으로도 \(a\)는 가장 선호되거나 가장 불호되는 것으로 합의된다는 것입니다. 이때 모두가 동시에 \(a\)를 좋아할 필요도, 싫어할 필요도 없습니다. 어떤 구성원은 \(a\)를 가장 좋아하고, 다른 구성원은 \(a\)를 가장 싫어해도 됩니다. 그냥 \(a\)를 선호 리스트의 중간에 두는 구성원이 없으면 됩니다.
정리 2. 극단적 상황에서의 사회적 합의
어떤 후보 \(a\)를 고정하자. 각 구성원 \(i\)가 다른 임의의 후보 \(d\)에 대해 \( a \succ_i d \) 혹은 \( a \prec_i d \) 중 하나만 만족한다면, 사회적으로 합의된 선호 \(\prec\)에서도 다른 임의의 후보 \(d\)에 대해 \( a \succ d \)이거나 \(a \prec d\)이다.
[증명] 귀류법으로 증명하겠습니다. 만약 \( \prec \)에서 \(a\)가 가장 선호되거나 가장 불호되지 않는다면, \( c \prec a \prec b \)인 서로 다른 두 후보 \(b\)와 \(c\)가 존재합니다. 아래 표는 예시입니다. 마지막 열을 제외한 나머지는 각 구성원들의 선호 리스트를 나타냅니다. 빈칸은 증명에서 상관이 없는 부분이며, 후보가 위에 있을 수록 선호한다는 의미입니다. 마지막 열은 구성원들의 선호 리스트로부터 사회적으로 합의된 선호를 나타냅니다. 현재의 가정이 반영되어 있습니다.
| \(\prec_1\) | \(\prec_2\) | \(\prec_3\) | ... | \(\prec_n\) | \(\prec\) |
| \(a\) | \(a\) | \(b\) | \(b\) | ||
| \(b\) | \(c\) | \(c\) | \(a\) | ||
| \(c\) | \(c\) | ||||
| \(b\) | \(c\) | \(b\) | |||
| \(a\) | \(a\) |
이제 각 구성원 \(i\)에 대해 \( \prec_i \)에서 후보 \(c\)를 후보 \(b\)의 바로 위의 우선 순위에 두겠습니다. 이렇게 얻은 선호 리스트를 \( \prec'_i \)라고 하고, 이 리스트들로부터 합의된 선호를 \(\prec'\)이라고 부르겠습니다. 아래 표에서 \(c\)의 위치가 모두 \(b\) 바로 위에 있는 것을 확인할 수 있습니다.
| \(\prec'_1\) | \(\prec'_2\) | \(\prec'_3\) | ... | \(\prec'_n\) | \(\prec'\) |
| \(a\) | \(a\) | \(c\) | ? | ||
| \(c\) | \(b\) | ? | |||
| \(c\) | \(b\) | \(c\) | ? | ||
| \(b\) | \(b\) | ? | |||
| \(a\) | \(a\) | ? |
\(\prec'\)이 만족하는 성질 두 가지를 알아 봅시다. 첫 번째로, 만들어진 선호 리스트에서는 모든 구성원들이 \(b\)보다 \(c\)를 더 좋아하므로 만장일치성에 의해 \[ b \prec' c \tag{1} \]를 만족할 것입니다. 이제 \(a\)와 \(b\)의 상대적인 위치에 주목해 봅시다. 후보 \(a\)는 \( \prec_i \)와 \(\prec'_i\) 둘 다에서 가장 높은 우선 순위를 갖든지 가장 낮은 우선 순위를 갖습니다. 그러므로 두 리스트에서의 \(a\)와 \(b\)의 상대적인 위치는 동일합니다. 다시 말해, \(a \prec_i b \)라면 \( a \prec'_i b \)이고 \( a \succ_i b \)라면 \( a \succ'_i b \)를 만족합니다. 따라서 원래 \( a \prec b \)를 만족했으므로 관계 없는 대안으로부터의 독립성에 의해 \[ a \prec' b \tag{2} \]도 만족해야 합니다. 같은 원리로 \(a\)와 \(c\)의 상대적인 위치도 모두 동일하므로 \[ c \prec' a \tag{3} \]도 만족해야 합니다. 식 2와 3을 통해서 우리는 \[ c \prec' a \prec' b \]를 이끌어 낼 수 있습니다. 하지만 이는 앞서 구한 식 1과 모순을 이룹니다. ■
이제 두 번째 단계로 넘어가겠습니다. 이번 단계가 증명의 핵심입니다. 여기서 말하고자 하는 것은 후보 \(a\)를 하나 고정했을 때, \(a\)를 제외한 나머지 후보들의 사회적으로 합의된 선호에서의 상대적 위치를 독재적으로 결정하는 구성원이 존재한다는 것입니다.
정리 3. 버금 독재성
어떤 후보 \(a\)를 고정하자. 그러면 다음을 만족하는 구성원 \(i_a\)가 존재한다. \(a\)와 같지 않은 임의의 서로 다른 두 후보 \(b, c\)에 대해, \( b \prec_{i_a} c \)이면 \( b \prec c \)이고, \( b \succ_{i_a} c \)이면 \( b \succ c \)이다.
[증명] 각 구성원 \(i\)로부터 임의의 선호 리스트 \( \prec^\mathsf{(i)}_i \)를 받았다고 합시다. 이때 사회적으로 합의된 선호를 \( \prec^\mathsf{(i)} \)라고 부르겠습니다. 아래 표는 예시입니다. 빈칸은 증명에서 상관이 없는 부분을 나타냅니다.
| \(\prec^\mathsf{(i)}_1\) | \( \prec^\mathsf{(i)}_2 \) | \( \cdots \) | \( \prec^\mathsf{(i)} _{i-1}\) | \( \prec^\mathsf{(i)}_i \) | \(\cdots\) | \( \prec^\mathsf{(i)}_n \) | \( \prec^\mathsf{(i)} \) |
| \(c\) | \(a\) | ? | |||||
| \(a\) | \(c\) | ? | |||||
| \(c\) | ? | ||||||
| \(b\) | \(b\) | \(b\) | \(b\) | ? | |||
| \(b\) | ? | ||||||
| \(a\) | \(c\) | ? | |||||
| \(c\) | \(a\) | ? | |||||
| \(a\) | ? |
우리의 목표는 \( a \)가 아닌 임의의 \(b, c\)에 대해서, \( b \prec^\mathsf{(i)}_{i_a} c \)이면 \( b \prec^\mathsf{(i)} c \)이고, \( b \succ^\mathsf{(i)}_{i_a} c \)이면 \( b \succ^\mathsf{(i)} c \)를 만족하는 구성원 \(i_a\)를 찾는 것입니다.
각 구성원 \(i\)에 대해, \( \prec^\mathsf{(i)}_i \)에서 다른 후보들의 상대적인 위치는 건드리지 않고 \(a\)만 빼서 가장 아래에 두는 선호 리스트를 생각해 보겠습니다. 그러면 \(a\)는 모든 후보보다 낮은 우선 순위를 가지므로 만장일치성에 의해 이때는 \(a\)를 가장 낮은 순위에 두는 것으로 사회적으로 합의될 것입니다.
| - | - | \( \cdots\) | - | - | \(\cdots\) | - | - |
| \(c\) | ? | ||||||
| \(c\) | ? | ||||||
| \(c\) | \(b\) | ? | |||||
| \(b\) | \(b\) | \(b\) | \(b\) | ? | |||
| \(c\) | ? | ||||||
| \(c\) | ? | ||||||
| ? | |||||||
| \(a\) | \(a\) | \(a\) | \(a\) | \(a\) | \(a\) |
반대로 이번에는 모든 구성원들이 \(a\)를 가장 선호한다고 합시다. 역시나 다른 후보들의 상대적인 위치는 건드리지 않습니다. 이번에는 \(a\)가 모든 후보보다 선호되므로 만장일치성에 의해서 사회적으로 합의된 선호에서도 \(a\)는 가장 높은 우선 순위를 가질 것입니다.
| - | - | \( \cdots \) | - | - | \(\cdots\) | - | - |
| \(a\) | \(a\) | \(a\) | \(a\) | \(a\) | \(a\) | ||
| \(c\) | ? | ||||||
| \(c\) | ? | ||||||
| \(c\) | \(b\) | ? | |||||
| \(b\) | \(b\) | \(b\) | \(b\) | ? | |||
| \(c\) | ? | ||||||
| \(c\) | ? | ||||||
| ? |
다음과 같은 작업을 생각해 봅시다. 처음에는 모든 구성원이 \(a\)를 가장 아래에 둡니다. 그다음, 구성원 1부터 한 명씩 차례로 \(a\)를 선호 리스트의 가장 높은 곳에 둡니다. 당연히 \(a\)를 제외한 나머지 후보들의 상대적인 위치는 변하지 않습니다.
우리는 이 작업을 진행하는 동안 매번 구성원들의 선호 리스트가 정리 2의 조건을 만족한다는 것을 알 수 있습니다. 따라서 사회적으로 합의된 선호에서는 매번 \(a\)를 가장 높은 우선 순위에 두든지 가장 낮은 우선 순위에 두어야 합니다. 앞의 논의에 의해 작업을 시작할 때는 모든 구성원들이 \(a\)를 가장 싫어하므로 \(a\)가 가장 낮은 우선 순위를 갖는 것으로 사회적으로 합의됩니다. 반대로 작업을 마칠 때는 모든 구성원들이 \(a\)를 가장 좋아하므로 \(a\)가 가장 높은 우선 순위를 갖는 것으로 합의되죠. 따라서 분명 이 작업 중 언젠가 어떤 구성원의 선호 리스트에서 \(a\)가 가장 낮은 위치에서 가장 높은 위치로 변하는 순간 사회적으로 합의된 선호에서도 \(a\)의 위치가 가장 낮은 곳에서 가장 높은 곳으로 바뀌는 때가 적어도 한 번은 있습니다. 처음으로 이 상태를 일으킨 구성원을 \(i_a\)라고 부르겠습니다.
\(i_a\)라고 이름을 붙인 것을 알 수 있듯이 해당 구성원이 우리가 현재 찾고 있는 구성원입니다. 이를 증명해 보겠습니다. 위 작업에서 구성원 \(i_a\)가 \(a\)를 가장 낮은 곳에서 가장 높은 곳으로 올리기 바로 직전의 상태는 다음과 같습니다. 그때의 각 구성원 \(i\)의 선호 리스트를 \( \prec^\mathsf{(ii)}_i \), 사회적으로 합의된 선호를 \( \prec^\mathsf{(ii)} \)라고 부르겠습니다. 참고로 이때는 \(a\)가 사회적으로 가장 불호되고 있다는 것을 확인하시기 바랍니다.
| \( \prec^\mathsf{(ii)}_1 \) | \( \prec^\mathsf{(ii)}_2 \) | \( \cdots \) | \( \prec^\mathsf{(ii)}_{i_a - 1} \) | \( \prec^\mathsf{(ii)}_{i_a} \) | \(\cdots\) | \( \prec^\mathsf{(ii)}_n \) | \( \prec^\mathsf{(ii)} \) |
| \(a\) | \(a\) | \(a\) | ? | ||||
| \(c\) | \(c\) | ? | |||||
| \(b\) | ? | ||||||
| \(c\) | \(b\) | ? | |||||
| \(b\) | \(b\) | \(b\) | \(c\) | ? | |||
| ? | |||||||
| \(c\) | ? | ||||||
| \(a\) | \(a\) | \(a\) |
이제 구성원 \(i_a\)가 \(a\)를 가장 높은 곳에 올린 다음의 상태도 생각해 봅시다. 그때의 각 구성원 \(i\)의 선호 리스트를 \( \prec^\mathsf{(iii)}_i \), 사회적 합의를 \( \prec^\mathsf{(iii)} \)라고 하겠습니다. 이때는 \(a\)가 가장 높은 우선 순위를 갖는 것으로 사회적으로 합의됨을 확인하시기 바랍니다.
| \( \prec^\mathsf{(iii)}_1 \) | \( \prec^\mathsf{(iii)}_2 \) | \( \cdots \) | \( \prec^\mathsf{(iii)}_{i_a - 1} \) | \( \prec^\mathsf{(iii)}_{i_a} \) | \(\cdots\) | \( \prec^\mathsf{(iii)}_n \) | \( \prec^\mathsf{(iii)} \) |
| \(a\) | \(a\) | \(a\) | \(a\) | \(a\) | |||
| \(c\) | \(c\) | ? | |||||
| ? | |||||||
| \(c\) | \(b\) | \(b\) | ? | ||||
| \(b\) | \(b\) | \(b\) | ? | ||||
| \(c\) | ? | ||||||
| \(c\) | ? | ||||||
| \(a\) | ? |
마지막으로 위 상태와 유사하나 약간 다른 상태를 생각해 보고자 합니다. 일반성을 잃지 않고 구성원 \( i_a \)가 \(b\)를 \(c\)보다 상대적으로 선호한다고 하겠습니다. 굳이 앞에서 나온 선호 리스트 중 어느 것에서 \(b\)를 선호하는지를 밝히지 않았습니다. 그 이유는 \( \prec^\mathsf{(i)}_{i_a} \)이든 \( \prec^\mathsf{(ii)}_{i_a} \)든 \( \prec^\mathsf{(iii)}_{i_a} \)든 \(a\)를 제외한 나머지 후보들의 상대적인 위치는 모두 동일하기 때문입니다. 이제 \( \prec^\mathsf{(iii)}_{i_a} \)에서 \(b\)는 \(a\)의 바로 위(즉, 가장 위)에 \(c\)는 \(a\)의 바로 아래에 두겠습니다. 나머지 구성원의 선호 리스트는 상태 \( \mathsf{(ii)} \)와 \( \mathsf{(iii)} \)와 동일합니다. 이때의 구성원 \(i\)의 선호 리스트를 \( \prec^\mathsf{(iv)}_i \), 사회적으로 합의된 선호를 \( \prec^\mathsf{(iv)} \)라고 부르겠습니다.
| \( \prec^\mathsf{(iv)}_1 \) | \( \prec^\mathsf{(iv)}_2 \) | \( \cdots \) | \( \prec^\mathsf{(iv)}_{i_a - 1} \) | \( \prec^\mathsf{(iv)}_{i_a} \) | \(\cdots\) | \( \prec^\mathsf{(iv)}_n \) | \( \prec^\mathsf{(iv)} \) |
| \(a\) | \(a\) | \(a\) | \(b\) | ? | |||
| \(c\) | \(a\) | \(c\) | ? | ||||
| \(c\) | ? | ||||||
| \(c\) | \(b\) | ? | |||||
| \(b\) | \(b\) | \(b\) | ? | ||||
| ? | |||||||
| \(c\) | ? | ||||||
| \(a\) | ? |
이제 \(c \prec^\mathsf{(iv)} b\)임을 보이겠습니다. 먼저 상태 \( \mathsf{(ii)} \)와 상태 \( \mathsf{(iv)} \)를 비교해 봅시다. \( i_a \)를 뺀 나머지 구성원은 동일한 선호 리스트를 갖습니다. 구성원 \(i_a\)는 대신 \( a \prec^\mathsf{(ii)}_{i_a} b \)와 \( a \prec^\mathsf{(iv)}_{i_a} b \)를 만족합니다. 따라서 상태 \( \mathsf{(ii)} \)와 상태 \( \mathsf{(iv)} \)에서 \(a\)와 \(b\)의 상대적인 선호도는 모든 구성원이 동일합니다. 게다가 \( \prec^\mathsf{(ii)} \)에서 \(a\)는 가장 낮은 우선 순위를 가지므로 자명하게 \( a \prec^\mathsf{(ii)} b \)를 만족합니다. 따라서 관계 없는 대안으로부터의 독립성에 의해 \[ a \prec^\mathsf{(iv)} b \]임을 알 수 있습니다. 같은 이치로 상태 \( \mathsf{(iii)} \)와 상태 \(\mathsf{(iv)}\)에서의 \(a\)와 \(c\)의 상대적인 위치를 비교하면 \[ c \prec^\mathsf{(iv)} a \]임을 얻을 수 있습니다. 위 두 식을 조합하면 \[ c \prec^\mathsf{(iv)} b \]가 됩니다.
앞에서 설명했다시피 모든 구성원들의 선호 리스트에서 \(a\)를 제외한 후보들의 상대적인 위치는 상태 \( \mathsf{(i)} \), \( \mathsf{(ii)} \), \( \mathsf{(iii)} \) 모두 동일합니다. 마지막으로 상태 \( \mathsf{(iv)} \)에서는 구성원 \(i_a\)의 선호 리스트가 바뀌지만, \( c \prec^\mathsf{(iv)} b \)는 유지됩니다. 따라서 모든 구성원들이 생각하는 \(b\)와 \(c\)의 상대적인 선호도는 상태 \(\mathsf{(i)}\)과 \( \mathsf{(iv)} \)에서 모두 동일합니다. 따라서 관계 없는 대안으로부터의 독립성에 의해 \[ c \prec^\mathsf{(i)} b \]임을 보일 수 있습니다. 이것으로 증명이 마무리됩니다. ■
정리 3은 매우 강력한 조건입니다. 정리 3에서 보장된 구성원 \(i_a\)는 \(a\)를 제외한 나머지 후보들에 대해서는 자신이 원하는 순서대로 사회적으로 합의된 선호에 영향을 미칠 수 있기 때문이죠. 다만 이것만으로는 \(i_a\)를 독재자로 단정할 수 없습니다. 후보 \(a\)가 어떻게 될지를 모르기 때문이죠. 다음 정리는 \(i_a\)가 실제로 독재자임을 보이는 데 요긴하게 활용됩니다.
정리 4. 버금 독재성과 독재성
임의의 서로 다른 두 후보 \(a\)와 \(b\)에 대해, 정리 3을 통해 각각 보장된 구성원을 \(i_a\), \(i_b\)라고 하자. 그러면 반드시 \(i_a = i_b\)이다.
[증명] 정리 3의 증명에서 사용했던 작업을 다시 해보겠습니다. 처음에는 모든 구성원의 선호 리스트에서 \(a\)를 가장 낮은 곳에 둔 채로 시작합니다. 그 다음, 구성원 1부터 구성원 \(n\)까지 차례로 \(a\)를 선호 리스트의 가장 높은 곳에 올리겠습니다. 정리 3의 증명에서 우리는 다음을 알 수 있습니다. 구성원 \(i_a\)가 \(a\)를 선호 리스트의 가장 높은 곳에 올리기 전에는 사회적으로 합의된 선호에서 \(a\)는 가장 낮은 우선 순위를 가질 것입니다. 반대로 구성원 \(i_a\)가 \(a\)를 가장 높은 우선 순위에 둔 순간 사회적으로 합의된 선호에서도 \(a\)가 가장 높은 우선 순위를 갖게 됩니다.
\(a\)도 \(b\)도 아닌 아무 후보 \(c\)를 하나 갖고 오겠습니다. 후보자의 개수는 세 개 이상이므로 그러한 후보를 항상 찾을 수 있습니다. 그러면 정리 3에 의해 만약 후보자 \(i_b\)가 \(a\)를 \(c\)보다 좋아한다면 사회적으로 합의된 선호에서도 \(a\)가 \(c\)보다 높은 위치에 있을 것이고, 반대로 \(a\)보다 \(c\)를 좋아한다면 \(c\)가 더 위에 있는 것으로 합의될 것입니다.
만약 \(i_b < i_a\)라고 해 봅시다. 그러면 위 작업에서 \(i_a\)가 \(a\)를 가장 위에 올리기 전에 \(i_b\)가 \(a\)를 가장 위에 올릴 것입니다. \(i_b\)의 선호 리스트에서 \(a\)가 가장 위에 있으므로 분명 \(a\)를 \(c\)보다 좋아할 것입니다. 따라서 사회적으로 합의된 선호에서도 \(a\)가 \(c\)보다 위에 있어야 합니다. 하지만 \(i_a\)가 아직 \(a\)를 가장 높은 우선 순위에 두지 않았기 때문에 \(a\)는 여전히 사회적으로 합의된 선호에서 가장 아래에 위치해야 합니다. 이는 모순입니다.
비슷한 원리로 만약 \(i_b > i_a\)라면, 위 작업에서 \(i_b\)가 \(a\)를 가장 아래에 둔 상태에 \(i_a\)가 \(a\)를 가장 높은 우선 순위에 두게 됩니다. 그러면 사회적으로 합의된 선호에서 \(a\)는 가장 높은 곳에 위치하게 되죠. 그렇지만 \( i_b \)의 선호 리스트에서 \(a\)는 분명 \(c\)보다 낮은 곳에 있으므로 사회적으로 합의된 선호에서도 \(a\)가 \(c\)보다 낮은 곳에 있어야 합니다. 이 경우에도 똑같이 모순이 발생하는 것을 확인할 수 있습니다. ■
이제 정리 3을 통해 얻은 구성원 \(i_a\)가 실제 독재자임을 보일 수 있습니다. 임의의 서로 다른 두 후보 \(b\)와 \(c\)에 대해, \(b\)도 \(c\)도 아닌 제삼(第三) 후보 \(a\)를 고정시킨 후 정리 3을 적용합니다. 그러면 \(i_a\)의 선호에 따라 \(b\)와 \(c\)의 사회적으로 합의된 선호가 결정됩니다. 그런데 정리 4에 의해 제삼 후보를 어떤 것으로 잡든 모두 동일한 구성원이 선택됩니다. 따라서 임의의 서로 다른 두 후보에 대해 해당 구성원의 선호도가 곧 사회적으로 합의된 선호에 반영되므로 그 구성원은 독재자입니다.
마치며
이것으로 애로우의 불가능성 정리에 대한 설명을 모두 마칩니다. 이 정리는 민주주의 사회에서는 갈등을 합리적으로 해소할 수 있는 방법은 애초에 존재하지 않는다는 어찌 보면 매우 암울한 현실을 알려 줍니다. 다만 본문의 조건보다는 약할지라도 여전히 합리적인 조건에 대해서는 긍정적인 결과가 있는지 모르겠습니다. 혹여 관련하여 공부하게 되면 공유해 보도록 하겠습니다.
사회 후생 함수는 구성원들로부터 선호 리스트를 입력 받아 사회적으로 합의된 선호를 출력합니다. 하지만 선거나 투표와 같이 우리는 하나의 후보를 선출하는 일에 좀더 익숙합니다. 이렇게 구성원들로부터 선호 리스트를 입력 받아 사회적으로 합의된 후보 하나를 출력하는 함수를 사회 선택 함수(social choice function)라고 부릅니다. 아무래도 출력의 크기가 작으니 사회 후생 함수보다는 나은 결과가 있지 않을까 기대해 봄직 합니다. 하지만 안타깝게도 여전히 합리적인 조건들을 모두 만족하는 사회 선택 함수는 존재할 수 없다는 것이 알려져 있습니다. 이것이 바로 기바드-사데르스웨이트 정리(Gibbard-Satterthwaite theorem)입니다.
정리 5. 기바드-사데르스웨이트 정리
후보가 세 개 이상일 때, 어떤 사회 선택 함수가 만장일치성과 유인 부합성(incentive compatibility)을 만족하면 반드시 독재자가 존재한다.
다음에는 이 정리에 대해서 다루어 보고자 합니다.
읽어 주셔서 고맙습니다.
참조
[1] Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
[2] John Geanakoplos. Three brief proofs of Arrow’s impossibility theorem. Economic Theory 26.1 (2005): 211-215.
[3] Mathsaurus. Arrow's Theorem - Dictators exist in any voting system with these simple properties! (full proof!). 2019. Link: https://youtu.be/bltSohBl6dM
'알고리즘 & 게임 이론 > Mechanism design' 카테고리의 다른 글
| 최적 경매 (Optimal Auction) (0) | 2023.04.08 |
|---|---|
| 비크리-클라크-그로브스 메커니즘 (Vickrey-Clarke-Groves Mechanism) (0) | 2022.01.22 |
| 비크리 경매 (Vickrey Auction) (6) | 2021.12.04 |
