한국어 초록
최근 마르코프 게임(Markov game)에서의 상관균형(correlated equilibrium) 개념에 관한 연구가 급증하고 있다. 그러나 기존 결과들은 정규형 상관균형(normal-form correlated equilibria, NFCE)보다 약한 개념에 초점을 맞추고 있어, Papadimitriou와 Roughgarden의 선구적 연구(JACM'08)로까지 거슬러 올라가는, 그러한 균형을 계산하는 더 어려운 문제는 미해결로 남아 있다. 본 논문에서는 플레이어 수 $n$이 고정된 유한 구간(finite-horizon) 마르코프 게임에서 NFCE에 대한 최초의 효율적인 알고리즘을 제시한다. 구체적으로, 상태(state) 수가 $S$, 구간(horizon)이 $H$, 플레이어당 행동(action) 수가 최대 $A$일 때, 이 알고리즘은 $S(AH/ε)^{O(n)}$ 시간에 $ε$-NFCE를 계산한다. 이는 정규형(normal-form) 설정을 넘어서는 흥미로운 문제 범주에서 NFCE에 대해 $1/ε$ 및 게임 기술(description)에 대해 다항 시간(polynomial time)인 최초의 알고리즘이다. 더불어, 추천(recommendation)이 상태들 간에 독립적이라는 일반적인 가정 하에서, 우리는 다수 플레이어 게임이거나 정밀도가 지수적으로 작은 경우 PPAD-완전성(PPAD-completeness)—즉 내쉬 균형(Nash equilibrium)과의 계산적 동치성—을 보인다. 우리 접근법의 핵심 아이디어는 일련의 보조 단계 게임(auxiliary stage game)들에 대해 후방 귀납법(backward induction)을 수행하는 것이지만, 각 단계에서 상수 기댓값 상관균형(constant-expectation correlated equilibrium)을 계산한다는 차이가 있다. 이는 추천을 따를 때의 조건부 기대 보상(payoff)이 추천 내용과 독립적인, 상관균형의 자연스러운 세분화(refinement)이다. 실제로 우리의 환원(reduction)은 양방향으로 성립하여, 마르코프 게임에서 상수 기댓값 상관균형(constant-expectation CE)과 NFCE 사이의 동치성을 확립한다. 플레이어 수가 고정된 경우, 상수 기댓값 상관균형은 선형계획법(linear programming)과 적절한 이산화(discretization)를 결합하여 근사적으로 계산할 수 있음을 관찰한다. 반면, i) 다항행렬(polymatrix, 다수 플레이어) 게임에서는 상수 정밀도에서, ii) 2인 게임에서는 지수적으로 작은 정밀도에서 PPAD-hard임을 보인다. 후자의 결과는 랭크-2(rank-2) 2인 게임과의 예상치 못한 연관성에서 비롯된다.
원문 초록
There has been a surge of recent work on correlated equilibrium concepts in Markov games. However, existing results focus on concepts weaker than normal-form correlated equilibria (NFCEs), leaving open the more challenging question of computing such equilibria, which goes back to the seminal work of Papadimitriou and Roughgarden (JACM'08). Here, we establish the first efficient algorithm for NFCEs in finite-horizon Markov games with a fixed number of players $n$. In particular, with $S$ states, horizon $H$, and at most $A$ actions per player, it computes an $ε$-NFCE in time $S(AH/ε)^{O(n)}$. This is the first algorithm polynomial in $1/ε$ and the description of the game for NFCEs in an interesting class of problems beyond the normal-form setting. Moreover, under the usual assumption that recommendations are independent across states, we show PPAD-completeness---that is, computational equivalence to Nash equilibria---either in many-player games or when the precision is exponentially small. The key idea behind our approach is to run backward induction on a sequence of auxiliary stage games, but with the twist that in each step we compute a constant-expectation correlated equilibrium. This is a natural refinement of correlated equilibrium in which the conditional expected payoff from obeying is independent of the recommendation. In fact, our reduction goes both ways, establishing an equivalence between constant-expectation CEs and NFCEs in Markov games. For a fixed number of players, we observe that a constant-expectation CE can be computed approximately by combining linear programming with suitable discretization. In contrast, it is PPAD-hard in i) polymatrix (many-player) games at constant precision, and ii) two-player games at exponentially small precision. The latter result follows from an unexpected connection to rank-2 two-player games.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.