똑똑한 질문 몇 개로 모두가 만족하는 최고의 짝을 찾아주는 방법

이 논문을 주목해야하는 이유

반 친구들에게 청소 구역을 나눠주거나, 회사에서 팀원들에게 프로젝트를 맡길 때처럼 누군가에게 무언가를 나눠주는 일은 아주 흔합니다. 이때 모든 사람을 최대한 만족시키는 것이 중요합니다. 하지만 한 사람 한 사람에게 모든 것에 대해 얼마나 좋은지 일일이 물어보는 것은 너무 시간이 많이 걸립니다.

이 논문은 모든 것을 다 물어보지 않고, 각 사람에게 아주 적은 수의 질문만 던져서 거의 완벽에 가까운 최선의 결과를 찾아내는 놀라운 방법을 제안합니다. 이 기술을 사용하면 시간과 노력을 아끼면서도 훨씬 더 공정하고 효율적인 결정을 내릴 수 있어, 우리 생활과 사회를 더 좋게 만드는 데 큰 도움이 될 것입니다.

연구 배경

n명의 사람에게 n개의 물건을 하나씩 짝지어줘야 하는 상황을 생각해 봅시다. 가장 좋은 방법은 각자 어떤 것을 가장 좋아하고, 또 얼마나 좋아하는지 정확한 점수를 매겨달라고 하는 것입니다. 하지만 "이 일은 87점만큼 좋고, 저 일은 53점만큼 좋아요"처럼 모든 것에 점수를 매기는 것은 귀찮고 어렵습니다.

그래서 보통은 "어떤 걸 제일 좋아해요? 그다음은요?"처럼 선호하는 순서만 물어봅니다. 이것을 '순위' 정보라고 합니다. 순서만 물어보면 훨씬 간단하지만, 큰 문제가 있습니다. 1순위를 얼마나 간절히 원하는지, 2순위와 차이가 얼마나 큰지를 알 수 없다는 점입니다. 이렇게 정보가 부족한 상태에서 결정을 내리면, 모두의 만족도를 합친 결과가 최선이 아닐 수 있습니다. 과학자들은 이 최선과의 차이를 '왜곡'이라고 부릅니다. 이 연구는 '왜곡'을 최소화하기 위해 아주 적은 질문만으로 점수 정보를 얻어내는 방법을 찾기 위해 시작되었습니다.

쉽게 이해하기

이 논문은 간단한 '순위' 정보에 더해, 몇 가지 핵심적인 '점수' 질문을 추가하면 결과가 훨씬 좋아진다는 것을 보여줍니다.

예를 들어 100명의 학생에게 100개의 좌석을 배정한다고 상상해 봅시다.

기존 방식 : 모든 학생에게 100개의 자리를 전부 마음에 드는 순서대로 적어 내라고 합니다. 이것만으로는 누가 특정 자리를 얼마나 더 간절히 원하는지 알 수 없어 최적의 배정을 하기 어렵고, '왜곡'이 커집니다.
새로운 방식 : 순위를 적어 내는 것은 똑같지만, 여기에 몇 가지 질문을 추가합니다. 예를 들어, 각 학생에게 딱 두 가지만 더 물어보는 겁니다.

질문 1: "네가 1순위로 뽑은 자리는 100점 만점에 몇 점짜리 행복을 주니?"
질문 2: "선생님이 임의로 정한 '창가 3번째 자리'는 너에게 몇 점짜리 행복을 주니?"

놀랍게도, 이렇게 딱 두 개의 점수 질문만 추가해도 '왜곡' 수치가 크게 줄어들어 훨씬 더 공정한 결과를 만들 수 있다는 것을 이전 연구에서 발견했습니다. 이 논문은 여기서 한 걸음 더 나아갑니다. 만약 질문을 두 개가 아니라 세 개, 네 개로 늘리면 '왜곡'이 얼마나 더 줄어드는지에 대한 완벽한 공식을 만들어냈습니다. 더 많이 질문할수록 결과는 점점 더 완벽에 가까워집니다.

핵심 정리

목표: n명의 사람과 n개의 대상을 짝지을 때, 모두의 만족도를 합친 총합이 가장 커지도록 만드는 것.
기존 방식의 문제: 좋아하는 '순서'만 물어보면, '얼마나' 좋아하는지 알 수 없어 최선의 결정을 내리기 어렵다.
해결책: 순위 정보에 더해, 각 사람에게 몇 가지 '점수'를 묻는 질문을 추가한다.
핵심 발견: 점수를 묻는 질문의 개수를 늘릴수록 '왜곡'은 n의 1/λ 제곱만큼 획기적으로 줄어든다.
최적의 방법: 이 논문이 제시한 방법은 주어진 질문 개수 내에서 '왜곡'을 줄일 수 있는 거의 가장 좋은 방법이라는 것이 수학적으로 증명되었다.

깊게 이해하기

이 연구의 핵심은 '순위' 정보와 '기수 효용' 정보의 차이를 활용하는 것입니다. '순위'는 선호도의 순서만을 나타내지만, '기수 효용'은 선호도의 강도를 나타내는 구체적인 숫자입니다.

이 논문의 가장 중요한 기여는 질문의 개수와 왜곡 사이의 관계를 일반화된 공식 O으로 밝혔다는 점입니다. 여기서 n은 사람 또는 대상의 수입니다. 이 공식이 얼마나 강력한지 예를 들어 보겠습니다. 1,000명의 사람이 있다면:

질문을 2개 하면, 왜곡은 √1000, 즉 약 32 수준으로 줄어듭니다.
질문을 3개 하면, 왜곡은 ³√1000, 즉 10 수준으로 훨씬 더 많이 줄어듭니다.
질문을 10개 하면, 왜곡은 ¹⁰√1000, 즉 약 2 수준으로 엄청나게 줄어듭니다.

즉, 질문을 하나씩 추가할 때마다 결과가 얼마나 더 좋아지는지를 정확히 예측할 수 있게 된 것입니다. 또한 연구팀은 이 방법이 단순히 사람과 물건을 1:1로 짝짓는 문제뿐만 아니라, 여러 사람의 의견을 모아 단 하나의 선택지를 고르는 더 일반적인 '사회적 선택' 문제에도 확장될 수 있음을 보여주었습니다.

연구의 중요성과 차별점

이전 연구들이 "질문 두 개를 더하면 좋아진다"는 것을 보여줬다면, 이 연구는 "질문을 λ개 더하면 정확히 이만큼 좋아진다"는 일반적인 법칙을 발견했다는 점에서 매우 중요합니다. 이것은 마치 자전거를 발명한 것을 넘어, 기어를 바꾸면 속도가 얼마나 빨라지는지에 대한 원리를 완벽하게 설명해낸 것과 같습니다.

이 연구는 시스템 설계자에게 아주 실용적인 지침을 줍니다. "시간이 부족하면 1인당 2개의 질문만 하고 이 정도의 결과에 만족해라", "만약 더 완벽한 결과가 필요하다면, 1인당 4개의 질문을 해야 한다"와 같이 상황에 맞춰 질문의 개수와 결과의 질 사이에서 최적의 균형점을 찾을 수 있게 해줍니다.

연구의 활용 가능성

이 논문에서 제시한 방법은 제한된 정보로 최선의 결정을 내려야 하는 다양한 분야에서 시스템의 효율성과 공정성을 높이는 데 사용될 수 있습니다.

• 활용 분야