Preference Analysis Using Random Spanning Trees: A Stochastic Sampling Approach to Inconsistent Pairwise Comparisons

1. 연구 배경 및 문제 제기 (Problem)

• 기존 방법론의 한계: 의사결정 분석 (MCDM) 에서 선호도를 도출할 때, 쌍대 비교 (Pairwise Comparisons, PC) 를 통해 단일 우선순위 벡터 (Priority Vector) 를 산출하는 것이 일반적입니다. 그러나 인간의 판단은 본질적으로 불완전하며 일관성 (Consistency) 이 결여되는 경우가 많습니다.
• 일관성 (Inconsistency) 에 대한 오해: 기존 방법론 (AHP 의 고유벡터법, 행렬의 기하평균법 등) 은 일관성 결여를 '오차'로 간주하고 이를 최소화하거나 보정하여 하나의 '진짜' 선호도를 찾으려 합니다. 이는 판단에 내재된 불확실성과 다의적 의미를 폐기하는 결과를 초래합니다.
• 계산적 병목 현상: 일관성이 없는 판단을 처리하기 위해 '신장 트리 (Spanning Trees)' 접근법이 제안된 바 있습니다. 이는 모든 가능한 독립적인 판단 조합을 열거하여 가능한 모든 우선순위 벡터의 집합을 찾는 방법입니다. 그러나 문제의 규모 (대안 수 $n$, 기준 수 $m$) 가 커질수록 신장 트리의 조합 수가 기하급수적으로 증가하여 ($m^{m-2}n^{n-2}$), 실제적인 문제 (예: 4 대안, 6 기준) 에서도 수십억 개의 조합이 발생하여 완전 열거 (Complete Enumeration) 가 계산적으로 불가능해집니다.
• 불완전 데이터의 처리: 실제 현장에서는 의사결정자가 모든 쌍대 비교에 응답하지 못하는 '불완전 데이터'가 빈번히 발생합니다. 기존 많은 방법론은 결측치를 추정 (Imputation) 하거나 완전한 데이터가 필요하지만, 이는 데이터의 무결성을 훼손할 수 있습니다.

2. 제안된 방법론 (Methodology)

이 논문은 일관성 결여를 '오차'가 아닌 '선호도 불확실성 (Preference Uncertainty)'의 신호로 재해석하고, 이를 통계적으로 분석하기 위한 확률적 무작위 보행 (Stochastic Random Walk) 샘플링 프레임워크를 제안합니다.

• 핵심 개념:
  • 신장 트리 (Spanning Trees): 쌍대 비교 행렬에서 $n-1$개의 독립적인 판단으로 구성된 그래프 이론적 구조입니다. 각 신장 트리는 의사결정자의 하나의 일관된 '마인드셋 (Mindset)'을 나타냅니다.
  • 확률적 지표:
    • 쌍대 승리 지수 (Pairwise Winning Index, PWI): 한 대안이 다른 대안보다 선호될 확률.
    • 순위 수용 지수 (Rank Acceptability Index, RAI): 특정 대안이 특정 순위 (1 위, 2 위 등) 에 도달할 확률 분포.
• 무작위 보행 샘플링 (Random Walk Sampling):
  • 모든 신장 트리를 생성하여 열거하는 대신, 무작위 보행 (Random Walk) 알고리즘을 사용하여 신장 트리 집합에서 통계적으로 대표성 있는 표본을 추출합니다.
  • 이 방법은 Broder 와 Aldous 의 연구를 기반으로 하여, 생성된 표본이 전체 집합에서 균일하게 무작위 추출된 것과 통계적으로 동등함을 보장합니다.
• 표본 크기 결정:
  • 통계적 표본 이론을 적용하여 원하는 정확도 ($\lambda$) 와 신뢰 수준 ($C$) 을 달성하기 위해 필요한 반복 횟수 (표본 크기) 를 수학적으로 도출합니다.
  • 공식: $It(\lambda, C) = \frac{Z_C^2}{4\lambda^2}$ (예: 99% 신뢰도, $\pm 1\%$ 정확도 달성 시 약 16,641 회 반복 필요).
• 불완전 데이터 처리:
  • Kirchhoff 공식을 활용하여 결측치가 있는 쌍대 비교 행렬에서도 신장 트리를 생성할 수 있으므로, 별도의 데이터 보정 없이 불완전 데이터에 직접 적용 가능합니다.

3. 주요 결과 및 검증 (Results)

논문은 두 가지 사례를 통해 방법론의 유효성을 입증했습니다.

1. 교육 사례 (School Selection Example):

   • 3 개의 학교, 6 개의 기준을 가진 소규모 문제 (약 94 만 개의 신장 트리 조합) 에 적용.
   • 완전 열거 결과 vs 무작위 샘플링 결과: 무작위 보행을 통해 생성된 20,000 개의 표본으로 계산한 PWI 와 RAI 값이 전체 집합을 열거하여 얻은 실제 값과 1% 이내의 오차로 매우 근사함을 확인했습니다.
   • 통찰: 단일 순위가 아닌, "학교 A 가 1 위일 확률 51%, 2 위일 확률 49%"와 같은 확률적 분포를 제공하여 의사결정자의 불확실성을 정량화했습니다.

2. 통신 백본 인프라 선정 사례 (Telecom Backbone Selection):

   • 4 개의 대안 (광케이블, 전력선 통신, 마이크로파, 위성), 6 개의 상위 기준 (기술, 인프라, 경제 등) 을 가진 대규모 문제.
   • 계산 규모: 총 약 217 억 (21.7 Billion) 개의 신장 트리 조합이 존재하여 완전 열거가 불가능한 상황.
   • 성능: 20,000 번의 무작위 보행 반복을 통해 20 개의 실험을 수행. 각 실험 간 표준 편차가 0.005 이하로 매우 안정된 결과를 도출했습니다.
   • 결과:
     • '마이크로파'와 '위성 통신'이 1 위가 될 확률이 높음 (약 47%, 45%).
     • '광케이블'과 '전력선 통신'은 하위 순위 (3 위, 4 위) 에 머무를 확률이 매우 높음.
     • 기존 AHP/RGM 방법론과 달리, 어떤 대안이 우세한지뿐만 아니라 그 우세함이 얼마나 '강건한지 (Robustness)'를 확률적으로 제시했습니다.

4. 주요 기여 (Key Contributions)

1. 계산적 장벽 해소: 신장 트리 접근법의 기하급수적인 계산 복잡도를 무작위 샘플링을 통해 해결하여, 대규모 실세계 문제에 적용 가능한 수준으로 확장했습니다.
2. 불확실성의 정량화: 일관성 결여를 제거하려는 시도를 중단하고, 이를 선호도의 다중성 (Multiplicity) 과 불확실성으로 해석하여 PWI 와 RAI 를 통해 정량화했습니다.
3. 불완전 데이터 처리: 결측치 보정 없이 불완전한 쌍대 비교 행렬을 직접 처리할 수 있는 유연성을 제공합니다.
4. 통계적 엄밀성: 단순한 휴리스틱이 아닌, 통계적 표본 이론에 기반하여 필요한 샘플 크기를 보장하고 결과의 신뢰 구간을 제공합니다.

5. 의의 및 시사점 (Significance)

• 의사결정 지원의 패러다임 전환: "어떤 대안이 가장 좋은가?"라는 단일 정답을 찾는 것을 넘어, "어떤 대안이 얼마나 확신 있게 좋은가?"라는 확률적 통찰을 제공합니다. 이는 불확실성이 높은 환경에서의 의사결정자에게 더 풍부한 정보를 제공합니다.
• 실용성: 통신 인프라와 같은 대규모, 복잡한 다기준 의사결정 문제에서 기존 방법론으로는 불가능했던 '선호도 분포' 분석을 가능하게 합니다.
• 강건성 분석: PWI 와 RAI 를 통해 특정 대안의 순위가 판단의 미세한 변화에 얼마나 민감한지 (불확실성이 큰지) 를 파악할 수 있어, 의사결정자가 추가 정보 수집이 필요한 영역을 식별하는 데 도움을 줍니다.

결론적으로, 이 논문은 신장 트리 기반의 선호도 분석을 이론적 가능성을 넘어 실용적인 도구로 격상시켰으며, 불완전하고 일관성 없는 인간의 판단을 통계적으로 엄밀하게 처리하여 더 나은 의사결정을 지원하는 강력한 프레임워크를 제시했습니다.