콘도르케트 역설

사회적 선택 이론에서 콘도르케트 역설(투표의 역설 또는 투표의 역설이라고도 한다)은 18세기 후반에 드 콘도르케트 후작에 의해 지적된 상황으로, 비록 개별 유권자의 선호가 순환적이지 않더라도 집단적 선호가 순환될 수 있는 상황이다.^[1][2][3] 이것은 역설적이다. 왜냐하면 그것은 다수의 소망이 서로 충돌할 수 있다는 것을 의미하기 때문이다: 예를 들어 주요인들은 후보 A가 B보다, B가 C보다, 그리고 C가 A보다 더 좋다. 이렇게 되면 서로 상충되는 주요 요소들이 각각 다른 개인 집단으로 이루어져 있기 때문이다.

따라서 모든 개인의 선호의 일부에 대한 과도성이 사회적 선호의 과도성으로 귀결되어야 한다는 기대는 구성의 오류의 한 예다.

이 역설은 루이스 캐롤과 에드워드 J. 낸슨에 의해 독자적으로 발견되었지만, 1940년대 던컨 블랙에 의해 대중화되기 전까지는 그 의미가 인정되지 않았다.^[4]

예

우리가 A, B, C의 세 후보를 가지고 있고, 선호도가 다음과 같은 세 명의 유권자가 있다고 가정하자(선호도 순서가 감소하면서 각 유권자에 대해 좌우로 나열된다).

Voter	First preference	Second preference	Third preference
Voter 1	A	B	C
Voter 2	B	C	A
Voter 3	C	A	B

If C is chosen as the winner, it can be argued that B should win instead, since two voters (1 and 2) prefer B to C and only one voter (3) prefers C to B. However, by the same argument A is preferred to B, and C is preferred to A, by a margin of two to one on each occasion. Thus the society's preferences show cycling: A is preferred over B which is preferred over C which is preferred over A. A paradoxical feature of relations between the voters' preferences described above is that although the majority of voters agree that A is preferable to B, B to C, and C to A, all three coefficients of rank correlation between the preferences of any two voters are negative (namely, –.5), as calculated with Spearman's rank correlation coefficient formula designed by Charles Spearman much later.^[5]

Cardinal ratings

Note that in the graphical example, the voters and candidates are not symmetrical, but the ranked voting system "flattens" their preferences into a symmetrical cycle.^[6] Cardinal voting systems provide more information than rankings, allowing a winner to be found.^[7][8] For instance, under score voting, the ballots might be:^[9]

	A	B	C
1	6	3	0
2	0	6	1
3	5	0	6
Total:	11	9	7

Candidate A gets the largest score, and is the winner, as A is the nearest to all voters. However, a majority of voters have an incentive to give A a 0 and C a 10, allowing C to beat A, which they prefer, at which point, a majority will then have an incentive to give C a 0 and B a 10, to make B win, etc. (In this particular example, though, the incentive is weak, as those who prefer C to A only score C 1 point above A; in a ranked Condorcet method, it's quite possible they would simply equally rank A and C because of how weak their preference is, in which case a Condorcet cycle wouldn't have formed in the first place, and A would've been the Condorcet winner). So though the cycle doesn't occur in any given set of votes, it can appear through iterated elections with strategic voters with cardinal ratings.

Necessary condition for the paradox

Suppose that x is the fraction of voters who prefer A over B and that y is the fraction of voters who prefer B over C. It has been shown^[10] that the fraction z of voters who prefer A over C is always at least (x + y – 1). Since the paradox (a majority preferring C over A) requires z < 1/2, a necessary condition for the paradox is that

${\displaystyle x+y-1\leq z<{\frac {1}{2}}\quad {\text{and hence}}\quad x+y<{\frac {3}{2}}.}$

Likelihood of the paradox

It is possible to estimate the probability of the paradox by extrapolating from real election data, or using mathematical models of voter behavior, though the results depend strongly on which model is used. In particular, Andranik Tangian has proved that the probability of Condorcet paradox is negligible in a large society.^[11][12]

Impartial culture model

We can calculate the probability of seeing the paradox for the special case where voter preferences are uniformly distributed among the candidates. (This is the "impartial culture" model, which is known to be unrealistic,^{[13][14][15]: 40} so, in practice, a Condorcet paradox may be more or less likely than this calculation.^{[16]: 320 [17]})

For ${\displaystyle n}$ voters providing a preference list of three candidates A, B, C, we write ${\displaystyle X_{n}}$ (resp. ${\displaystyle Y_{n}}$, ${\displaystyle Z_{n}}$) the random variable equal to the number of voters who placed A in front of B (respectively B in front of C, C in front of A). The sought probability is ${\displaystyle p_{n}=2P(X_{n}>n/2,Y_{n}>n/2,Z_{n}>n/2)}$ (we double because there is also the symmetric case A> C> B> A). We show that, for odd ${\displaystyle n}$, ${\displaystyle p_{n}=3q_{n}-1/2}$ where ${\displaystyle q_{n}=P(X_{n}>n/2,Y_{n}>n/2)}$ which makes one need to know only the joint distribution of ${\displaystyle X_{n}}$ and ${\displaystyle Y_{n}}$.

If we put ${\displaystyle p_{n,i,j}=P(X_{n}=i,Y_{n}=j)}$, we show the relation which makes it possible to compute this distribution by recurrence: ${\displaystyle p_{n+1,i,j}={1 \over 6}p_{n,i,j}+{1 \over 3}p_{n,i-1,j}+{1 \over 3}p_{n,i,j-1}+{1 \over 6}p_{n,i-1,j-1}}$.

The following results are then obtained:

${\displaystyle n}$	3	101	201	301	401	501	601
${\displaystyle p_{n}}$	5.556%	8.690%	8.732%	8.746%	8.753%	8.757%	8.760%

The sequence seems to be tending towards a finite limit.

Using the Central-Limit Theorem, we show that ${\displaystyle q_{n}}$ tends to ${\displaystyle q={1 \over 4}P( T >{{\sqrt {2}} \over 4})}$ where ${\displaystyle T}$ is a variable following a Cauchy distribution, which gives ${\displaystyle q={\dfrac {1}{2\pi }}\int _{{\sqrt {2}}/4}^{+\infty }{\frac {dt}{1+t^{2}}}={\dfrac {\arctan 2{\sqrt {2}}}{2\pi }}={\dfrac {\arccos {\frac {1}{3}}}{2\pi }}}$ (constant quoted in the OEIS).

The asymptotic probability of encountering the Condorcet paradox is therefore ${\displaystyle {{3\arccos {1 \over 3}} \over {2\pi }}-{1 \over 2}={\arcsin {{\sqrt {6}} \over 9} \over \pi }}$ which gives the value 8.77%.^[18][19]

세 개 이상의 객체의 경우에 대한 일부 결과가 계산되었다.^[20]

관련 모델에 대한 콘도르셋 주기의 가능성은 큰 전기자동차의 경우 다음과 같은 값에 접근한다.^[19]

• 공정한 익명문화(IAC): 6.25%
• 균일문화(UC): 6.25%
• 최대 문화 조건(MC): 9.17%

이 모든 모델은 비현실적이며, 주기 가능성에 대한 상한을 설정하기 위해 조사된다.^[19]

그룹 일관성 모델

좀 더 현실적인 유권자 선호도로 모델을 만들면 후보 수가 적고 유권자 수가 많은 선거에서 콘도르케트 역설은 매우 드물게 나타난다.^{[15]: 78}

공간모형

3개 후보 선거의 연구는 12개의 다른 유권자 행동 모델을 분석했고, 투표의 공간적 모델이 실제 순위에 따른 선거 데이터에 가장 정확하다는 것을 발견했다. 이들은 이 공간 모델을 분석해 100명의 유권자가 5%, 1000명의 유권자가 0.5%, 1만명의 유권자가 0.06%의 확률로 유권자의 수가 증가함에 따라 사이클이 0으로 감소할 가능성을 발견했다.^[21]

경험적 연구

그 역설의 경험적 사례를 찾기 위한 많은 시도가 있었다.^[22] Condorcet 역설의 경험적 식별은 모든 대안보다 의사결정자의 선호에 대한 광범위한 데이터를 전제한다. 즉, 매우 드물게 이용할 수 있는 것이다.

크고 작은 총 265개의 실제 선거를 다루는 37개의 개별 연구를 요약한 결과 총 9.4%^{[16]: 325} 의 확률로 콘도르케트 역설 사례가 25건(그리고 이는 역설 사례가 없는 경우보다 보고될 가능성이 높기 때문에 높은 추정치가 될 수 있다).^{[15]: 47}

선거개혁회의의 84개 실제 순위투표에서 추출한 883개의 3자선거를 분석한 결과 콘도르셋 사이클 가능성이 0.7%로 나타났다. 이러한 파생 선거는 350명에서 1,957명의 유권자를 가지고 있었다. 1970-2004년 미국 선거 온도계 조사의 유사한 데이터 분석 결과 콘도르셋 주기 가능성은 0.4%로 나타났다. 이러한 파생 선거는 759명에서 2521명 사이의 "유권자"^[21]를 가지고 있었다.

역설의 예는 작은 환경(예: 의회)에서 가끔 일어나는 것처럼 보이지만, 일부는 확인되었지만, 몇몇은 더 큰 그룹(예: 선거인단)에서 거의 발견되지 않았다.^[23]

시사점

선거를 결정하는 데 콘도르셋 방법이 사용될 때, 순환적 사회 선호의 투표 역설은 선거에는 콘도르셋 승자가 없다는 것을 암시한다. 즉, 서로 상대하는 1대1 선거에서 이길 수 있는 후보가 없다. 스미스가 정한 것으로 알려진 가장 작은 규모의 후보군이 여전히 있을 것이고, 그렇게 되면 그룹 내의 각 후보들이 그룹 밖의 각 후보자들을 상대로 일대일 선거에서 승리할 수 있을 것이다. 콘도르셋 방법의 몇 가지 변형들은 승자를 결정하기 위해 발생할 때 그러한 애매한 점을 어떻게 해결하느냐에 따라 다르다.^[24] 콘도르셋 당첨자가 없을 때 항상 스미스 씨로부터 누군가를 선출하는 콘도르셋 방법은 스미스 효율적이라고 알려져 있다. 순위만 사용해도 각 후보가 정확히 대칭적인 상황에 있기 때문에 앞에서 제시한 사소한 예에 대해서는 공정하고 결정론적인 해결책이 없다는 점에 유의한다.

투표 역설이 있는 상황은 투표 메커니즘이 관련 없는 대안들의 독립이라는 공리를 위반하게 할 수 있다. 즉, 투표 메커니즘에 의한 승자의 선택은 패배한 후보가 투표할 수 있는지의 여부에 의해 영향을 받을 수 있다.

2단계 투표 프로세스

실제 상황에서 투표 역설이 존재할 수 있다는 한 가지 중요한 시사점은 2단계 투표 과정에서 최종 승자는 두 단계가 구조화되는 방식에 따라 달라질 수 있다는 것이다. 예를 들어, 한 정당의 지도부를 대상으로 한 공개 예비선거에서 A 대 B의 승자가 총선에서 제2당 대표 C와 맞붙게 된다고 가정하자. 앞의 예에서 A는 B를 제1당 공천으로 물리친 뒤 총선에서 C에게 패하게 된다. 그러나 만약 B가 제1당이 아닌 제2당에 있었다면, B는 그 당의 공천을 위해 C를 물리친 다음 총선에서 A에게 패할 것이다. 따라서 두 단계의 구조는 A 또는 C가 최종 승자인지에 차이를 만든다.

마찬가지로, 입법부의 일련의 투표 구조는 선호하는 결과를 보장하기 위해 투표를 주선하는 사람에 의해 조작될 수 있다.

콘도르케트 역설의 구조는 일부 기하학적 구조에서 "보다 빨리 회전한다", "들어올리고 들어올리지 않는다", "보다 강하다"와 같은 관계의 비타협성을 나타내는 기계 장치들에서 재현될 수 있다.^[25]

참고 항목

• 화살의 불가능 정리
  • Kenneth Arrow(케네스 화살표), 비타협성 분포 난이도 + 다수결 원칙의 예와 함께 섹션
• 디스커버리 딜레마
• 기바르-사테르스와이트 정리
• 관련 없는 대안의 독립성
• 즉석 결선투표
• 나카무라 번
• 2차 투표
• 가위바위보
• 심슨의 역설
• 스미스 세트

참조

추가 읽기

• Garman, M. B.; Kamien, M. I. (1968). "The paradox of voting: Probability calculations". Behavioral Science. 13 (4): 306–316. doi:10.1002/bs.3830130405. PMID 5663897.
• Niemi, R. G.; Weisberg, H. (1968). "A mathematical solution for the probability of the paradox of voting". Behavioral Science. 13 (4): 317–323. doi:10.1002/bs.3830130406. PMID 5663898.
• Niemi, R. G.; Wright, J. R. (1987). "Voting cycles and the structure of individual preferences". Social Choice and Welfare. 4 (3): 173–183. doi:10.1007/BF00433943. JSTOR 41105865. S2CID 145654171.