기버드-새터스웨이트 정리 (Gibbard–Satterthwaite Theorem)

한 줄 정의: 대안이 세 개 이상일 때, 모든 유권자가 언제나 정직하게 투표하는 것이 최선이 되는 결정론적 순위투표 방식은 사실상 독재자 한 명이 결과를 정하는 방식뿐이라는 사회선택이론의 불가능성 정리.

쉽게 풀면

여러 사람이 세 가지 이상의 후보 중 하나를 뽑아야 하는 상황을 생각해 보세요. 기버드-새터스웨이트 정리는, '완벽하게 공정하면서도 아무도 거짓말할 이유가 없는' 투표 규칙이 존재하려면 결국 한 사람의 선택이 곧 전체 결과가 되는 '독재' 방식밖에 없다는 것을 수학적으로 증명합니다.

왜 중요한가

이 정리는 애로우의 불가능성 정리와 함께 사회선택이론의 두 축을 이루며, 선거 제도 설계, 위원회 의사결정, 매칭 알고리즘 등 다수의 선호를 하나로 모으는 모든 메커니즘 설계 문제에서 전략적 조작 가능성을 완전히 없앨 수 없다는 이론적 한계를 제시합니다.

논문에서는 이렇게 쓰입니다

"본 연구는 기버드-새터스웨이트 정리에 따라 결정론적이고 전략내구적인 순위투표 규칙이 존재하지 않음을 전제로, 확률적 투표 메커니즘의 근사적 전략내구성을 분석한다."

완벽하게 조작 불가능한 결정론적 투표 규칙은 불가능하므로, 대안으로 확률적 메커니즘을 사용해 조작 유인을 최소화하는 접근을 연구한다는 의미입니다.

"제안된 매칭 알고리즘이 완전한 전략내구성을 달성하지 못하는 것은 기버드-새터스웨이트 정리가 시사하는 근본적 한계와 일치하며, 이는 설계상의 결함이 아니라 이론적으로 불가피한 결과이다."

알고리즘이 조작에 완전히 안전하지 않은 이유는 만든 사람의 실수가 아니라, 수학적으로 피할 수 없는 한계임을 설명하는 문장입니다.

조금 더 깊게 보면

기버드-새터스웨이트 정리는 애로우의 불가능성 정리와 형식적으로 동치 관계에 있는 것으로 알려져 있다. 대안이 정확히 두 개일 때는 성립하지 않으며, 대안의 수를 제한하거나 결과에 무작위성을 허용하면 정리의 결론을 부분적으로 피해갈 수 있다. 이 정리가 다루는 '전략내구성'은 어떤 유권자도 자신의 진짜 선호 순서를 그대로 표현하는 것보다 다른 순서로 거짓 투표하는 것이 유리해지는 상황이 전혀 없어야 한다는 매우 강한 조건이며, 현실의 투표 제도 대부분은 이 조건을 완전히 만족하지 못한 채 부분적인 절충안으로 설계됩니다.

주의할 점

이 정리는 "모든 투표는 무의미하다"는 뜻이 아니라, 완전한 전략내구성과 비독재성을 동시에 만족하는 결정론적 규칙이 존재하지 않는다는 수학적 한계를 말하는 것입니다.