매칭 마켓 (Matching Market)

 

이분 매칭 문제

- 완벽한 매칭 그리고 제약된 집합

• 우리는 완벽한 매칭으로 이러한 과제를 언급한다. 이분 그래프의 양쪽의 노드들의 개수를 동일하게 할 때, 완벽한 매칭은 왼쪽과 오른쪽에서의 노드들을 할당하는 것이다.
  • 각 노드는 할당되어진 노드로 엣지에 의해 연결되어진다.
  • 왼쪽의 어떤 다른 두 노드는 오른쪽에서 같은 노드로 연결되지 않는다. (1:1)
• 제약 집합(Constricted Sets)
  • 이분 그래프가 완벽히 매칭이 된다면, 완벽한 매칭을 형성하는 엣지를 표시하는 것을 설명하기 쉽다. 그러나 만약 이분 그래프가 완벽한 매칭을 갖지 않는다면? 완벽한 매칭이 없다는 것을 누군가에게 납득시킬 수 있는가?

- 제약 집합과 매칭 이론

• 제약 집합: S를 노드의 집합이라고 하고, N(S)를 이웃 노드의 집합이라고 할 때, S가 N(S)보다 엄격하게 더 크다면, S는 제한되어야 한다.
• 매칭 이론: 만약 이분 그래프(노드의 개수는 왼쪽,오른쪽 동일)가 완벽한 매칭을 갖지 않는다면, 제약 집합을 포함해야만 한다. 즉, 제약집합이 있으면 완벽한 매칭은 존재하지 않는다.

그림 (b)에 대한 설명: Valuations 에서 가장 큰 값을 갖는 경우의 Room 으로 매칭이 이루어진다. 근데 7,6 처럼 차이가 크지 않은 경우(두번째 집합)는 다음 값을 보고 행동을 결정한다. 5,2의 차이는 7,6보다 차이가 크기 때문에 Room 2 와 Room3 의 엣지를 크로스 매칭한다.

- 최적화 할당

• 노드가 얻는 각각의 valuation의 총합을 크게 만드는 것
• 반드시 모든 노드에게 좋아하는(가치가 높은) 아이템(노드)을 할당할 필요는 없다.

- 가격 & 마켓-정리 속성(Market-Clearing Property)

• 중앙 조정(Central coordination): 최적화 할당 혹은 완벽한 매칭을 결정하는 중앙 관리자
• 마켓을 분권화한다.
  • 아이템에 가격을 매기는 특정 틀(scheme)로 중앙 관리자를 대체한다.
  • 개개의 노드가 valuations 와 가격에 따라 self-interest를 따르게 한다.

- 가격, 페이오프(payoffs), 그리고 선호되는 판매자

• 가격과 payoffs: 각 판매자 i가 집을 가격 Pi로 판매한다고 할 때, 만약 구매자 j가 해당 가격에 집을 구매한다면 구매자의 payoff는 그 집에 대한 valuation에서 지불해야 했던 금액을 뺀 것으로 정의된다. (Vij - Pi) 가격 집합이 주어졌을 때, 구매자 j가 payoff를 최대화하길 원한다면, 판매자 i로부터 이 품질 Vij - Pi를 최대화하도록 구매할 것이다.
• 다음은 경고사항이다.
  • 첫째, 이 품질이 몇몇 판매자 간의 동점에서 최대화되어진다면, 그 때 구매자는 그들 중 하나를 고름으로써 payoff를 최대화할 수 있다.
  • 둘째, 만약 payoff Vij - Pi가 판매자의 모든 선택에 대해 음수라면, 그 때 구매자는 어떤 것도 구매하지 않을 것이다. 여기서 구매자가 단순히 아무것도 하지 않음으로써 payoff=0을 얻을 수 있다.
• 구매자 j의 선호되는 판매자들
  • 구매자 j의 payoff를 최대화시키는 판매자, payoff >= 0

- 선호되는 판매자 그래프 & Market-Clearing Prices (MCP)

• 선호되는 판매자 그래프: 각 구매자와 선호되는 판매자 혹은 판매자들 사이에 엣지를 연결
• Market-Clearing Prices(MCP)
  • 가격 집합은 선호되는 판매자 그래프가 완벽한 매칭을 가지는 경우 market-clearing이다.
  • 구매자들이 다른 아이템을 얻음으로써 구매자들 사이에서 언쟁이 해결된다.

- Properties of MCP

• MCP의 존재: 구매자 valuations의 집합에 대해, market-clearing prices의 집합이 존재한다.
• MCP의 최적성(Optimality)
  • market-clearing prices의 어떤 집합에 대해, 선호되는 판매자 그래프에서의 완벽한 매칭은 판매자들의 구매자로의 할당될 때 valuation의 총합을 최대가 되게 한다.
  • market-clearing prices의 집합과 선호되는 판매자 그래프에서의 완벽한 매칭은 모든 판매자들과 구매자들의 payoff의 가능한 합을 최대화한다.
• MCP의 최적성 보이기 
  • 선호되는 판매자 그래프에서의 완벽한 매칭을 M이라 할 때, M의 총 payoff는 각 구매자가 자신의 payoff를 최대화하는 물건을 잡고 있으므로, M은 최대 총 payoff를 가진다. Total payoff of M = Total Valuation of M - Sum of all prices로 정의된다. → max total payoff means max total valuation

- MCP 구성하기 

• 구매자 valuations의 임의의 집합이 주어졌을 때, MCP로 가는 절차가 있다. 실제로 그 절차는 auction(경매)의 한 종류이다. 다수의 경매되는 물품들과 다른 valuations를 가지는 다수의 구매자들이 있다.
• 경매가 이루어지는 방식
  • 초기에 모든 판매자들은 가격을 0으로 한다.
  • 구매자들은 선호되는 판매자를 고른다.
  • 그리고 선호되는 판매자 그래프를 확인한다. 만약 이 그래프가 완벽한 매칭을 갖지 않는다면, 구매자들의 제약 집합 S가 존재한다. 이웃 노드의 집합 N(S)은 판매자들의 집합임을 고려하라. 집합 S에 있는 구매자들은 오로지 N(S)에 있는 판매자들이 판매하는 것을 원한다. 그러나 S에 있는 구매자들보다 N(S)에 있는 판매자들이 더 적다. 그래서 N(S)에 있는 판매자들은 높은 수요(high demand)를 갖는다. 너무 많은 구매자들이 그들에게 관심을 보인다.
  • 구매자들은 판매자가 한 단위씩 가격을 올릴 때마다 반응하고 경매는 그 때 계속된다.
• 다른 방법도 있는데, 가격에서 reduction 연산은 하는 것이다. 가장 작은 가격이 0이 되도록 가격을 스케일하는데 유용하다. 그러므로 모든 가격이 엄격히 0보다 큰 노드에 도달한다면, 각각의 가격으로부터 p를 빼서 가격을 낮춘다. 이는 가장 낮은 금액을 0으로 만들고 동일한 상대량에 의해 모든 다른 가격들도 바뀐다.

- MCP 구성을 위한 경매 절차

1. 각 라운드에서 시작, 가장 작은 가격이 0인 현재 가격 집합이 있다.

2. 선호되는 판매자 그래프를 구성하고 완벽한 매칭이 있는지 검사한다.

3. 완벽한 매칭이 있으면, 현재 가격들이 market-clearing 상태이다.

4. 완벽한 매칭이 없다면, 구매자 제약 집합 S와 이웃 노드의 집합인 N(S)를 찾는다.

5. N(S)에 있는 각 판매자는 (동시에) 한 단위씩 가격을 올린다.

6. 필요하다면, 가장 작은 가격이 0이 되도록 가격을 낮추는데 다른 가격들로부터 동일한 상대량을 각각 빼준다.

7. 새로운 가격 집합으로 경매의 다음 라운드를 진행한다.

처음에 0으로 시작해서 1개의 노드만 N(S)에 있다. 그 노드의 가격을 올리고 다시 경매를 시작한다.

계속 가격을 올리다 보면 N(S)에 판매자 노드가 하나씩 추가된다. 추가되면서 다음 라운드 직전에 N(S)에 있는 모든 판매자 노드는 동시에 한 단위씩 가격을 올린다. 위 그림에서 (d)는 가격 집합이 market-clearing prices 상태이다.

• 경매는 끝이 나야만 한다.
  • 사실, 가격이 멈추지 않고 영원히 바뀔 수는 없다. 경매는 항상 끝나야 한다. 이것을 보여주는 방법은 어떤 종류의 잠재적 에너지가 그것이 실행될 때 경매에서 고갈되고 있다는 정확한 감각을 알아내는 것이다. 경매는 이 잠재적인 에너지를 초기에 한정된 공급으로만 시작하므로, 결국 고갈되어야 한다.
  • 여기 우리가 이 잠재적 에너지 개념을 정확히 정의하는 방법이 있다. 현재 가격 세트의 경우, 구매자가 현재 판매자로부터 받을 수 있는 최대 지급액이 될 가능성을 정의하십시오. 이것은 구매자의 잠재적 보상이다. 만약 현재의 가격이 market-clearing prices 이라면 구매자는 실제로 이 보상을 받을 것이다. 우리는 또한 판매자의 잠재력이 그가 청구하는 현재 가격이라고 정의한다. 이것은 판매자의 잠재적 보상이다. 현재 가격이 market-clearing prices 이라면 판매자는 실제로 이 보상을 받을 것이다. 마지막으로, 우리는 경매의 잠재적 에너지를 구매자와 판매자 모두 모든 참가자의 잠재력의 합으로 정의한다.
  • 퍼텐셜 payoff는 현재 가격 정책에서 책정 가능한 최대 payoff