Aggregative games with bilevel structures: Distributed algorithms and convergence analysis

기술 요약: 이중 수준 구조를 가진 집합적 게임: 분산 알고리즘 및 수렴 분석

문제 정의
본 논문은 가상의 리더의 목적 함수를 최소화하는 내부 단계(inner level)에 의해 결정되는 집합적(aggregation) 항을 특징으로 하는, 이중 수준 구조를 가진 집합적 게임(Aggregative Games, AGs)에서 분산적으로 내쉬 균형(Nash Equilibrium, NE)을 찾는 문제를 다룹니다. 집합적 항이 플레이어들의 국소적 행동의 직접적인 합이나 평균인 전통적인 AG와 달리, 본 프레임워크에서의 집합적 항은 내부 단계의 가상 리더의 목적 함수를 최소화하는 값에 의해 결정됩니다. 구체적으로, 게임 $\Gamma(V, \Omega, J)$는 $n$명의 외부 단계 플레이어를 포함하며, 각 플레이어는 자신의 국소적 행동 $x_i$와 전역 집합적 변수 $\sigma(x)$에 의존하는 비용 함수 $J_i(x_i, \sigma(x))$를 최소화합니다. 여기서 집합적 변수 $\sigma(x)$는 다음과 같은 내부 단계 최적화 문제의 해로 정의됩니다:
$$\sigma(x) = \arg \min_{y} \sum_{i=1}^n g_i(x_i, y)$$
여기서 $g_i$는 플레이어 $i$의 국소 함수와 집합적 변수 $y$의 함수이며, 이들은 $y$에 대해 강볼록(strongly convex)하다고 가정됩니다.

식별된 핵심 과제는 외부 단계의 플레이어들이 오직 국소적인 정보만을 보유하고 있다는 점입니다: 즉, 자신의 비용 함수 $J_i$, 가상 리더의 목적 함수의 국소 부분인 $g_i$, 그리고 자신의 국소 행동 집합입니다. 플레이어들은 내부 단계 목적 함수의 전체 정보나 전역 집합적 항에 직접 접근할 수 없습니다. 결과적으로, 플레이어의 외부 단계 비용 함수의 기울기(gradient)는 $\nabla_{x_i}\sigma(x)$에 의존하게 되는데, 이는 내부 단계 함수들의 헤시안(Hessian) 행렬의 역행렬을 포함하며, 이는 개별 플레이어가 직접 접근할 수 없는 항입니다.

방법론
연결된 통신 그래프 하에서 이 문제를 해결하기 위해, 저자들은 두 가지 분산 알고리즘을 제안합니다:

1. 2차 기울기 기반 분산(SOGD) 알고리즘:
   이 알고리즘은 플레이어가 2차 기울기 정보(헤시안 행렬)에 접근할 수 있다고 가정합니다. 이는 세 가지 구성 요소를 통합합니다:

   • 프라이멀-듀얼(Primal-Dual) 전략: 내부 단계의 전역 목적 함수를 협력적으로 최소화함으로써 집합적 $\sigma(x)$를 추정하는 데 사용됩니다.
   • 분산 평균 추적(Distributed Average Tracking): 내부 단계 목적 함수와 관련된 헤시안 행렬의 평균을 추적하는 데 사용됩니다.
   • 투영이 포함된 기울기 하강법(Gradient Descent with Projection): 플레이어는 크라스노셀스키-만(Krasnoselskii-Mann) 반복법을 이용한 투영 기울기 전략을 사용하여 외부 단계의 행동을 업데이트합니다. 이 전략은 필요한 외부 단계 비용 함수의 기울기 항을 계산하기 위해 추적된 헤시안 정보를 활용합니다.

2. 1차 기울기 기반 분산(FOGD) 알고리즘:
   고차원 응용 분야(예: 메타 러닝)에서 헤시안 행렬을 계산하는 것이 비용이 많이 들거나 불가능할 수 있음을 인식하여, 저자들은 1차 방법론을 제안합니다.

   • 분산 추정 전략: 헤시안을 직접 계산하는 대신, 이 알고리즘은 보조 변수와 섭동 파라미터 $\delta_i$를 도입합니다. 이를 통해 집합의 기울기와 두 번째 인자에 대한 비용 함수의 기울기 곱을 추정합니다.
   • 보조 최적화: 플레이어들은 필요한 기울기 항을 추정하기 위해 보조 최적화 문제를 해결함으로써, 2차 정보를 직접 사용하는 것을 피합니다.

주요 기여
본 논문은 다음과 같은 독창성과 기여를 주장합니다:

• 일반화된 프레임워크: 제안된 이중 수준 구조는 기존의 단일 수준 AG 및 강볼록 목적 함수를 가진 분산 최적화 문제를 일반화합니다. 이는 플레이어가 일반적으로 전체 기울기 정보에 접근할 수 있는 기존의 스태켈버그(Stackelberg) 게임 형식과는 다르며, 여기서는 집합적 항이 완전히 관측되지 않는 내부 단계의 해에 의존합니다.
• SOGD 알고리즘 설계: 저자들은 프라이멀-듀얼 방법, 분산 평균 추적, 기울기 하강법을 결합한 새로운 알고리즘을 개발했습니다. 이들은 완만한 가정 하에서 플레이어의 행동이 NE로 점근적으로 수렴하며, 수렴 속도는 $O(\sqrt{\ln t}/t)$임을 증명했습니다.
• FOGD 알고리즘 및 오차 분석: 헤시안 행렬을 사용할 수 없는 경우를 위해 FOGD 알고리즘이 도입되었습니다. 저자들은 수렴 오차와 추정 파라미터 $\delta_i$ 사이의 선형 관계를 확립하여, 오차가 이 파라미터들에 대해 선형임을 증명했습니다.

결과 및 수렴 분석

• SOGD 수렴: 그래프 연결성, 내부 함수의 볼록성, 내부 함수의 강볼록성 및 리프시츠 연속성(Lipschitz continuity) 가정 하에서, SOGD 알고리즘은 플레이어의 행동 $x_t$와 집합적 추정치 $y_{i,t}$가 각각 NE $x^*$와 $\sigma(x^*)$로 수렴함을 보장합니다. 수렴 속도는 $O(\sqrt{\ln t}/t)$로 나타나며, 저자들은 이것이 감쇠 스텝 사이즈를 사용하는 분산 최적화의 일반적인 $O(\ln t/\sqrt{t})$ 속도보다 빠르다고 언급했습니다.
• FOGD 수렴: FOGD 알고리즘은 근사 NE로 수렴합니다. 이론적 분석은 수렴 오차가 추정 파라미터 $\delta_i$를 포함하는 항들에 의해 제한됨을 보여줍니다. 구체적으로, 오차 경계는 $\sqrt{\delta_i} + \delta_i$에 비례하는 항을 포함하며, 이는 $\delta_i$가 작을수록 높은 정확도를 얻을 수 있음을 나타내지만, 실제적인 제약으로 인해 $\delta_i$를 임의로 작게 만들 수는 없음을 의미합니다.
• 수치 시뮬레이션: 알고리즘은 20개의 기지국이 있는 소셀(small-cell) 네트워크의 분산 전력 할당 문제에 대해 테스트되었습니다. 시뮬레이션은 두 알고리즘 모두 시스템을 이론적 평형 상태로 유도하며, 오차 지표의 궤적이 예측된 대로 시간이 지남에 따라 감소함을 확인했습니다.

의의 및 주장
본 논문은 집합적 항이 단순한 행동의 합이 아니라 가상 리더의 내부 단계 최소화 과정에 의해 결정되며, 플레이어가 이 내부 단계에 대한 전체 정보를 갖지 못하는 이중 수준 구조를 가진 분산 집합적 게임을 연구한 첫 사례로 자리매김합니다. 저자들은 자신의 연구가 전통적인 AG와 분산 최적화의 연구 프레임워크를 통합한다고 강조합니다.

본 연구의 의의는 "가격" 또는 "집합적 요소"가 단순한 행동의 합이 아니라 복잡하고 분산된 최적화 프로세스(예: 소셀 네트워크의 네트워크 가격 책정)로부터 발생하는 창발적 속성인 시나리오에 대한 이론적 토대와 실용적인 알고리즘을 제공한다는 점에 있습니다. 저자들은 FOGD 알고리즘이 근사적 수렴을 달ai하지만, 1차 정보만을 사용하여 정확한 수렴을 달성하는 것은 향후 조사가 필요한 어려운 문제임을 겸허히 인정합니다. 향후 연구로는 네트워크 유발 시간 지연, 패킷 손실 및 통신 대역폭 제약 문제를 다룰 것을 제안합니다.