Sequential Elimination and Union Shapley Value for Group Assessment in Coalitional Games

기술 요약: 연합 게임에서 그룹 평가를 위한 순차적 제거 및 유니온 샤플리 값

문제 제기
협력 게임 이론 및 네트워크 중심성, 머신러닝 데이터 가치 평가와 같은 관련 분야에서 근본적인 과제는 개별 플레이어 평가를 그룹으로 확장하는 것입니다. 기존 방법들은 일반적으로 두 가지 직관적인 접근법에 의존합니다:

1. 합산: 개별 가치의 집계 (예: 샤플리 값의 합). 이는 플레이어 간의 협력 구조와 의존성을 무시합니다.
2. 병합: 그룹을 단일 병합 요소로 취급하여 평가 (예: Merge 샤플리 값). 이는 게임 구조를 변경하며, 독립적인 플레이어와 고도로 의존적인 플레이어 간의 차이를 구분하지 못합니다.

두 접근법 모두 그룹 내 의존성을 정확하게 포착하는 데 자주 실패합니다. 예를 들어, 두 개의 분리된 플레이어 쌍이 독립적으로 가치를 생성하는 게임에서 개별 값을 합산하거나 그룹을 병합하면, 협력하는 플레이어 쌍과 독립적인 플레이어 쌍에게 동일한 중요도를 부여할 수 있으며, 이는 그들의 시스템적 영향력 비대칭성을 반영하지 못합니다.

방법론
저자들은 순차적 제거에 기반한 세 번째 접근법을 제안하고 분석합니다. 이 프레임워크에서는 그룹의 요소들을 하나씩 제거하고, 그 결과로 생성된 축소 게임에서의 평가를 집계합니다. 핵심 가설은 이 방법이 중복 효과를 할인하고 그룹의 부재로 인한 손실에 초점을 맞춤으로써 그룹의 순 기여도를 자연스럽게 측정한다는 것입니다.

본 연구는 연합 게임의 그룹 가치에 대한 포괄적인 공리 분석에 기반합니다. 방법론은 다음과 같습니다:

• 공리적 클래스 정의: 저자들은 그룹 (약 일관성) 세미값 클래스를 도입합니다. 이는 선형성, 대칭성, 약한 단조성, Null Player Out, 그리고 더미 플레이어 공리를 만족하는 그룹 값들입니다. 또한, Grabisch 와 Roubens 가 도입한 Dummifying Player 공리를 더미 플레이어 공리에 대체하는 시너지 세미값에 해당하는 클래스를 정의합니다.
• 순차적 확장: 이 논문은 플레이어 값이 균형 기여 속성을 만족할 때에만 순차적 확장을 허용함을 입증합니다. 또한, 모든 일관된 세미값 (Null Player Out 을 만족) 이 고유한 순차적 확장을 허용함이 증명되었습니다.
• 포텐셜 함수: 저자들은 Hart 와 Mas-Colell 이 도입한 포텐셜 함수를 활용하여 샤플리 값의 순차적 확장을 특징짓습니다.

주요 기여 및 결과

1. 유니온 샤플리 값 (The Union Shapley Value):
   저자들은 샤플리 값의 고유한 순차적 확장으로서 유니온 샤플리 값을 도입합니다. 이는 원래 게임의 포텐셜과 그룹이 제거된 후의 게임 포텐셜 간의 차이로 정의됩니다:
   $$US_S(N, v) = P(N, v) - P(N \setminus S, v) = \sum_{T \subseteq N, S \cap T \neq \emptyset} \frac{\Delta v(T)}{|T|}$$
   여기서 $\Delta v(T)$는 Harsanyi 배당금입니다.

   • 해석: 이 값은 그룹이 이탈할 때 게임에 가해지는 "손상"을 측정합니다. 그룹이 해당 연합의 여러 구성원을 포함하더라도 각 연합의 배당금이 최대 한 번만 계산되도록 기여도를 집계합니다.
   • 공리화: 유니온 샤플리 값은 포텐셜 (또는 균형 기여) 공리와 효율성의 결합으로 유일하게 특징지어집니다. 또한 그룹 세미값들 사이에서는 그룹 평등 (일치 게임에서 모든 그룹이 동등하게 중요하다) 으로 유일하게 특징지어집니다.

2. 그룹 가치의 공리적 분류:
   논문은 그룹 평가의 두 가지 변형을 구분합니다:

   • 총 가치 (Total Worth): 그룹의 총 가치를 평가하는 값들 (예: 합산 확장, Merge 샤플리, 유니온 샤플리). 이들은 그룹 세미값으로 포착됩니다.
   • 시너지 (Synergy): 그룹의 시너지를 측정하는 값들 (예: 상호작용 지수). 이들은 시너지 세미값으로 포착됩니다.
     저자들은 이 두 클래스 간의 함수적 대응을 제공합니다. 구체적으로, Merge 샤플리 값이 상호작용 지수 (시너지적 대응물) 에 해당하며, 유니온 샤플리 값이 인터섹션 샤플리 값이라는 새로운 시너지 값에 해당함을 보여줍니다.

3. 인터섹션 샤플리 값 (The Intersection Shapley Value):
   전체 그룹을 포함하는 연합들의 배당금 합으로 정의됩니다:
   $$IS_S(N, v) = \sum_{S \subseteq T \subseteq N} \frac{\Delta v(T)}{|T|}$$
   이 값은 기여도의 교집합을 측정합니다. 크기가 두 개인 그룹의 경우, 유니온 샤플리 값과 인터섹션 샤플리 값의 합은 개별 샤플리 값의 합과 같습니다:
   $$US_{\{i,j\}}(N, v) + IS_{\{i,j\}}(N, v) = SV_i(N, v) + SV_j(N, v)$$
   이 분해는 그룹의 결합 가치를 "유니온" 부분 (한 번만 계산된 기여도) 과 "인터섹션" 부분 (시너지) 으로 분리할 수 있게 합니다.

4. 기존 연구와의 비교:
   분석은 제안된 값들과 기존 문헌 간의 관계를 명확히 합니다:

   • Merge 샤플리 값 (Marichal 등) 은 더미 연합 공리를 만족하는 유일한 그룹 세미값임이 입증되었습니다.
   • 상호작용 지수 (Grabisch 와 Roubens) 는 표준 더미 플레이어 공리 대신 Dummifying Player 공리를 위반하기 때문에 그룹 세미값과 구별되는 시너지 세미값으로 식별됩니다.
   • 논문은 순차적 확장 접근법이 모든 일관된 세미값에 적용되며 강력한 공리적 속성을 가진 값을 산출하므로 이론적으로 견고함을 입증합니다.

의의
본 논문은 순차적 확장 접근법, 특히 유니온 샤플리 값이 연합 게임에서 플레이어 가치를 그룹으로 확장하는 가장 자연스럽고 이론적으로 근거 있는 방법 중 하나라고 주장합니다. 총 가치 평가와 시너지 측정을 구분함으로써 저자들은 기존 문헌의 개념들 간의 차이를 명확히 하는 통합된 프레임워크를 제공합니다. 유니온 및 인터섹션 샤플리 값의 도입은 기여도의 중복을 할인해야 하는 경우 (유니온) 나 순수 시너지를 분리해야 하는 경우 (인터섹션) 에 특히 상호작용을 분석하기 위한 새로운 도구를 제공합니다. 이 연구는 이러한 값들이 임의의 휴리스틱이 아니라 균형 기여, 포텐셜, 그룹 평등과 같은 근본적인 공리에 의해 유일하게 결정됨을 확립합니다.