arXiv:2610.28141v3 cs.GT

고정 집합과 상관 균형 계산의 난해성

Fixed Sets and the Hardness of Computing Correlated Equilibria

Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm, Brian Hu Zhang

제출 2026-11-18

한국어 초록

폴리토프 게임의 근사 상관 균형을 계산하는 문제가 PPAD-완전임을 보이며, 따라서 이는 내시 균형을 찾는 문제와 다항 시간 동치이다. 이는 상관 균형이 내시 균형보다 다루기 쉬운 대상이라는 게임 이론의 통상적 관점에 이의를 제기한다. 개념적으로 우리는 상관 균형을 고정점의 자연스러운 일반화인 고정 집합과 연결한다. 연속 함수 $f$의 고정 집합이란 $S \subseteq \operatorname{conv} f(S)$를 만족하는 비어 있지 않은 유한 집합 $S$이다. 핵심 기술적 기여는 고정 집합 계산이 역다항 정밀도에서도 PPAD-난해임을 증명한 것이다.

원문 초록

We show that computing an approximate correlated equilibrium of a polytope game is PPAD-complete, and thus polynomial-time equivalent to finding a Nash equilibrium. This challenges the conventional view in game theory that correlated equilibria are more tractable objects than Nash equilibria. From a conceptual standpoint, we connect correlated equilibria to a natural generalization of fixed points, which we call fixed sets. A fixed set of a continuous function $f$ is a nonempty finite set $S$ such that $S \subseteq \operatorname{conv} f(S)$. Our main technical contribution is to prove that computing a fixed set is PPAD-hard even at inverse polynomial precision.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2610.28141v3제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.