[소응] 10장 Matching Markets

10-1 Bipartite Graphs and Perfect Matchings

1. Perfect Matching

• 모든 노드가 정확하게 하나씩 연결되어 있고,
• 어떤 왼쪽의 노드도 동일한 오른쪽 노드에 할당되지 않은 경우.

2. Constricted sets & Matching Theorem

• Constricted set(수축된 집합)
• biparite에서 perfect matching이 없음을 보여주기 위한 개념.
• 어떤 노드 집합 S에 대해 N(S)가 S의 이웃집합을 나타낸다고 하자.
• 이 경우, S가 수축된 집합인 경우는 S가 N(S)보다 훨 씬 큰 경우임.(위의 예시 참고)

• Matching Theorem
• 만약 양쪽에 동일한 수의 노드가 있는 이분 그래프가 perfect matching을 갖지 않았다면,
• 그 그래프에는 반드시 constricted set이 존재할 것임.

 

10-2 Valuations and Optimal Assignments

1. Optimal Assignment

• 할당에 대한 퀄리티: 각 개인이 받는 valuation의 합
• optimal 할당?
• 퀄리티가 최대한 높고, 모든 사람의 행복을 극대화.
• 그러나 모두가 자신이 가장 좋아하는 아이템을 갖는 것은 아님.

 

10-3 Prices and the Market-Clearing Property

1. Central coordination

• 원래는 중앙 관리자가 perfect matching을 만들어 주는데, 없이도 가능함.

 

2. Prices, Payoffs & Preferred sellers

• 판매자 i는 pi가격으로 집을 판매하기로 결정. 
• 구매자 j의 수익은 vij - pi이다.
• 구매자는 vij - pi가 최대인 판매자에게서 구매할 것임.
  • 음수가 나오면 구매하기 싫어짐.
  • 여러 판매자한테 동일한 수익이 기대되면 아무나 선택.

3. Market Clearing Matching

• 개개인의 payoff를 최대화해주는 방안을 선택했는데 모두 다른 선택을 한 경우.(b)

 

4. Market-clearing prices(MCP)

• Market-clearing의 상황에서 가격 집합.
• 구매자 간의 경쟁 없고, 서로 다른 아이템을 얻음.

5. Properties of MCP***

(시험문제에서 이를 찾으라는 식으로 문제가 나올 수도 있음)

• MCP의 존재(Existence)
  • 어떤 구매자들의 선호도나 가치 평가가 주어져도 MCP는 존재한다.
• MCP의 최적성(Optimality)
  • MCP 결과 판매자와 구매자에게 최대 가능한 수익을 만들어줌.
  • 증명
  • M을 완벽한 매칭이라고 하자.
  • M의 total payoff는 각 구매자가 개별적으로 수익을 최대화하는 집을 선택함.
  • M에 대한 총 payoff = M의 총 valuation - 모든 가격의 합
  • 모든 가격의 합은 고정임!
  • 따라서 payoff가 최대화 되었다 = valuation이 최대화 되었다.

 

10-4 Constructing a Set of Market-Clearing Prices

1. Constructing MCP

• 임의의 구매자 가치 평가가 주어지면 MCP에 도달하는 절차가 있음.
• 이는 일종의 auction임.
• 여러 물건이 경매되고, 여러 구매자들이 다른 valuation을 가짐.

2. MCP 구축을 위한 Auction 과정(7)

1. 초기화: 모든 판매자는 가격을 0으로 설정
2. 구매자 반응: 각 구매자는 선호하는 판매자를 선택.
3. 매칭 확인: market clearing 상황이면, auction 종료
4. 수축 집합 확인: market clearing 상황이 아니면, constrictedset of buyers 집합 S을 찾음.
5. 가격 조정: N(S)에 포함되는 판매자들은 1단위씩 가격올림.(얘네는 인기 많은 애들이었으니까~)
6. 가격 축소: 필요한 경우, 가격을 축소해 가장 낮은 가격이 0이 되도록 조정. 모든 가격을 동일한 양만큼 감소,
7. 반복: market clearing 상태가 나올 때까지 반복

(예시는 교재 확인. 꼭!!! 중요해 보영! - 다른예제도 직접 풀어보깅!! 상황이 주어지고 MCP를 구하시오 ~하면 구할줄 알아야함!!!!)

위에서 price를 높이고, 낮추는 과정을 보았는데, 이러한 과정은 무조건 언젠가는 MCP를 찾고 끝냄.