스포츠 경기, 돈이면 결과 바꿀 수 있을까?

월드컵, 올림픽, 리그전… 공정해야 할 스포츠 경기에도 ‘은밀한 거래’가 숨겨져 있을 수 있다. 특히 ‘도전자 챔프(Challenge the Champ)’ 같은 단순한 토너먼트에서는 한 번 이긴 선수가 챔프가 되고, 또 다음 도전자를 맞이한다. 그런데 여기서 챔프가 계속 승리하도록 다른 선수들을 몰래 매수한다면?

이번 논문은 바로 이런 ‘챔프 유지 뇌물 문제(CBCCT)’를 수학적으로 다뤘다. 누구를 얼마에 매수해야 예산 한도 안에서 원하는 확률로 챔프가 살아남을 수 있을까? 현실 같지만, 사실 복잡한 계산 문제다.

문제는 간단한데 계산은 어렵다

이론적으로는 쉽다. 각 선수는 ‘얼마를 받으면 질 확률이 얼마나 높아진다’는 뇌물 벡터를 갖고 있다. 챔프는 이들을 한 명씩 상대한다. 전체 경기에서 챔프가 이길 확률이 목표치 이상이 되도록 뇌물을 적절히 배분하는 게 문제의 핵심이다.

놀라운 건, 이게 간단한 것 같아도 약한 NP-난해(Weakly NP-hard) 문제라는 사실이다. 게다가 선수 수를 변수로 보면 W[1]-난해(W[1]-hard)라서 단순한 고속 알고리즘으로는 풀기 어렵다.

그래도 방법은 있다

희망적인 소식도 있다. 연구진은 ‘선수 수’ 대신 ‘뇌물 가격 종류’나 ‘확률 종류’를 변수로 삼으면 문제를 더 쉽게 풀 수 있다는 걸 증명했다. 실제로 뇌물 가격은 몇 가지로 한정되기 마련이고, 확률도 대략적인 예측치이기 때문에 가능한 얘기다.

이를 위해 연구팀은 혼합 정수 선형계획(MILP) 기법을 활용했다. 변수 일부는 정수로 제한하고 나머지는 연속 값으로 풀어, 깔끔한 최적해를 뽑아내는 것이다.

알고리즘만 쓸모 있나? 선거 캠페인에도!

흥미로운 건 이 연구가 스포츠에만 그치지 않는다는 점이다. 논문에서는 ‘챔프’를 정치 후보로, 도전자들을 유권자로 바꿔 보면 선거 캠프의 전략 모델링에도 활용 가능하다고 설명한다. 유권자에게 어떤 메시지를 전달하고 얼마를 써야 이길 확률을 높일 수 있을지 계산할 수 있다는 것!

수학으로 드러난 조작의 기술

스포츠 경기의 공정성은 늘 도전받는다. 이번 연구는 이를 기계적으로 풀어내면서 동시에 더 정교한 조작 방지 정책과 공정한 운영 방식을 고민할 근거를 제공한다.

‘도전자 챔프’는 게임만이 아니라 세상 모든 경쟁의 은유다. 그 뒤를 지키는 건 결국 돈일까, 규칙일까?

출처 논문
Juhi Chaudhary, Hendrik Molter, Meirav Zehavi. (2025). Parameterized Analysis of Bribery in Challenge the Champ Tournaments. Journal of Artificial Intelligence Research, 83, Article 7. https://doi.org/10.1613/jair.1.17239