연합 게임·Shapley 배분·Core 전체 집합

협력의 가치와 나누는 규칙은 다른 질문이다

세 연구실이 데이터를 합쳐 유용한 벤치마크를 만든다고 생각해 봅시다. 어떤 조합의 연구실이 얼마의 가치를 만들 수 있는지와, 최종 가치를 누구에게 얼마나 줄지는 다른 질문입니다. 모든 그룹의 가치에 합의해도 평균적인 기여를 계산한 배분과 연합이 이탈하지 않는 안정적 배분은 다를 수 있습니다.

이 단원은 주어진 가치함수를 갖는 이전 가능한 효용 게임을 다룹니다. 플레이어 집합은 N={0,1,2}입니다. 부분집합 S마다 v(S)는 그 연합이 얻을 수 있는 총보수이며 빈 연합의 가치는 0입니다. 공통 단위의 보수를 연합 내부에서 재분배할 수 있다고 가정합니다. 과학적 성과나 개인의 만족처럼 서로 다른 효용을 언제나 교환할 수 있다는 주장이 아닙니다.

특성함수는 협상의 자세한 절차도 추상화합니다. 외부 플레이어의 전략을 지정하지 않아도 연합 S의 가치가 의미 있다고 가정합니다. 외부의 방해나 다른 연합의 형성이 S의 능력을 바꾼다면 더 풍부한 모형이 필요합니다. 실습은 v(S)를 제공하며 관측 데이터에서 연합의 인과적 능력을 식별하지 않습니다.

연합·배분·효율성을 구분한다

연합은 플레이어의 부분집합이고, 배분 x=(x0,x1,x2)는 각자의 보수 벡터입니다. 효율성은 전체 연합이 만든 가치를 모두 나누는 조건입니다.

$$x_0+x_1+x_2=v(N).$$

효율적이라는 것만으로 각자가 참여할 이유가 생기지는 않습니다. 개별 합리성은 x_i≥v({i})를 요구합니다. 각자가 혼자 만들 수 있는 가치보다 적게 받지 않아야 한다는 뜻입니다. 효율성과 개별 합리성을 함께 만족하는 배분을 imputation이라고 부릅니다.

그림의 회색 삼각형은 음이 아닌 효율 배분을 나타냅니다. 혼자서도 양의 가치를 만드는 플레이어가 있으면 이 삼각형 안의 모든 점이 개별 합리적인 것은 아닙니다. 회색 영역을 모든 제약을 이미 만족한 집합으로 읽지 마세요.

입력은 x0=v(N)p0/12, x1=v(N)p1/12를 정하고 x2는 효율성으로 계산합니다. p0+p1이 12를 넘으면 x2는 음수입니다. 그 조회를 삼각형으로 몰래 투영하지 않고 바깥 사각형 안에 그대로 보여 줍니다. 제약 위반을 설명하기 위해 위반한 값을 보존합니다.

먼저 들어온 사람이 누구인지에 따라 추가 기여가 달라진다

한 가입 순서를 정하고 빈 연합에서 시작합니다. 앞선 플레이어 집합이 S일 때 플레이어 i가 들어오며 추가하는 가치는 다음과 같습니다.

$$\Delta_i(S)=v(S\cup\{i\})-v(S).$$

한 순서의 세 추가 기여를 더하면 중간 값들이 소거되어 v(N)−v(empty)=v(N)이 됩니다. 하지만 순서를 바꾸면 그 변화를 누구의 기여로 계산하는지가 달라질 수 있습니다. 대체 가능한 자원은 대체자가 오기 전에는 큰 가치를 더하고, 대체자가 이미 있으면 아무 가치도 더하지 않을 수 있습니다.

여기서 순서는 가상의 기여 계산 순서입니다. 실제 가입 시점이나 특정 협상 프로토콜을 관측했다는 뜻이 아닙니다. 표에는 세 명의 모든 여섯 순서를 나열합니다. 열은 항상 같은 플레이어를 가리키므로 가입 위치가 달라도 같은 사람의 기여를 비교할 수 있습니다.

여섯 순서를 모두 평균한 Shapley 배분

Shapley 배분은 모든 가입 순서에 같은 가중치를 줍니다.

$$\phi_i=\frac1{6}\sum_\sigma\Delta_i(S_{\sigma,i}).$$

세 플레이어에서는 이를 부분집합으로 묶어 다음처럼 쓸 수도 있습니다.

$$\phi_i=\sum_{S\subseteq N\setminus\{i\}} \frac{|S|!(2-|S|)!}{3!} \left[v(S\cup\{i\})-v(S)\right].$$

계수는 정확히 S가 i보다 먼저 오는 순서의 비율입니다. 각 순서의 기여 합이 v(N)이므로 평균을 취해도 효율성이 성립합니다. 한계 기여에서 완전히 같은 역할을 하는 플레이어는 같은 값을 받고, 항상 추가 기여가 0인 null player는 0을 받습니다. 기여 차이가 가치함수에 선형이므로 서로 다른 게임을 더하면 배분도 더해집니다. 이러한 성질은 규칙을 선택하는 근거이며 보편적인 공정성의 정의를 자동으로 정하는 것은 아닙니다.

Serrano의 협력 게임 논문 §4는 기여 평균 공식과 공리적 해석을 설명합니다. 실습은 여섯 순서를 정확히 전부 계산합니다. 아래 곡선의 중간 평균은 고정한 나열 순서에 의존하며, 여섯 번째 값이 전체 평균입니다. 표본을 늘려 추정치가 수렴하는 Monte Carlo 실험이 아닙니다.

연합 안정성을 요구한 집합이 core다

어떤 연합이 현재 배분에서 받는 합이 자기 가치보다 작으면, 함께 이탈해 더 나은 결과를 만들 수 있습니다. 연합 내부에서 보수를 자유롭게 이전할 수 있으므로 양의 초과분을 나눠 각 구성원을 더 좋게 만들 수 있습니다. 연합 slack을 다음처럼 둡니다.

$$\operatorname{slack}_x(S)=\sum_{i\in S}x_i-v(S).$$

음의 slack은 그 연합의 blocking 가능성을 나타냅니다. 등호는 허용합니다. 자기 가치만큼 받는 연합에는 모두를 엄격히 더 좋게 만들 양의 초과분이 없습니다. Core는 효율성과 모든 연합의 하한을 만족하는 배분 전체입니다.

$$\operatorname{Core}(v)=\left\{x: \sum_{i\in N}x_i=v(N),\quad \sum_{i\in S}x_i\ge v(S)\quad\forall S\subseteq N \right\}.$$

단일 플레이어 연합의 제약에 개별 합리성이 포함됩니다. 빈 연합의 slack 0은 실제 값입니다. 효율적 배분에서 전체 연합의 slack도 실제로 0입니다. 이 0들을 관측 불가 기호로 바꾸지 않습니다. Serrano §3의 연합 이탈 해석처럼, core는 안정적인 배분의 집합이고 Shapley는 한 배분을 지정하는 규칙입니다.

손계산: 독립적인 자원의 가산 가치

세 플레이어가 각각 1,2,3의 독립 가치를 만든다고 합시다. 연합 가치는 포함한 사람들의 가치를 더한 것이고 v(N)=6입니다. 모든 순서의 기여가 (1,2,3)이므로 Shapley도 같습니다.

개별 합리성은 x0≥1, x1≥2, x2≥3을 요구합니다. 하한들의 합이 이미 6이므로 효율성과 함께 만족하려면 모두 등호여야 합니다. 따라서 전체 core가 (1,2,3) 한 점입니다. 더 큰 영역 중 한 점을 임의로 골랐다는 뜻이 아닙니다.

첫 안내 예제는 p0=2, p1=4를 입력해 x0=1, x1=2, x2=3을 만듭니다. 모든 연합이 자신의 가치를 정확히 받아 slack이 0입니다. 입력 하나를 움직여도 합은 6으로 유지되지만 누군가는 혼자 하는 것보다 덜 받게 될 수 있습니다.

손계산: core가 존재해도 Shapley가 그 밖에 있을 수 있다

플레이어 0에게 왼쪽 장갑 한 개, 플레이어 1과 2에게 오른쪽 장갑을 하나씩 줍니다. 왼쪽 장갑과 오른쪽 장갑 하나가 함께 있으면 가치 6을 만들고, 아니면 0을 만듭니다. v({0,1})=v({0,2})=v(N)=6, v({1,2})=0입니다.

플레이어 0은 여섯 순서 중 네 번 결정적인 기여를 하고, 오른쪽 장갑의 각 소유자는 한 번씩 결정적입니다. Shapley는 (4,1,1)입니다. 효율적이고 개별 합리적이지만 연합 {0,1}은 5를 받는 대신 자신들만으로 6을 만들 수 있습니다. Slack은 −1입니다. 연합 {0,2}도 같습니다.

Core를 직접 구하면 x0+x1≥6과 합 6에서 x2≤0을 얻습니다. x0+x2≥6에서는 x1≤0입니다. 단일 연합의 하한은 둘 다 0 이상을 요구하므로 x1=x2=0, x0=6입니다. Core는 (6,0,0) 한 점이고 Shapley는 그 밖에 있습니다.

따라서 기여 평균과 연합 안정성의 차이를 단지 core가 없는 경우의 문제라고 설명하면 틀립니다. 안정적인 배분이 존재하는 경우에도 두 개념은 다릅니다.

손계산: 정말로 빈 core인 다수결 게임

두 명 이상인 연합은 모두 가치 6을 만들고 한 명은 0을 만든다고 합시다. 대칭성과 기여 계산에서 Shapley는 (2,2,2)입니다. 그러나 각 두 명 연합은 4만 받으면서 스스로 6을 만들 수 있습니다.

다른 효율적 배분으로 모든 쌍을 만족시킬 수도 없습니다. 필요한 세 제약을 더해 보세요.

$$x_0+x_1\ge6,\quad x_0+x_2\ge6,\quad x_1+x_2\ge6.$$

합하면 2(x0+x1+x2)≥18이어야 합니다. 효율성에서 왼쪽은 12이므로 모순입니다. 이것이 빈 core의 증명입니다. 화면의 격자에서 점을 못 찾았다는 계산 실패가 아닙니다. 가치함수와 가입 순서가 정의되어 있으므로 Shapley 배분은 여전히 계산할 수 있습니다.

영역과 선분 전체를 보여 줘야 한다

전체 만장일치 게임에서는 세 명이 모두 모일 때만 6을 만들고 나머지 연합은 0입니다. Core는 x0+x1+x2=6인 음이 아닌 배분의 삼각형 전체입니다. 꼭짓점은 (6,0,0),(0,6,0),(0,0,6)이고 Shapley (2,2,2)는 그중 한 내부점입니다.

쌍 01 만장일치 게임에서는 0과 1이 함께 포함될 때만 가치가 6입니다. Core는 x2=0, x0+x1=6, x0,x1≥0인 선분입니다. 플레이어 2는 null player이며 Shapley는 (3,3,0)입니다. 마커 하나만 그리면 안정적인 배분이 무수히 많다는 사실을 숨기게 됩니다.

실습의 다섯 모형은 한 점, 영역, 빈 집합, Shapley를 포함하지 않는 비어 있지 않은 집합, 선분을 다룹니다. 모든 가치에 양의 배율을 곱하면 배분과 slack도 같은 배율로 바뀌지만 정규화한 기하와 소속 판단은 유지됩니다.

이 기하가 정확한 이유

효율성으로 x2를 없애면 여섯 진부분 연합 제약은 (x0,x1)의 반평면이 됩니다. 단일 연합 하한과 x2 하한이 가능한 집합을 유계로 만듭니다. 비어 있지 않으면 꼭짓점은 제약 경계의 가능한 교점에 있으며, 선분 끝점이나 한 점인 경우도 포함됩니다.

세 플레이어의 경계 법선은 좌표 방향 또는 공통 대각 방향이어서 0이 아닌 두 경계 행렬식의 크기가 1입니다. 정수 가치에서는 꼭짓점 좌표도 정수입니다. 구현은 조회 격자와 여섯 순서 평균까지 함께 표현하기 위해 공통 분모 12를 씁니다. 소속과 slack 비교는 정수 분자로 수행하고, 소수 변환과 각도 정렬은 이미 정한 꼭짓점을 그릴 때만 사용합니다.

이는 작은 모형과 제한된 정확한 입력에 대한 설명입니다. 일반 게임의 core가 비었다는 것을 성긴 격자 검색으로 증명할 수는 없으며, 여기서의 전수 열거가 플레이어 수가 큰 문제의 계산 효율성을 보장하지도 않습니다.

AI와 연결하려면 가치함수를 먼저 정해야 한다

데이터 제공자, 특성, 모델 부품을 플레이어로 볼 수는 있지만 연합 가치가 무엇인지 먼저 정의해야 합니다. 예측 정확도, 누락 특성을 처리하는 규칙 아래의 효용, 인과 개입의 가치는 서로 다른 함수입니다. 평균 기여 규칙이 그중 어떤 함수가 과학적으로 적절한지 결정하지는 않습니다.

조건부 관측에 근거한 점수는 특성 간 상관과 누락 값을 표현하는 방식에 의존할 수 있습니다. 따라서 attribution이 자동으로 인과 효과나 지급 권리가 되는 것은 아닙니다. 실습에서 v(S)를 모두 보여 주는 이유도 배분 규칙과 기저 가치의 식별 문제를 구분하기 위해서입니다.

다음 단원의 Markov 팀 게임에서는 특성함수의 가치를 나누는 대신, 공동 행동으로 변하는 시스템을 어떻게 개선할지 묻습니다. 협력이라는 단어를 공유해도 모형의 기본 요소와 보장은 다릅니다.

확인 문제와 해설

문제 1. 장갑 게임에서 연합 {0,2}의 slack을 Shapley 배분과 core 배분에서 각각 구하세요.

해설. Shapley에서는 4+1−6=−1이고 core에서는 6+0−6=0입니다. 0은 맞닿은 안정성 제약이며 음수는 연합이 더 나은 결과를 만들 여지를 뜻합니다.

문제 2. x2가 음수인 조회는 효율성을 위반하나요? 회색 삼각형 안에서도 개별 합리성이 실패할 수 있나요?

해설. x2를 효율성으로 계산하므로 합은 v(N)을 유지합니다. 이 실습에서는 음의 x2가 단일 연합 하한을 위반합니다. 반대로 가산 게임의 (0,3,3)은 음이 아니고 효율적이지만 플레이어 0의 독립 가치 1을 주지 못합니다.

문제 3. 다수결의 모순 증명이 169개 조회점 검색보다 강한 이유와, 전체 만장일치의 해가 한 점이 아닌 이유를 설명하세요.

해설. 세 쌍의 필요 부등식을 합하면 격자 사이를 포함한 모든 실수 효율 배분을 배제합니다. 전체 만장일치는 음이 아닌 좌표와 합 6만 요구하므로 삼각형 전체가 남습니다. 두 결론 모두 그림의 해상도와 독립적입니다.