🤖 machine learning

A Benchmark for Multi-Party Negotiation Games from Real Negotiation Data

이 논문은 실제 협상 데이터를 기반으로 다자간 협상 게임을 생성하는 벤치마크를 제시하고, 다양한 게임 구조에 따라 각기 다른 가치 함수 근사법이 어떻게 작동하는지 분석하여 장기적 계획과 견고한 상태 가치 학습의 중요성을 강조합니다.

원저자: Leo Benac, Jonas Raedler, Zilin Ma, Finale Doshi-Velez

게시일 2026-03-17

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Leo Benac, Jonas Raedler, Zilin Ma, Finale Doshi-Velez

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

이 논문은 **"복잡한 다자간 협상"**을 어떻게 더 잘 이해하고, 인공지능 (AI) 이 이를 어떻게 더 잘 해결할 수 있을지 연구한 내용입니다.

기존의 협상 연구는 대부분 "최종 결과물 하나를 나누는 것" (예: 가격 흥정) 에 집중했습니다. 하지만 현실의 협상, 특히 기후 변화나 인도적 지원 같은 큰 문제는 한 번에 결정되지 않습니다. 대신, 여러 단계에 걸쳐 서로 다른 약속들을 하나씩 맺어가는 과정입니다.

이 논문의 핵심 내용을 일상적인 비유로 설명해 드릴게요.

1. 현실의 협상은 '한 번의 거래'가 아니라 '연속된 약속'입니다

비유: 거대한 퍼즐 맞추기
기존 연구는 "이 퍼즐 조각을 주고받아서 최종 그림을 완성하자"라고 생각했습니다. 하지만 현실은 다릅니다.

새로운 방식: 우리는 퍼즐을 맞추는 도중에도 서로 약속을 해야 합니다. "내가 이 조각을 먼저 끼우면, 너는 저쪽을 먼저 끼워줘."라고 약속을 주고받습니다.
중요한 점: 한번 한 약속은 되돌릴 수 없습니다 (Binding Commitment). 만약 내가 실수로 잘못된 조각을 끼워버리면, 그 이후의 모든 퍼즐이 망가질 수 있습니다. 그래서 "지금 당장 이익이 보이는지"만 보고 결정하면 나중에 큰 낭패를 볼 수 있습니다.

2. 연구자들이 만든 도구: "협상 시뮬레이션 공장"

이 연구팀은 AI 가 이런 복잡한 협상을 연습할 수 있도록 가상의 협상 게임 생성기를 만들었습니다. 마치 레고 조립 키트처럼, 다양한 난이도와 상황을 설정할 수 있습니다.

조절 가능한 요소들:
- 인원 수: 3 명일 수도, 100 명일 수도 있습니다.
- 목표의 복잡도: "A 와 B 를 모두 해야 한다 (모든 것 아니면 무)" 같은 까다로운 목표 vs "A 하나만 해도 점수" 같은 쉬운 목표.
- 이해관계: 서로 돕는 경우 (협력) vs 서로의 이익이 충돌하는 경우 (대립).
- 보상 구조: 무조건 이득만 보는 경우 vs 손해를 볼 수도 있는 경우.

이 공장을 통해 AI 가 다양한 상황 (협상의 '지형') 을 경험하게 하고, 어떤 전략이 통하는지 테스트했습니다.

3. 세 가지 '안경' (전략) 으로 세상을 바라보기

AI 가 협상 중 "지금 이 약속을 맺어야 할까?"를 판단할 때, 미래의 결과를 예측하는 **'가치 함수 (Value Function)'**가 필요합니다. 연구팀은 AI 에게 세 가지 서로 다른 **'안경'**을 씌워보았습니다.

단거리 안경 (Myopic Reward): "지금 당장 내 주머니에 들어오는 돈만 보고 결정해."
- 장점: 즉각적인 이익이 명확할 때 좋습니다.
- 단점: 나중에 큰 손해를 볼지 모르고 함정에 걸릴 수 있습니다.
낙관주의 안경 (Upper Bound): "나중에 모든 좋은 일이 다 이루어질 거야! 하지만 나쁜 일은 절대 생기지 않게 조심해야 해."
- 장점: 나쁜 결과 (손해) 를 극도로 경계합니다.
- 단점: 너무 조심해서 좋은 기회를 놓칠 수 있습니다.
비관주의 안경 (Lower Bound): "나중에 나쁜 일이 벌어질지도 몰라. 그래도 그 worst case(최악의 상황) 에서도 내가 살아남을 수 있는 길을 찾아."
- 장점: 불확실한 상황에서도 안전한 길을 찾습니다.
- 단점: 너무 방어적으로 나와서 공격적인 기회를 놓칠 수 있습니다.

4. 실험 결과: "만능 열쇠는 없다"

이 세 가지 안경을 다양한 협상 게임에 적용해 보니 놀라운 결과가 나왔습니다.

상황에 따라 승자가 달라집니다:
- 공정한 게임 (Balanced): 단거리 안경이 가장 잘 작동했습니다. (지금 당장 계산이 명확할 때)
- 위험한 게임 (Negative-dominated): 낙관주의 안경이 가장 잘 작동했습니다. (상대가 나를 해칠 수 있는 '독약' 같은 함정이 있을 때, 이를 피하는 게 중요했기 때문입니다.)
- 기회 많은 게임 (Positive-dominated): 비관주의 안경이 가장 잘 작동했습니다. (상대가 나쁜 일을 할지 모를 때, 안전한 길로 가는 게 이득이었습니다.)

핵심 교훈: 어떤 협상 상황에서도 항상 똑같은 전략을 쓰는 AI 는 실패합니다. 상황을 읽고 안경을 갈아 끼울 수 있는 AI가 필요합니다.

5. 현실 적용: 기후 협상 데이터로 검증

이론만으로는 부족했기에, 연구팀은 실제 **하버드 협상 챌린지 (기후 변화 관련)**의 문서 데이터를 가져와서 실제 협상 게임으로 만들었습니다.

결과: 여기서도 '비관주의 안경 (Lower Bound)'이 가장 좋은 성과를 냈습니다. 기후 협상은 서로의 이익이 복잡하게 얽혀 있고, 한 번 실수하면 돌이킬 수 없기 때문에, 위험을 감수하기보다 안전한 진전을 추구하는 전략이 더 효과적이었습니다.
LLM(대형 언어 모델) 의 한계: 최신 AI 챗봇 (LLM) 을 그대로 쓰자니 점수가 매우 낮았습니다. 즉, "말만 잘하는 AI"는 복잡한 약속과 전략적 계산이 필요한 협상에서는 아직 부족하다는 뜻입니다.

요약 및 결론

이 논문은 **"협상은 한 번의 거래가 아니라, 되돌릴 수 없는 약속들이 쌓아 올리는 과정"**임을 강조합니다.

문제: 기존의 AI 는 미래를 너무 단순하게 보거나, 상황에 맞지 않는 전략만 고집합니다.
해결: 다양한 협상 시나리오를 만들어내고, 상황에 따라 다른 전략 (안경) 을 쓸 수 있는 AI 를 개발해야 합니다.
미래: 앞으로의 AI 는 "지금 당장 이득"만 쫓는 게 아니라, 장기적인 약속과 위험 관리를 동시에 고려할 수 있어야 진정한 협상가가 될 수 있습니다.

간단히 말해, **"협상은 체스 게임처럼 한 수 한 수를 계산하며, 상대방이 어떤 함정을 놓을지, 내가 어떤 약속을 해야 나중에 큰 상을 받을지 미리 예측하는 능력"**이 필요하다는 것을 증명했습니다.

1. 문제 정의 (Problem)

기존의 계산적 협상 모델 (게임이론, 다중 에이전트 강화학습 등) 은 대부분 최종 결과 (예: 가격, 물품 분배) 에 대한 비구속적 제안과 수용을 기반으로 합니다. 그러나 실제 고위험 다자간 협상 (인도적 협상, 기후 회의 등) 은 다음과 같은 특징을 가집니다:

순차적 행동 수준 협상: 단일 합의가 아니라, 양자 및 소그룹 간의 구체적인 행동 약속들이 순차적으로 이루어집니다.
구속력 있는 약속 (Binding Commitments): 한 번 이루어진 약속은 취소할 수 없으며, 미래의 선택지를 제한하고 향후 협상 기회를 재형성합니다.
최종 보상만 존재 (Terminal-only Rewards): 중간 단계의 보상은 없으며, 모든 약속이 완료된 시점에서만 보상이 발생합니다.
전략적 복잡성: 최종 합의뿐만 아니라, 파트너 선정 순서, 약속의 시퀀싱, 중간 약속들의 상호작용이 전략의 핵심입니다.

현재 이러한 환경에 대한 벤치마크가 부족하여, 기존 알고리즘이 언제 신뢰할 수 있는 지침을 제공할 수 있는지 (예: 누구와 먼저 협상해야 하는지) 불분명합니다.

2. 방법론 (Methodology)

2.1. 게임 포멀라이제이션 (Game Formalization)

플레이어와 약속: $N_P$ 명의 플레이어가 $T$ 턴 동안 협상합니다. 각 플레이어는 이진 벡터 $C_n$ 으로 자신의 약속을 나타내며, 약속은 $0 \to 1$ 로만 변경 가능합니다 (되돌릴 수 없음).
목표와 보상: $N_G$ $N_{G}$ 개의 목표가 존재하며, 각 목표는 특정 플레이어들의 약속 조합 ( $C_g$ $C_{g}$ ) 에 의해 충족됩니다.
- 선형 목표 (Linear): 충족된 약속의 비율에 비례하여 보상이 발생합니다.
- 전부 아니면 전무 (All-or-Nothing): 모든 필요한 약속이 충족되어야 보상이 발생합니다.
보상 구조: 플레이어는 각 목표에 대해 긍정적, 부정적, 또는 영 (0) 의 효용을 가집니다. 보상은 게임 종료 시점 ( $T$ ) 에만 실현됩니다.

2.2. 제어 가능한 게임 생성기 (Configurable Game Generator)

연구팀은 다양한 전략적 난이도를 가진 인스턴스를 생성하기 위해 다음과 같은 구조적 속성을 제어할 수 있는 생성기를 개발했습니다:

규모: 플레이어 수, 목표 수, 약속 수.
동기 정렬 (Incentive Alignment): 협력적 (효용이 유사함) vs 대립적 (효용이 상충됨).
보상 구조: 균형형, 긍정 우세형, 부정 우세형.
목표 복잡도: 목표 달성에 필요한 약속의 수 (Zeta 분포 사용).
목표 비선형성: 선형 목표 vs 전부 아니면 전무 목표의 비율.
선호 구조: 목표 간 효용의 상관관계 (잠재 요인 차원 $d$ 로 제어).

2.3. 게임 플레이 프로토콜 및 평가

프로토콜: 완전 정보 (모든 플레이어의 선호도 공개), 순차적 양자 협상.
- 각 턴에는 제안자 (Proposer) 와 파트너 (Partner) 가 선정됩니다.
- 제안자는 파트너의 가치 함수를 고려하여 최적의 약속 업데이트를 제안합니다 (최소 1 개, 최대 $k$ 개의 새로운 약속).
- 파트너는 자신의 기대 보상이 증가하거나 유지될 경우만 수락합니다.
평가 기준:
- 작은 게임: 동적 프로그래밍을 통해 최적 해 (Exact Solution) 를 계산하고, $L_1$ 오차로 평가.
- 큰 게임: 최적 해 계산이 불가능하므로 '협상 없음 (No Negotiation)' 베이스라인 대비 총 보상 개선량 ( $\sum \Delta_n$ ) 으로 비교 평가.

2.4. 가치 함수 근사 (Value-Function Approximations)

결정 과정을 위해 세 가지 편향된 '렌즈 (Lenses)'를 사용하여 가치 함수를 근사했습니다:

단시적 보상 (Myopic Reward): 미래 협상을 무시하고 현재 상태의 즉각적 보상만 고려합니다.
상한선 (Optimistic Upper Bound): 플레이어가 모든 긍정적 목표를 달성할 것이라고 가정합니다. 부정적 노출에 대해 매우 보수적으로 행동합니다.
하한선 (Pessimistic Lower Bound with Credible Threats): 상대방이 플레이어에게 해로운 목표를 달성할 것이라고 가정합니다 (신뢰할 수 있는 위협). 단기적 손실을 감수하더라도 장기적 긍정적 목표를 확보하는 전략을 취합니다.

3. 주요 기여 (Key Contributions)

제어 가능한 게임 생성기: 규모, 동기 정렬, 보상 구조, 목표 복잡도, 비선형성, 선호 상관관계 등을 정밀하게 제어하여 다양한 협상 지형을 생성할 수 있는 도구 제공.
참조 플레이 절차 및 평가 스위트: 고정된 프로토콜 하에서 다양한 가치 함수 근사법의 성능을 격리하여 평가할 수 있는 체계 마련. 작은 게임에서는 정밀한 최적 해 비교, 큰 게임에서는 상대적 비교가 가능합니다.
가치 함수 렌즈를 통한 난이도 규명: 세 가지 단순한 근사법 (단시적, 낙관적, 비관적) 이 서로 다른 게임 구조에서 어떻게 작동하는지 매핑했습니다. 단일 방법이 모든 상황에서 우월하지 않으며, 게임의 구조적 속성에 따라 최적의 전략이 달라짐을 증명했습니다.
실제 기반 대규모 인스턴스: 하버드 협상 챌린지 (Harvard Negotiation Challenge) 의 기후 협상 문서에서 추출한 실제 데이터를 기계 판독 가능한 게임 인스턴스로 변환하여, 합성 데이터의 패턴이 실제 시나리오로 전이되는지 검증했습니다.

4. 실험 결과 (Results)

4.1. 게임 생성기 기반 결과 (Regime Sweep)

난이도 요인: 균형 잡힌 보상 구조 (Balanced) 와 대립적 동기 (Adversarial) 가 가장 높은 난이도를 보였습니다. 또한, '전부 아니면 전무 (All-or-Nothing)' 목표의 비율이 높을수록 난이도가 증가했습니다.
근사법 성능:
- 균형형 게임: **단시적 보상 (Myopic Reward)**이 가장 낮은 오차를 보였습니다. (미래에 대한 과도한 가정이 위험할 수 있음)
- 부정 우세형 게임 (Negative-Dominated): **상한선 (Upper Bound)**이 가장 잘 작동했습니다. 특히 '독약 (Poison Pill)' 시나리오 (국소적으로는 이득이지만 장기적으로 큰 손해를 입히는 제안) 에서 상한선 근사법이 함정을 피하는 데 결정적 역할을 했습니다.
- 긍정 우세형 게임 (Positive-Dominated): **하한선 (Lower Bound)**이 가장 우수했습니다. 상대방이 위협을 실행할 것이라고 가정하고, 긍정적 진전을 확보하는 데 집중하는 전략이 효과적이었습니다.

4.2. 실제 협상 데이터 (Real-Life Negotiation)

하버드 협상 챌린지 기반의 기후 협상 시나리오 (22 명, 45 개 목표) 에서 **하한선 (Lower Bound)**이 베이스라인 대비 가장 큰 보상을 개선했습니다. 이는 해당 시나리오가 긍정 우세형이면서 선형 목표가 주를 이루기 때문입니다.
단시적 보상도 선형 목표 구조 덕분에 좋은 성능을 보였습니다.
**상한선 (Upper Bound)**은 지나치게 보수적이라 베이스라인보다 낮은 성과를 냈습니다.
제로샷 LLM: 복잡한 다자간 협상 환경에서 LLM 만을 의존하는 것은 가치 함수 기반 접근법보다 훨씬 열악한 결과를 보였습니다.

5. 의의 및 결론 (Significance & Conclusion)

이 연구는 다음과 같은 중요한 시사점을 제공합니다:

상황 의존적 전략의 필요성: 협상 에이전트는 하나의 고정된 가치 평가 함수를 사용하는 것이 아니라, 협상의 구조적 속성 (동기 정렬, 보상 분포, 목표 비선형성 등) 을 인식하고 적응적인 평가 전략을 선택해야 합니다.
장기적 계획의 중요성: 구속력 있는 약속과 최종 보상만 존재하는 환경에서는, 단기적 보상만 보는 접근법 (Myopic) 이 실패할 수 있으며, 장기적 관점에서 상태 가치를 학습하고 계획하는 에이전트가 필요합니다.
차별화된 벤치마크 제공: 기존 협상 벤치마크가 다루지 않았던 '구속력 있는 순차적 행동' 영역에 대한 체계적인 평가 도구를 제공함으로써, 향후 다중 에이전트 강화학습 및 협상 알고리즘 개발의 방향성을 제시합니다.

결론적으로, 이 논문은 실제 협상의 복잡성을 포착하는 새로운 벤치마크를 제시하고, 다양한 게임 regimes 에서 어떤 가치 평가 전략이 효과적인지에 대한 실증적 증거를 제공하여, 더 강력하고 적응적인 협상 에이전트 개발의 기초를 마련했습니다.