다인수 불완전 정보 게임의 Nash equilibrium 계산을 위한 변수 범위 축소 (Variable Bound Tightening)

최근 대규모 2인 제로섬 불완전 정보 게임 (two-player zero-sum imperfect-information games)에서의 Nash equilibrium 근사 알고리즘과 다인수 전략형 게임 (multiplayer strategic-form games)에서의 Nash equilibrium의 정확한 계산 분야에서 상당한 진전이 있었습니다. Counterfactual regret minimization (CFR)과 fictitious play는 대규모 게임으로 확장 가능하며 2인 제로섬 게임에서 수렴성을 보장하지만, 다인수 게임에서 Nash equilibrium으로의 수렴을 보장하지는 않습니다. 최근, sequence-form 게임 표현으로부터 유도된 비선형 상보성 문제 (nonlinear complementarity problem) 정식화에 기반하여 이차 제약 프로그램 (quadratically constrained program)을 해결함으로써, 다인수 불완전 정보 게임에서 Nash equilibrium을 정확하게 계산하는 접근 방식이 제시되었습니다. 이 정식화는 Gurobi의 비볼록 이차 솔버 (nonconvex quadratic solver)를 사용하여 해결되었으며, 이 솔버는 McCormick envelopes를 통해 쌍선형 항 (bilinear terms)의 볼록 완화 (convex relaxations)를 해결함으로써 변수 범위 (variable bounds)를 반복적으로 정밀화하는 공간 분기 한정법 (spatial branch-and-bound)을 채택합니다. Presolve 과정 동안 Gurobi는 보조 변수 (auxiliary variables)를 도입하며, 경우에 따라 이진 변수 (binary variables)를 도입하여 내부적인 MIQCP 재정식화를 유도합니다. 이 접근 방식은 Gambit 소프트웨어 제품군의 이전 알고리즘들보다 성능이 우수함을 입증하였으며, 지배된 행동 (dominated actions)을 제거한 후 3인 Kuhn poker를 빠르게 해결하였습니다. 그러나 해당 알고리즘은 24시간 이내에 게임의 전체 버전을 해결할 수는 없었습니다. 본 논문에서 우리는 비선형 상보성 정식화에서의 slack 변수와 multiplier 변수에 대한 유한한 범위 (finite bounds)를 도출합니다. 이러한 범위는 공간 분기 한정법 내에서 사용되는 볼록 완화를 강화하며 상당한 계산적 개선을 이끌어냅니다. 우리는 제안된 범위가 3인 Kuhn poker의 정확한 Nash equilibrium 계산에 미치는 영향을 입증합니다.