Finding Common Ground in a Sea of Alternatives

이 논문은 무한한 대안과 다양한 선호를 가진 집단 간 공통된 합의를 찾기 위해 사회선택 이론의 비례적 거부 코어 (proportional veto core) 개념을 기반으로 한 효율적인 샘플링 알고리즘을 제안하고, 그 이론적 하한과 실험적 유효성을 입증합니다.

핵심

"모두의 공통점을 찾는 바다에서 항해하기" 논문 설명

이 논문은 대립과 갈등이 심한 세상에서, 서로 다른 의견을 가진 사람들이 모두 받아들일 수 있는 '공통의 언어'를 어떻게 찾아낼 수 있을까? 라는 질문에 답합니다. 특히 최근 화두인 인공지능 (AI) 이 이 문제를 해결하는 데 어떤 역할을 할 수 있는지, 그리고 어떤 방식이 가장 공정한지 수학적으로 증명합니다.

이 내용을 일상적인 비유와 쉬운 한국어로 설명해 드리겠습니다.

---

1. 문제 상황: "우리와 그들"의 전쟁

지금 우리 사회는 정치나 사회적 이슈를 두고 "우리 vs 그들"로 나뉘어 극단적으로 대립하고 있습니다. 서로의 말을 들으려 하지 않고, 오직 자신의 주장만 내세우다 보니 대화는 막히고, 신뢰는 무너집니다.

이 문제를 해결하기 위해 '시민 회의' 나 '대화 프로그램' 같은 시도들이 있습니다. 하지만 이 방법들은 비용이 많이 들고, 많은 사람이 모이면 소수의 목소리가 묻히기 쉽습니다.

여기서 생성형 AI (LLM) 가 등장합니다. AI 는 무수히 많은 문장 (대안) 을 만들어낼 수 있기 때문에, 서로 다른 의견을 조율하는 '중재자' 역할을 할 수 있을 것 같아 보입니다. 실제로 '하버마스 머신 (Habermas machine)' 같은 AI 도구를 써서 사람들이 합의점을 찾게 하려는 시도가 있었죠.

하지만 큰 문제가 하나 있습니다.
AI 가 만들어낸 수많은 문장 중 어떤 것을 최종 선택할지 정하는 규칙이 잘못되어 있다면, 소수의 의견은 완전히 무시당하고 다수결의 폭주가 일어날 수 있습니다. 마치 "다수가 좋아하는 것만 고르면 되니까, 소수의 고통은 무시해도 돼"라고 말하는 것과 같습니다.

2. 해결책: "비토 (Veto) 권한"을 가진 공정한 규칙

저자들은 이 문제를 해결하기 위해 "비례적 거부권 핵심 (Proportional Veto Core, PVC)" 이라는 수학적 개념을 제안합니다.

🍕 비유: 피자를 나누는 상황

가상의 상황을 상상해 보세요. 100 명이 모여서 피자를 주문합니다.

• 30 명은 '페퍼로니'를 원하고, 70 명은 '치즈'를 원합니다.
• 만약 단순 다수결이라면 70% 의 의견인 '치즈' 피자가 선택됩니다. 30% 는 불만족스럽지만 어쩔 수 없습니다.
• 하지만 이 논문의 규칙 (PVC) 은 다릅니다. "30% 의 사람들이 '페퍼로니'를 싫어하는 대신, '치즈'보다 훨씬 더 싫어하는 '양파' 피자가 있다면, 그 '양파' 피자는 절대 선택될 수 없다"는 것입니다.

즉, 소수 집단이 "우리가 절대 싫어하는 것"을 찾아내면, 그걸로 그 대안은 탈락합니다.
이 규칙은 "소수 집단이 얼마나 큰 무언가를 포기할 수 있는가?"를 기준으로 합니다. 만약 30% 의 사람들이 70% 의 대안들을 모두 좋아한다면, 그 30% 는 30% 에 해당하는 '거부권'을 행사할 수 있게 됩니다.

핵심 메시지: "공통점"이란 "모두가 100% 만족하는 것"이 아니라, "아무도 극도로 싫어하지 않는 것" 입니다. 이 논문의 AI 는 바로 이런 '아무도 싫어하지 않는 안전한 피자를 찾아내는' 역할을 합니다.

3. 방법론: "바다에서 보석 찾기"

문제는 AI 가 만들어낼 수 있는 문장의 수가 무한에 가깝다는 점입니다. 모든 문장을 다 확인하고 선택할 수는 없습니다.

저자들은 "질문 (Query)" 을 통해 효율적으로 보석을 찾는 방법을 개발했습니다.

• 생성 질문 (Generative Query): AI 에게 "이 주제에 대해 다양한 문장을 10 개 만들어줘"라고 묻습니다. (바다에서 물고기를 잡는 행위)
• 판별 질문 (Discriminative Query): "이 두 문장 중 어떤 게 더 싫어요?"라고 사람들에게 묻습니다. (잡은 물고기 중 가장 못 생긴 걸 고르는 행위)

이 논문은 "얼마나 많은 질문을 해야 진짜 좋은 공통점을 찾을 수 있을까?" 에 대한 수학적 답을 제시합니다.

• 결과: 생각보다 적은 질문으로도, 아주 높은 확률로 '공통점 (PVC)'에 해당하는 문장을 찾을 수 있습니다.
• 한계: 반대로, 그 문장이 정말로 '공통점'인지 확신 (인증) 하려면 더 많은 질문이 필요하다는 것도 증명했습니다. (보석을 찾기는 쉽지만, 그것이 진짜 보석인지 증명하는 건 어렵다는 뜻입니다.)

4. 실험 결과: AI vs 전통적인 투표

저자들은 실제 데이터로 실험을 해보았습니다.

• 전통적인 투표 방식 (Schulze, 다수결 등): 소수의 의견을 무시하고 다수결로 결정하는 방식은, '공통점'을 찾는 데 실패했습니다. (비록 소수가 싫어하는 문장을 고를 확률이 높음)
• 이 논문의 알고리즘 (Veto-by-Consumption): 소수의 '싫어하는 것'을 배제하는 방식을 따랐더니, 거의 완벽하게 '공통점'을 찾아냈습니다.
• AI 가 직접 문장을 만드는 경우: AI 가 새로운 문장을 만들어내면, 잘만 하면 공통점을 찾을 수 있지만, 사람들의 성향을 제대로 이해하지 못하면 (예: 특정 성향에 치우친 데이터만 줌) 오히려 더 나쁜 결과를 낳았습니다.

5. 결론: 왜 이 연구가 중요한가?

이 논문은 AI 시대의 민주주의를 위한 안전장치를 제시합니다.

1. 소수의 목소리를 보호합니다: 다수가 싫어하지 않는 것만 고르는 게 아니라, 소수가 "절대 싫어하는 것"을 배제함으로써 극단적인 대립을 막습니다.
2. 효율성을 증명합니다: 모든 의견을 다 들을 수는 없지만, 수학적으로 증명된 방법으로 적은 비용으로도 공정한 합의를 이끌어낼 수 있습니다.
3. AI 의 올바른 사용법을 알려줍니다: AI 는 단순히 "가장 인기 있는 말"을 고르는 도구가 아니라, "누구도 배제하지 않는 안전한 말"을 찾아주는 도구로 사용되어야 함을 보여줍니다.

한 줄 요약:

"우리가 모두 동의할 수 있는 완벽한 문장은 없을지라도, 아무도 극도로 싫어하지 않는 안전한 문장을 찾아내는 수학적 나침반을 만들었습니다. 이 나침반을 통해 AI 는 우리 사회의 극단적인 대립을 해소하는 '공통의 언어'를 찾아낼 수 있습니다."

기술 요약

1. 문제 정의 (Problem Definition)

• 배경: 극심한 정치적 양극화 (Polarization) 가 민주주의를 위협하고 있으며, 이를 해결하기 위해 다양한 집단의 의견을 수렴하여 '공통된 지점 (Common Ground)'을 찾는 노력이 필요합니다. 최근 대규모 언어 모델 (LLM) 은 방대한 텍스트 생성 능력을 통해 이러한 과제를 수행할 잠재력을 가졌으나 (예: Habermas machine), 생성된 수많은 대안 중 어떤 것을 선택할지에 대한 체계적인 기준이 부족합니다.
• 핵심 문제:
  1. 무한한 대안 공간: LLM 은 실질적으로 무한한 수의 문장 (대안) 을 생성할 수 있습니다. 기존의 유한한 대안을 전제로 한 사회적 선택 이론 (Social Choice Theory) 을 어떻게 적용할 것인가?
  2. 소수 의견의 보호: 기존의 다수결 투표 규칙 (예: Schulze 규칙) 은 소수 의견을 무시하고 소수 다수 (slight majority) 의 선호를 반영할 수 있어, 진정한 공통 지점을 찾기 어렵게 만듭니다.
  3. 정보의 제한: 모든 대안과 유권자의 선호도를 완벽하게 알 수 없으며, 생성 (Generative) 과 판별 (Discriminative) 쿼리를 통해 제한된 정보만 접근 가능합니다.

2. 방법론 및 모델 (Methodology & Model)

저자들은 **$\epsilon$-비례 거부 코어 ($\epsilon$-Proportional Veto Core, $\epsilon$-PVC)**를 기반으로 한 새로운 수학적 모델을 제안합니다.

A. $\epsilon$-비례 거부 코어 ($\epsilon$-PVC)

• 정의: 유권자 집단의 특정 연합 (Coalition) 이 대안 $a$보다 선호하는 대안들의 집합 $S$의 측정도 (Measure) 가 일정 임계값을 초과할 때, 그 연합은 $a$를 '거부 (Block)'할 수 있습니다. $\epsilon$-PVC 는 어떤 연합도 이를 거부할 수 없는 대안들의 집합입니다.
• 수식적 의미: 유권자 집합 $N$의 크기가 $n$일 때, 유권자 비율 $|T|/n$만큼의 연합이 대안 $a$보다 선호하는 대안 집합 $S$의 확률 분포 $D$에서의 측정도 $\mu_D(S)$가 $1 - \frac{|T|}{n} + \epsilon$보다 크다면 $a$는 거부됩니다.
• 의미: $\epsilon$이 작을수록 소수 집단이라도 충분히 큰 대안 집합을 선호한다면 그 대안을 거부할 수 있어, 소수 의견이 결과에 반영됨을 보장합니다. $\epsilon \to 0$에 가까울수록 진정한 '공통 지점'에 가깝습니다.

B. 쿼리 기반 정보 접근 모델

무한한 대안 공간에서 효율적으로 $\epsilon$-PVC 원소를 찾기 위해 두 가지 쿼리 유형을 사용합니다.

1. 생성 쿼리 (Generative Queries): 알 수 없는 분포 $D$에서 무작위 대안을 샘플링합니다 (예: LLM 에 프롬프트를 입력하여 문장 생성).
2. 판별 쿼리 (Discriminative Queries): 유권자의 선호를 질의합니다.
   • Min-query: 주어진 집합 중 유권자가 가장 싫어하는 대안을 반환.
   • Pairwise query: 두 대안 중 유권자가 더 선호하는 것을 반환.

C. 알고리즘

• 샘플링 기반 알고리즘 (Algorithm 2):
  1. 생성 쿼리를 통해 $\tau \approx O(1/\epsilon^2 \cdot \log(1/\delta))$개의 대안 집합 $M$을 샘플링합니다.
  2. 이 집합 내에서 무작위 유권자를 선택하고 Min-query 를 수행하여 가장 싫어하는 대안을 제거하는 과정을 반복합니다 (Vote by Veto 규칙 적용).
  3. 최종적으로 남은 하나의 대안을 반환합니다.
• 이론적 보장: 이 알고리즘은 높은 확률 ($1-\delta$) 로 $\epsilon$-PVC 에 속하는 대안을 반환하며, 필요한 쿼리 횟수는 유권자 수 $N$이나 대안 공간의 크기에 의존하지 않습니다.

3. 주요 기여 (Key Contributions)

1. 무한 대안 공간에 대한 공식적 모델 제안: 사회적 선택 이론을 LLM 이 생성하는 무한한 텍스트 공간에 적용하기 위해 $\epsilon$-PVC 를 확장하고, 이를 위한 '임계 $\epsilon$ (Critical $\epsilon$)' 지표를 정의했습니다.
2. 샘플 복잡도 (Sample Complexity) 분석:
   • 상한선 (Upper Bound): $\tilde{O}(1/\epsilon^2)$개의 생성 및 판별 쿼리로 $\epsilon$-PVC 원소를 찾을 수 있음을 증명했습니다.
   • 하한선 (Lower Bound): 어떤 알고리즘도 $\Omega(1/\epsilon^2)$보다 적은 쿼리로는 $\epsilon$-PVC 원소를 식별할 수 없음을 정보 이론적 하한을 통해 증명했습니다. 이는 제안된 알고리즘이 최악의 경우에서 최적 (Tight) 임을 의미합니다.
   • 발견과 식별의 간극: $\epsilon$-PVC 원소를 '발견 (Generate)'하는 데는 $\tilde{O}(1/\epsilon)$ 쿼리가 suffice 하지만, 그것이 $\epsilon$-PVC 에 속함을 '식별 (Identify)'하는 데는 $\tilde{O}(1/\epsilon^2)$이 필요하다는 흥미로운 간극을 발견했습니다.
3. LLM 기반 투표 규칙 평가 프레임워크: 생성된 문장들이 얼마나 잘 공통 지점을 반영하는지 측정하기 위해 임계 $\epsilon$을 실증적 지표로 활용하는 방법을 제시했습니다.

4. 실험 결과 (Experimental Results)

저자들은 합성 데이터 (Synthetic Data) 를 사용하여 다양한 투표 규칙과 LLM 기반 방법을 비교 평가했습니다.

• 데이터셋: 다양한 정치적 주제 (낙태, 선거인단, 의료 등) 에 대해 100 명의 가상의 유권자 (Persona) 와 100 개의 대안을 생성했습니다.
• 비교 대상:
  • 기존 투표 규칙: Schulze, Borda, IRV, Plurality 등.
  • 제안 알고리즘: Veto-By-Consumption (VBC, 제안된 샘플링 알고리즘).
  • LLM 기반 생성/선택: GPT-Blind, GPT-Synthesize 등.
• 주요 결과:
  1. VBC 의 우월성: 제안된 VBC 알고리즘은 모든 주제에서 **가장 낮은 임계 $\epsilon$ (평균 0.001 미만)**을 기록하여, 소수 의견을 가장 잘 반영하는 공통 지점을 찾았습니다.
  2. 기존 규칙의 한계: Schulze 규칙 (Habermas machine 사용) 은 VBC 보다 임계 $\epsilon$이 약 10 배 높았으며, Plurality 규칙은 무작위 선택보다도 성능이 나쁜 경우가 있었습니다. 이는 다수결 중심 규칙이 소수 의견을 배제할 수 있음을 시사합니다.
  3. LLM 의 성능: LLM 이 직접 공통 지점을 생성하거나 선택하는 경우, VBC 나 Borda 점수법보다는 성능이 떨어졌습니다. 특히 유권자 분포 (Ideology) 가 편향된 경우 (예: 보수층만 있는 집단), LLM 기반 생성 규칙은 임계 $\epsilon$이 급격히 증가하여 무작위 선택보다도 나쁜 결과를 보였습니다. 이는 LLM 이 일반 대중의 편향을 학습하고 있어 특정 소수 집단의 요구를 충족시키지 못할 수 있음을 보여줍니다.
  4. 정보의 중요성: LLM 에 유권자 프로필 (Persona) 과 선호도 순위 정보를 제공할수록 성능이 향상되었으나, 여전히 VBC 에는 미치지 못했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 이론적 의의: 무한한 대안 공간에서의 사회적 선택 문제를 해결하기 위한 엄밀한 수학적 틀 ($\epsilon$-PVC) 과 최적의 샘플링 알고리즘을 제시했습니다.
• 실용적 의의:
  • AI 기반 합의 도출: LLM 을 활용한 민주적 deliberation 시스템 (예: Habermas machine) 에서 단순히 다수결을 적용하는 대신, **비례 거부 코어 (PVC)**를 기반으로 한 규칙을 도입해야 소수 의견이 배제되지 않는 진정한 공통 지점을 찾을 수 있음을 증명했습니다.
  • LLM 의 한계와 보완: LLM 은 훌륭한 생성 도구이지만, 편향된 분포를 학습하고 있어 소수 집단을 대표하는 공통 지점을 자동으로 찾아내기 어렵습니다. 따라서 LLM 이 생성한 대안들을 필터링하거나 선택할 때, **샘플링 기반의 사회적 선택 알고리즘 (VBC)**을 결합하는 것이 필수적입니다.
• 미래 전망: 이 연구는 AI 와 민주주의의 접점에서, 어떻게 하면 기술이 극단적인 양극화를 완화하고 포용적인 합의를 이끌어낼 수 있는지에 대한 새로운 방향성을 제시합니다.

요약하자면, 이 논문은 **"무한한 대안 속에서 소수 의견까지 고려한 진정한 공통 지점을 찾기 위해서는, 단순한 LLM 생성이나 다수결 투표가 아닌, 비례 거부 코어 ($\epsilon$-PVC) 를 기반으로 한 효율적인 샘플링 알고리즘이 필요하다"**는 것을 이론적, 실험적으로 입증했습니다.