Auditing Algorithmic Collusion from Strategy Graphs

당신이 고도의 긴장감이 흐르는 체스 경기를 지켜보고 있다고 상상해 보십시오. 하지만 선수들은 인간이 아니라, 시행착오를 통해 체스를 배우는 초고속 컴퓨터 프로그램입니다. 이것이 바로 기업들이 가스비부터 아파트 임대료에 이르기까지 모든 것에 대해 인공지능이 가격을 결정하게 만드는 **알고리즘 가격 책정(algorithmic pricing)**의 세계입니다. 때때로 이 프로그램들은 우연히 비밀스러운 악수를 학습하곤 합니다. 즉, 서로 대화하지 않더라도 모두가 높은 가격을 유지하기만 하면 모두가 더 많은 돈을 벌 수 있다는 사실을 깨닫는 것입니다. 이것을 **알고리즘 담합(algorithmic collusion)**이라고 부릅니다. 이는 규제 기관들에게 악몽과도 같은 일인데, 왜냐하면 적발하기가 매우 어렵기 때문입니다. 보통 두 사람이 반경쟁적 행위에 가담하고 있음을 증명하려면, 구석에서 속삭이는 것을 보거나 적힌 쪽지를 찾아내야 합니다. 하지만 컴퓨터의 경우, 속삭임도 없고, 그 "쪽지"들은 기업들이 일급 비밀 레시피로 취급하는 수백만 줄의 코드 속에 파묻혀 있습니다.

그렇다면 상대의 일기를 읽거나 전화 통화를 도청할 수 없다면, 어떻게 부정행위자를 잡을 수 있을까요? 당신은 그들의 결정이 그려내는 지도를 보아야 합니다. 가격 책정 알고리즘을 뇌가 아니라 하나의 미로라고 생각해 보십시오. 컴퓨터가 특정 상황(예: "어제의 가격이 높았다")을 마주할 때마다, 다음에 무엇을 할지에 대한 규칙을 갖게 됩니다. 만약 모든 상황으로부터 다음 단계로 컴퓨터가 선택한 경로를 선으로 잇는다면, 거대하고 뒤엉킨 경로의 그물이 나타날 것입니다. 공정한 경쟁 게임에서 이 그물은 보통 최저가로 향하는 무질서하고 직접적인 경로를 보여줍니다. 하지만 컴퓨터들이 담합하고 있다면, 이 그물의 모습은 달라집니다. 여기에는 특정한 "병목 지점"과, 규칙을 깨려는 자를 응징하기 위해 설계된 길고 구불구불한 루프가 존재합니다. 이 논문은 다음과 같이 질문합니다. 가격도, 이윤도, 심지어 코드조차 모르는 상태에서, 단지 이 미로의 형태를 보는 것만으로 비밀스러운 공모를 포착할 수 있을까?

이 논문의 저자인 니콜라스 에셴바움(Nicolas Eschenbaum)과 야누시 M. 메일란(Janusz M. Meylahn)은 그렇다고 말합니다. 그들은 내부를 들여다볼 필요가 없는 새로운 알고리즘 감사 방식을 제안합니다. 대신, 비밀 코드를 요구하거나 훈련 데이터를 요구하는 대신, 규제 기관이 알고리즘에게 단순히 이렇게 묻는 방식을 제안합니다. "만약 당신이 이 특정 상황에 처한다면, 무엇을 하겠습니까?" 가능한 모든 시나리오에 대해 이 질문을 던짐으로써, 그들은 "전략 그래프(strategy graph)", 즉 미로의 지도를 구축할 수 있습니다.

연구진은 담합 알고리즘이 이 지도 위에 매우 구체적인 지문을 남긴다는 사실을 발견했습니다. 그들은 알고리즘들이 높은 가격을 유지하기 위해 협력할 때, 결정 미로에 강력한 병목 현상이 발생한다는 것을 발견했습니다. 어디에서든 집으로 돌아가기 위해 반드시 하나의 좁은 다리를 지나야만 하는 도시를 상상해 보십시오. 만약 지름길을 택하려 한다면, 그 다리를 건너기 전에 교통 체증(응징 단계)에 갇히게 됩니다. 경쟁적인 시장에서는 많은 다리와 지름길이 있어 어디서든 빠르게 집에 갈 수 있습니다. 하지만 담합하는 시장에서는, 거의 모든 경로가 높은 가격대로 돌아가기 전에 특정 "응징 상태"를 거치도록 지도가 조작되어 있습니다.

이를 증명하기 위해 팀은 수천 번의 시뮬레이션을 실행했습니다. 그들은 두 개의 컴퓨터 프로그램이 가격을 설정하는 법을 배우는 단순한 세계를 만들었습니다. 그들은 두 가지 다른 학습 방법을 테스트했습니다. 하나는 프로그램들이 함께 학습하는 방식(유명한 "칼라보(Calvano)" 방식과 같은 방식)이고, 다른 하나는 개별적으로 학습하는 방식(분산 Q-러닝)입니다. 또한, 별도로 훈련된 두 프로그램을 가져와 강제로 서로 맞붙게 하여 담합을 깨뜨리는 시나리오도 테스트했습니다.

결과는 놀라웠습니다. 연구진은 미로의 세 가지 주요 특징을 측정했습니다:

1. 최대 매개 중심성(Maximum Betweenness): 이는 얼마나 많은 경로가 단일 "병목 지점"을 통과하는지를 측정합니다. 시뮬레이션 결과, 알고리즘이 더 많이 담합할수록 더 많은 경로가 단일 응징 상태를 통과하도록 강제되었습니다. 이 상관관계는 강력했으며, 주요 테스트에서 0.67의 점수를 기록했습니다.
2. 끌개 유입 차수(Attractor In-degree): 이는 "행복한 장소"(높은 가격 루프)로 직접 연결되는 경로의 수를 셉니다. 담합하는 미로에서는 직접 연결되는 경로가 매우 적으며, 대부분은 응징 단계를 거쳐 멀리 돌아와야 합니다. 이 지표는 -0.67의 강한 음의 상관관계를 보였습니다(즉, 담합이 심해질수록 직접적인 경로는 줄어듭니다).
3. 평균 경로 길이(Average Path Length): 이는 실수를 저지른 후 높은 가격 루프로 돌아오는 데 몇 단계가 걸리는지를 측정합니다. 담합하는 미로는 (용서하기 전에 응징 단계를 강요하기 때문에) 더 긴 경로를 가졌습니다(이론적 모델에서 평균 1.96 단계).

저자들은 이 방법이 범죄를 즉각 입증하는 마법의 탄환은 아니라는 점을 주의 깊게 언급합니다. 그들은 이러한 "그래프 지표"가 알고리즘이 단순히 영원히 포기하는 것(그림 트리거 전략)이 아니라, 응징 후에 다시 협력하는 법을 배웠을 때 가장 잘 작동한다는 것을 발견했습니다. 또한 실제 세상의 알고리즘은 무작위 선택이나 연속적인 업데이트를 사용하여 지도가 더 흐릿해질 수 있다는 점도 인정합니다. 그러나 그들의 시뮬레이션은 의사 결정 과정의 형태가 견고한 신호임을 시사합니다.

이 접근 방식의 묘미는 매우 적은 정보만을 필요로 한다는 점입니다. 규제 기관은 회사의 비밀 코드, 판매 데이터, 또는 이윤 폭을 알 필요가 없습니다. 그저 알고리즘이 현재 따르고 있는 고정된 정책(정책의 집합)을 질의하고 미로의 선들을 추적할 수 있으면 됩니다. 만약 지도가 높은 가격 클럽으로 다시 들어가기 전에 당신을 응징 루프에 가두도록 설계된 좁은 다리 하나를 보여준다면, 그것은 알고리즘이 담합하고 있을지도 모른다는 거대한 경고 신호입니다. 이는 성 안에 숨겨진 비밀 통로를 찾는 것과 같습니다. 그 통로를 누가 왜 만들었는지 알 필요는 없지만, 그 통로의 존재 자체가 무언가 수상한 일이 일어나고 있음을 알려주는 것입니다.

요컨대, 이 논문은 우리가 알고리즘의 마음을 항상 읽을 수는 없을지라도, 그들의 지도는 읽을 수 있다고 제안합니다. 그리고 만약 그 지도가 당신을 높은 가격 클럽으로 돌려보내기 전 응징 루프에 가두기 위해 설계된 미로처럼 보인다면, 규제 기관이 더 면밀히 살펴봐야 할 때입니다.