Move Fast

이분 매칭 문제

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

• 우리는 완벽한 매칭으로 이러한 과제를 언급한다. 이분 그래프의 양쪽의 노드들의 개수를 동일하게 할 때, 완벽한 매칭은 왼쪽과 오른쪽에서의 노드들을 할당하는 것이다.
  • 각 노드는 할당되어진 노드로 엣지에 의해 연결되어진다.
  • 왼쪽의 어떤 다른 두 노드는 오른쪽에서 같은 노드로 연결되지 않는다. (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

네 가지 주요 경매 유형

- Ascending-bid auctions or English auctions

• 물리적으로나 전자적으로 입찰자(bidder)가 존재하는 실시간 상호적으로 수행되는 경매이다. 판매자(seller)는 점차 가격을 올리고, 마지막 한 명의 입찰자가 남을 때까지 입찰자들이 빠져 나간다. 구두로 진행되는 경매에서는 입찰자가 가격을 외치거나 전자적으로 가격을 제출하는 방식이다.

- Descending-bid auctions or Dutch auctions

• 판매자가 현재 가격을 지불하는 첫 입찰자가 나올 때까지 가장 높은 초기 값에서 점차 가격을 내리는 방식이다.

- First-price sealed-bid auctions

• 입찰자는 동시에 판매자에게 몰래 입찰 가격을 제출한다. 입찰자들은 판매자에게 밀봉된 봉투에 가격을 적어 담아 제공하였다. 그 봉투는 판매자가 모두 함께 열게 하였다. 가장 높은 가격을 제시한 입찰자가 물건을 얻는다.

- Second-price sealed-bid auctions or Vickrey auctions

• 몰래 입찰 가격을 제시하고 판매자가 한 번에 입찰 가격을 공개하는 방식(여기서 입찰자는 아무것도 안하거나, 가격을 제시하거나, 포기하는 3가지 행동만 가능)은 위와 동일. 가장 높은 가격을 제시한 입찰자가 물건을 얻는데, 지불하는 가격은 두번째로 제시된 높은 가격이다.

- Descending-Bid & First-Price Auctions

• 첫번째, descending-bid auction을 고려하라. 여기서 판매자가 높은 초기 가격을 시작으로 점점 가격을 낮추기 때문에, 어떤 입찰자도 마지막 누군가가 실제로 입찰을 할 때까지 어떤 것도 말하지 않는다. 입찰자들은 경매가 진행중인 동안에 아무도 아직 현재 가격을 받아들이지 않았다는 사실 이외에 아무것도 알지 못한다. 각각의 입찰자 i에 대해 첫번째 가격 bi이 있다. 이 가격은 입찰을 한다는 의지가 있는 것이기 때문에 입찰 가격 bi는 입찰자 i의 “입찰” 자체를 의미한다. 실제 입찰을 하는 사람은 입찰자가 제시한 가장 높은 가격을 지불한다.

- Ascending-Bid & Second-Price Auctions

• 점점 가격을 올리는 과정에서 사람들이 떨어져 나가고, 마지막으로 남은 입찰자는 두번째로 높게 제시된 가격을 지불한다.
• 경매를 포기할 때까지 입찰자가 머무는 경우를 생각해보자.
  • 첫번째, 가격이 당신의 true value에 도달한 후에 경매에 참가하는 것이 말이 되는가? 그렇지 않다. 머물면 오히려 얻지 못하고 손해를 보게 된다. (true value보다 높은 가격을 지불해야 하므로)
  • 두번째, 가격이 당신의 true value에 도달하기 전에 포기하는 것이 말이 되는가? 그렇지 않다. 만약 일찍 포기한다면, 아무것도 얻지 못한다. 실제로 true value에 도달하기 전에 입찰을 할 수도 있을 것이다.
• 이는 입찰자가 ascending-bid auction 에서 가격이 true value에 도달할 정확한 순간이 올 때까지 머물러야 한다는 것을 의미한다. 만약 각 입찰자가 포기할 시기의 가격이 누군가의 입찰 가격이라면, 사람들은 그들의 입찰가로 자신의 true value를 사용해야 한다.
• 마지막에 입찰자가 둘만 남은 경우, 입찰자 한 명이 중도 포기를 한다면 책정한 금액은 그 사람의 second price이다. 따라서 마지막까지 남은 입찰자 한 명이 second price로 지불한다.
• 두번째로 높은 가격을 지불하는 이유
  • 경매의 낙찰 금액은 참여자의 true value가 아니라 경쟁자의 true value(=second highest)에 의해 좌지우지 된다.
• ascending-bid auction의 끝에 동시에 발생하는 3가지 일에 대한 단순한 생각이다.
  • second price를 제시한 입찰자는 중도 포기한다.
  • 마지막으로 남은 입찰자는 혼자인 것을 알고 어떤 높은 가격에 동의하는 것을 멈춘다.
  • 판매자는 현재 가격(=중도포기한 입찰자의 true value)으로 마지막에 남은 입찰자에게 아이템을 준다.
• 더욱이, 이러한 입찰의 정의에 따라, ascending-bid auction의 결과를 결정하는 규칙은 다음과 같이 재구성될 수 있다. 입찰가가 가장 높은 사람은 가장 오래 머무는 사람이다. 그래서 당첨된 물건, 그리고 그녀는 두 번째 사람이 탈락한 가격을 지불한다. 즉, 그녀는 이 두 번째 사람의 입찰에 응한다. 따라서 그 품목은 두 번째로 높은 가격으로 마지막에 남은 입찰자에게 간다. 이것은 정확히 sealed-bid second-price auction에 사용되는 규칙이며, ascending-bid auction 는 구매자와 판매자 간의 실시간 상호작용을 수반하는 반면, sealed-bid version 은 판매자가 열고 평가하는 밀봉된 입찰에서 순수하게 발생한다는 차이점이 있다. 그러나 규칙의 밀접한 유사성은 second-price auction을 위한 최초에 반직관적인 가격 규칙을 동기를 부여하는 데 도움이 된다. 그것은 sealed-bid를 사용하여 ascending-bid auction 의 시뮬레이션으로 볼 수 있다. 더욱이 입찰자들이 그들의 true value가 정확히 도달되는 지점까지 ascending-bid auction 에 남기를 원한다는 사실은 다음 섹션에서 무엇이 우리의 주된 결과가 될지에 대한 직관을 제공한다. 게임 이론의 관점에서 sealed-bid second-price auction 를 공식화한 후에, 우리는 한 사람의 true value를 입찰하는 것이 dominant strategy이라는 것을 알게 될 것이다.

- 경매 형식 비교

• first-price auction에서 입찰자들은 second-price auction에서 입찰하는 것보다 더 낮은 입찰가격을 제시 하는 경향이 있을 것이고, 사실 이 입찰의 인하는 마지막 낙찰자의 가격 크기 차이로 보일 수 있으므로, 위의 경향이 아닌 경우에 차이가 발생하는 걸 없앤다.
• Second-Price Auctions: 입찰자가 직전에 중도포기한 사람의 true value를 지불하는 것은 second price sealed-bid auction에서의 dominant strategy이다.
• Second-Price Auction을 게임으로 공식화하기
  • 입찰자 i의 true value 를 vi라고 표현하고, 입찰자의 전략은 true value의 함수로 입찰하기 위한 양 bi 이다. second-price sealed-bid auction에서 입찰가격 bi와 true value 로 vi를 가지는 입찰자 i의 payoff는 입찰가 bi가 채택되지 않았다면 payoff는 0이고, 만약 입찰되었다며 second-price인 다른 bj에 대해 payoff 는 vi - bj가 된다.
    • 원한 목표가치(vi) - 낙찰 가격 (bj = 입찰자 j의 true value)

- Second-Price Auctions에서의 정직한 입찰

• 주장: sealed-bid second-price auction에서 dominant strategy는 각 입찰자 i가 bi = vi 인 입찰가를 선택하는 것이다.
• 증명: 만약 입찰자 i가 bi = vi 로 낙찰할 때, 다른 이들이 사용하는 전략에 무관하게 가격을 바꾸는 어떤 행동도 payoff를 향상시키진 않는다는 사실을 보여야 한다. 입찰자 i가 입찰가를 올리는 상황과 입찰가를 내리는 상황 2가지 경우를 고려해보자. 핵심은 두 경우 모두 입찰가격만 입찰자 i가 이길지 말지에 영향을 주지만, 실제 낙찰하는 상황에서 얼마나 많이 지불할 지에는 영향을 주지 않는다. 지불하는 양이 다른 입찰 가격에 의해 전적으로 결정되고, 다른 가격들 중 가장 큰 가격에 의해 특히 그러하다. 입찰자 i가 가격을 수정할 때 모든 다른 입찰가격이 그대로이기 때문에, i의 입찰가격 변화는 오로지 입찰자가 이기는/지는 결과가 바뀐다면 실제 Payoff에 영향을 준다.
• 두 가지 상황에 대해 명심해야할 것.
  • 첫번째, 입찰자 i가 vi보다 큰 b’i (>vi)로 낙찰이 된 경우 입찰자는 true value 보다 큰 가격을 제시했으니 vi로는 졌지만, 입찰가격 b’i로 실제 낙찰은 되었으니 이겼다고 보며 결국 가격의 변화는 입찰자에게만 영향을 미친다. 이것이 발생하려면, 가장 높은 다른 입찰 가격 bj는 bi와 b’i 사이에 존재해야 한다. 이 경우 가격변경으로 인한 i의 payoff는 기껏해야 vi - bj <= 0일 것이다. 그래서 이러한 b’i로 가격변경은 i의 payoff를 향상시키지 않는다. (payoff가 항상 음수임)
  • 두번째, 입찰자 i가 vi보다 작은 b’’i (<vi)로 낙찰이 된 경우 입찰자 i의 payoff는 true value보다 작은 가격을 제시했으니 vi로는 이겼지만 b’’i로는 졌다고 본다. 가격을 변경하기 이전에 vi는 winning bid였고, second-price bid bk는 vi 와 b’’i 사이에 있었다. 이 경우 가격 변경 전 i의 payoff는 vi - bk >= 0 이다. 가격 변경 이후에는 입찰자 i가 졌기 때문에 payoff는 0이 된다. 이 또한 가격 변경 i 의 payoff를 향상시키지 않는다. (가격 변경 전 payoff가 변경 후 payoff보다 높을 수 밖에 없다.)

• 위에서 세로축은 가격축이고, bi’은 첫번째 경우의 낙찰 지점이다. 맨 밑에 bi’’은 두번째 경우의 낙찰 지점이다.
• truthful bidding is a dominant strategy in a sealed-bid second-price auction.
• 진실이 dominant strategy라는 사실이 개념적으로 second-price auction 을 매우 깨끗하게 만든다.

- First-Price Auctions

• sealed-bid first-price auction에서 입찰자의 가격은 이길지 말지에 영향을 주지 않지만 낙찰 시점에 얼마나 지불할 지에는 영향을 준다.
• 결과적으로, 이전 섹션에서 언급한 대부분이 재수행되어야만 하고, 결론은 다르게 나온다. 만약 입찰자 i의 가격 bi가 winning bid가 아니라면, payoff = 0이다. 반대로 winning bid이면, 그 때 payoff는 vi - bi 이다. 주목해야할 첫번째는 true value로 입찰하는 것은 더 이상 dominant strategy가 아니다. true value로 입찰함으로써 낙찰하지 못할 경우 payoff=0이 되고, 이겨도 payoff=0이기 때문이다.
• 입찰하는 최적화된 방법은 입찰가 bi를 조금씩 깎는 것이다. 그렇게 해서 이긴다면 payoff (>0)를 얻을 수 있다. 입찰가를 얼마씩 줄일지는 두 개의 반대 세력 사이에서 trade-off를 균형을 맞추는 것을 포함한다. true value에 너무 가깝게 입찰을 한다면, 이겨도 payoff가 크지 않다. 그러나 true value에서 멀어질수록 이겼을 때 payoff가 증가하게 된다. 그 때 높은 입찰가일 확률을 줄인다. 두 요소 사이에 trade-off를 최적화하는 법은 다른 입찰자들과 그들이 제시할 값들의 분포에 대한 지식에 의존하는 복잡한 문제이다. 예를 들어, 사람이 많을 수록 입찰가격이 증가할 확률이 더 높다. 따라서 입찰 시 이보다 더 높은 가격을 제시할 필요가 있다.

- 공통값을 가지고 경매하는 것과 승자의 저주

• 지금까지 입찰자가 제시하는 가격이 경매가 되는 동안 독립적이라는 사실을 가정했다. 각 입찰자는 자신만의 가격만 알고 있고, 다른 이들이 얼마나 가격을 제시했는지 고려하지 않는다. 이것은 많은 상황에서 이치에 맞지만, 입찰자들이 물건을 재판매하려는 환경에는 분명히 적용되지 않는다. 이 경우, 물체에 대한 공통의 최종 값이 있다. 재판매 시 발생하는 양이지만 반드시 알 필요는 없다. 각 입찰자 i는 이 공통값의 추정인 vi를 알아내기 위해 몇 가지 사적인 정보를 가질 수도 있다. 개개인의 추정은 전형적으로 약간 잘못될 것이고 그들은 또한 전형적으로 서로서로 독립적이지 않을 것이다. 이러한 추정에 있어 가능한 모델은 true value를 v라고 가정하고, 각 입찰자 i의 추정 vi는 vi = v + xi 에 의해 정의되어진다. 여기서 xi는 i의 추정값에서 오차를 나타내며 평균 0인 랜덤 값이다.

낙찰 시, 공통 값보다 over-estimated 인 가격을 지불했을 가능성이 높으면 낙찰 받은 물건을 되팔 때 손해를 볼 수 있다.

- Seller Revenue(판매자 수익)

• first-price와 second-price 경매 방식에서 판매자가 만들 수 있는 기대할만한 이득을 비교하는 방법
  • 2가지 경쟁적인 요소가 있다. second-price auction에서 판매자는 두번째로 가장 높은 입찰가를 청구해야 하므로, 명확히 돈을 덜 모으기로 한다. first-price auction에서 입찰자는 가격을 줄이고, 판매자가 모을 수 있는 금액도 줄인다.
• 어떻게 이러한 반대 요소가 서로서로 trade-off 되는지 이해하기 위해, [0,1] 간격에서 균등 분포하는 독립적인 값들을 가진 n명의 입찰자를 고려해보자. 판매자의 수익이 가장 높은 값과 두번째로 높은 입찰가를 기반으로 할 것이기 때문에 이러한 질적인 측면에서 기댓값을 알 필요가 있다. 기댓값을 계산하는 것은 복잡하나 아래에 단순한 답이 있다.

입찰자의 true value는 n/(n+1)이었다. 여기에 (n-1)/n 을 곱하는 것은 입찰가를 깎는다는 의미

결국 판매자 수익의 기댓값은 (n-1)/(n+1)