진실만 말하는 ‘시설 배치 알고리즘’의 탄생

-

 

공평하게 분배된 공공시설을 나타내는 상징적인 그림 — 지도 위에 사람들이 흩어져 있고, 용량이 정해진 여러 시설이 균형 있게 배치된 모습, 각 시설 주변에 반투명한 서비스 범위가 그려진, 현대적이고 미니멀한 스타일



— AI가 만든, 거짓말을 못하는 도시 설계법


“도시 한복판에 공공시설을 지어야 한다면, 어디에 놓는 게 가장 공평할까?”
이 단순해 보이는 질문이 사실은 수학, 경제학, 그리고 인공지능까지 얽힌 난제다. 사람들이 자기 이익을 위해 위치 정보를 살짝 속인다면, 아무리 훌륭한 계획도 무너질 수 있기 때문이다.

이 문제를 정면으로 파고든 연구가 최근 발표됐다. 제목은 다소 길다 — 〈역량이 있는 시설 위치 문제에 대한 진실성 있는 메커니즘 설계: 시설이 두 개 이상일 경우(On the design of truthful mechanisms for the capacitated facility location problem with two and more facilities)〉. 이탈리아 파두아 대학, 중국 인민대, 영국 바스 대학의 연구진이 함께한 이 논문은 ‘정직함’을 보장하는 새로운 알고리즘 설계를 제시한다.


시설 배치 문제, 그런데 ‘수용 인원 제한’까지?

일반적으로 ‘시설 배치 문제’(Facility Location Problem, FLP)는 사람들의 위치를 바탕으로 m개의 시설을 어디에 둘지를 정하는 수학적 퍼즐이다. 병원, 도서관, 물류센터처럼 최대한 많은 사람을 가깝게 서비스하는 게 목표다.
그런데 현실은 단순하지 않다. 시설마다 수용 가능한 인원이 정해져 있다. 병원 병상이 100개뿐이거나, 서버 용량이 한정돼 있는 경우다. 이를 **수용 인원 제한 시설 배치 문제(m-CFLP)**라 부른다.

이 연구는 특히 두 가지 상황에 집중했다.

  1. 모든 시설이 동일한 수용 인원(k명)을 가지고, 전체 인원(n명)이 딱 맞아떨어지는 경우
    • 예: 3개의 진료소, 각 10명 수용, 환자 수 30명.
  2. 시설이 두 개뿐인데, 각 시설이 절반 이상 인원을 수용할 수 있는 경우
    • 예: 두 개의 물류창고가 각각 최소 전체 주문량의 절반을 처리 가능.


거짓말을 원천 차단하는 알고리즘

문제의 핵심은 ‘진실성’(truthfulness)이다. 각 사람이 자신의 위치를 솔직하게 말하게 만들 방법이 필요하다. 만약 누군가 “사실은 집이 좀 더 먼 곳에 있다”고 거짓말을 해서 시설을 자기 집 앞으로 끌어올 수 있다면? 전체 효율이 깨지고, 공정성도 무너진다.

연구진은 이를 해결하기 위해 두 가지 새로운 메커니즘을 제안했다.

1. 전파 중앙값 메커니즘(PMM, Propagating Median Mechanism)

중앙값을 중심으로 시설 위치를 정하고, 이를 양쪽으로 ‘전파’하며 배치하는 방식이다.

  • 장점: 최대 이동 거리(최대 비용, MC) 측면에서 ‘완벽’에 가깝다.
  • 단점: 일부 경우 사회 전체 이동 거리(사회적 비용, SC)가 조금 더 늘어날 수 있다.

2. 전파 내부점 메커니즘(PIPM, Propagating InnerPoint Mechanism)

중앙값 대신, 중간 구간의 ‘양 끝점’을 먼저 정하고 나머지를 채워나간다.

  • 장점: 경우에 따라 사회적 비용이 더 낮다.
  • 특징: 최대 비용은 PMM과 동일하게 억제.

두 방법 모두 거짓말을 통한 이득이 불가능하도록 설계됐다. 연구진이 수학적으로 증명한 결과, 어떤 개인도 위치를 속여서 본인에게 더 유리한 시설 배치를 만들 수 없다.


왜 이런 게 중요한가?

기존의 무제한 수용 시설 배치 문제(m-FLP)에서는 m이 2개를 초과하면 ‘진실성·익명성·결정론’을 동시에 만족하는 메커니즘이 불가능하다는 게 알려져 있었다. 그런데 이번 연구는 수용 인원 제한이 오히려 이 불가능성을 깨뜨릴 수 있다는 걸 보여줬다.

즉, 병원·학교·서버처럼 ‘용량’이 있는 현실적 상황에서는, 전략적 거짓말을 막으면서도 효율적인 배치가 가능하다는 얘기다.



성능 검증 — 숫자가 말한다

연구진은 ‘사회적 비용’과 ‘최대 비용’이라는 두 가지 지표를 기준으로 알고리즘 성능을 평가했다.

  • PMM: 최대 비용 측면에서 완벽(비율 2), 사회적 비용은 m과 k에 따라 예측 가능한 범위에서 증가.
  • PIPM: 최대 비용은 동일하게 2, 사회적 비용은 상황에 따라 더 낮을 수 있음.

또한 두 알고리즘은 기존 방식보다 시설 수가 많아질수록 성능이 좋아지는 드문 특징을 보였다. 반대로 기존 메커니즘들은 시설이 많아질수록 성능이 떨어졌다.

결론 — 공정한 배치는 가능하다

이번 연구는 단순히 수학 퍼즐을 푼 게 아니다.

  • 재난 구호: 임시 대피소 위치 결정
  • 물류·배송: 한정된 허브 창고 배치
  • IT 인프라: 서버·네트워크 자원 배치
    이 모든 분야에서, ‘누가 더 가까운가’라는 민감한 이해관계를 거짓말 없이 다룰 수 있는 방법을 제시한 것이다.

연구진의 말처럼, 이번 결과는 **“진실성을 보장하면서도 효율적인 사회적 선택이 가능하다”**는 희망을 보여준다. 앞으로 이 알고리즘들이 실제 도시 설계나 네트워크 운영에 도입된다면, 우리는 조금 더 공정하고 효율적인 사회를 만들 수 있을지 모른다.


출처
Auricchio, G., Wang, Z., & Zhang, J. (2025). On the design of truthful mechanisms for the capacitated facility location problem with two and more facilities. Artificial Intelligence, 348, 104390. https://doi.org/10.1016/j.artint.2025.104390