알고리즘 담합과 정보 가치 없는 균형의 복잡도
Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria
한국어 초록
(성긴) 상관 균형((coarse) correlated equilibrium, CE)에서 플레이어가 고정된 행동을 고수함으로써 추천으로부터 얻는 보수(payoff)와 동일한 수준을 달성할 수 있을 때, 이를 정보 가치 없는(information-value-free, IVF) 균형이라고 합니다. 알고리즘 담합(algorithmic collusion)을 규제하는 문제에서 동기를 얻은 이 균형 정제(refinement) 개념은 Hartline, Wang, Zhang [EC'26]에 의해 도입되었으며, 명시적으로 표현된 정규형 게임(normal-form game)에서 다항 시간 내에 계산될 수 있음이 밝혀졌습니다. 본 논문에서는 다수의 플레이어 또는 지수적으로 많은 순수 전략을 특징으로 하여 보다 현실적인 전략적 상호작용을 모델링하는 간결한 게임(succinct game)에서 IVF(C)CE의 복잡도를 조사합니다. 먼저 다인 폴리매트릭스 게임(polymatrix game) 또는 2인 베이즈 게임(Bayesian game)에서 근사가 상수인 경우에도 정보 가치 없는 CE를 계산하는 것이 PPAD-완전(PPAD-complete)임을 보입니다. 또한 무조건적인 지수적 질의 하한(query lower bound)을 증명합니다. 우리의 결과는 중앙 집중형 모델에서조차 IVFCE 계산이 다루기 힘들며(intractable), 효율적인 학습 역학(learning dynamics)의 존재 가능성을 배제함을 입증합니다. 이는 특정 부류의 학습 알고리즘만을 다루었던 Hartline, Wang, Zhang의 불가능성 결과를 크게 강화하며, 최근의 알고리즘 담합 규제에 대한 강력한 계산적 비판을 제공합니다. 이러한 난해성 결과를 우회하기 위해 정보 가치 없는 CCE의 복잡도를 조사합니다. 후회 일치(regret matching)나 FTRL과 같은 특정 무후회(no-regret) 알고리즘은 이 문제에 대해 완전 다항 시간 근사 스킴(FPTAS)을 제공합니다. 근사가 지수적으로 작을 때의 복잡도는 미묘한 양상을 보입니다. 한편으로는 무후회 역학을 활용하여 $\text{CLS} = \text{PPAD} \cap \text{PLS}$에 속함을 규명합니다. 다른 한편으로는 이것이 적어도 P-행렬 선형 상보성 문제(P-matrix linear complementarity problem)만큼 어렵고, 따라서 단순 확률 게임(simple stochastic game)만큼 어렵다는 점을 보여줍니다. 이는 중대한 돌파구가 없는 한 IVFCCE조차 다항 시간 알고리즘을 허용할 가능성이 낮음을 보여줍니다.
원문 초록
A (coarse) correlated equilibrium (CE) is information-value-free (IVF) if a player can match the payoff obtained from recommendations by committing to a fixed action. Motivated by the problem of regulating algorithmic collusion, this refinement was introduced by Hartline, Wang, and Zhang [EC'26], who showed that it can be computed in polynomial time in explicitly represented normal-form game. In this paper, we examine the complexity of IVF(C)CEs in succinct games, which model more realistic strategic interactions that feature either many players or exponentially many pure strategies. We first show that computing an information-value-free CE is PPAD-complete in many-player polymatrix games or two-player Bayesian games, even when the approximation is a constant. We also prove an unconditional exponential query lower bound. Our results establish that IVFCEs are intractable, even in the centralized model, and rule out the existence of any efficient learning dynamics. This significantly strengthens the impossibility result of Hartline, Wang, and Zhang, which concerns a particular class of learning algorithms, and furnishes strong computational critiques of recent regulation on algorithmic collusion. To sidestep these hardness results, we examine the complexity of information-value-free CCE. Certain no-regret algorithms---such as regret matching or FTRL---provide a fully polynomial-time approximation scheme (FPTAS) for this problem. The complexity when the approximation is exponentially small turns out to be nuanced. On the one hand, leveraging no-regret dynamics, we establish membership in $\text{CLS} = \text{PPAD} \cap \text{PLS}$. On the other hand, we show that it is at least as hard as the P-matrix linear complementarity problem, and hence as hard as simple stochastic games. This shows that even IVFCCEs are unlikely to admit a polynomial-time algorithm barring a major breakthrough.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2609.22757v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.