Matching Market

- 바이팔타이트 : 노드 타입이 두가지인 그래프. 방과 사람 두 편이 있는데, 나는 이 방에 관심있어요 하는게 링크임.

-> 전형적으로 쇼핑몰에서 서치엔진 같은 것 생각할때도, 고객들이 있고 물건들이 있음. 누가 무슨 물건 샀다 하는 정보를 이용해서 추천을 함. 이것도 물건이 물건을 살 순 없잖아?

- 모든 사람에게 모든 방을 배치할 경우에는 우측 굵은 링크대로 하면 각1방 배정받게 됨. 이런 상황을 퍼펙트매칭이라고 한다.

 

- 여기서의 어사인먼트(누구에게 무엇을 준다 하는 내용 자체 = 할당) : 매칭, 배정시키는 것.

-> 같은 개수의 방과 사람인 바이팔타이트 그래프라고 했을 때 오른쪽 사람들에게 왼쪽 노드를 어사인하는 것.

- 퍼펙트매칭의 조건 : 각 노드는 한개의 노드로 반대노드와 연결되어야하고, 두 노드가 같은노드에 어사인되면 안된다. 한 사람이 방 두개 어사인해도 안된다. 퍼펙트매칭이 없으면 어떻게 할 것이냐? 있는걸 증명하는게 훨씬 쉬움.

 

- 퍼펙트 매칭  없습니다.

-> 웬디는 1, 신은 2 피크람은 1,2 그래서 3명이 원하는 방이 2개임. 어떤 방법을 쓰더라도 나눠줄 방법이 없는 것.

 

- 노드 셋이 S면, N(S)는 노드의 이웃(링크로 연결된 애들) = S셋에서 연결된 애들을 짝 모아놓은 것.

-> 앞의 원에 있는 3개의 집합이 S임.

- 컨스트릭트 셋 : S의 셋이 더 커야한다. N(S)는 룸1,2임. S의 크기는 3, N(S)는 2.

-> 바이팔타이트 그래프에서 퍼펙트매칭이 없다면 반드시 컨스트릭트 셋이 있어야함.

 

- 스파스(희소) 매트릭스. 1이 너무 적어

- 링크를 그려놨는데, 인코딩해보자=숫자로 만들어보자.

-> Xin은 룸1,2는 라이크. 요람은 1, 조는 2,3라이크. 이 숫자가 밸류임. 밸류에이션이라 부름.

 

- 요람은 1번방을 제일 좋아한다. 조도 1번방을 제일 좋아한다.

-> 이상황에서 어떻게 옵티멀한 어사인먼트를 해줄 것이냐 : 제일 미친듯이 좋아하는사람한테 준다(?)

 

- Quality of an assignment : 각 개인이 자기가 받은 방에 대해 평가한 valuation의 합계

- 옵티멀 어사인먼트 : 모든 사람의 총 행복을 극대화.

 

- 센추럴 코오디네이션 : 누군가 중간에서 조정해주는것 = 기숙사 사감이 앉아서 방배정해주는 것.

 

- 디 센츄럴라이즈 마켓 -> 모두가 겉으로 봤을 때 제일 좋은물건을 가져가고 싶지 않을까?

근데 가격이 올라가면 또 달라질 것이다. 각 사람의 이익=(밸류와 프라이스의 차이)에 따라 달라질 것.

-> 각 사람이 다른 밸류에이션 갖고있기때문에 가격이 달라지면 각 사람이 페이오프를 계산함.
→ 물건이 좋다고 꼭 가는게 아니다. 각 사람 자신의 셀프 인터레스트를 따라 움직이도록 하면 센트러 코디네이션 안하고도 마켓을 디센트럴라이즈 할 수 있는 방법.

 

 

- 각 판매자 i가 자신의 집을 매물로 내놓으며 가격 pi ≥ 0에 판매하겠다고 제안한다고 가정.

구매자j의 페이오프는 이 주택의 가치에서 지불 금액을 뺀 값 : Vij(j가 i주택에 얼마의 가치를 뒀느냐) - Pi.

-> 내가 조금 돈을 더 주더라도 좋은 집 사야지 이런 생각은 없다! 오로지 페이오프를 극대화시키려함.

페이오프가 같다면, 랜덤 초이스.

 

- 판매자 i를 선택할 때마다 구매자의 보상 vij - pi; 가 음수인 경우 : 거래x -> 0의 보상.

- preffered sellers : preffer한 걸 좋아한다(?) -> j의 입장에서, 음수가 아닌 페이오프를 맥시마이즈 해주는 셀러!

 

2014

- a : valuation : 각 사람이 물건에 대해 마음속에 갖고 있는 밸류. 

- a : price : 각 집의 가격. 현재로서 프라이스는 셀러가 정함. 

- 마켓 클리어링 프라이스 : 모든 집들을 다 assign할 수 있는 가격을 찾는 것.

 

- 좌하단 210 케이스에서, x y z 모두 a집을 사려고 함 -> 마켓 클리어링 불가!

- 우상단 520 케이스에서, 마켓 클리어링 가능! 520 이지만 숫자 상관없이 마켓 클리어링 프라이스임.

-> 페이오프를 계산하면 됨. 페이오프 극대화 관점에서 y는 c를 사는게 가장 좋기 때문.

-> 가격이 달라지면 페이오프가 달라진다!

-> 다들 a집이 제일 좋다곤 했음. 

 

- 프리퍼드 셀러 그래프 : 각 바이어를 프리퍼드 셀러와 연결 시킨 그래프!

- MCP :  프리퍼드 셀러 그래프가 퍼펙트 매칭인 경우(+모든 바이어를 프리퍼드 셀러와 연결) 가격 집합이 MCP!

-Existence of MCP :  모든 바이어의 밸류에이션 집합에 대해 a set of MCP가 존재한다!

-> 이걸 찾으라고 시험에서 내지 않을까?

- Optimality of MCP : optimal하다는 것?
-> 모든 MCP에 대해 preferred-seller 그래프에서 퍼펙트매칭 이라는 것은 맥시멈 토탈 밸류에이션을 가진다!
- MCP집합과 그 결과 preferred seller 그래프에서 퍼펙트 매칭 경우, 모든 판매자와 구매자에게 가능한 최대 보상 합계를 생성.

 

MCP의 optimality
- M : 프리퍼드 셀러 그래프에서 퍼팩트 매칭
- M의 토탈 페이오프 :  각 구매자는 개별적으로 자신의 보상을 극대화하는 집을 잡기 때문에 M은 맥시멈 토탈 페이오프를 가짐.
- M의 총 보상 = M의 총 가치 - 모든 가격의 합계
- price는 변하지 않음(상수) -> payoff가 극대화 됐다? valuation이 극대화 됐다!
-> 따라서 max total payoff 는 max total valuation을 의미함

 

MCP의 구성

- MCP는 결국 price를 찾아내는 것 -> 밸류에이션이  주어져야함

- 임의의 바이어 밸류애이션이 주어졌을 떄 MCP에 도달하도록 해주는 프로시저가 있다 = 옥션!

- 옥션은 가격을 점점 올리며 한 사람 남을 때 까지 하는 것.

 

1 이니셜라이즈 : 0으로 프라이스를 세팅. 모든 셀러들이 0으로 세팅

-> 밸류에이션이 고정되어 있으니 price에 반응!

 

2 페이오프 계산! 프리퍼드 셀러 그래프를 그릴 수 있음. 이 위에 퍼펙트매칭이 존재한다? mcp를 찾았다는 말

 

그런데 아니라면 이제 할 일이 있는 것

 

3 4명의 사람이 하나의 집에 관심이 있다면, 집주인은 가격을 올려야하겠지?

-> 각 판매자는 동시에 1 unit의 가격을 올림. -> 가격이 오르면 페이오프가 변함 = 셀러가 변한 것!
4 -> 프리퍼드 셀러 그래프를 다시 그림 -> 이 때 퍼펙트 매칭이 있을 수 있겠지? -> 없을시 반복

 

 

- reduction operation도 있음 : 가장 낮은 가격이 0이 되도록 싹 리덕션!

- 매칭이 안되면 올리고 리덕션하고 올리고 리덕션하고 할텐데 무한에 빠지진 않음. 퍼펙트매칭이 존재할테니.

 

 

 

a - 000으로 시작 -> xyz가 constricted set에 있음. a가 이웃이지. 인기가 너무 많아!

b - price를 하나 올리고, 가장 낮은 프라이스가 0인지 체크 : 0이 있으니 리덕션 할 필요는 없음

-> 다시 페이오프 계산

- 퍼펙트 매칭이 없으니 다시 컨스트릭트 셋을 찾아야함 : x,z or x,y,z

c - 여기서는 컨스트릭트 셋을 x,z로 잡고 a의 가격을 또 올림 -> 이번엔 xyz가 컨스트릭트 셋이고 a,b가 네이버

d - a,b 가격을 동시에 올림 -> 이번엔 퍼펙트 매칭이 포함되어있다! 이 때의 가격이 MCP임

 

위 예시에서는 두 가지 포인트가 있다

1. 오버 디맨드된 네이버 셋이 하나 이상으로 구성이 되면 동시에 가격을 올려야함

2. MCP가 하나는 아니다! 우측 520도 MCP임!

 

 

 

- 그래서, auction은 어쨌든 반드시 끝나야한다! 단, 답이 있다고 해서 무조건 찾을 수 있는 것은 아님.

포텐셜 에너지라는게 있는데, 옥션 과정이 진행되면서 제한된 포텐셜 에너지가 조금씩 drained된다. 

- 포텐셜 에너지는 구매자의 포텐셜 페이오프 + 판매자의 포텐셜 가격