2012년 노벨 경제학상

  • JongMan
    JongMan

    노벨 경제학상이 Stable Marriage Problem을 푸는 Gale-Shapely Algorithm의 저자들에게 돌아갔다는 소식입니다.

    알고리즘을 만들어서 노벨 경제학상을 받다니 오오 멋있어요 오오

    기념으로 JMBook에서 해당 알고리즘을 다루는 부분을 복붙해 봅니다. ^^

    안정적 결혼 문제

    n명의 남성과 여성이 단체 미팅에서 만났습니다. 여러 게임을 진행하는 동안 모든 사람은 자신이 원하는 상대방의 우선 순위를 맘 속에 정했고, 이제 한쌍씩 짝을 지어 줄 차례가 되었습니다. 그런데 서로 짝이 아닌 두 남녀가 각자 자신의 짝보다 상대방을 더 선호한다는 사실을 알게 되면 두 남녀는 곧장 미팅장을 뛰어나와 도망가 버리게 됩니다. 이런 일이 일어나지 않도록 짝을 지어줄수 있는 방법이 항상 있을까요? 아니면 불가능한 경우가 있을까요?

    흔히들 안정적 결혼 문제(Stable marriage problem)라고 부르는 이 문제는 구성적 증명으로 해결되는 대표적 문제입니다. 이 문제를 푼 사람들은 답의 존재성을 보이는 대신 답을 만드는 알고리즘을 제시함으로써 답이 존재함을 보였지요.
    이 알고리즘은 다음과 같이 진행됩니다.

    1. 처음에는 여성들이 모두 자신이 가장 선호하는 남성의 앞에 가서 프로포즈를 합니다. 남성이 그 중 제일 마음에 드는 여성을 고르면 나머지는 퇴짜를 맞고 제 자리로 돌아갑니다.
    2. 퇴짜를 맞은 여성들은 (상대에게 짝이 있는지 없는지는 관계 없이) 다음으로 마음에 드는 남성에게 다가가 프로포즈합니다. 남성들은 현재 자기 짝보다 더 맘에 드는 여성이 다가왔다면, 지금의 파트너에게 퇴짜를 놓고 새 여성에게 넘어갑니다.
    3. 더 프로포즈할 여성이 없을 때까지 2번 항목을 반복합니다.

    이 알고리즘이 우리가 원하는 답을 구할 수 있음을 보이려면 이 알고리즘이 항상 종료한다는 것, 모든 사람이 짝을 찾는다는 것, 그리고 결과적으로 이뤄지는 짝들이 항상 ‘안정적’임을 증명해야만 하죠. 이 증명은 의외로 간단합니다.

    종료 증명

    각 여성은 퇴짜 맞을 때마다 지금까지 프로포즈했던 남성들보다 우선순위가 낮은 남성에게 프로포즈합니다. 따라서 각 여성이 최대 n명의 남성들에게 순서대로 프로포즈한 이후엔 더이상 프로포즈할 남성이 없으므로, 이 과정은 언젠가 반드시 종료합니다.

    모든 사람들이 짝을 찾는지 증명

    프로포즈를 받은 남성은 그 중 한 사람을 반드시 선택하고, 더 우선 순위가 높은 여성이 프로포즈해야만 짝을 바꾸므로 한 번이라도 프로포즈를 받은 남성은 항상 짝이 있기 마련이죠. 귀류법을 적용하여
    남녀 한 사람씩 짝을 찾지 못하고 남았다고 가정합시다. 그런데 여성은 우선순위가 높은 순서대로 모두에게 한 번씩 프로포즈하기 때문에, 이 남성에게도 한 번은 프로포즈했겠죠. 이 남성은 프로포즈를 받아들였어야 하고, 따라서 짝을 찾지 못하는 사람은 있을 수 없습니다.

    짝들의 안정성

    역시 귀류법으로 증명합니다. 이 과정의 결과로 짝을 지었는데 짝이 아닌 두 남녀가 서로 자신의 짝보다 상대방을 더 선호한다고 가정합시다. 여성은 지금 자신의 짝 이전에 그 남성에게 반드시 프로포즈했어야 합니다. 그런데도 이 남성이 이 여성과 짝지어지지 않았다는 말은 더 맘에 드는 여성에게 프로포즈를 받아서 수락했다는 뜻이죠. 남성은 더 맘에 드는 여성이 나타났을 때만 짝을 바꾸므로, 프로포즈 받았던 여성보다 맘에 들지 않는 여성과 최종적으로 짝이 되는 일은 없습니다. 따라서 우리가 가정했던 상황은 존재할 수 없지요.


    12년 전
10개의 댓글이 있습니다.
  • Being
    Being


    12년 전 link
  • hyunhwan
    hyunhwan


    12년 전 link
  • Pekaz
    Pekaz


    12년 전 link
  • kty1965
    kty1965


    12년 전 link
  • hyunhwan
    hyunhwan

    이것이 바로 기승전북


    12년 전 link
  • Baekjoon
    Baekjoon

    대박


    12년 전 link
  • wookayin
    wookayin


    12년 전 link
  • killerna
    killerna

    (진지하게 출간일이 궁금해요..;;;)


    12년 전 link
  • Stun
    Stun

    이해하기 쉽게 그리고 간단한게 끝내버리셨네요 :)

    그런데 읽는 도중에 조금 어색한 부분이 있어서 코멘트 달아봅니다.

    "그런데 서로 짝이 아닌 두 남녀가 각자 자신보다 상대방을 더 선호한다는 사실을 알게 되면 두 남녀는 곧장.."

    이 부분에서 "자신"이 "자신의 짝"이 되어야 되는게 아닌가요?

    지적질 같아서.. 조금 망설였습니다만 제 의견이 도움이 될 수도 있을 것 같아서 코멘트 달아봅니다.


    12년 전 link
  • JongMan
    JongMan

    @Stun, 아이고 지적질이라뇨. 코멘트 감사합니다. 원문에도 그렇게 썼나 하고 화들짝 놀라서 보니, 제가 pdf에서 복붙하다가 잘라먹었나 봅니다. ㅎㅎ


    12년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.