최근 발표된 연구 논문은 시장의 경쟁적 특성이 컴퓨터 과학의 난제인 P 대 NP(P vs NP) 문제와 밀접하게 연결되어 있다는 흥미로운 주장을 제기했습니다. 이 논문에 따르면, 시장이 진정으로 경쟁적이기 위해서는 P와 NP가 같지 않아야 합니다. 즉, 특정 복잡한 계산 문제를 효율적으로 풀 수 없어야만 시장 내 담합이 불안정해지고 경쟁이 유지된다는 것입니다.
필립 Z. 메이민(Philip Z. Maymin) 교수의 이 연구는 만약 P=NP라면, 기업들이 복잡하고 노이즈가 많은 시장에서 담합 합의로부터의 이탈을 효율적으로 탐지할 수 있게 되어 담합이 지속 가능한 균형 상태가 될 것이라고 설명합니다. 반대로 P!=NP라면, 담합 탐지 문제는 계산적으로 불가능해져 담합을 위한 처벌 위협이 신뢰성을 잃고 담합 자체가 불안정해진다는 논리입니다. 이는 기업의 계산 능력이 향상될수록 시장이 경쟁 체제에서 담합 체제로 이동할 수 있음을 시사하며, 최근 알고리즘 담합(algorithmic collusion)의 등장을 설명하는 이론적 배경이 될 수 있습니다.
이 연구는 메이민 교수의 2011년 연구, 즉 시장 효율성이 P=NP를 요구한다는 주장과 결합될 때 더욱 중요한 의미를 갖습니다. 두 연구를 종합하면, 시장은 정보 효율적이거나 경쟁적일 수는 있지만, 동시에 둘 다일 수는 없다는 근본적인 불가능성(impossibility)에 직면하게 됩니다. 인공지능(AI)의 발전은 기업의 계산 능력을 확장하여 시장을 경쟁적 영역에서 담합적 영역으로 밀어붙이고 있으며, 이는 시장의 미래 구조와 규제 방향에 대한 심도 깊은 논의를 촉발할 것으로 예상됩니다.