완전경쟁 시장은 P≠NP일 때만 가능하다: 계산복잡도가 밝힌 AI 담합의 필연성

경제학 교과서 첫 페이지는 언제나 “완전경쟁 시장"으로 시작합니다. 수많은 판매자가 서로 경쟁하며 가격이 자연스럽게 최적점을 찾아간다는 그 아름다운 그림 말입니다. 그런데 최근 컴퓨터과학과 경제학의 경계에서 흥미로운 주장이 흘러나오고 있습니다. 이 완벽한 균형이 사실은 “계산적으로 너무 어려워서” 유지된다는 겁니다. 그리고 AI가 그 어려움을 풀어버리는 순간, 시장은 조용히 담합으로 미끄러진다는 이야기입니다.

솔직히 처음 들으면 무슨 소린가 싶습니다. P vs NP 같은 난해한 수학 문제가 시장의 가격표와 무슨 상관이란 말일까요. 오늘은 이 연결고리를 하나씩 풀어보겠습니다.

P vs NP, 5분만에 감 잡기

먼저 P vs NP가 뭔지 짚고 넘어가야 합니다. 이건 컴퓨터과학 60년 역사에서 가장 유명한 미해결 문제입니다.

아주 거칠게 설명하면 이렇습니다. 어떤 문제는 답을 빠르게 찾을 수 있습니다. 이런 문제를 P라고 부릅니다. 또 어떤 문제는 답을 찾기는 어렵지만, 누가 답을 알려주면 그게 맞는지 빠르게 확인할 수는 있습니다. 이런 문제를 NP라고 부릅니다.

예를 들어볼까요. 거대한 스도쿠 퍼즐을 푸는 건 오래 걸립니다. 하지만 다 채워진 스도쿠가 규칙에 맞는지 검사하는 건 순식간입니다. 답을 찾는 건 어려운데, 확인하는 건 쉽죠. 이게 바로 NP의 전형입니다.

P vs NP 질문은 단순합니다. “확인이 쉬운 문제는 사실 찾기도 쉬운 것 아닐까?” 만약 P=NP라면, 세상의 거의 모든 어려운 문제가 갑자기 쉬워집니다. 암호도 뚫리고, 최적화도 즉시 풀립니다. 반대로 P≠NP라면, 어떤 문제들은 본질적으로 계산이 오래 걸릴 수밖에 없습니다. 대부분의 학자는 P≠NP 쪽에 걸고 있습니다.

시장은 사실 거대한 계산기입니다

여기서 경제학이 등장합니다. 시장이 균형 가격을 찾는 과정을, 컴퓨터가 문제를 푸는 과정으로 바라보면 시야가 완전히 달라집니다.

경제학자 하이에크는 오래전에 시장을 “정보 처리 장치"라고 불렀습니다. 수백만 명의 소비자와 판매자가 각자 아는 정보를 가격이라는 신호 하나로 압축한다는 거죠. 이 관점을 계산복잡도 이론으로 밀고 나가면, 시장 균형을 찾는 일 자체가 하나의 계산 문제가 됩니다.

문제는 이 계산이 종종 지독하게 어렵다는 겁니다. 실제로 일반적인 시장 균형을 찾는 문제는 NP만큼, 혹은 그보다 더 어려운 계산 난이도를 가진다는 연구들이 쌓여 있습니다. 여러 상품이 얽히고, 참여자들의 선호가 복잡하게 엮이면, 진짜 최적 가격을 계산하는 건 사실상 불가능에 가깝습니다.

그런데 잠깐, 이게 나쁜 소식일까요. 흥미롭게도 이 “계산의 어려움"이야말로 경쟁을 지켜주는 방패였을지도 모릅니다.

담합이 어려운 진짜 이유

담합을 떠올려 봅시다. 여러 회사가 몰래 가격을 높게 유지하기로 짜는 겁니다. 소비자에겐 최악이고, 회사엔 꿀입니다.

담합이 성공하려면 몇 가지가 필요합니다. 상대가 언제 배신할지 감시해야 하고, 최적의 담합 가격을 계산해야 하고, 시장 변화에 맞춰 계속 조율해야 합니다. 이게 전부 엄청난 계산과 정보 공유를 요구합니다.

인간이 운영하던 시절엔 이게 자연스러운 장벽이었습니다. 사람이 모여 가격을 짜면 증거가 남고, 계산도 느리고, 배신자를 실시간으로 잡아낼 수도 없었습니다. 그래서 대부분의 시장은 담합이 “귀찮고 어려워서” 어느 정도 경쟁을 유지했습니다.

여기서 도발적인 명제가 나옵니다. “완전경쟁 시장은 P≠NP일 때만 가능하다.” 다시 말해, 담합에 필요한 계산이 본질적으로 어렵기 때문에 시장이 경쟁 상태로 남는다는 겁니다. 만약 그 계산이 쉬워진다면, 경쟁을 유지하던 마찰이 사라지고 담합이 기본값이 됩니다.

AI가 마찰을 지워버릴 때

이제 불편한 부분입니다. AI 가격 책정 알고리즘이 바로 그 “계산의 어려움"을 녹여버리고 있습니다.

이미 현실에서 벌어지는 일입니다. 여러 회사가 같은 AI 가격 책정 소프트웨어를 쓰면, 서로 전화 한 통 하지 않아도 가격이 나란히 올라갑니다. 알고리즘이 시장 데이터를 실시간으로 읽고, 경쟁사의 반응을 학습하고, “지금 가격을 내리면 결국 우리 둘 다 손해"라는 결론에 스스로 도달하기 때문입니다. 명시적으로 짜지 않았는데 결과는 담합과 똑같습니다. 학계에서는 이걸 알고리즘 담합이라고 부릅니다.

핵심은 이겁니다. 예전엔 담합에 필요한 감시와 조율이 인간에겐 너무 비싼 계산이었습니다. AI에겐 아닙니다. 강화학습 알고리즘들은 서로를 감시하고 응징하는 전략을, 아무도 프로그래밍하지 않았는데 실험 환경에서 스스로 찾아냅니다. 계산의 벽이 무너진 겁니다.

미국 부동산 임대료 책정 소프트웨어를 둘러싼 소송, 여러 나라 규제 당국이 AI 가격 담합을 들여다보기 시작한 흐름이 이 우려가 이론에만 머물지 않는다는 걸 보여줍니다.

그래서 우리는 무엇을 걱정해야 할까요

한 가지 짚고 넘어가겠습니다. 최근 30일 기준으로 이 주제를 정면으로 다룬 커뮤니티 논의는 많지 않았습니다. 아직 대중적으로 뜨겁게 회자되는 이슈라기보다, 소수의 연구자와 규제 당국이 조용히 씨름하는 영역에 가깝습니다. 그래서 오히려 지금 알아둘 가치가 있다고 생각합니다.

정리하면 이렇습니다. 우리가 당연하게 여기던 시장 경쟁은, 어쩌면 담합이 계산적으로 너무 어려웠던 덕분에 유지된 우연이었을 수 있습니다. AI는 그 난이도를 빠르게 낮추고 있습니다. 법은 “명시적 합의"를 담합으로 처벌하지만, 알고리즘은 합의 없이 담합의 결과만 만들어냅니다. 기존 경쟁법이 이 틈을 어떻게 메울지가 앞으로의 진짜 숙제입니다.

여러분에게 질문을 하나 던지고 싶습니다. 아무도 짜지 않았지만 모두가 손해를 보는 가격이 만들어졌을 때, 우리는 누구에게 책임을 물어야 할까요. 알고리즘일까요, 그걸 도입한 회사일까요, 아니면 그런 결과를 예견하지 못한 우리 모두일까요.