비크리 경매

Vickrey auction

빅리 경매 또는 밀봉 입찰 2차 경매(SPSBA)는 밀봉 입찰 경매의 일종이다. 입찰자들은 경매에 나온 다른 사람들의 입찰 사실을 모른 채 서면 입찰서를 제출한다. 가장 높은 입찰자가 이기지만 지불된 가격이 두 번째로 높은 입찰이다. 이러한 유형의 경매는 전략적으로 영국의 경매와 유사하며 입찰자들에게 그들의 진짜 가치를 입찰할 동기를 부여한다. 이 경매는 1961년[1] 컬럼비아대 교수 윌리엄 비크리에 의해 처음 학문적으로 묘사되었지만, 1893년 이후 우표 수집가들에 의해 사용되었다.[2] 1797년 요한 볼프강괴테는 밀봉된 입찰의 2가 경매를 이용하여 원고를 팔았다.[3]

비크리의 원본 논문은 주로 분리할 수 없는 단 하나의 상품만이 판매되고 있는 경매를 고려했다. 비크리 경매와 2차 가격 밀봉 입찰 경매라는 용어는 이 경우 동등하고 상호간에 사용된다.[clarification needed] 동일한 상품이 여러 개일 경우 입찰자가 역수요곡선을 제출하고 기회비용을 지불한다.[4]

비크리 경매는 경제 문헌에서는 많이 연구되지만 실제론 흔치 않다. 구글과 야후'의 온라인 광고프로그램에서[5][6] 사용되는 일반화된 2차 경매, 비크리-클라크-그로브 경매(인센트럴 호환이 아님)와 같이 복수 경매에 대한 Vickrey 경매의 일반화된 변형들이 존재한다.

특성.

자가 보상 및 인센티브 호환성

개인 가치가 있는 빅리 경매에서 각 입찰자는 판매 품목에 대한 가치평가를 입찰(재매각)하여 기대 효용성을 극대화한다. 이러한 유형의 경매는 때때로 기관담보부증권(MBS) 시장에서 특정 풀 거래에 사용된다.

사후효율

Vickrey 경매는 가장 일반적인 상황에서 의사결정이 효율적이다([citation needed]승자가 가장 높은 평가를 받는 입찰자임). 따라서 다른 경매 유형의 효율성 특성을 입증할 수 있는 기준 모델을 제공한다. 판매자가 "플레이어 제로"로 포함되면 사후 효율적(0과 동일한 이전 합계)일 뿐이며, 이들의 이전은 다른 플레이어의 이전 이전 이전(즉, 입찰) 합계의 부정적인 것과 같다.

약점

  • 그것은 순차적인 경매 없이 구매자가 자신의 가치에 대해 확신이 서지 않는 경우, 즉 시장가격의 발견을 허용하지 않는다.
  • 판매자들은 이익을 증가시키기 위해 실링 입찰 방식을 사용할 수 있다.

Vickrey-Clarke-Groves(VCG) 메커니즘에는 다음과 같은 추가적인 단점이 있다.

  • 입찰 담합에 취약하다. 빅리 경매의 모든 입찰자들이 서로의 가치를 공개한다면, 그들은 경매에서 누가 이겼는지 보존하면서 그들의 가치의 일부 또는 전부를 낮출 수 있다.[7]
  • 경매에서 구매자가 자신의 이익을 극대화하기 위해 여러 명의 신원을 사용하는 실 입찰 버전에 취약하다.[8]
  • 그것은 반드시 판매자 수익을 최대화하는 것은 아니다; 판매자 수익은 VCG 경매에서 0일 수도 있다. 경매의 개최 목적이 단순히 구매자 간에 자원을 배분하는 것이 아니라 판매자의 이익을 최대화하는 것이라면 VCG는 좋지 않은 선택일 수 있다.
  • 판매자의 수익은 입찰자와 제안의 집합과 관련하여 단조롭지 않다.

입찰에 관한 판매자 수익의 비단조성(이 기사 하단에 기술된 VCG 기회비용 메커니즘을 도입하지 않은 경우)은 다음 예시로 나타낼 수 있다. 입찰자 A, B, C 세 개와 입찰자 Y, Z 두 개 동종 품목을 고려해 보십시오.

  • A는 두 가지 물건을 모두 원하며 Y와 Z의 패키지에 대해 2달러를 입찰한다.
  • B와 C는 둘 다 하나의 아이템에 대해 각각 2달러씩 입찰했다(Y나 Z는 2달러씩 입찰). 그들은 정말로 한 아이템을 원하지만 두 번째 아이템이 있든 상관하지 않기 때문이다.

지금은 Y와 Z를 B와 C에 할당하고 있지만 가격은 B와 C를 각각 제거하면 알 수 있듯이 0달러다. 만약 C가 2달러 대신 0달러를 입찰한다면, 판매자는 0달러 대신 2달러를 벌 것이다. 입찰이 증가하거나 감소할 때 판매자의 수익이 증가할 수 있기 때문에, 판매자의 수익은 입찰과 관련하여 단조롭지 않다.

진실된 입찰의 지배 증거

비크리 경매에서 분리할 수 없는 단일 품목을 가진 지배적인 전략은 각 입찰자가 그 품목의 진정한 가치를 입찰하는 것이다.[9]

을(를) 해당 품목에 대한 i의 가치로 입찰하도록 하십시오. 를 내가 입찰한 품목에 입찰하도록 하라. The payoff for bidder i is

과대입찰 전략은 진실하게 입찰하는 것이 지배적이다. 입찰자 i가 b > v 을(를) 입찰한다고 가정합시다

만약 < i\ v i {\i}(가) 있다면, 입찰자는 과대 입찰뿐만 아니라 진실된 입찰로 그 품목을 따낼 것이다. 입찰 금액은 보답을 변경하지 않으므로 이 경우 두 전략은 동일한 보답을 갖는다.

j ib > i i 경우 입찰자는 어느 쪽이든 품목을 잃게 되므로 이 경우 전략이 동등한 보상을 받게 된다.

i < i b b { b i{\i} 경매에서 낙찰될 것이다. 진실한 입찰에 대한 보상은 영(0)인 반면, 그들이 상품의 가치보다 더 많이 지불했기 때문에 초과 입찰 전략에 대해 보상은 부정적일 것이다. 따라서 자신의 진정한 가치평가보다 더 높은 가격을 입찰하는 전략은 진실하게 입찰하는 전략이 지배한다.

저가매수 전략은 진실하게 입찰하는 것이 지배적이다. 입찰자가 < v < v i 를 입찰한다고 가정합시다

j > v i(가) 있는 경우 입찰자는 저매입뿐만 아니라 진실한 입찰로 품목을 잃게 되므로 전략이 이 경우에 동일한 보상을 받게 된다.

만약 < b b {\ i(가) 있다면, 입찰자는 어느 쪽이든 해당 항목을 낙찰하여 이 경우 전략이 동등한 보상을 받게 된다.

< < i v i i} 경매에 당첨될 것이다. 진실한 전략에 대한 보상은 그들이 아이템의 가치보다 적게 지불했기 때문에 긍정적일 것이고, 반면에 저가 입찰에 대한 보상은 제로일 것이다. 따라서 저입찰 전략은 진실하게 입찰하는 전략이 지배한다.

진실한 입찰은 다른 가능한 전략(과소입찰과 과대입찰)을 지배하기 때문에 최적의 전략이다.

Vickrey 경매와 봉인된 첫 번째 가격 경매의 수익 균등성

가장 흔한 두 경매는 밀봉된 첫 번째 가격(또는 고가의) 경매와 공개 상승 가격(또는 영어) 경매다. 전자의 경우, 각 구매자는 밀봉된 입찰서를 제출한다. 입찰자는 그 물건을 낙찰받고 입찰에 응한다. 후자에는 경매인이 연속적으로 높은 호가를 발표하고 아무도 더 높은 호가를 받아들이지 않을 때까지 계속된다. 구매자의 평가액이 v 이고 현재 가 b 이라고 가정해 보자 < {\라면 구매자는 손을 들어 패한다 > 구매자가 현재의 고 입찰자가 아니라면 다른 사람을 낙찰자가 되게 하는 것보다 입찰하는 것이 더 이득이다. 따라서 매수자는 호가가 자신의 가치평가에 도달할 때 입찰에서 탈락하는 것이 지배적인 전략이다. 따라서 비크리가 밀봉한 2차 가격 경매에서와 마찬가지로, 가장 높은 평가를 받은 구매자가 지불한 가격은 두 번째로 높은 가치와 같다.

밀봉된 2차 가격 경매에서 예상 지불액을 고려하십시오. 으로 구매자들이 지배적인 전략 평가 v와 함께 상대방의 가치)<>{\displaystyle v}, v{\displayst를 이기는 구매자에 따르면 입찰을 하고 비크리 및 지원[0,1]{\displaystyle[0,1]}과 균일 분포에서 각 구매자의 값이 있었던 독립적인 무승부 거라고 추정했습니다. 2구매자들의 사례로 인식되었다.yl 이(가) 높은 값이라고 가정하십시오. 그러면 당첨금이[ 간격으로 균일하게 배분되므로 당첨자의 예상 지급액은 다음과 같다.

)= 1 .

이제 밀봉된 첫 번째 가격 경매에서 v 을(를) 가진 구매자의 균형 입찰은 다음과 같음을 주장한다.

( v)= ( v)= 1 {.

즉, 밀봉된 제1가 경매에서 낙찰자의 지불은 밀봉된 제2가 경매에서 예상되는 수입과 같다.

수입등가증서

전략 )= / 2 에 따라 구매자 2가 입찰한다고 가정합시다 여기서 은 평가 v 에 대한 구매자의 입찰이다 우리는 구매자 1의 최선의 답변이 동일한 전략을 사용하는 것임을 보여줄 필요가 있다.

먼저 구매자 2가 전략 B()=v / B(를) 하는 경우 구매자 2의 최대 입찰은 B( )=1/ B이므로 구매자 1은 1/2 이상의 입찰로 확률 1로 승리한다는 점에 유의하십시오. / 간격으로 입찰 을(를) 고려하십시오 구매자 2의 값은 x이(가) 되도록 하십시오 다음 B x)= / < x< 균일하게 분포된 값에 대한 비크리의 가정 하에서 승리 확률은 ( )= 2 = w이다 따라서 구매자 1의 예상 보수는 다음과 같다.

( ) 은(는) = / = 에서 최대값을 차지한다는 점에 유의하십시오

네트워크 라우팅에서 사용

네트워크 라우팅에서 VCG 메커니즘은 부가가치 개념에 기초한 지급 체계 모음입니다. 네트워크 라우팅에서 VCG 메커니즘의 기본 개념은 솔루션의 일부인 각 링크나 노드(네트워크 모델에 따라 다름)의 소유자에게 공시가격과 부가가치를 지불하는 것이다. 많은 라우팅 문제에서, 이 메커니즘은 전략적으로 입증될 뿐만 아니라, 모든 전략적으로 입증되는 메커니즘들 중에서 최소한이다.

네트워크 흐름, 유니캐스트 또는 멀티캐스트의 경우, 그래프 G의 최소 비용 흐름(MCF)은 각 링크의 신고 비용k d에 기초하여 계산되며 지급액은 다음과 같이 계산된다.

MCF의 각 링크(또는 노드) 가 지급됨

= + M F( - e )- M F( G)

여기서 MCF(G)는 그래프k GG - ek 링크 e가 없는 그래프 G를 나타낸다. MCF에 없는 링크는 무보수로 지급된다. 이 라우팅 문제는 VCG가 전략적으로 입증 가능하고 최소인 경우 중 하나이다.

2004년에, 예상 VCG 과지급이 노드와 에지 확률 p, G( ) style 접근하는 것으로 나타났다.

n으로, = n에 대해 \script 에 접근한다 이 결과 이전에 G(n, p)에서 VCG 과지불금이 발생하는 것으로 알려졌다.

그리고

아주 가능성이 높은

일반화

복수 상품이나 분할 상품에 대한 가장 분명한 일반화는 모든 낙찰자들이 가장 높은 낙찰되지 않은 입찰 금액을 지불하도록 하는 것이다. 이것은 획일적인 가격 경매로 알려져 있다. 그러나 균일가 경매는 각 입찰자가 단 하나의 단위에 대한 요구가 없는 한 입찰자가 2차 경매에서와 같이 그들의 진정한 가치를 입찰하는 결과를 가져오지는 않는다. 진실하게 입찰하기 위한 동기를 유지하는 Vickrey 경매의 일반화는 Vickrey-Clarke-Groves (VCG) 메커니즘으로 알려져 있다. VCG의 아이디어는 유틸리티의 합계를 극대화하기 위해 아이템을 할당하고, 각 입찰자가 다른 모든 참가자들에게 소개한 "기회비"를 지불한다는 것이다. 입찰자에 대한 이 기회비용은 첫 번째 입찰자가 입찰하지 않았다면 낙찰되었을 다른 모든 입찰자의 총 입찰에서 다른 모든 실제 낙찰자의 총 입찰액을 뺀 값으로 정의된다.

다른 종류의 일반화는 예약 가격, 즉 해당 품목이 전혀 판매되지 않는 최저 가격을 정하는 것이다. 어떤 경우에는 예약가격을 정하면 경매인의 수익이 실질적으로 증가할 수 있다. 이것은 베이지안-최적 메커니즘 설계의 예다.

참고 항목

참조

  • Vijay Crishna, 옥션 이론, Academic Press, 2002.
  • 피터 크램턴, 요아프 쇼엄, 리처드 스타인버그(Eds), 콤비네토리얼 경매, MIT 프레스, 2006년 1장 ISBN0-262-03342-9.
  • Paul Milgrom, 2004년 케임브리지 대학 출판부의 경매 이론 작업에 착수.
  • Teck Ho, "소비 및 생산" UC 버클리, 2010년 Haas Class of 2010.

메모들

  1. ^ Vickrey, William (1961). "Counterspeculation, Auctions, and Competitive Sealed Tenders". The Journal of Finance. 16 (1): 8–37. doi:10.1111/j.1540-6261.1961.tb02789.x.
  2. ^ Lucking-Reiley, David (2000). "Vickrey Auctions in Practice: From Nineteenth-Century Philately to Twenty-First-Century E-Commerce". Journal of Economic Perspectives. 14 (3): 183–192. doi:10.1257/jep.14.3.183.
  3. ^ Benny Moldovanu and Manfred Tietzel (1998). "Goethe's Second-Price Auction". The Journal of Political Economy. 106 (4): 854–859. CiteSeerX 10.1.1.560.8278. doi:10.1086/250032. JSTOR 2990730.
  4. ^ Jones, Derek (2003). "Auction Theory for the New Economy". New Economy Handbook. Emerald Publishing Ltd. ISBN 978-0123891723.
  5. ^ 벤자민 에델만, 마이클 오스트롭스키, 마이클 슈바르츠: "인터넷 광고와 일반화된 2차 가격 경매: 수십억 달러 상당의 키워드 판매" American Economic Review 97(1), 2007 페이지 242–259.
  6. ^ Hal R. Varian: "위치 경매". International Journal of Industrial Organization, 2006, doi:10.1016/j.ijindorg.2006.10.002 .
  7. ^ "Vickrey Auction". maxi-pedia.com.
  8. ^ 로렌스 M. 아우수벨, 그리고 폴 밀그롬. Lovely but Lonely Vickrey 옥션. 조합 경매, MIT 출판사, 2006, 1장, 페이지 12.
  9. ^ von Ahn, Luis (30 September 2008). "Auctions" (PDF). 15–396: Science of the Web Course Notes. Carnegie Mellon University. Archived from the original (PDF) on 8 October 2008. Retrieved 6 November 2008.