Coalitions in Repeated Games

이 논문은 지속적 약속과 처벌을 통해 연합의 방해 행위를 억제하는 역사 의존적 체계를 모델링하고, 이를 반복 매칭 및 협상 상황에 적용하는 반복 게임 내 연합 행동에 대한 새로운 프레임워크와 해법을 제시합니다.

핵심

이 논문은 **"함께 살아가는 사람들 (또는 기업) 이 어떻게 서로의 이기적인 욕망을 통제하고, 장기적인 협력을 유지할 수 있는가?"**에 대한 질문을 던집니다.

기존의 게임 이론은 "내가 지금 당장 이득을 보려면 배신하는 게 낫다"는 생각 때문에 협력이 깨지는 경우를 많이 다뤘습니다. 하지만 이 논문은 **"과거의 행동과 미래의 보상이나 처벌이 어떻게 현재의 결정을 바꾸는가?"**를 분석하며, 특히 소그룹 (동맹) 이 함께 움직일 때 어떤 일이 벌어지는지 설명합니다.

이 복잡한 내용을 일상적인 비유로 쉽게 풀어보겠습니다.

---

1. 핵심 아이디어: "방 배정 게임"과 "악마의 계약"

논문 도입부에서 **'룸메이트 문제 (Roommates Problem)'**를 예로 듭니다.
세 친구 (앤, 벨라, 캐롤) 가 방을 구합니다. 방은 두 명만 들어갈 수 있고, 한 명은 혼자 남아야 합니다.

• 앤은 벨라를 좋아하고, 벨라는 캐롤을 좋아하고, 캐롤은 앤을 좋아합니다.
• 만약 앤과 벨라가 방을 함께 쓴다면, 벨라는 캐롤과 함께 살고 싶어 하고, 캐롤도 벨라와 함께 살고 싶어 합니다.
• 그래서 어떤 조합을 해도, 두 명이 "우리 둘이 같이 살자!"라고 몰래 약속하면 현재의 조합이 깨집니다. 이를 경제학 용어로 **'블로킹 (Blocking, 방해)'**이라고 합니다.

이 논문이 제안하는 해결책:
"일회성 게임이 아니라, 매달 반복해서 방을 배정한다고 상상해 보세요."

• 규칙: "이번 달엔 앤과 벨라가 같이 살게. 하지만 만약 벨라가 캐롤과 몰래 방을 바꾸려고 시도하면, 다음 달부터는 앤과 캐롤이 같이 살고 벨라는 혼자 방을 쓸 거야."
• 효과: 벨라는 당장 캐롤과 함께 사는 재미 (단기 이익) 를 얻더라도, 다음 달부터 혼자 방을 써야 하는 고통 (장기적 손실) 이 더 큽니다.
• 결론: 미래에 대한 약속 (상처) 과 처벌 (고독) 이 있기 때문에, 사람들은 현재의 유혹을 이겨내고 규칙을 따릅니다.

이 논문의 핵심은 **"미래의 보상이나 처벌을 어떻게 설계하면, 작은 동맹 (소그룹) 이라도 서로 배신하지 않고 협력하게 만들 수 있는가?"**를 찾는 것입니다.

---

2. 주요 발견: "동질성"이 협력을 방해한다?

논문의 가장 놀라운 발견은 사람들의 성향이 너무 비슷하면 오히려 협력이 깨지기 쉽다는 것입니다.

비유: "쌍둥이 형제" vs "서로 다른 성격"

• 서로 다른 성격 (Misaligned Interests):

  • 앤은 "돈"을 중요하게 생각하고, 벨라는 "명예"를 중요하게 생각합니다.
  • 만약 두 사람이 동맹을 맺어 규칙을 어기려 한다면, 앤은 "돈을 더 벌면 좋겠는데, 처벌받으면 명예가 떨어지니 싫어"라고 생각할 수 있습니다.
  • 전략: 규칙을 만든 사람은 "앤만 처벌하고 벨라는 용서해 줄게"라고 위협할 수 있습니다. 앤은 동맹을 깨뜨리고 혼자 규칙을 지키려 할 것입니다. 이렇게 동맹을 갈라놓는 (Divide and Conquer) 전략이 효과적입니다.

• 완벽한 동질성 (Aligned Interests):

  • 앤과 벨라가 완벽하게 똑같은 가치관을 가진 쌍둥이라고 칩시다. 둘 다 "돈"만 중요하고, 둘 다 똑같이 생각한다면?
  • 규칙을 만든 사람이 "앤만 처벌할게"라고 해도, 벨라는 "앤이 처벌받으면 나도 같이 불행해지니까 안 돼"라고 생각하며 함께 저항합니다.
  • 결과: 동질적인 그룹은 하나의 거대한 괴물처럼 행동하며, 외부의 처벌을 무력화시킵니다. 이 경우엔 협력이 깨지기 쉽고, 오직 **가장 효율적인 결과 (Core)**만 유지될 수 있습니다.

요약: 서로 다른 이해관계를 가진 사람들은 서로를 견제하며 협력을 유지할 수 있지만, 완벽하게 같은 생각을 가진 그룹은 외부의 통제 (처벌) 를 뚫고 이기적인 행동을 할 수 있습니다.

---

3. 돈 (보상) 은 해결책일까?

사람들은 "돈을 주고받으면 (이전, Transfer) 동맹이 더 단단해지겠지?"라고 생각하기 쉽습니다. 하지만 이 논문은 상황에 따라 정반대라고 말합니다.

상황 A: 돈 거래가 모두에게 공개될 때 (Public Transfers)

• 비유: "우리 둘이 방을 바꾸고, 앤이 벨라에게 100 만 원을 줄게."라고 모두가 보는 앞에서 거래를 합니다.
• 결과: 규칙을 만든 사람은 "앤이 벨라에게 돈을 줬구나. 그럼 앤만 처벌하고 벨라는 용서해 줄게"라고 할 수 있습니다.
• 효과: 공개된 돈 거래는 오히려 동맹을 갈라놓는 약점이 됩니다. 동맹원들 사이에 '누가 얼마나 받았는지'가 드러나기 때문에, 처벌을 피하기 위해 서로를 배신할 유인이 생깁니다.

상황 B: 돈 거래가 비밀일 때 (Secret Transfers)

• 비유: "우리 둘이 방을 바꾸고, 앤이 벨라에게 몰래 100 만 원을 줄게."라고 남몰래 거래를 합니다.
• 결과: 규칙을 만든 사람은 "누가 누구에게 돈을 줬는지 모르니, 앤과 벨라를 구분해서 처벌할 수 없어. 둘 다 처벌해야 해."라고 생각할 수밖에 없습니다.
• 효과: 비밀 거래는 동맹을 단단하게 묶어줍니다. 외부의 처벌을 무력화시키고, 동맹이 원하는 대로 세상을 바꿀 수 있게 합니다.
  • 실제 예시 (임금 투명성): 노동 시장에서 "임금이 공개된다면 (Public)" 기업과 노동자 사이의 비밀 협상이 어렵고, 기업들이 노동자를 갈라놓을 수 있습니다. 하지만 "임금이 비밀이라면 (Secret)" 기업들이 노동자들과 비밀리에 임금을 낮추는 합의를 하고, 이를 외부가 통제하기 어려워집니다.

---

4. 결론: 우리가 배울 점

이 논문은 우리의 일상생활, 정치, 비즈니스에 큰 시사점을 줍니다.

1. 동질적인 그룹은 위험하다: 완전히 같은 생각을 가진 사람들 (예: 같은 이념의 정치인들, 같은 이익을 추구하는 기업들) 이 뭉치면 외부의 규제나 처벌을 뚫고 독점적인 행동을 할 수 있습니다.
2. 차이점이 안전장치다: 구성원들의 이해관계가 조금씩 다르면, "누군가는 처벌받고 누군가는 용서받는다"는 전략으로 그들을 갈라놓아 협력을 유지할 수 있습니다.
3. 비밀은 양날의 검: 비밀스러운 돈 거래나 협상은 동맹을 강화하지만, 사회 전체의 공정성을 해쳐 '핵심 (Core)'이라는 최소한의 규칙만 남게 만들 수 있습니다.
   • 임금 투명성 논쟁: 노동자들이 많고 경쟁이 치열할 때는 임금 공개가 노동자들의 협상력을 높여줍니다 (기업들이 서로를 견제하게 만들기 때문). 하지만 노동자가 귀하고 기업들이 독점적이라면, 임금 공개는 기업들이 서로 담합하여 임금을 낮추는 데 이용될 수 있습니다.

한 줄 요약:

"미래의 보상이나 처벌로 사람을 통제할 수 있지만, 그들이 너무 비슷하거나 비밀리에 돈을 주고받으면 그 통제망은 무너집니다. 따라서 건강한 협력을 위해서는 구성원 간의 '차이'와 '투명성'이 중요합니다."

기술 요약

논문 제목: Coalitions in Repeated Games (반복 게임에서의 연합)
저자: S. Nageeb Ali, Ce Liu
발행일: 2026 년 4 월 6 일 (arXiv:1906.00280v4)

이 논문은 반복 게임에서 개인적 행동뿐만 아니라 연합 (coalition) 의 행동을 분석하기 위한 새로운 프레임워크와 해법 개념을 제시합니다. 기존 반복 게임 이론이 개인의 이기적 행동과 역사 의존적 보상/징벌을 통해 협력을 유도하는 데 초점을 맞췄다면, 본 논문은 **집단적 이탈 (group defection)**을 어떻게 억제할 수 있는지, 그리고 어떤 조건에서 동적 인센티브가 연합의 협력을 가능하게 하거나 실패하게 하는지를 규명합니다.

---

1. 연구 문제 (Problem)

• 기존 이론의 한계:
  • 반복 게임 (Repeated Games): 개인의 이기적 행동 (defection) 을 억제하기 위해 역사 의존적 (history-dependent) 인 보상과 징벌을 연구함 (예: Folk Theorem). 하지만 이는 주로 개인적 행동에 국한됨.
  • 정적 게임 (Static Games): 연합 게임 (Cooperative Games), 매칭 이론, 정치 경제학 등에서 '핵 (Core)', '쌍대적 안정성 (Pairwise Stability)', '콘도르세 승자 (Condorcet Winner)'와 같은 개념을 사용함. 그러나 이러한 개념들은 미래의 약속이나 처벌을 고려하지 않는 정적 (static) 상호작용에 기반함.
• 핵심 질문: 반복 게임의 동적 인센티브 (미래의 보상과 처벌) 를 도입하여, 연합이 이익을 위해 기존 합의를 깨는 행위 (blocking) 를 어떻게 방지할 수 있는가?
• 구체적 사례: '룸메이트 문제 (Roommates Problem)'를 예로 들면, 3 명이 방을 공유할 때 어떤 조합도 정적 상태에서는 안정적이지 않음 (어떤 조합도 다른 조합으로 이탈할 유인이 있음). 반복 게임에서 이러한 불안정성을 해결할 수 있는가?

2. 방법론 (Methodology)

저자는 **완벽 연합 균형 (Perfect Coalitional Equilibrium, PCE)**이라는 새로운 해법 개념을 도입합니다.

• 모델 설정:

  • 단계 게임 (Stage Game): 플레이어들이 대안 (alternative) 을 선택하고, 연합이 이를 차단 (block) 하여 다른 대안을 선택할 수 있는 구조. (전략형 게임, 특성함수 게임, 매칭 게임, 투표 게임 등을 포괄).
  • 역사 의존적 계획 (History-dependent Schemes): 과거의 행동 (특히 연합의 차단 시도) 에 따라 미래의 대안과 보상을 결정하는 계획.
  • PCE 정의: 어떤 역사 (history) 에서도 어떤 연합도 미래의 연속 게임 (continuation play) 을 고려했을 때, 현재 계획을 차단하는 것이 이득이 되지 않는 계획. 즉, 연합의 차단이 자발적으로 억제되는 '자기 실행 (self-enforcing)' 계획.

• 분석 도구:

  • 재귀적 구조 (Recursiveness): PCE 는 아브루, 피어스, 스타체티 (1990) 의 자기 생성 (self-generation) 접근법을 따름.
  • 연합 최소최대 (Coalitional Minmax): 연합이 공동으로 최선의 대응을 할 때 달성할 수 있는 최소 보상 수준.
  • 인센티브 정렬 (Alignment of Incentives): 연합 내 구성원들의 효용 함수가 얼마나 일치하는지 (equivalent utilities) 분석.

3. 주요 기여 및 결과 (Key Contributions & Results)

3.1. 연합의 이익 정렬과 PCE 의 범위

• 정리 1 (Theorem 1): PCE 는 각 플레이어에게 연합 최소최대 (coalitional minmax, $v^\circ_i$) 이상의 보상을 보장합니다.
  • 이익이 완전히 일치하는 경우 (Common-interest): 연합 구성원들의 효용이 완전히 일치하면, 연합은 단일 행위자처럼 행동하여 높은 보상을 보장받습니다. 이 경우 PCE 는 효율적인 결과만 선택합니다.
  • 이익이 약간이라도 어긋나는 경우: 구성원들의 효용이 완벽하게 일치하지 않으면, PCE 는 연합을 분열시킬 수 있습니다. 특정 연합원을 '희생양 (scapegoat)'으로 지정하여 처벌하고 나머지는 용서하는 전략을 통해 연합의 이탈을 억제할 수 있습니다. 이 경우 PCE 는 개인적 최소최대 (individual minmax) 이상인 거의 모든 실현 가능한 보상을 지원합니다 (Folk Theorem 과 유사).

3.2. 정적 대칭성과 비대칭적 처벌

• 정리 3 (Theorem 3): 강하게 대칭적인 (Strongly Symmetric) PCE 는 매우 제한적입니다.
  • 대칭적인 처벌은 연합 구성원들의 이익을 정렬시켜, 처벌 단계에서도 연합이 이탈할 유인을 만들 수 있습니다.
  • 따라서 PCE 를 유지하려면 **비대칭적 (asymmetric)**인 처벌 (누구를 처벌할지 역사에 따라 다르게 결정) 이 필수적입니다. 이는 완전 감시 하에서도 비대칭적 행동이 효율성을 유지하는 데 필요함을 보여줍니다.

3.3. 이전 (Transfers) 의 역할과 비밀성

• 공개된 이전 (Public Transfers):
  • 정리 4 (Theorem 4): 이전이 공개적으로 관찰되면, 연합 내부의 이익 분배가 투명해집니다. 이는 연합을 분열시키는 '희생양' 전략을 더 정교하게 구사할 수 있게 하여, 개인의 최소최대 이상인 모든 보상을 지원할 수 있게 합니다. 즉, 공개 이전은 연합을 약화시킵니다.
• 비밀 이전 (Secret Side-payments):
  • 정리 5 (Theorem 5): 연합이 내부에서 비밀로 이전 (side-payments) 을 할 수 있으면, 연합은 단일 행위자처럼 행동하여 연합 최소최대를 보장받습니다.
  • 이는 동적 인센티브를 무력화시켜, 지원 가능한 보상 집합을 **단계 게임의 핵심 (Core)**으로 축소시킵니다. 즉, 비밀 이전은 '반 - 포크 정리 (Anti-folk Theorem)'를 초래합니다.

3.4. 응용: 노동 시장 매칭과 임금 투명성

• 임금 투명성 (Wage Transparency):
  • 임금이 공개될 때: 기업과 근로자가 과거 임금 협상을 통해 미래에 협상력을 행사할 수 있습니다. 근로자가 많거나 한계 생산성이 빠르게 감소하는 경우, 근로자들은 집단 협상을 통해 높은 임금을 유지할 수 있습니다.
  • 임금이 비공개일 때 (Private Wages): 기업과 근로자 간 비밀 계약이 가능해지면, 기업은 근로자들 간의 경쟁을 유도하여 임금을 단계 게임의 핵심 수준 (경쟁적 수준) 으로 낮출 수 있습니다.
  • 결론: 임금 투명성은 근로자의 협상력을 강화할 수도, 기업의 담합을 용이하게 할 수도 있습니다. 이는 시장의 구조 (근로자의 희소성, 한계 생산성 감소 속도) 에 따라 누가 이득을 보는지 결정됩니다.

4. 의의 및 시사점 (Significance)

1. 이론적 통합: 반복 게임 (비협력적) 과 연합 게임 (협력적) 의 이론적 접근을 통합하여, 집단 행동의 동적 안정성을 분석하는 새로운 틀을 마련했습니다.
2. 역사 의존성의 중요성: 역사 의존적 계획이 연합의 이익 정렬 정도에 따라 어떻게 다르게 작용하는지 규명했습니다. 특히, 이익이 완벽하게 일치하지 않을 때만 동적 인센티브가 효과적으로 작동하여 협력을 유도할 수 있음을 보였습니다.
3. 비대칭적 전략의 필요성: 대칭적 처벌 (예: 그림 트리거) 은 연합을 분열시키기 어렵기 때문에, 반복 게임에서 연합을 통제하려면 비대칭적이고 정교한 처벌 메커니즘이 필요함을 증명했습니다.
4. 실증적 함의 (임금 투명성): 임금 투명성 논쟁에 새로운 차원을 추가했습니다. 투명성이 항상 근로자에게 유리한 것이 아니라, 시장 조건에 따라 기업이나 근로자 중 한쪽의 담합 능력을 강화할 수 있음을 보여주었습니다.
5. 비밀 이전의 위험성: 집단 행동에서 비밀스러운 자금 이체가 가능하면, 장기적 협력이 붕괴되고 단기적 핵심 (Core) 결과로 회귀할 수 있음을 경고합니다.

요약

이 논문은 **"연합이 반복 게임에서 어떻게 행동하는가?"**에 대한 답을 제시하며, 동적 인센티브가 연합을 통제할 수 있는지는 구성원들의 이익 정렬 여부와 정보의 투명성 (특히 비밀 이전 가능 여부) 에 달려있다는 핵심 통찰을 제공합니다. 이는 노동 시장, 정치 협상, 네트워크 형성 등 다양한 분야에서 집단적 행동과 제도의 설계에 중요한 시사점을 줍니다.