Matching Markets (매칭중인 상점들)

Bipartite Matching Problem ?

노드들이 2개의 타입 중 하나에 속해 있으며 항상 다른 타입의 노드와만 연결되어야 한다.

Perfect Matching?

한 영역의 노드에서 다른 영역의 노드로 연결지을 때 서로의 영역에 하나하나 매칭되어 있을 때

 

Constricted Set

두 영역에 서로 같은 수의 노드가 있을 때,

Perfect Matching이 안될때 생기는 제한된 셋을 말한다. ( Perfect matching이 안되는 증거)

Matching Theorem

Bipartite Graph에 Perfect Matching이 없다면 반드시 Contricted Set이 존재해야 한다.

 

 

Optimal Assignment

각 노드에 반대편의 노드들에 대한 구체적인 목표치(valuation)이 있고, 가장 높은 값이 최선 선택지로 할당한다.

그리고 각각의 valution의 합이 최대가 되도록 할당하자.

 

Prices & Market-Clearing Property

 

-> not central coordination = 지금까지 중앙에서 선택해줬지만 이제는 각 노드에서 선택하도록 하자

-> and use valuations and prices = 대신 각자가 흥미가 있는 valuations 와 price를 선택하자.

 

Game thoery 관점으로 생각하면,

payoff = 각 노드의 가격을 buyer의 그 노드에 대한 가치에 뺀 값

vij = buy j의 노드 i에 대한 valuation  , pi = i 노드의 price

 

Preferred sellers 

모든 buyer의 payoff를 최대화한 값의 bipartite graph

이때 payoff는 음수가 될 수 없다. 왜? 음수가 되면 차라리 안 살 것이기 때문이다.

 

Market-Clearing Prices?

이제 집을 사려하는 buyer들이라고 생각하면, 자신이 원하는 valuation에 대해 payoff가 최고가 될 수 있는 것만 고른 후 (Preferred Seller)

그게 Perfect matching이 되면 Market-Clearing Prices들이라고 한다.

 

Optimality of MCP

MCP의 집합 중 어떠한 MCP는 total valution이 가장 클 것이다.

==> 일단 개개인이 자신의 payoff를 극대화하기 위한 방법은 preferred seller를 한다면 전체 또한 역시 maximum payoff를 가질 것이다.

 

어떻게 MCP를 찾을까?

 

Auction을 이용하자!

 

(1) 처음에 모든 sellers들의 가격을 0으로 하자

 

(2) 이제 매칭을 시켜보자. 

 

(3) 이때 Perfect Matching이 나온다면 그것이 MCP가 된다.

 

(4) 안나오면 Constricted set을 찾자. 그리고 그 contricted set이 정한 seller의 가격을 올리자

 

(5) 이때 reduction이라는 과정이 필요한데,

 

reduction??

graph상에서 가장 낮은 price가 0이 없을 때 가장 낮은 걸 0으로 맞추실 수 있도록 다 조정하자!

( 전체적인 가격의 규모를 조정하는 작업 )