단일 편차를 넘어선 균형 계산

Computing Equilibrium beyond Unilateral Deviation

대부분의 잘 알려진 균형 개념, 예를 들어 내쉬 균형 및 상관된 균형은, 단일 플레이어가 일방적으로 전략을 변경함으로써 자신의 효용을 향상시킬 수 없다는 것을 보장합니다. 하지만 이러한 개념은, 연합이 이루는 협력적인 전략 변경에 의한 이익 가능성에 대한 보장을 제공하지 않습니다. 문헌에서는 다자간 편차에 대한 안정성을 제공하는 해법 개념(예: 강한 내쉬 균형 및 연합 증명 균형)이 제안되지만, 이러한 해법은 일반적으로 존재하지 않습니다. 본 논문에서는, 연합의 편차 유인을 완전히 없애는 대신, 연합의 편차 유인을 최소화하는 대안적인 해법 개념을 연구합니다. 이 해법은 존재성이 보장됩니다. 구체적으로, 우리는 편차 연합의 평균적인 이득을 최소화하는 데 초점을 맞추고, 가중 평균 및 연합 내 최대 이득으로 프레임워크를 확장합니다. 반대로, 최소 이득에 해당하는 유사한 개념은 계산적으로 해결하기 어렵다는 것이 밝혀졌습니다. 평균 이득 및 최대 이득 목표에 대해, 이러한 균형을 계산하는 복잡성에 대한 하한을 증명하고, 이 하한에 부합하는 알고리즘을 제시합니다. 마지막으로, 우리는 본 프레임워크를 사용하여 'Exploitability Welfare Frontier' (EWF)를 해결합니다. EWF는 주어진 exploitability (모든 일방적인 편차에 대한 최대 이익) 하에서 달성 가능한 최대 사회 복지입니다.

Most familiar equilibrium concepts, such as Nash and correlated equilibrium, guarantee only that no single player can improve their utility by deviating unilaterally. They offer no guarantees against profitable coordinated deviations by coalitions. Although the literature proposes solution concepts that provide stability against multilateral deviations (\emph{e.g.}, strong Nash and coalition-proof equilibrium), these generally fail to exist. In this paper, we study an alternative solution concept that minimizes coalitional deviation incentives, rather than requiring them to vanish, and is therefore guaranteed to exist. Specifically, we focus on minimizing the average gain of a deviating coalition, and extend the framework to weighted-average and maximum-within-coalition gains. In contrast, the minimum-gain analogue is shown to be computationally intractable. For the average-gain and maximum-gain objectives, we prove a lower bound on the complexity of computing such an equilibrium and present an algorithm that matches this bound. Finally, we use our framework to solve the \emph{Exploitability Welfare Frontier} (EWF), the maximum attainable social welfare subject to a given exploitability (the maximum gain over all unilateral deviations).