A characterization of the von Neumann and Morgenstern stable set in matching markets

활기찬 시장을 상상해 보세요. 기업(Firms)은 직원을 채용하기 위해 고군분투하고 있고, 직원(Workers)은 일자리를 찾고 있습니다. 모두에게는 누구와 함께 일하고 싶은지에 대한 엄격한 선호 목록이 있습니다. 목표는 사람들이 스스로 파트너를 바꾸거나 친구와 함께 바꾸려 할 만큼 불행해지지 않도록 이들을 짝지어 주는 것입니다.

경제학에서는 이 시장의 '안정성'을 생각하는 두 가지 주요 방법이 있습니다:

1. "후회 없는" 규칙 (코어, The Core): 이것은 표준적인 방식입니다. 어떤 매칭이 안정적이라는 것은, 단 하나의 기업과 단 하나의 직원이 현재의 파트너보다 서로를 더 원해서 관계를 바꾸려 하지 않는 상태를 의미합니다. 이는 마치 친구들이 저녁 식사 자리를 결정하는 것과 같습니다. 만약 어떤 두 사람이 더 행복해지기 위해 자리를 바꾸고 싶어 하지 않는다면, 그 좌석 배치는 "안정적"입니다.

2. "천하무적 클럽" 규칙 (폰 노이만-모르겐슈테른 또는 vNM 안정성): 이것은 이 논문이 연구하는 더 까다로운 개념입니다. 특정 좌석 배치 하나를 보는 대신, 배치들의 '클럽'을 봅니다. 어떤 클럽이 "vNM 안정 집합"이 되려면 다음 두 가지 규칙을 충족해야 합니다:

   • 내부 평화: 클럽 내부의 어떤 배치도 같은 클럽 내의 다른 배치에 의해 "패배"해서는 안 됩니다. (단순히 다른 배치가 약간 더 낫다고 해서 클럽에서 누군가를 쫓아낼 수는 없습니다.)
   • 외부 방어: 만약 당신이 클럽 밖에 있다면, 클럽 내부의 누군가가 당신을 이길 수 있어야 합니다. (클럽에 속하지 않았다면, 당신을 개선할 수 있는 존재가 내부에 있어야 합니다.)

문제점

오랫동안 경제학자들은 "후회 없는" 규칙(코어)은 이해하기 쉽고 계산하기 쉽다는 것을 알고 있었습니다. 하지만 "천하 무적 클럽"(vNM 안정성)은 미스터리였습니다. 그것은 마치 안개 낀 방에서 특정한 모양을 찾는 것과 같았습니다. 그런 클럽이 존재하는지, 단 하나의 클럽만 존재하는지, 혹은 어떻게 그 클럽을 찾을 수 있는지 아무도 몰랐습니다.

이 논문의 위대한 발견

저자들은 이 미스터리를 풀었습니다. 이 특정 유형의 시장에는 정확히 하나의 그러한 "천하무적 클럽"이 존재한다는 것을 발견했으며, 이를 구축하는 정확한 방법을 알아냈습니다.

이들이 어떻게 했는지에 대한 간단한 비유는 다음과 같습니다:

1. "나쁜 이웃" 목록

시장이 하나의 동네라고 상상해 보세요. 어떤 이웃들(기업과 직원의 쌍)은 서로 맞지 않습니다. 그들은 관계를 바꾸고 싶어 할 수도 있지만, 그렇게 하는 것은 전체 동네의 안정성을 깨뜨리는 연쇄 반응을 일으킬 수 있습니다.
저자들은 "천하무적 클럽"을 찾기 위해서, 먼저 가능한 매칭 목록에서 특정 "나쁜 이웃"들을 식별하여 제거해야 한다는 것을 깨달았습니다. 이들은 다음과 같은 쌍들입니다:

• 순환을 깨뜨리는 쌍: 시장의 자연스러운 흐름(즉, 누가 누구를 좋아하는지에 대한 구조적 위계인 '격자(lattice)'라는 세련된 용어)을 방해하는 쌍들입니다.
• 효율성을 차단하는 쌍: 설령 현재 직접적으로 막고 있지는 않더라도, 시장이 모두가 조금 더 행복해지는 "더 나은" 상태로 나아가는 것을 가로막는 쌍들입니다.

2. "정돈된" 시장

이 "나쁜 이웃"들을 목록에서 제거하면, 축소된 시장이 남습니다. 이것은 망가진 장난감과 잡동사니를 모두 버려 방을 깔끔하게 정리하는 것과 같습니다. 그러면 오직 유용하고 호환 가능한 것들만 남게 됩니다.

3. 마법 같은 결과

이 논문은 놀라운 사실을 증명합니다: "천하무적 클럽"(vNM 안정 집합)은 이 정돈된 방에서의 "후회 없는" 그룹(코어)과 정확히 일치합니다.

다시 말해:

• vNM 안정 집합을 찾기 위해 복잡한 수학이 필요하지 않습니다.
• 어떤 배정이 클럽에 속해야 하는지 추측할 필요도 없습니다.
• 저자들이 식별한 특정 "나쁜 쌍"들을 제거한 후, 그 새로운, 더 작은 시장에서 표준적인 "후회 없는" 솔루션을 찾기만 하면 됩니다.

즉:

• 당신은 복잡한 수학 없이 vNM 안정 집합을 찾을 수 있습니다.
• 당신은 어떤 배정이 클럽에 속해야 하는지 추측할 필요가 없습니다.
• 단지 원래의 시장에서 저자들이 식별한 특정 "나쁜 쌍"들을 제거하고, 그 새로운, 더 작은 시장에서 표준적인 "후회 없는" 솔루션을 찾으면 됩니다.

이것이 왜 중요한가

이 논문 이전에는 vNM 안정 집합을 찾는 것이 모든 갈림길을 추측하며 미로를 푸는 것과 같았습니다. 이 논문은 당신에게 지도를 제공합니다. "추측하지 마세요. 단지 이 특정 막다른 길들을 제거하면, 솔루션은 바로 그 중심에 있습니다"라고 말해주는 것입니다.

이 논문은 두 가지 다른 경제 이론의 세계를 연결합니다:

• **지배(dominance)**의 세계 (누가 누구를 이기는가).
• **표준 매칭(standard matching)**의 세계 (누가 누구와 행복한가).

저자들은 적절한 렌즈(즉, "축소된" 렌즈)를 통해 시장을 바라본다면, 이 두 세계가 실제로 동일하다는 것을 보여줍니다. 또한, 이 고유한 솔루션을 표준적인 도구를 사용하여 계산할 수 있는 단계별 레시피(알고리즘)를 제공함으로써, 이론적인 퍼즐을 실질적이고 해결 가능한 문제로 바꾸어 놓았습니다.

요약하자면: 이 논문은 도망치기 힘든 "천하무적 클럽"의 매칭이, 불필요한 혼란을 일으키는 특정 쌍들을 제거한 시장의 "행복한 그룹"이라는 것을 찾아냈습니다. 그러한 클럽은 단 하나뿐이며, 우리는 이제 그것을 찾는 정확한 방법을 알고 있습니다.