단일 편향 너머의 균형 계산

나시 균형과 상관 균형과 같은 가장 익숙한 균형 개념들은, 단일 플레이어가 편향(unilateral deviation)하여도 효용을 개선할 수 없음을 보장할 뿐입니다. 이들은 연합(coalition)에 의한 수익성 있는 조정된 편향(coordinated deviations)에 대해서는 어떠한 보장을 제공하지 않습니다. 문헌에서는 다자간 편향(multilateral deviations)에 대한 안정성을 제공하는 해법 개념( extit{e.g.}, 강한 나시 균형과 연합-증명 가능한 균형(coalition-proof equilibrium))을 제안하지만, 이러한 개념들은 일반적으로 존재하지 않습니다. 본 논문에서는 이를 대체하는 해법 개념을 연구합니다. 이 개념은 편향 동기를 소멸시키도록 요구하는 대신 이를 최소화함으로써 존재함이 보장됩니다. 구체적으로, 우리는 편향 연합의 평균 이익(average gain)을 최소화하는 데 초점을 맞추고, 이를 가중 평균(gweighted-average) 및 연합 내 최대 이익(maximum-within-coalition gains)으로 확장합니다. 반면, 최소 이익(minimum-gain)에 대한 유사체는 계산상 비실현 가능(computationally intractable)함이 입증되었습니다. 평균 이익과 최대 이익 목표에 대해, 우리는 이러한 균형을 계산하는 복잡도에 대한 하한(lower bound)을 증명하고, 이 한계와 일치하는 알고리즘을 제시합니다. 마지막으로, 우리는 본 프레임워크를 extit{Exploitability Welfare Frontier}(EWF) 해결에 활용합니다. 이는 주어진 취약성(exploitability, 즉 모든 단일 편향에 대한 최대 이익) 하에서 달성 가능한 최대 사회적 후생입니다.