이연인수경매

Deferred-acceptance auction
다음에 대한 시리즈 일부
경매
Auction Room, Christie's, circa 1808.
종류들
입찰
컨텍스트
이론
온라인.

이연인수경매(DAA)는 가장 매력적이지 않은 입찰을 반복적으로 거부해 할당이 선택되는 경매다. 그것은 무선 스펙트럼 재분배 경매와 같은 복잡한 경매에 특히 적합하게 만드는 전략적 속성을 가진 진실된 메커니즘이다.[1]

예

정부가 다음 두 가지 영역에서 방송권을 판매하려고 한다고 가정합시다. 남북. 세 명의 요원이 이러한 권리를 두고 경쟁한다.

  • 앨리스는 두 분야 모두 필요하며, 그들을 3백만 달러로 소중히 여긴다.
  • 밥은 북한만 있으면 되고, 그것을 100만 달러로 평가한다.
  • 칼은 남방만 있으면 되고, 백만 달러는 된다.

정부는 사회 복지를 극대화하기를 원한다. 이 경우 앨리스에게 모든 권리를 주거나(복지=3), 북쪽을 밥에게, 남쪽을 칼에게 주거나(복지=2). 평가액은 대리점들의 사적인 정보인 만큼 정부는 대리점들이 자신의 진정한 가치를 밝히도록 유도하기 위해 진실된 메커니즘을 사용할 필요가 있다. 우리는 두 종류의 진실된 메커니즘을 비교한다.

비크리-클라크-그로브스 솔루션

Vickrey-Clarke-Groves (VCG) 알고리즘은 사회적으로 최적화된 할당을 찾는데, 이는 앨리스에게 두 영역 모두를 주는 것이다. 앨리스는 다른 요원들에게 부과하는 외부성에 따라 결정된 대가를 지불해야 한다. 이 경우 앨리스는 2백만 달러를 지불하는데, 그녀가 없었다면 밥과 칼의 복지는 2백만 달러가 되었을 것이기 때문이다. 밥과 칼은 아무것도 받지 않고 아무것도 지불하지 않는다.

이와 유사한 결과는 즉시 승인(또는 선취) 경매를 통해 이행될 수 있다. 이 경매는 여전히 유효하게 선정될 수 있는 최고 가치의 대리인을 반복적으로 받아들이고, 그들에게 문턱 지불(이기기 위해 그들이 했어야 할 최저 입찰)을 부과한다. 이 경우 앨리스가 먼저 선택되기 때문에 밥과 칼은 더 이상 선택할 수 없다. 앨리스는 그녀의 한계값인 100만 달러를 지불한다.

이연인수경매솔루션

2. 이연-수락 경매는 최적의 활성 에이전트 세트를 유지하면서 거부될 수 있는 최저가 에이전트를 반복적으로 거부한다. 그래서 칼이 먼저 거절당하고 밥이 먼저 거절당한다. 앨리스는 남았고 그녀는 받아들여졌다. 그녀는 100만 달러의 임계값을 지불한다.

두 가지 경매 유형은 모두 진실하다 - 어떤 대리인도 다른 가치를 보고해서는 얻을 수 없다. 그러나, 그들은 요원들이 연합을 형성할 수 있을 때 다르다. 밥과 칼이 함께 4백만 달러로 입찰가를 올렸다고 가정하자. 이제 VCG 경매는 밥과 칼의 값을 받아 각각 0의 가격을 부과할 것이다(각각 앨리스에게 할당하는 데 아무런 영향을 주지 않기 때문이다! 대조적으로, DAA는 앨리스를 거절한 다음, 밥과 칼을 받아들이고, 각각 3백만 달러인 그의 임계값을 부과할 것이다. 그래서 그들은 그들의 오보로부터 아무것도 얻지 못한다. (사실, 그들은 2백만 달러를 잃는다.

참고 항목

2014년 스탠퍼드대 경제학자인 폴 밀그롬과 일리야 시걸이 이연수 경매 실적을 분석했다.[2] 같은 해 팀 러프가든을 포함한 당시 스탠포드 컴퓨터 과학 연구자들이 이중 경매 환경에 이 아이디어를 적용한 것이 윤곽을 드러냈다.[3]

관련기사

참조

  1. ^ Paul Milgrom and Ilya Segal (2014). "Deferred-Acceptance Auctions and Radio Spectrum Reallocation" (PDF). Retrieved 8 August 2016.
  2. ^ Dütting, Paul; Gkatzelis, Vasilis; Roughgarden, Tim (2014). "The performance of deferred-acceptance auctions". Proceedings of the fifteenth ACM conference on Economics and computation - EC '14. p. 187. doi:10.1145/2600057.2602861. ISBN 9781450325653.
  3. ^ Dütting, Paul; Roughgarden, Tim; Talgam-Cohen, Inbal (2014). Modularity and Greed in Double Auctions. Proceedings of the 15th Conference on Economics and Computation (EC'14). pp. 241–258. doi:10.1145/2600057.2602854. ISBN 9781450325653.