Characterizing Necessary Losers to Explain Tournaments Losers

기술 요약: 토너먼트 패배자를 설명하기 위한 필수 패배자 특성화

문제 정의
본 논문은 주어진 토너먼트 규칙(투표 시스템)에 의해 특정 후보가 선택되지 않는 이유를 공식적으로 설명하는 과제를 다룹니다. 계산 사회 선택(computational social choice) 및 설명 가능한 인공지능(XAI) 분야의 기존 문헌은 후보가 승리하는 이유를 정당화하는 것(구성적 설명)에 집중해 왔으나, 후보가 패배하는 이유를 설명하는 데에는 공백이 존재합니다. 특히 절차적 정의 이론에 따르면 불리한 결과가 발생했을 때 설명이 신뢰 유지를 위해 매우 중요하다는 점을 고려할 때, 이 공백은 중요합니다.

저자들은 이 문제를 후보들 간의 쌍체 비교를 나타내는 토너먼트를 사용하여 프레임화합니다. 이들은 **파괴적 최소 지지 집합(Destructive Minimal Supports, dMS)**이라는 개념을 도입합니다. dMS는 조사 대상 후보가 해당 부분 토너먼트 내에서 **필수 패배자(necessary loser)**가 되는 원래 토너먼트의 최소 부분 토너먼트로 정의됩니다. 후보가 필수 패배자라는 것은, 미지정된 나머지 비교 결과가 어떻게 결정되더라도 해당 부분 토너먼트의 모든 가능한 완성 형태에서 승리하지 못함을 의미합니다. 이 접근 방식은 잔여 비교가 어떻게 해결되든 관계없이 후보의 패배를 보장하는 가장 작은 쌍체 비교 집합을 식별하기 위해 귀추적 추론(abductive reasoning)을 활용합니다.

방법론
본 논문은 에지가 한 후보가 다른 후보를 선호하는 투표자 수를 나타내는 부분 $n$-가중 토너먼트를 기반으로 한 공식 프레임워크를 채택합니다. 방법론은 세 가지 주요 단계로 진행됩니다:

1. 공식적 특성화: 저자들은 6가지 일반적인 토너먼트 솔루션인 탑 사이클(Top Cycle, TC), 보르다(Borda, BO), 코플랜드(Copeland, CO), 맥시민(Maximin, MM), 언커버드 세트(Uncovered Set, UC), 가중 언커버드 세트(Weighted Uncovered Set, wUC)에 대해 후보가 필수 패배자가 되기 위한 필요충분조건을 도출합니다.

   • **탑 사이클(TC)**의 경우, 패배자와 강결합 성분(strongly connected component)을 분리하는 "일방향 경계(one-way frontier)"의 존재 여부에 의존합니다.
   • 보르다(BO) 및 **코플랜드(CO)**의 경우, 조건은 패배자의 최대 가능한 점수를 다른 후보들로 구성된 연합의 최소 가능한 평균 점수와 비교하는 것을 포함합니다.
   • 맥시민(MM) 및 **가중 언커버드 세트(wUC)**의 경우, 저자들은 문제를 특정 이분 그래프($l$-결핍 유도 그래프)에서의 완전 매칭 존재 문제로 환원합니다. 이들은 부분 토너먼트 내에서 특정 트리 구조의 존재를 보장하는 홀의 결혼 정리(Hall's Marriage Theorem)를 활용하여 후보의 패배를 특성화합니다.

2. 알고리즘 분석: 본 논문은 이러한 설명을 찾는 데 드는 계산 복잡도를 조사합니다. 이는 결정 문제(후보가 필수 패배자인지 여부를 판별)와 최적화 문제(총 가중치 합을 최소화하는 최소 파괴적 최소 지지 집합, 즉 SdMS를 찾는 것)를 구분합니다.

3. 크기 경계: 저자들은 각 규칙에 대한 SdMS의 크기에 대한 명시적인 공식과 타이트한 상한선을 제공하며, 투표자 수($n$)와 후보 수($m$)가 설명의 복잡도에 어떻게 영향을 미치는지 분석합니다.

주요 기여 및 결과
본 논문은 원문의 표 1에 요약된 바와 같이 다음과 같은 구체적인 특성화 및 결과를 제공합니다:

• 탑 사이클 (TC): 후보가 필수 패배자인 필요충분조건은 부분 토너먼트에서 모든 후보가 $K$ 외부의 후보(패배자 포함)를 이기는 비어 있지 않은 다른 후보들의 집합 $K$가 존재하는 것입니다. 가장 작은 dMS의 크기는 $\lfloor m^2/4 \rfloor$로 제한되며 다항 시간 내에 계산할 수 있습니다.
• 보르다 (BO): (Schwartz로부터 적응된) 특성화에 따르면, 후보가 필수 패배자인 경우는 후보 집합 $K$가 패배자의 최대 가능한 점수보다 엄격히 큰 최소 집합적 보르다 점수를 가질 때입니다. 저자들은 보르다의 SdMS를 찾는 것이 **NP-완전(NP-complete)**일 것으로 추측합니다. 크기에 대한 상한은 $n(m-1) + 1$입니다.
• 코플랜드 (CO): 보르다와 유사하지만 가중치가 없는 토너먼트로 제한됩니다. SdMS는 $m$의 크기 경계 내에서 다항 시간 내에 계산될 수 있습니다.
• 맥시민 (MM): 후보가 필수 패배자인 경우는 패배자의 잠재적 최대 점수와 관련된 특정 가중치 제약을 만족하는 부분 토너먼트 내의 트리 구조가 존재하는 경우입니다. SdMS는 $\binom{n+1}{2}(m-2) + n + 1$의 크기 경계를 가지며 다항 시간 내에 계산 가능합니다.
• 언커버드 세트 (UC) 및 가중 언커버드 세트 (wUC): 특성화는 특정 커버링 조건을 충족하는 트리 구조를 포함합니다. 특히 wUC의 경우, SdMS는 다항 시간 내에 계산 가능합니다. 이는 후보를 승리하게 만들기 위한 가장 작은 지지 집합을 찾는 구성적 버전의 문제가 NP-완전으로 알려진 것과 대조적입니다. 크기 경계는 $n(m-2) + \binom{n+1}{2}$입니다.

의의 및 주장
저자들은 이 연구를 설명 가능한 AI 및 집단 의사결정의 절차적 정의 분야에 대한 기여로 포지셔닝합니다. 주요 주장은 다음과 같습니다:

1. "불리한 결과"의 공백 해결: 본 논문은 후보가 왜 패배하는지에 대한 귀추적 설명을 제공함으로써, 후보가 왜 승리하는지를 설명하는 것과는 구별되는, 그리고 종종 더 복잡한 XAI의 중요한 공백을 메웁니다.
2. 설명의 효율성: 결과는 대부분의 토너먼트 규칙(TC, CO, MM, UC, wUC)에 대해 가장 작은 설명(SdMS)을 효율적으로(다항 시간 내에) 계산할 수 있으며, 전체 토너먼트 데이터의 일부($O(m^2)$ 또는 $O(nm)$)만을 필요로 한다는 것을 보여줍니다. 이는 복잡한 투표 시스템에서도 압축되고 이해 가능한 설명이 가능하다는 것을 시사합니다.
3. 복잡도 대비: 본 논문은 상당한 계산 복잡도의 비대칭성을 강조합니다. 가중 언커버드 세트에 대해 가장 작은 구성적 지지(후보를 승리하게 함)를 찾는 것은 NP-완전인 반면, 가장 작은 파괴적 지지(후보가 패배함을 증명함)를 찾는 것은 P 클래스에 속합니다.
4. 한계 및 향후 과제: 저자들은 보르다 규칙의 SdMS에 대한 복잡도 상태가 여전히 미해결 상태(NP-완전으로 추측됨)임을 겸허히 언급합니다. 또한, 크기(비교 횟수)를 최소화하는 것이 반드시 가장 인간이 이해하기 쉬운 구조를 의미하는 것은 아니라는 점을 인정하며, 어떤 지표를 사용자가 설명으로서 선호하는지 결정하기 위해 향후 실증적 연구가 필요함을 시사합니다.

본 논문은 이러한 공식적이고 최소한의 설명을 제공하는 것이, 특히 불리한 결과에 직면한 이해관계자들에게 의사결정 과정의 정당성과 신뢰성을 높일 수 있다고 결론짓습니다.