애로의 불가능성 정리

사회 선택 이론에서 **애로의 불가능성 정리**(Arrow’s impossibility theorem) 또는 **일반 가능성 정리**(general possibility theorem) 또는 **애로의 역설**(Arrow’s paradox)는 투표자들에게 세 개 이상의 서로 다른 대안이 제시될 때, 어떤 투표 제도도 공동체의 일관된 **선호순위**(ranked preferences) 를 찾을 수 없다는 것, 즉 애로 정리에서 제시된 몇 가지 기준을 충족하면서, 선호의 '완전성'(completeness)과 '이행성'(transitiveness)을 만족시킬 수 있는 사회 후생 함수(social welfare function)를 찾을 수 없다는 것을 의미한다. 이론 경제학자인 케네스 애로의 이름을 따서 정리의 이름이 붙여졌다. 그는 그의 박사논문 'A Difficulty in the Concept of Social Welfare'jstor=1828886에서 이 정리를 설명했고 1951년 그의 책 'Social Choice and Individual Values'zbl=0984.91513 덕분에 널리 알려졌다. 1972년 애로는 경제 '일반 균형 모델'(general equilibrium theory)과 '사회적 후생론'(welfare theory)을 개척한 공로를 인정받아 그 해 노벨 경제학상의 공동 수상자로 선정됐다. 애로는 '정의 영역 배제 불가능'(unrestricted domain, 보편성 원칙), '비 독재'(non-dictatorship, 투표권의 동등한 영향력), '만장일치(파레토 원칙)', '무관한 선택대상으로부터의 독립'(independence of irrelevant alternatives, IIA)을 투표 제도가 만족해야 될 조건으로 제시했다. '기바드-새터스웨이트 정리'(Gibbard–Satterthwaite theorem)는 이를 확장해 선거가 갖는 함의를 해석하였다. 간단히 설명하면, 불가능성 정리는 어떤 투표 제도를 선택해도 다음과 같은 세 가지 "공정성" 기준을 만족시킬 수 없다는 것을 증명한다. * 만약 *모든* 유권자들이 **가**안에 비해 **나**안을 선호한다면, 이 공동체는 **가**보다 **나**안을 선호한다. * 만약 **가**와 **나**안에 대한 *모든* 유권자의 선호도가 변하지 않는다면, **가**와 **나**안에 대한 공동체의 선호도 변하지 않는다. (단, *가*와 *다*, *나*와 *다*, *다*와 *라*안에 대한 개인 선호도는 바뀔 수 있다.) * 투표를 좌지우지하는 *독재자*는 존재하지 않는다: 모든 유권자는 공동체 결정에 동일한 비중의 투표권을 갖는다. 만약 각각의 대안에 임의의 선호 값을 부여한다면(기수(基數)적 효용), 불가능성 정리를 우회하는 공동체 결정이 가능하다. 하지만 애로는, 다른 많은 경제학자들과 같이, 기수적 효용(cardinal utility)이 사회 후생을 평가하는 의미있는 도구라고 생각하지 않았고, 따라서 선호순위를 바탕으로 불가능성 정리를 도출했다. 선호를 바탕으로 한 애로의 공리(公理, axiom)적 접근법은, 하나의 통일된 틀안에서 거의 모든 사회 제도를 분석할 수 있는 도구를 제시한다. 이런 점에서, 애로의 공리적 접근은 개별 제도를 하나씩 다루는 그 이전의 '투표 이론'에서 (질적으로) 한단계 발전한 방법이라고 볼 수 있다. 따라서, 일부 학자들은 사회 선택 이론의 새로운 패러다임이 애로의 정리에서 시작됐다고 평가한다.pages=Introduction, page 10.
# 정의

## 개인과 대안
애로의 불가능성 정리에서 사용되는 사회 후생 함수의 개념은 사회의 구성원들의 어떤 의제의 여러 가지 대안들에 대한 선호로부터 사회 전체의 선호를 도출하는 과정을 모형화한다. 처음 몇 자연수들의 집합 I=\\{1,2,\dotsc,n\\}이 주어졌다고 하자. 이 집합의 원소를 **개인**(individual)이라고 부른다. 이는 어떤 한 사회를 구성하는 n명의 사람들을 나타낸다. 임의의 집합 A가 주어졌다고 하자. 이는 유한 개의 원소로 구성되어 있을 수 있고, 무한히 많은 원소를 가질 수도 있다. A의 원소는 **대안**(alternative)이라고 부르며, a,b,c 등으로 표기한다. 이는 사회의 어떤 의제에서 선택 가능한 모든 방안들로 해석할 수 있다.
## 선호 순서
대안들의 집합 A 위의 원전순서 R를 생각하자. 사회 선택 이론의 문맥에서 이는 A 위의 **선호 순서**(preference order)로 불린다. 즉, R는 A 위의 이항 관계이며, (b,a)\in R를 a\gtrsim_Rb로 표기할 때, 다음 두 조건을 만족시킨다. * (완전성, completeness) a\gtrsim_Rb이거나 b\gtrsim_Ra이다. * (이행성, transitivity) 만약 a\gtrsim_Rb이며 b\gtrsim_Rc라면, a\gtrsim_Rc이다. 선호 순서는 개인이나 사회가 주어진 대안들을 어떤 순서로 선호하는지를 나타낸다. a\gtrsim_Rb는 R에서 a가 b보다 더 선호되거나, a와 b가 똑같이 선호됨을 나타낸다. 만약 a\gtrsim_Rb이며 b\gtrsim_Ra라면, a\sim_Rb로 적으며, R에서 a와 b가 똑같이 선호된다고 한다. 만약 a\gtrsim_Rb이지만 a\not\sim_Rb라면, a>_Rb로 적으며, R에서 a가 b보다 선호된다고 한다. 완전성에 따르면, 주어진 선호 순서에서, 두 대안은 똑같이 선호되거나, 하나가 다른 하나보다 더 선호된다. 이행성에 따르면, 만약 선호 순서 R에서 a가 b보다 선호되며 b가 c보다 선호된다면, a는 c보다 선호된다. 즉, 완전성과 이행성 조건은 개인 또는 사회가 주어진 대안들에 대하여 취할 수 있는 태도가 충분히 “합리적”일 것을 요구한다. A 위의 선호 순서의 집합을 \mathcal R(A)로 표기하자. 만약 선호 순서 R에서 똑같이 선호되는 두 대안이 항상 같은 대안이라면, R는 전순서가 된다. 선호 전순서의 집합은 \mathcal R_{\operatorname{to(A)로 표기한다. 예를 들어, A=\\{x,y,z\\}가 세 개의 대안으로 이루어졌다면, 총 13개의 선호 순서는 다음과 같다 (이 가운데 1~6번째가 전순서이다). # x>y>z # x>z>y # y>x>z # y>z>x # z>x>y # z>y>x # x>y\sim z # y>x\sim z # z>x\sim y # y\sim z>x # x\sim z>y # x\sim y>z # x\sim y\sim z
## 선호 프로필
곱집합 \mathcal R(A)^n은 n개의 선호 순서의 튜플 (R_1,R_2,\dotsc,R_n)들의 집합이다. 원소 (R_1,R_2,\dotsc,R_n)\in\mathcal R(A)^n는 n명의 개인의 선호 순서들의 조합이며, 이를 **선호 프로필**(preference profile)이라고 부른다. 선호 프로필의 i번째 성분 R_i는 i번째 개인의 선호 순서를 나타낸다. \mathcal R_{\operatorname{to(A)^n은 \mathcal R(A)^n의 부분 집합이며, 모든 성분이 전순서인 선호 프로필들로 구성된다.
## 사회 후생 함수
**사회 후생 함수**(social welfare function, 약자 SWF)는 선호 프로필의 집합에서 선호 순서의 집합으로 가는 함수 f\colon\mathcal R(A)^n\to\mathcal R(A)로 정의된다. 이는 모든 개인의 선호 순서들의 조합 (R_1,R_2,\dotsc,R_n)으로부터 사회의 선호 순서 f(R_1,R_2,\dotsc,R_n)를 결정하는 규칙을 나타내며, 집합적 의사 결정 제도를 모형화한다. 애로의 불가능성 정리는 사회 선택이 개인의 선택을 잘 반영함을 나타내는 일련의 조건들을 만족시키는 의사 결정 제도가 존재하지 않는다고 단언한다. 이 가운데 다음 조건은 이미 사회 후생 함수의 정의에 암시되어 있다. * (무제한적 정의역, unrestricted domain) 사회 후생 함수의 정의역은 모든 선호 프로필을 원소로 포함한다. 즉, 어떤 개인 선호 순서들의 조합에 대해서도 유일한 사회 선호 순서를 산출한다.
## 애로의 불가능성 정리
**애로의 불가능성 정리**에 따르면, 만약 |A|\ge 3이라면, 다음 세 조건을 모두 만족시키는 사회 후생 함수 f\colon\mathcal R(A)^n\to\mathcal R(A)는 존재하지 않는다. * (약한 파레토, weak Pareto) 만약 모든 R_i가 a를 b보다 선호한다면, f(R_1,R_2,\dotsc,R_n)에서도 a가 b보다 선호된다. 즉, 모든 개인이 어떤 두 대안에 대하여 만장일치를 이뤘다면, 사회 선호는 이를 존중한다. (그러나 모두가 a와 b를 똑같이 선호하더라도 사회는 a와 b를 똑같이 선호하지 않을 수 있다. 또한 모두의 선호가 a\gtrsim b를 만족시키더라도 사회 선호는 이를 만족시키지 않을 수 있다.) * (무관한 대안들로부터의 독립, independence of irrelevant alternatives, 약자 IIA) 두 대안의 사회 선호에서의 상대적 위치는 오직 그 두 대안의 각 개인 선호에서의 상대적 위치에만 의존한다. 즉, 임의의 두 선호 프로필 (R_1,R_2,\dotsc,R_n) 및 (R_1',R_2',\dotsc,R_n')에 대하여, 만약 각 R_i와 R_i'에서 대안 a와 b의 상대적 위치가 동일하다면, f(R_1,R_2,\dotsc,R_n)과 f(R_1',R_2',\dotsc,R_n')에서 a와 b의 상대적 위치는 동일하다. * (비독재성, non-dictatorship) 사회 선호를 한 개인이 좌지우지할 수 없다. 즉, 다음 조건을 만족시키는 개인 i\in I이 존재하지 않는다. ** (독재자, dictator) 임의의 선호 프로필 (R_1,R_2,\dotsc,R_n) 및 두 대안 a,b에 대하여, 만약 R_i가 a를 b보다 선호한다면, f(R_1,R_2,\dotsc,R_n)에서도 a가 b보다 선호된다. (그러나 i가 똑같이 선호하는 두 대안이 사회에서도 똑같이 선호될 필요는 없다.)
# 정리가 갖는 의미
애로의 정리는 수학적 결과이지만, 이를 종종 단순하게 해석하기도 한다: *"공정한 투표란 없다", "순위를 매기는 모든 투표방법은 오류가 있다.", 또는 "오류가 없는 투표는 오직 독재뿐이다."* 정리를 단순화 시킨 위와 같은 표현은 원문의 내용과 거리가 있다. 정확히 말해, 불가능성 정리는 어떠한 (선호순위만이 투표에 영향을 미치고, 여러번 투표를 시행해도 동일한 결과를 도출할 수 있는) 확정적 투표 제도도 애로가 제시한 조건을 모두 동시에 만족시킬 수 없다는 것을 말한다. 애로가 자신의 조건들을 언급하면서 "공정성"이란 단어를 사용한 것은 사실이다. 또 파레토 효율이나 비강제성 요구는 많은 사람들에게 합리적인 가정으로 여겨진다. 일부 학자날짜=2012-3-22들은 IIA 가정을 약화시키는 것이 정리의 역설을 우회하는 한 방법이라고 본다. 이들 학자들은 IIA가 너무 강한 조건이라고 주장하며, 그 예로 대부분의 현실적 투표제도가 IIA조건을 만족시키지 못한다고 말한다. 또, IIA조건 위반은 단순히 선호가 순환성(cyclic preference)을 보이는 경우에도 가능하다는 점을 지적한다. 유권자들이 다음과 선호순위를 갖고 있다고 가정해보자: * 유권자 1은 A > B > C 의 순서로 선호 * 유권자 2은 B > C > A 의 순서로 선호 * 유권자 3은 C > A > B 의 순서로 선호 A와 B를 두고 투표할때, 유권자 1·3은 A에 투표하고 유권자 2만 B에 투표한다. 따라서 다수결을 통해 이 공동체는 B 보다는 A를, C 보다는 B를, 그리고 A 보다는 C를 선택한다: 어떤 두 대안을 비교하더라도, '가위 바위 보'와 같은 선호체계를 갖는다. 이경우, (사회 선호가 전이성 혹은 비순환성을 갖는다고 전제했을때.) 가장 많은 득표를 얻은 후보가 승리하는 다수결의 원칙을 적용한 *그 어떤* 선호 결합 규칙(사회 후생함수)도 IIA를 만족시키지 못한다. 귀류법을 이용해 이것을 증명하기 위해, (반대로) 선호 결합 규칙이 IIA를 만족한다고 해보자. 다수결 원칙이 존중되기 때문에, 투표를 통해 이 공동체는 A 보다는 B를, B 보다는 C를, 그리고 C 보다는 A를 선호하는 것으로 나타난다. 따라서 선호의 순환성이 나타나고, 사회 선호가 전이성을 만족한다는 가정에 위배된다. 결국, 애로의 정리가 실제로 보이는 것은, 어떤 다수결 원칙의 투표도 *사소하지 않은* 게임이라는 것과 투표 행위의 결과를 예측하기 위해서는 대부분의 경우 게임 이론을 도입해 분석해야 된다는 것이다. 우리가 게임 이론의 '균형'이란 개념을 도입한다고 해서 다양한 규범적 조건들을 만족시킬수 있다는 것을 의미하지는 않는다. 실제로, 선호순위 체계에서 균형점으로 매핑하는 과정은 '사회 선택 규칙'에 따르게 되고, 이런 사회 선택 규칙의 유용성은 사회 선택 이론(social choice theory)에서 다뤄진다.pages =Section 7.2. 이런 결론은 게임이 꼭 효율적 균형을 갖는 다고 볼수없기 때문에 실망스러울수도 있다: 누구도 최선이라고 인정하지는 않는 후보에게, 모두가 선거에서 (차선으로) 그 후보에 투표할 수 있다.
# 증명

## “단칼” 증명
사회 후생 함수 f\colon\mathcal R(A)^n\to\mathcal R(A)가 약한 파레토와 IIA 조건을 만족시킨다고 하자.zbl=1245.91030 f에 대하여 독재자 i\in I가 존재함을 보이면 족하다. 모든 개인이 만장일치로 a를 b보다 선호하는 선호 프로필 (R_1,\dotsc,R_n)에서 개인의 선호 순서를 1부터 n까지 하나씩 b를 a보다 선호하도록 변경하여, n번의 변경 끝에 모두가 b를 a보다 선호하는 선호 프로필 (R_1',\dotsc,R_n')에 도달하는 과정을 생각하자. 약한 파레토 조건에 따라 a>_{f(R_1,\dotsc,R_n)}b이며 b>_{f(R_1',\dotsc,R_n')}a이다. 사회가 처음에는 a를 더 선호하다가 마지막에는 b를 더 선호하므로, 처음 a>b가 거짓이 되는 시점이 존재한다. 개인 i_{ab}의 선호를 변경하였을 때 사회 선호에서 a>b가 처음 거짓이 된다고 가정하자 (즉, b\gtrsim a가 처음 참이 된다). IIA 조건에 따라, i_{ab}는 오직 a와 b에만 의존하며, (R_1,\dotsc,R_n)의 선택이나 개인의 선호 순서를 변경하는 과정의 영향을 받지 않는다. {| class="wikitable" ! 개인 !! 선호 프로필 Ⅰ !! 선호 프로필 Ⅱ |- ! 1,\dotsc,i_{ab}-1 | b>c>a || b>a\land c>a |- ! i_{ab} | a>b>c || b>a>c |- ! i_{ab}+1,\dotsc,n | a>b>c || a>b\land a>c |} 서로 다른 세 개의 대안 a,b,c\in A가 주어졌을 때, 위 표의 조건들을 만족시키는 두 선호 프로필을 생각하자. 그렇다면, 선호 프로필 Ⅰ에 대응하는 사회 선호에서 세 대안의 상대적 위치는 a>b>c이다. 여기서 a>b는 i_{ab}의 정의에 따른 것이며, b>c는 약한 파레토 조건 때문이다. 선호 프로필 Ⅱ에 대응하는 사회 선호에서 세 대안의 상대적 위치는 b\gtrsim a>c이다. 여기서 b\gtrsim a는 i_{ab}의 정의에 따르며, a>c는 선호 프로필 Ⅰ와 Ⅱ에서 a와 c의 선호가 동일하다는 사실과 선호 프로필 Ⅰ에 대응하는 사회 선호의 추이성으로부터 얻는다. 선호 프로필 Ⅱ에서, i_{ab}를 제외한 개인에 대하여 b와 c의 상대적 위치는 임의적이지만 (b>c일 수도, b\sim c일 수도, c>b일 수도 있다), b와 c에 대한 사회의 의견은 i_{ab}의 의견과 일치한다. IIA 조건에 따라, 임의의 서로 다른 세 대안 a,b,c에 대하여, i_{ab}는 다음 조건을 만족시킴을 알 수 있다. * (b와 c에 대한 독재자) 임의의 선호 프로필 (R_1,R_2,\dotsc,R_n)에 대하여, 만약 R_{i_{ab가 b를 c보다 선호한다면, f(R_1,R_2,\dotsc,R_n)에서도 b가 c보다 선호된다. 임의의 서로 다른 대안 a,b,c에 대하여, i_{bc}를 구하는 과정을 생각하자. 이 과정에서, i_{ab}가 b를 c보다 선호하는 한, 사회 역시 b를 c보다 선호하므로, i_{bc}\ge i_{ab}이다. 또한, i_{cb}를 구하는 과정에서, i_{ab}가 b를 c보다 선호하게 될 때 사회 역시 이미 b를 c보다 선호하므로, i_{ab}\ge i_{cb}이다. 따라서 i_{bc}\ge i_{ab}\ge i_{cb}이다. b와 c의 역할을 뒤바꾸면 i_{cb}\ge i_{bc}를 얻는다. 따라서 임의의 서로 다른 세 대안 a,b,c에 대하여, i_{bc}=i_{cb}=i_{ab}이다. |A|\ge 3이므로, i_{ab}는 두 대안 a,b의 순서와 무관하며, 서로소가 아닌 두 쌍의 대안에 대하여 값이 같음을 알 수 있다. 만약 두 쌍의 서로 다른 대안 (a,b) 및 (c,d)가 서로소라면, (a,b)와 (b,c), (b,c)와 (c,d)는 각각 하나의 대안을 공유하는 두 쌍의 대안이므로, i_{ab}=i_{bc}=i_{cd}이다. 이에 따라, i_{ab}는 서로 다른 두 대안 a,b의 선택과 무관하다. 이를 i로 표기하자. 그렇다면 임의의 두 서로 다른 대안 b,c에 대하여, |A|\ge 3이므로 b,c가 아닌 대안 a를 취할 수 있다. i=i_{ab}이므로, i는 b와 c에 대한 독재자이다. 이에 따라, i는 (모든 대안에 대한) 독재자이다.