Interleaved Information Structures in Dynamic Games: A General Framework with Application to the Linear-Quadratic Case

1. 문제 정의 (Problem Statement)

비협력적 동적 게임 (Noncooperative Dynamic Games) 에서 나쉬 균형 (Nash Equilibrium) 을 계산하는 것은 각 에이전트가 의사결정 시점에 접근할 수 있는 정보의 구조에 크게 의존합니다. 기존 연구는 주로 두 가지 극단적인 정보 구조에 집중해 왔습니다.

• 피드백 (Feedback): 모든 에이전트가 매 시간 단계마다 전체 게임 상태 (모든 에이전트의 상태) 를 관찰합니다.
• 오픈 루프 (Open-loop): 모든 에이전트가 초기 상태만 관찰하고, 이후 상태 변화에 대한 정보는 접근하지 못합니다.

그러나 실제 다중 에이전트 환경에서는 에이전트들이 전체 상태나 초기 상태만 관찰하는 것이 아니라, 특정 시간 단계마다 다른 에이전트들의 상태 부분집합 (subset) 만 관찰하는 경우가 많습니다. 이를 교차된 정보 구조 (Interleaved Information Structures) 라고 합니다. 현재까지 이러한 교차된 정보 구조를 가진 동적 게임을 체계적으로 모델링하고 해결할 수 있는 일반적인 프레임워크는 존재하지 않았습니다. 특히 선형 - 2 차 (LQ) 게임에서 이러한 구조 하의 나쉬 균형을 특징짓는 리카티 (Riccati) 유사 방정식을 유도하는 방법은 명확하지 않았습니다.

2. 방법론 (Methodology)

이 논문은 수학적 프로그래밍 네트워크 (Mathematical Program Networks, MPNs) 프레임워크를 기반으로 한 새로운 접근법을 제시합니다.

A. MPN 을 활용한 게임 모델링

저자들은 동적 게임을 $T$ 시간 단계와 $N$ 개의 에이전트로 구성된 네트워크로 모델링합니다.

• 노드 (Nodes): 각 에이전트 $i$ 와 각 시간 단계 $t$ 에 대해 최적화 문제 (비용 함수 최소화) 를 나타내는 노드 $N^i_t$ 를 생성합니다.
• 엣지 (Edges): 에이전트 간의 정보 의존성을 방향성 있는 엣지로 표현합니다.
  • 시간적 의존성: 에이전트 $i$ 의 현재 결정이 미래 결정에 영향을 미치므로, $N^i_t \to N^i_{t+1}$ 형태의 엣지가 존재합니다.
  • 관찰 의존성 (Interleaved): 에이전트 $i$ 가 시간 $t$ 에 에이전트 $j$ 의 상태를 관찰한다면, $j$ 의 현재 결정이 $i$ 의 미래 결정 문제 ($t+1$) 에 영향을 미칩니다. 이는 $N^j_t \to N^i_{t+1}$ 엣지로 표현됩니다.
• 해 그래프 (Solution Graph): 각 노드의 최적해는 다른 노드들의 해에 의존하는 조건부 최적화 문제로 정의되며, 전체 MPN 의 균형은 모든 노드의 해 그래프의 교집합으로 정의됩니다.

B. 선형 - 2 차 (LQ) 게임에 대한 체계적 유도

선형 - 2 차 (LQ) 동적 게임의 경우, 제약 조건의 아핀 (affine) 구조와 비용 함수의 볼록성 (convexity) 을 이용하여 다음과 같은 절차를 따릅니다.

1. MPN 구성: 교차된 정보 구조를 반영하여 게임의 MPN 을 구축합니다.
2. KKT 조건 도출: 각 노드의 최적화 문제에 대해 카루시 - 쿤 - 타커 (KKT) 조건을 작성합니다. 이때 라그랑주 승수 (Lagrange multipliers) 는 상태 동역학 제약과 정보 구조에 따른 의존성 제약에 대해 정의됩니다.
3. 리카티 유사 방정식 유도: 모든 노드의 KKT 조건을 연결하여 연립 방정식을 구성하고, 이를 통해 나쉬 균형을 특징짓는 리카티 유사 방정식 (Riccati-like equations) 을 유도합니다.

3. 주요 기여 (Key Contributions)

1. 교차된 정보 구조를 위한 MPN 프레임워크 제안:
   임의의 교차된 정보 구조 (각 에이전트가 다른 에이전트들의 상태 부분집합을 관찰하는 경우) 를 가진 동적 게임을 수학적 프로그래밍 네트워크 (MPN) 로 체계적으로 모델링하는 방법을 제시했습니다. 이는 계층적 의사결정 구조뿐만 아니라, 에이전트 간의 비대칭적 정보 흐름을 포착하는 자연스러운 프레임워크입니다.

2. LQ 게임에 대한 리카티 유사 방정식 유도 절차 개발:
   $N$ 에이전트 LQ 동적 게임에서 임의의 교차된 정보 구조 하에 나쉬 균형을 특징짓는 리카티 유사 방정식을 체계적으로 유도하는 알고리즘을 개발했습니다. 이는 기존의 피드백 또는 오픈 루프 균형 계산법을 일반화한 것입니다.

3. 구체적 사례 연구 (Cyclic Information Structure):
   3 에이전트 LQ 게임에서 순환적 (cyclic) 인 정보 구조 (에이전트 1 은 2 를, 2 는 3 을, 3 은 1 을 관찰) 를 가진 사례를 통해 제안된 프레임워크의 유효성을 입증했습니다. 이 예제를 통해 KKT 조건을 어떻게 구성하고 라그랑주 승수를 분석하여 최종 방정식을 도출하는지 구체적으로 보여주었습니다.

4. 결과 및 분석 (Results and Analysis)

• 일반성: 제안된 MPN 프레임워크는 오픈 루프와 피드백을 특수한 경우로 포함하며, 그 사이의 다양한 비대칭적 정보 구조를 유연하게 처리할 수 있음을 보였습니다.
• 해의 존재성 및 유일성: LQ 게임의 볼록성 때문에 KKT 조건이 최적성을 위한 필요조건이자 충분조건이 되며, 이를 통해 유도된 리카티 유사 방정식 체계가 나쉬 균형을 유일하게 결정함을 확인했습니다.
• 계산적 접근: 순환적 정보 구조 예제에서, 특정 라그랑주 승수 (예: $\lambda^i_{t,(i,m)}$) 가 0 이 되거나 불필요할 수 있음을 분석하여, 방정식 체계가 실제 계산에 필요한 최소한의 정보로 축소될 수 있음을 보였습니다.

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

이 연구는 다중 에이전트 시스템의 현실적인 시나리오를 더 정확하게 모델링할 수 있는 이론적 기반을 마련했습니다.

• 이론적 확장: 기존의 제한된 정보 구조 (전체 상태 관찰 또는 초기 상태만 관찰) 를 넘어, 부분적 관측이 교차하는 복잡한 환경에서의 게임 이론적 분석을 가능하게 합니다.
• 실용적 적용: 자율 주행 차량 군집, 스마트 그리드, 로봇 협업 등 에이전트들이 제한된 센서 범위를 통해 서로의 상태를 부분적으로만 파악하는 실제 시스템에 적용 가능한 균형 계산 방법을 제공합니다.
• 향후 연구 방향: LQ 게임을 넘어 더 일반적인 비선형 동적 게임으로의 확장 및, 에이전트의 결정에 따라 정보 구조가 진화하는 (동적으로 변화하는) 정보 구조에 대한 연구가 필요함을 시사합니다.

요약하자면, 이 논문은 MPN을 도구로 사용하여 교차된 정보 구조 하의 동적 게임을 체계적으로 모델링하고, LQ 게임에서 이를 해결할 수 있는 리카티 방정식 기반의 해법을 제시함으로써 비협력적 게임 이론의 중요한 한계를 극복했습니다.