정보관리자 [3687] · MS 2008 · 쪽지

2012-10-16 06:13:03
조회수 2,634

노벨 경제학상, 매칭이론의 셰플리와 로스가 수상

게시글 주소: https://a.orbi.kr/0003123753




미국 하버드대 Alvin Roth 교수와 UCLA 의 Lloyd Shapley 교수 공동 수상

가격만으로는 풀리지 않는 현실세계 운용 방식을 창안하여 가장 효율적인 배분 방법을 찾는데 공헌

Shapley는 Gale-Shapley Algorithm으로 이론적 바탕 마련, Roth는 이를 실생활에 적용


만약 이 알고리즘을 따른다면,

- 대학 입시에서, 학생을 선발하는 학교와, 대학에 입학하는 학생들 전원이 만족하는 합격쌍을 도출할 수 있음

- 모든 남자와 모든 여자가 결혼을 할 수 있음 (더 읽기: Stable marriage problem)


실제로 New York 시 공립학교 배정 방식은 2003년부터 Roth의 제안으로 이 알고리즘을 따라 바뀌었고, 2004년에는 Boston에서도 제도에 적용. 

- 한 학생이 가장 가고 싶은 한 학교에만 지원하면, 일단 각 학교는 자신의 학교에 1순위로 지원한 사람을 모두 합격시킴

- 떨어진 사람을 모아 다시 한 번 한 학교만 지원하게 하면, 자리가 남는 학교에서는 지원자를 받아주고 그렇지 않으면 떨어트림

- 마지막 한 명이 합격할 때까지 무한 반복

- "이런 식으로 하면 아무리 많은 사람이 거래에 참가해도 모두 불만족스럽지 않은 결과를 얻게 된다"


Lloyd Shapley

- 게임이론 대가이자, 효용이론(utility theory)의 산파

- "어떤 사람이 어떠한 선택을 하는지에 대한 최적의 공식을 만들었다"

- John Nash (영화 Beautiful Mind의 주인공) 의 협상이론(bargaining theory)을 발전시켰고, 향후 Roth에 의해 집대성되어 매칭이론이 됨

- 유명 천문학자 Harlow Shapley의 아들



0 XDK (+0)

  1. 유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.

  • 360˚ · 348893 · 12/10/16 09:49 · MS 2010

    저 대입제도 좋긴한데.. 우리나라에서 하면 문제많을것같네요 쏠림현상때문에

  • Mayer · 407207 · 12/10/16 13:33

    그래 서울대! 서울대가 좋겠다!

  • 엄마죄송해요ㅠㅠㅠㅠ흐그ㅡ흐 · 372742 · 12/10/16 16:15 · MS 2011

    다 서울대 지원하겠죠. 근데 서울대는 맘에 드는 몇 명만 꾸리고 데려서 확정지음. 그럼 나머지는 또 연고대에 지원. 연고대에서 또 좋은 애들 꾸려서 확정지음. 그럼 남은 애들은 그 다음 순위 또... 무한 반복.

    쏠림현상이 문제될 방안은 아닌 듯.

  • Middleincome · 416657 · 12/10/17 21:27 · MS 2012
    용어의 사용에 있어서 혼동의 여지가 있는 듯 한데요..
    우선, 제가 이해한 바로는 (NYT에서 검색했습니다.)

    1. 한 학생은 자신이 제일 가고 싶어하는 학교에 지원을 합니다.
    간단하게, 하나만 쓰는거죠.
    그럼 그 학교는 자신 학교에 원서를 넣은 학생의 스펙과 성적을 학교 나름대로의 알고리즘대로 순서를 매겨, 정원내의 학생은 일단 hold하고 순위 밖에 밀려난 학생들에게는 reject를 날립니다.

    이때, 합격이란 용어는 쓰지 않습니다.

    2. reject를 받은 학생은, 자신이 제일 원하던 학교에 떨어졌으니 자신이 생각하는 2지망 학교에 원서를 쓰게 됩니다.
    그럼 그 학교에서는, 또 1지망 중 정원내의 학생들을 hold한 상태이겠지요. 이때, 2지망으로 쓴 학생들의 성적과 스펙을 또 면밀히 전부 검토합니다.
    그것과 기존 hold한 학생들을 전부 합쳐 순위를 매겨, 정원 내의 학생은 hold, 그 밖은 reject를 보냅니다.

    3. 이런 방식대로라면, hold 통보를 받았다고 해도 자신이 정원 밖으로 밀려나게 되면 언제든지 reject를 받습니다.

    4. 이 과정을 reject가 더 이상 나오지 않을 때 까지 반복합니다.
  • Middleincome · 416657 · 12/10/17 21:36 · MS 2012
    이 방식대로라면, 학생의 진학 선호도와 학교의 인재 수용 욕구가 최적으로 매칭됩니다.
    즉 사회에 최대로 효율적인 분배가 가능하게 이루어지는 겁니다. 물론 아직 갈 길은 멀지만요.
    참고로, Alvin Roth 교수는 경제학 분야에서 노벨상의 대상으로는 잘 언급되지 않은 분입니다. 그래서 지금 경제학에서는 한층 더 매칭이론에 대한 관심이 쏠리고 있구요.

    +

    이 이론이 주목을 받은 점은, Lloyd Sharpley 교수가 실생활에 적용할 수 있는 알고리듬을 체계화시켜 이 과정을 수학적으로 도출했다는 것이네요.
    학생이 선호 순서를 적어내면, 그 알고리듬대로 학교 배정이 이루어지는 겁니다.

    여튼, 이 방식대로라면 학교 간 경쟁은 발생하지 않습니다.
    게다가 이 상황은 정의역과 치역이 서로 다른 변수를 가진 two-sided matching이기 때문에,
    양자가 서로 각자의 선호를 순차적으로 제시해서 서로를 택하는 과정이고, 이 과정을 통해서라면 학생이 선호를 속일 필요가 없기 때문에 효율적 분배가 가능합니다.