The Illusion of Collusion

이 논문은 경쟁자가 서로의 상태나 행동을 알지 못하는 상황에서도 다중-팔 밴딧 알고리즘이 동기화된 행동을 통해 '순진한 담합'을 학습할 수 있음을 보여주며, 이는 탐험과 확정을 어떻게 균형시키는지에 따라 발생 여부가 결정된다고 주장합니다.

핵심

이 논문은 **"알고리즘이 서로 대화도 하지 않고, 심지어 상대방의 존재를 모른 채도 어떻게 서로 짜고 가격을 올리는지 (담합)"**에 대한 놀라운 연구를 담고 있습니다.

제목인 **'착각적인 담합 (The Illusion of Collusion)'**이라는 말처럼, 이 알고리즘들은 실제로 "우리 서로 가격 올리자고 합의하자"라고 말한 적이 없습니다. 그냥 각자 "어떻게 하면 돈을 더 많이 벌까?"라고 혼자 고민하다가, 우연히 같은 결론에 도달한 것입니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 상황 설정: 두 명의 바보 같은 상인

가상 시장이 있다고 상상해 보세요. 여기 두 명의 상인 (A 와 B) 이 있습니다.

• 상인 A 와 B는 서로의 존재를 알지 못합니다. 상대방이 무엇을 했는지, 어떤 가격을 책정했는지도 모릅니다.
• 그들은 오직 자신의 경험만 보고 결정을 내립니다. "오늘 비싸게 팔았더니 잘 팔렸어? 아니면 싸게 팔았더니 더 잘 팔렸어?"를 기록만 합니다.
• 그들은 **'학습 알고리즘 (머신러닝)'**을 사용해서 가격을 정합니다.

이 두 상인이 서로 모르고 각자 학습을 하다가, 우연히 **서로 같은 고가 (High Price)**를 계속 유지하게 되면, 이는 겉보기에 담합처럼 보입니다. 하지만 실제로는 전혀 의도하지 않은 결과입니다.

2. 핵심 발견: "랜덤성 (무작위성)"이 키입니다

이 연구의 가장 중요한 발견은 **"알고리즘이 얼마나 '랜덤 (무작위)'하게 행동하느냐"**에 따라 결과가 완전히 달라진다는 것입니다.

A. "완전한 무작위"를 사용하는 경우 (예: 에psilon-그리디)

• 비유: 상인이 매일 아침 동전을 던져서 결정합니다. "앞면이면 비싸게, 뒷면이면 싸게 팔자"라고 하되, 가끔은 "오늘은 그냥 임의로 해보자"라고 생각하며 random 하게 행동합니다.
• 결과: 담합이 일어나지 않습니다.
• 이유: 너무 자주 random 하게 움직이다 보니, 서로 가격이 맞물려서 "아, 우리가 같이 비싸게 팔면 더 잘 팔리네"라는 패턴을 잡을 틈이 없습니다. 항상 혼란스럽기 때문에 결국 경쟁 상태 (싸게 팔기) 로 돌아갑니다.

B. "점점 덜 랜덤해지고 결정적이 되는" 경우 (예: 탐욕적 알고리즘)

• 비유: 상인은 처음엔 "무작위"로 실험을 많이 합니다. 하지만 시간이 지나면서 "어? 비싸게 팔았을 때 더 잘 팔리는 것 같아!"라고 확신하게 됩니다. 그리고 나중에는 100% 확신을 가지고 "내일도 무조건 비싸게 팔자!"라고 결정합니다.
• 결과: 담합이 일어날 가능성이 매우 높습니다.
• 이유: 두 상인이 모두 "비싸게 팔면 이득이다"라고 학습하게 되면, 서로의 행동을 보지 않아도 **서로 같은 타이밍에 같은 행동 (비싼 가격)**을 하게 됩니다. 마치 두 사람이 거울을 보지 않아도 서로 같은 춤을 추는 것처럼 말이죠.

C. "완전히 결정적인" 경우 (예: UCB 알고리즘)

• 비유: 상인은 실험도 안 하고, 무작위성도 없습니다. "이론적으로 계산해보니 비싸게 팔아야 이득이다"라고 딱 정해진 규칙대로만 움직입니다.
• 결과: 항상 담합이 일어납니다.
• 이유: 두 상인이 똑똑한 똑같은 규칙을 따르기 때문에, 서로의 행동을 예측할 필요도 없이 동일한 시점에 동일한 가격을 책정하게 됩니다. 이는 마치 두 대의 로봇이 같은 프로그래밍을 받아서 같은 행동을 하는 것과 같습니다.

3. '동기화 (Synchronicity)'라는 개념

이 논문은 **'동기화'**라는 새로운 개념을 도입합니다.

• 두 상인이 동시에 같은 행동을 (예: 동시에 비싼 가격 설정) 하는 빈도입니다.
• 알고리즘이 무작위성이 적을수록, 두 상인의 행동이 동기화될 확률이 높아집니다.
• 행동이 동기화되면, 서로가 "아, 우리가 같이 비싸게 팔고 있네? 그럼 이대로 계속하자"라고 학습하게 되어, 결국 담합 상태에 빠지게 됩니다.

4. 왜 이것이 문제인가? (정책적 시사점)

지금까지 법원은 "담합을 하려면 서로 대화하거나 (의사소통), 상대방의 가격을 보고 따라야 한다 (조건부 행동)"는 증거가 있어야만 처벌했습니다.

하지만 이 논문은 **"아니요, 서로 대화도 안 하고, 상대방 가격도 모른 채, 그냥 각자 똑똑한 알고리즘을 썼을 뿐인데도 담합이 일어날 수 있다"**고 말합니다.

• 경고: 만약 두 회사가 같은 종류의 '최고급 알고리즘'을 쓴다면, 그 알고리즘이 너무 똑똑해서 (랜덤성이 적어서) 서로 의도치 않게 가격을 담합 수준으로 올릴 수 있습니다.
• 해결책: 단순히 "상대방 가격을 보고 결정하지 마라"라고 금지하는 것만으로는 부족합니다. 알고리즘 자체가 **적당한 수준의 '무작위성 (실수할 가능성)'**을 가지고 있어야, 이런 우연한 담합을 막을 수 있습니다.

5. 한 줄 요약

"두 개의 똑똑한 AI 가 서로 대화도 안 하고 각자 '최고의 이익'을 쫓다 보면, 우연히 서로의 행동을 맞춰서 (동기화되어) 마치 담합한 것처럼 비싼 가격을 유지하게 될 수 있다. 특히 AI 가 너무 확신에 차서 (랜덤성이 사라져서) 행동하면 그 위험은 더 커진다."

이 연구는 AI 가 우리 시장을 어떻게 바꿀 수 있는지에 대한 새로운 경고이자, 규제 당국이 알고리즘의 '랜덤성'까지 고려해야 함을 시사합니다.

기술 요약

논문 요약: "The Illusion of Collusion" (협동의 환상)

저자: Connor Douglas, Foster Provost, Arun Sundararajan (NYU Stern School of Business)
발행일: 2026 년 2 월 (arXiv:2411.16574v2)

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

인공지능 (AI) 에이전트가 가격 결정 등 경쟁적 의사결정 환경에서 널리 사용되고 있습니다. 최근 연구들은 이러한 알고리즘들이 경쟁사 가격에 대한 명시적인 정보나 의도적인 합의 없이도, 독립적으로 학습하는 과정에서 마치 담합 (collusion) 한 것처럼 고가격을 유지하는 현상을 보여주고 있습니다.

기존의 담합 이론은 "의도적 조정 (intentional coordination)"이나 "의사 교환 (exchange of wills)"을 전제로 하지만, 알고리즘 담합은 이러한 증거가 부재한 상태에서 발생할 수 있어 규제적, 법적 난제를 야기합니다. 본 논문은 경쟁 알고리즘이 경쟁 상호작용에 대한 어떤 정보도 (상대방의 존재, 행동, 결과 등) 알지 못하는 '순진한 (naive)' 환경에서 어떻게, 그리고 언제 담합과 유사한 결과가 발생하는지 규명하는 것을 목표로 합니다. 이를 저자들은 **"순진한 알고리즘적 담합 (naive algorithmic collusion)"**이라고 명명합니다.

2. 방법론 (Methodology)

연구는 반복된 죄수의 딜레마 (Repeated Prisoner's Dilemma) 게임을 전략적 상호작용의 모델로 설정하고, 두 경쟁 에이전트가 멀티-암 밴딧 (Multi-armed Bandit, MAB) 학습 알고리즘을 사용하여 게임을 반복하는 상황을 분석합니다.

• 학습 환경: 에이전트는 상대방의 행동이나 게임 구조를 알지 못하며, 오직 자신의 행동과 그에 따른 보상 (reward) 히스토리만을 기반으로 학습합니다.
• 알고리즘 분류: 연구는 밴딧 학습 알고리즘의 행동 정책 (behavior policy) 에 내재된 **무작위성 (randomness)**의 정도에 따라 알고리즘을 세 가지 범주로 나누어 분석합니다.
  1. 지속적 무작위 알고리즘 (Persistently Random): 모든 시점에서 모든 행동에 대해 0 이 아닌 확률을 유지 (예: $\epsilon$-greedy with constant $\epsilon$).
  2. 점근적 탐욕 알고리즘 (Greedy-in-the-Limit): 초기에는 무작위 탐색을 하지만 시간이 지남에 따라 최적 행동으로 수렴하는 알고리즘 (예: $\epsilon$-greedy with decaying $\epsilon$, Explore-then-Commit).
  3. 결정론적 알고리즘 (Deterministic): 모든 시점에서 히스토리에 기반하여 단일 행동을 100% 확률로 선택 (예: UCB, Upper Confidence Bound).
• 분석 도구:
  • 동시성 (Synchronicity): 특정 에이전트가 특정 행동을 취했을 때, 상대방이 동일한 행동을 취하는 비율.
  • 경로 불변성 (Path-invariance): 보상 시퀀스의 순서가 달라도 동일한 가치 추정을 생성하는 알고리즘의 특성.
  • 마르코프 체인 (Markov Chain): 게임의 상태 전이를 모델링하여 장기적 균형 (long-run equilibrium) 을 분석.

3. 주요 기여 (Key Contributions)

1. 순진한 담합의 발생 메커니즘 규명: 경쟁 알고리즘이 상대방의 존재나 전략을 전혀 인지하지 못함에도 불구하고, 알고리즘의 학습 정책 특성 (특히 무작위성) 에 따라 담합이 발생할 수 있음을 이론적으로 증명했습니다.
2. 동시성 (Synchronicity) 의 중요성 강조: 담합 발생 여부는 단순히 알고리즘의 대칭성 (symmetry) 이나 관찰 가능성에 의해 결정되는 것이 아니라, 학습 과정에서 발생하는 **행동의 동시성 (synchronicity)**에 의해 결정됨을 제시했습니다.
3. 알고리즘 유형별 담합 가능성 분류: 알고리즘의 무작위성 정도에 따라 담합 발생 여부가 명확히 구분됨을 보였습니다.
   • 결정론적 알고리즘: 항상 담합 발생.
   • 지속적 무작위 알고리즘: 장기적으로 담합 발생 안 함.
   • 점근적 탐욕 알고리즘: 조건에 따라 담합 발생 가능 (경로 의존적).
4. 규제 정책 함의 제시: 경쟁사 가격을 기반으로 행동하지 않도록 하는 것만으로는 알고리즘 담합을 방지할 수 없음을 지적하고, 알고리즘의 무작위성 설계와 대칭성이 담합 위험에 미치는 영향을 규명했습니다.

4. 주요 결과 (Results)

4.1 알고리즘 유형별 담합 발생 여부

알고리즘 유형	무작위성 특징	장기적 담합 발생 여부	설명
지속적 무작위 (Persistently Random)	모든 행동에 대해 $\epsilon > 0$ 확률 유지	발생 안 함 (Never)	$\epsilon$-greedy (상수 $\epsilon$) 등. 무작위성이 충분히 크면 에이전트 간 행동이 무상관 (uncorrelated) 되어 경쟁 (L, L) 으로 수렴합니다.
점근적 탐욕 (Greedy-in-the-Limit)	초기 무작위, 후기 결정론적	조건부 발생 (Sometimes)	$\epsilon$-greedy (감소 $\epsilon$), ETC 등. 초기 탐색 단계에서의 무작위성과 보상 구조 ($\beta, \gamma$) 에 따라 동시성이 형성되어 담합이 발생할 수도, 경쟁이 발생할 수도 있습니다. 이는 **경로 의존적 (path-dependent)**입니다.
결정론적 (Deterministic)	무작위성 없음	항상 발생 (Always)	UCB 등. 대칭적인 결정론적 알고리즘은 초기 조건에 따라 행동이 동기화되어, 결국 상호 협력 (H, H) 상태에 도달하게 됩니다.

4.2 동시성 (Synchronicity) 의 역할

• 동시성과 담합: 에이전트들이 서로의 행동을 무작위로 맞추는 빈도 (동시성) 가 높을수록, 각 에이전트는 상대방이 자신의 협력 행동 (H) 에 협력할 것이라고 학습하게 되어 담합이 강화됩니다.
• 공분산 (Covariance) 부재: 만약 에이전트 간 행동이 통계적으로 무상관 (covariance $\le$ 0) 하면, 어떤 게임 파라미터 ($\beta, \gamma$) 에서도 담합이 최적의 전략이 될 수 없습니다.
• 경로 의존성: 동일한 알고리즘 쌍이라도 초기 학습 과정에서의 우연한 동시성 (synchronicity) 에 따라 장기적으로 담합이 발생할 수도, 경쟁이 발생할 수도 있습니다.

4.3 비대칭성과 초기 조건

• 비대칭성 (Asymmetry): UCB 알고리즘의 Tie-breaking 규칙이나 파라미터 ($\delta$) 가 약간이라도 비대칭적이더라도, 결정론적 알고리즘의 경우 여전히 담합으로 수렴할 가능성이 매우 높습니다.
• 초기 오프셋 (Offset Start): 한 에이전트가 먼저 학습을 시작하고 나중에 다른 에이전트가 합류하는 상황에서도, UCB 알고리즘은 높은 확률로 담합을 학습합니다.

5. 의의 및 시사점 (Significance & Policy Implications)

1. 담합의 '순진함' (Naivety): 알고리즘 담합은 복잡한 전략적 계산이나 미래에 대한 위협 (punishment) 을 의식한 결과가 아니라, 단순한 탐험 - 활용 (exploration-exploitation) 트레이드오프 과정에서 발생하는 부수적 현상일 수 있습니다.
2. 규제 정책의 한계:
   • "경쟁사 가격을 기반으로 행동을 결정하지 못하게 한다"는 기존 규제 방안은 불충분합니다. 상대방 가격을 보지 않아도 알고리즘의 무작위성 설계에 따라 담합이 발생할 수 있기 때문입니다.
   • 알고리즘 공급자의 대칭성 (symmetry) 이 오히려 담합 위험을 증가시킬 수 있습니다. 동일한 알고리즘을 사용하는 경쟁사들이 유사한 학습 경로를 따라가면서 담합을 유도할 수 있습니다.
3. 탐험 (Exploration) 의 역설:
   • 기존 연구는 탐험이 많을수록 담합 위험이 높다고 보았으나, 본 연구는 **지속적인 무작위 탐험 (persistent randomness)**이 오히려 담합을 방지하고 경쟁을 유도함을 보였습니다.
   • 반면, 초기에만 탐험하고 나중에는 결정론적으로 수렴하는 방식 (greedy-in-the-limit) 은 담합을 유발할 수 있습니다.
4. 규제 방향성:
   • 알고리즘의 무작위성 정책 (randomness policy) 과 파라미터 설정이 담합 발생에 결정적임을 고려하여, 특정 알고리즘 유형 (예: 결정론적 UCB) 에 대한 규제나 감시가 필요할 수 있습니다.
   • 시장 구조와 알고리즘의 조합을 고려한 선제적 (ex-ante) 규제 접근이 필요합니다.

결론

본 논문은 인공지능 기반 가격 결정 시스템이 경쟁사 정보를 전혀 얻지 못하더라도, 학습 알고리즘의 무작위성 수준과 **동시성 (synchronicity)**에 의해 담합과 유사한 결과가 발생할 수 있음을 이론적, 실험적으로 증명했습니다. 이는 알고리즘 담합이 단순히 의도적인 설계가 아니라, 특정 학습 메커니즘의 자연스러운 결과일 수 있음을 시사하며, 이에 대한 새로운 규제 프레임워크의 필요성을 제기합니다.