기바드-새터스웨이트 정리

정리의 내용

투표 규칙이란 각 투표자가 제출한 선호 순위를 받아 당선자 한 명을 정하는 방식이에요. 어떤 투표자가 진짜 선호를 숨기고 다르게 투표해서 더 나은 결과를 얻을 수 있다면 그 규칙은 '조작 가능'하다고 해요. 기바드(1973)와 새터스웨이트(1975)는 선택지가 셋 이상이고 모든 선택지가 당선될 가능성이 있는 규칙이 조작 불가능하려면 한 사람의 선호가 항상 결과를 결정하는 독재여야 함을 보였어요. 예컨대 상대다수제에서 당선 가능성이 낮은 후보를 지지하는 유권자가 차선의 유력 후보에게 표를 주는 것이 전략적 투표의 대표 사례예요. 더밋과 파쿼슨(1961)은 이러한 조작 가능성을 일찍이 추측했고, 파쿼슨(1969)은 전략적 투표 이론을 체계화했어요.

애로 정리와의 관계

이 정리는 애로의 불가능성 정리와 긴밀히 연결돼 있어요. 새터스웨이트(1975)는 조작 불가능성 조건이 애로의 조건들과 대응한다는 것을 보였고, 레니(2001)는 두 정리를 하나의 간결한 논증으로 함께 증명했어요. 애로 정리가 개인 선호를 사회 선호로 합치는 일관된 방법이 없다는 결과라면, 기바드-새터스웨이트 정리는 정직한 투표를 유도하는 공정한 방법이 없다는 결과예요. 후르비치(1972)가 제기한 유인 양립성 개념과 함께 이 정리는 메커니즘 디자인 분야의 기본 제약이 되었어요. 더건과 슈워츠(2000)는 동점이 있거나 결과가 집합인 경우로 정리를 일반화했어요.

예외와 우회 방법

정리의 가정을 완화하면 조작 불가능한 규칙이 존재할 수 있어요. 물랭(1980)은 선호가 단봉형이면 중위값을 고르는 규칙 같은 조작 불가능한 규칙이 있음을 보였고, 기바드(1977)는 확률을 섞은 규칙에서도 조작 불가능한 규칙은 무작위 독재와 같은 매우 제한된 형태뿐임을 증명했어요. 바르베라(2011)는 이러한 결과들을 종합했어요. 컴퓨터과학에서는 바르톨디, 토비, 트릭(1989)이 조작이 이론적으로 가능해도 그 방법을 찾는 계산이 매우 어려운 규칙이 있다고 보였고, 팔리셰프스키와 헤마스판드라 부부(2010)는 계산 복잡도로 선거를 보호하는 연구를 정리했어요.

자주 묻는 질문

기바드-새터스웨이트 정리를 쉽게 설명하면?

후보가 셋 이상인 선거에서는 독재가 아닌 한 어떤 투표 방식을 쓰더라도, 누군가는 진짜 마음과 다르게 투표하는 편이 유리한 상황이 생긴다는 정리예요.

애로의 불가능성 정리와 무엇이 다른가요?

애로 정리는 개인의 선호를 일관된 사회적 순위로 합치는 문제를, 기바드-새터스웨이트 정리는 사람들이 정직하게 투표할 유인이 있는지를 다뤄요. 두 정리는 수학적으로 밀접하게 연결돼 있어요.

출처 검토일: 2026-10-26

참고문헌

1. Gibbard, A. (1973). Manipulation of voting schemes: A general result. Econometrica, 41(4), 587–601.
2. Satterthwaite, M. A. (1975). Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2), 187–217.
3. Arrow, K. J. (1951). Social Choice and Individual Values. New York: Wiley.
4. Dummett, M., & Farquharson, R. (1961). Stability in voting. Econometrica, 29(1), 33–43.
5. Farquharson, R. (1969). Theory of Voting. New Haven, CT: Yale University Press.
6. Moulin, H. (1980). On strategy-proofness and single peakedness. Public Choice, 35(4), 437–455.
7. Barberà, S. (2011). Strategyproof social choice. In K. J. Arrow, A. Sen, & K. Suzumura (Eds.), Handbook of Social Choice and Welfare (Vol. 2, pp. 731–831). Amsterdam: North-Holland.
8. Bartholdi, J. J., Tovey, C. A., & Trick, M. A. (1989). The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3), 227–241.
9. Gibbard, A. (1977). Manipulation of schemes that mix voting with chance. Econometrica, 45(3), 665–681.
10. Duggan, J., & Schwartz, T. (2000). Strategic manipulability without resoluteness or shared beliefs: Gibbard–Satterthwaite generalized. Social Choice and Welfare, 17(1), 85–93.
11. Hurwicz, L. (1972). On informationally decentralized systems. In C. B. McGuire & R. Radner (Eds.), Decision and Organization (pp. 297–336). Amsterdam: North-Holland.
12. Faliszewski, P., Hemaspaandra, E., & Hemaspaandra, L. A. (2010). Using complexity to protect elections. Communications of the ACM, 53(8), 74–82.
13. Reny, P. J. (2001). Arrow's theorem and the Gibbard–Satterthwaite theorem: A unified approach. Economics Letters, 70(1), 99–105.