애로우 가능성 정리 연습 문제 풀어 보기

애로우 불가능성 정리보다는 가능성 정리로 부르는 사람들이 늘어나는 이유를 알려면, 다음 문제들을 풀어보는 것이 좋다. 아래 링크한 원문에서 고칠 곳이 있지만 고치지 않는다. 문제를 푸는 데는 지장이 없기 때문이다.

 

투표의 역설1. 애로우 가능성 정리(Arrow Possibility Theorem)

http://blog.daum.net/goodking/41

 

 

글 [1]

[예제 1~2] 다음 글을 읽고 물음에 답하시오.

콩도르세는 프랑스 혁명을 이끈 인물 중 한 명으로 노예 해방과 여성의 참정권을 옹호한 인물로 잘 알려져 있다. 혁명 후 프랑스가 지향해야 할 사회에 대한 그의 설계는 교육, 정치, 경제 등을 다루고 있다. 하지만 콩도르세는 왕의 처형을 반대했고 극단적 정치 노선을 경계했다. 반대파에 의해 적으로 몰린 그는 결국 의문사로 생을 마감하였다. 드라마틱한 콩도르세의 일생을 관통하고 있는 관심사 중 하나는 수학적 방법을 사용하여 사회 및 정치 문제를 해결하는 것이었다. 수학자였던 그는 달랑베르(J. d'Alembert) 등의 영향으로 적분 연구에 기여를 하였다. 그가 적분을 연구하던 시절의 프랑스는 루이 15세(King Louis XV) 의 통치를 받고 있었다. 당시 프랑스 재정을 담당했던 투르고(J. Turgo)와의 교류를 통해 콩도르세는 관심의 지평을 넓힐 수 있었다. 콩도르세와 함께 회자되는 ‘콩도르세의 역설’은 수학이 사회 및 정치 문제의 해결에 도움을 줄 수 있다는 그의 신념을 반영해준다. 세 명이 후보로 출마한 선거 상황을 고려하여 보자. 다른 후보들보다 선호되는 후보가 딱히 없는 경우가 발생할 수도 있다. 그러한 경우 중 하나는 일명 ‘다수결 규칙의 순환(majority rule cycle)’ 혹은 ‘순환적 무승부(circular tie)’로 불리는 것으로 수학의 관계 이론에서 중요한 이행성(transitivity) 조건이 깨진 상황에 해당한다. 실례로 세 후보 A, B, C에 대해 다수결 원칙에 따라 A가 B보다, B가 C보다 선호되지만 C가 A보다 선호되어 아무도 선출할 수 없게 되는 상황을 생각해 볼 수 있다. 수학은 그러한 상황이 발생하게 된 조건들을 명확히 해준다.

 

[예제 1] 콩도르세 역설을 통해 콩도르세가 궁극적으로 말하고자 하는 것은?

① 이행성의 조건이 성립하지 않는 경우도 있다.

② 다수결 원칙에 따라 다수가 선호하는 대안을 선택할 수 없는 경우도 있다.

③ 수학적 방법은 사회 및 정치 문제를 해결하는 데 도움을 줄 수 있다.

④ 수학 없이는 사회 및 정치 문제를 해결할 수 없다.

⑤ 사회 및 정치학은 수학의 분과가 될 것이다.

 

[예제 2] 세 후보 A, B, C 중 한 명을 뽑기 위해 M1, M2, M3의 선거단이 구성되었다. 이때 콩도르세의 ‘다수결 규칙의 순환’을 보여주는 M1, M2, M3의 선호 방식을 <보기>에서 고른다면? (반드시 쌍별로 후보들을 비교하여 다수가 선호한 후보가 누구인지를 고려하라.)

 

<보기>

(가) M1: A≻B≻C, M2: C≻A≻B, M3: B≻C≻A (나) M1: A≻B≻C, M2: A≻B≻C, M3: B≻C≻A (다) M1: A≻B≻C, M2: B≻A≻C, M3: C≻A≻B

 

① (가)   ② (나)   ③ (다)   ④ (가), (다)   ⑤ (나), (다)

 

 

[예제 3] 임의의 대안 x, y, z에 대하여 선호 관계 ‘?’가 이행성 조건을 만족하면, 다음의 경우들이 성립하는 것으로 증명되었다. 이때 도식의 빈 칸을 채워 본다면 (‘A→B’는 ‘A가 성립하면 B도 성립함’을 뜻한다.)

 

 

• PP: ‘x≻y’이고 ‘y≻z’이면, ‘x≻z’도 성립한다.

• PI: ‘x≻y’이고 ‘y∼z’이면, ‘x≻z’도 성립한다.

• IP: ‘x∼y’이고 ‘y≻z’이면, ‘x≻z’도 성립한다.

• II: ‘x∼y’이고 ‘y∼z’이면, ‘x∼z’도 성립한다.

 

 

 

글 [2]

[예제 4] 위 글의 <선호 방식의 프로필>에서 비합리적인 개인을 함축하고 있는 경우들의 배열에 해당하지 않는 것은?

 

① (1, 5, 10)   ② (2, 6, 9)   ③ (3, 7, 9)   ④ (4, 8, 9)   ⑤ (4, 8, 10)

 

 

[예제 5] <보기> 중 다음 프로필의 평가로 적절한 것은?

 

<보기>

	[x 대 y] 1  2  3  4	[y 대 z] 5  6  7  8	[z 대 x] 9 10 11 12
i j c	≻ ≻ ≺ ≺  ≻ ≺ ≻ ≺   ≻         ≺	≻ ≻ ≺ ≺ ≻ ≺ ≻ ≺ ≻         ≺	≻ ≻ ≺ ≺ ≻ ≺ ≻ ≺ ≻         ≺

 

<선호 방식의 프로필>

(가) 1, 4, 5, 8, 9, 12의 경우들은 조건 U를 만족하는 것에 해당하는군. (나) 2의 경우 반드시 ‘x≺cy’가 성립하겠군. (다) 1과 2의 경우에 12가 더해지면, 이행성 조건을 만족하는 결과가 얻어지는군.

 

① (가)   ② (나)   ③ (다)   ④ (가), (다)   ⑤ (나), (다)

 

 

 

글 [3]

[예제 6~8] 선호 관계 ‘?’는 이행성 조건을 만족한다. 각 사례에서 영이와 순돌은 세 후보 x, y, z 중에서 한 명을 선택하려고 한다. ‘(높은 위치를 점유한 후보)≻(낮은 위치를 점유한 후보)’가 성립한다고 가정하라.

 

<사례 1>

영이      순돌       다수결 투표 결과

x            z

y            x           x∼cy, y∼cz

z            y

 

<사례 2>

영이      순돌      다수결 투표 결과

x            z

y            x        x≻cy, y∼cz, x∼cz

z            y

 

<사례 3>

영이      순돌      다수결 투표 결과

x            z

y            x           x≻cy≻cz

z            y

 

[예제 6] 독재자를 함축하고 있는 사례를 고르고, 그 이유를 설명해 본다면?

 

[예제 7] 만장일치 조건이 깨어진 사례를 고르고, 그 이유를 설명해 본다면?

 

[예제 8] 이행성 조건이 깨어진 사례를 고르고, 그 이유를 설명해 본다면?

 

 

[예제 9~10] 다음 수학자의 글을 읽고 물음에 답하시오.

수학자: 수학적 증명에는 여러 방식들이 있습니다. 그러한 증명 방식들은 내용과 무관하게 형식적으로 다뤄질 수 있습니다. 어떤 발견의 수학적 증명 결과만 보면, 수학자들이 마치 특정 형식에 따라 증명을 한 것처럼 보입니다. 그러나 이것은 사실이 아닙니다. 증명 과정에는 독창적인 발상과 은유가 뒤섞이게 됩니다. 실례로 애로우의 가능성 정리에서 ‘다수에 반하는 유일한 반대자(d)’나 ‘독재자(D)’와 같은 개념을 발견하게 됩니다. 그러한 개념마저도 마지막에는 형식적으로 처리될 수 있지만, 그것의 최초 발상은 어떤 목적을 달성하기 위해 경제학이나 정치학의 배경 지식을 바탕으로 특정 상황을 설계하는 과정과 맞물려 있습니다. 애로우 증명을 살펴보면, 모순을 이용한 간접 증명 형식, 곧 ‘귀류법(reductio ad absurdum)’과 ‘경우에 따른 증명 형식’이 드러납니다. 귀류법은 증명하고자 하는 것을 부정하면 모순이 발생함을 보임으로써 증명하고자 하는 것이 증명되었다는 방식에 근거합니다. 경우에 따른 증명은 A 또는 B라는 각각의 경우에서 C가 증명 가능하면 ‘A 또는 B이면 C'라는 것도 증명되었다는 방식에 근거합니다. 애로우는 이러한 형식에 독재자와 같은 발상이 개입시켜 자신의 목적을 달성할 수 있었던 것입니다. 애로우의 목적이 무엇이었던가요?   • 애로우의 목적: ( A )   이러한 목적을 달성하기 위해 그는 IIA, U, ND를 만족하는 SWF가 있다고 가정하였습니다. 다수에 반하는 유일한 반대자 d에 해당하는 경우들에서 d는 항상 독재자인 까닭에, 그러한 SWF는 가정할 수 없게 됩니다. 다수에 따른 선호 방식 m도 ( B )을(를) 발생시킨다는 사실을 증명하였습니다. 이러한 증명을 통하여 애로우는 자신의 목적을 달성할 수 있었던 것입니다.

 

[예제 9] 수학자의 글에서 빈 칸에 들어갈 것으로 적절한 것은?

	(A)	(B)
①	콩도르세의 역설을 일반화 시킬 수 있는지를 따져 보는 것	모순
②	콩도르세의 역설을 일반화 시킬 수 있는지를 따져 보는 것	D
③	IIA, U, ND를 만족하는 SWF는 없다는 것	D
④	IIA, U, ND를 만족하는 SWF는 없다는 것	d
⑤	전통적 합리성 개념을 부정하는 것	모순

 

[예제 10] 다음 증명 도식의 빈 칸에 들어갈 것으로 적절한 것은?

 

 

    (가)         (나)               (다)                (라)      

①   d             m                  모순          애로우 정리

②   m            d                   모순                  D

③   d             D             애로우 정리             m

④   d D   애로우 정리           모순

⑤ SWF          d                  모순           애로우 정리

 

 

[예제 11] 다음의 <선호 방식의 프로필>에서 독재자는 누구인가?

 

<선호 방식의 프로필>

	[x 대 y] 1  2  3  4	[y 대 z] 5  6  7  8	[z 대 x] 9 10 11 12
i j c	≻ ≻ ≺ ≺ ≻ ≺ ≻ ≺ ≻ ≺ ≻ ≺	≻ ≻ ≺ ≺ ≻ ≺ ≻ ≺ ≻ ≺ ≻ ≺	≻ ≻ ≺ ≺ ≻ ≺ ≻ ≺ ≻ ≺ ≻ ≺

 

 

[예제 12~13] 다음 프로필을 분석하여 물음에 답하시오.

 

<세 명의 개인과 세 개의 대안이 주어진 상황에서의 선호 방식의 프로필>

	[x 대 y] 1 2 3 4 5 6 7 8	[y 대 z] 9 10 11 12 13 14 15 16	[z 대 x] 17 18 19 20 21 22 23 24
i j k c	≻ ≻ ≻ ≻ ≺ ≺ ≺ ≺ ≻ ≻ ≺ ≺ ≻ ≻ ≺ ≺ ≻ ≺ ≻ ≺ ≻ ≺ ≻ ≺ ≻                          ≺	≻ ≻ ≻ ≻ ≺ ≺ ≺ ≺ ≻ ≻ ≺ ≺ ≻ ≻ ≺ ≺ ≻ ≺ ≻ ≺ ≻ ≺ ≻ ≺ ≻                          ≺	≻ ≻ ≻ ≻ ≺ ≺ ≺ ≺ ≻ ≻ ≺ ≺ ≻ ≻ ≺ ≺ ≻ ≺ ≻ ≺ ≻ ≺ ≻ ≺ ≻                          ≺

 

[예제 12] 각 쌍별 대안 비교에서 다수의 선호 방식을 따른다고 할 때 빈 칸을 채워 본다면?

 

[예제 13] 빈 칸을 채워 최종적으로 완성된 프로필에서 콩도르세 역설을 발생시키는 조합을 하나 고른다면?

 

 

 

글 [4]

[예제 14] 다음 글을 읽고 도식의 빈 칸을 채워 본다면? (‘A→B’는 ‘A가 성립하면 B도 성립함’을, 그리고 ‘A-B'는 ‘A 그리고 B'를 뜻한다.)

임의의 대안 x, y, z에 대하여 약한 선호 관계 ‘?’가 이행성 조건을 만족하면, 다음의 경우들이 성립하는 것으로 증명되었다.   • PP: ‘x≻y’이고 ‘y≻z’이면, ‘x≻z’도 성립한다. • PI: ‘x≻y’이고 ‘y∼z’이면, ‘x≻z’도 성립한다. • IP: ‘x∼y’이고 ‘y≻z’이면, ‘x≻z’도 성립한다. • II: ‘x∼y’이고 ‘y∼z’이면, ‘x∼z’도 성립한다.   그러나 약한 선호 관계 ‘?’가 이행성 조건을 만족한다고 사전에 전제하지 않는 경우, 다음이 성립한다.   • PP는 PI, IP, II의 각각과 서로 독립적이다. 즉, PP가 성립하지 않는 경우 PI, IP, II는 여전히 성립할 수 있다. • PI이면 IP가 성립하고, IP가 성립하면 PI도 성립한다. • PI이면, II가 성립한다. • PP와 II가 동시에 성립하는 경우, PI도 성립한다. • PP와 PI가 동시에 성립하는 경우, ‘?’가 이행성 조건을 만족하게 된다.   여기서 보듯이, 산수의 대소 관계와 달리 약한 선호 관계는 PP가 성립한다고 자동적으로 이행성 조건을 만족하는 것이 아니다. 따라서 우리는 PP만을 만족하는 경우에 국한된 약한 선호 관계 ‘?’를 가정할 수 있는데, 그러한 ‘?’는 ‘유사 이행성’ 조건을 만족하는 관계로 정의된다. 유사 이행성 조건을 만족하는 관계에 근거한 선호 방식들은 대안들의 부분 집합에 대해 항상 최상의 대안을 갖게 되며, UD, IIA, P, ND 모두를 만족하는 집단적 선택 규칙을 산출해낼 수 있다.

 

 

   (A)      (B)      (C)      (D)

① PP        PI         II        IP

② PP        II          IP       PI

③ IP        PP         PI        II

④ IP        PP         PI        II

⑤ II         PP         IP       PI

 

 

[예제 15] 다음 조건을 만족하는 보다 산출법에 따를 때 투표로 당선될 인물은?

 

• N 명의 후보가 있을 때 각 투표자는 자신이 가장 선호하는 사람에게 n점의 주고, 그 다음 선호하는 사람에게는 n-1점을 준다.

• 반드시 1과 n 사이의 점수가 각 후보에게 부여되어야 하며, 각각의 후보에게 중복 점수의 부여는 불가능하다.

• 각 후보가 획득한 총점은 각 후보에게 부여된 점수에 득표수를 곱한 총합이 된다.

• 총점이 가장 높은 후보가 당선된다. 총점에서 동률이 나온다면, 나이가 더 많은 후보가 당선된다.

 

득표수

       130      110      90     160

4점    X         Z         Z       W

3점    Y         Y         Y       Y

2점    W        W        X       X

1점    Z         X         W      Z

 

① W   ② X   ③ Y   ④ Z   ⑤ W 또는 Z

 

 

[예제 16] 앞서 살펴본 애로우 정리의 증명 방식에 근거하여 민주주의가 단 두 정당을 허락해야 가능하다는 대중의 오해를 진단해 본다면?