비크리-클라크-그로브스 경매

다음에 대한 시리즈 일부
경매
종류들
올페이 암스테르담 앵글로 더치 물물교환 더블 베스트/비 베스트 브라질의 캘커타 양초 중국어 클릭박스 입찰 콤비네토리얼 공통값 이연수락 차별가격 더블 네덜란드어 영어 앞으로 프랑스어 일반화 1차 가격 일반화 2차 가격 일본인입니다 다중 속성 멀티유닛 저장 안 함 순위 역행 스코틀랜드의 밀봉1가 동시상승 단가 신호등 균일가격 고유입찰 수익가액 비크리 비크리-클라크-그로브스 왈라시안 양키
입찰
음영 칼로리치탄티스 취소사냥 점프 연결 스니핑 자살 암묵적 담합
컨텍스트
알고리즘 오토스 예술 자선 아이들. 크리켓 선수 도메인 이름 꽃들 대출 사기 노예 스펙트럼 우표 처녀성 와인 와이프즈
이론
디지털 상품 무정부 상태 가격 수익균등도 승자의 저주
온라인.
에비딩 민간전자시장 소프트웨어
v t

비크리-클라크-그로브스(VCG) 경매는 여러 품목의 밀봉입찰 경매의 일종이다. 입찰자들은 다른 입찰자들의 입찰에 대해 알지 못한 채, 해당 항목에 대한 자신의 평가액을 보고하는 입찰서를 제출한다. 경매제도는 각 개인이 야기하는 위해를 다른 입찰자에게 부과하는 사회적 최적 방식으로 그 품목을 할당한다.^[1] 그것은 각 입찰자에 대한 최적의 전략이 품목에 대한 진정한 가치를 입찰하는 것임을 보장함으로써 입찰자에게 진정한 가치를 입찰할 동기를 부여한다. 특히 단일 입찰자가 서로 다른 이름으로 여러 차례 입찰함으로써 해당 품목을 낙찰받을 수 있다. 여러 품목에 대한 빅리 경매의 일반화다.

이 경매는 윌리엄 비크리,^[2] 에드워드 H. 클라크,^[3] 그리고 테오도르 그로브스의^[4] 논문에서 이 아이디어를 연속적으로 일반화한 이름을 따왔다.

VCG 경매는 보다 일반적인 VCG 메커니즘의 특정한 사용이다. VCG 경매는 사회적 최적 품목 할당을 위해 노력하는 반면, VCG 메커니즘은 가능한 일련의 결과 중에서 사회적으로 최적의 결과를 선택할 수 있도록 한다. 입찰자들 간에 담합이 발생할 가능성이 높은 경우 VCG는 판매업자를 위해 생산된 수익과 배분 효율성 모두에서 일반화된 2차 가격 경매를 능가한다.^[5]

직관적 설명

동일한 제품 세트가 판매되고 있는 경매를 생각해 보십시오. 입찰자들은 그들이 N 제품을 받기 위해 지불할 의향이 있는 최대 가격을 발표함으로써 경매에 참여할 수 있다. 총 수령 대수에 따라 단위당 지불 의지가 다를 수 있기 때문에 각 구매자는 둘 이상의 입찰 신고를 할 수 있다. 입찰자는 밀봉되어 있기 때문에(경매시스템에서만 볼 수 있음) 어느 순간에도 다른 사람의 입찰을 볼 수 없다. 일단 입찰이 모두 이루어지면 경매는 마감된다.

그 후 가능한 모든 입찰 조합은 경매 시스템에 의해 고려되며, 경매 총합계를 최대화하는 것을 유지하며, 구매 가능한 제품의 총량을 초과하지 않고 각 입찰자의 최대 1개의 입찰가를 사용할 수 있다는 조건이다. 입찰에 성공한 입찰자는 입찰에 명시된 제품 수량을 받는다. 그러나 그들이 교환으로 지불하는 가격은 처음에 입찰했던 금액이 아니라 그들의 입찰이 다른 입찰자들에게 야기시킨 한계적 손해일 뿐이다(최소한 그들의 원래 입찰 금액만큼 높다).

다른 참가자에게 야기되는 이러한 한계 피해(즉, 각 개인이 성공적인 입찰로 지불한 최종 가격)는 다음과 같이 계산할 수 있다: (고려 중인 참가자를 제외한 입찰의 최선의 조합에서 경매 낙찰의 합계) - (현재 (최우수) 입찰 조합에서 다른 낙찰자가 입찰한 것. 두 번째로 좋은 입찰 조합의 입찰 합계가 가장 좋은 조합의 입찰 합계와 같다면, 구매자가 지불한 가격은 그들의 최초 입찰과 동일할 것이다. 다른 모든 경우에서, 구매자들이 지불하는 가격은 더 낮아질 것이다.

경매가 끝날 무렵, 모든 상품이 결합 의지가 가장 높은 사람들에게 귀속되었기 때문에 총 효용성은 극대화되었다. 대리인이 충분히 합리적이고 담합이 없는 경우, 다른 입찰자에게 미치는 한계 피해만 각 참가자에게 부과되기 때문에 지불 의사가 진실하게 보고되었다고 가정할 수 있으며, 이는 진실된 보고가 약하게 지배적인 전략이라고 할 수 있다. 그러나 이러한 유형의 경매는 두 번째 최선의 입찰 조합의 입찰 합계가 가장 좋은 입찰 조합의 입찰 합계와 같지 않는 한 판매자의 수익을 극대화하지 못할 것이다.

형식 설명

표기법

For any set of auctioned items ${\displaystyle M=\{t_{1},\ldots ,t_{m}\}}$ and any set of bidders ${\displaystyle N=\{b_{1},\ldots ,b_{n}\}}$, let ${\displaystyle V_{N}^{M}}$ be the social value of the VCG auction for a given bid-combination. 즉, 각 개인이 방금 획득한 아이템을 얼마나 소중히 여기는지, 모든 사람에게 합산한 것이다. 그들이 이기지 못하면 아이템의 가치는 0이다. 입찰자 $b{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$와 $항목{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ j ${\$의 경우$,$ 해당 항목에 대한 입찰자가 v ${\displaystyle i_{}}$(${\displaystyle {}_{}}$ ${\displaystyle j_{}}$ $){\displaystyle v_{i}(t_{j})$가 되도록 한다$.$ $표기법{\displaystyle }$ A ${\displaystyle \setminus }$ ${\displaystyle B}$ ${\displaystyle A\setminus B}$은 B의 요소가 아닌 A의 요소 집합을 의미한다$$.

과제

A bidder ${\displaystyle b_{i}}$ whose bid for an item ${\displaystyle t_{j}}$ is an "overbid", namely ${\displaystyle v_{i}(t_{j})}$, wins the item, but pays ${\displaystyle V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{$$i}\}^{M\setminus \{t_{j$ 이것은 나머지 요원들이 부담하는 승부의 사회적 비용이다.

설명

Indeed, the set of bidders other than ${\displaystyle b_{i}}$ is ${\displaystyle N\setminus \{b_{i}\}}$. When item ${\displaystyle t_{j}}$ is available, they could attain welfare ${\displaystyle V_{N\setminus \{b_{i}\}}^{M}.}$ The winning of the item by ${\displaystyle b_i}$${\displaystyle b_{i}}$ reduces the set of available items to ${\displaystyle M\setminus \{t_{j}\}}$, however, so that the attainable welfare is now ${\displaystyle V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}}$. 따라서 두 가지 복지수준의 차이는, $당첨자{\displaystyle {}_{}}$ b ${\$가 $t{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$를 얻었다는 점을 감안할 때, 예상대로 나머지 입찰자가 겪는 달성 가능한 복지의 손실이다$.$ 이 수량은 나머지 에이전트의 제공에 따라 달라지며 에이전트 $b{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$에게 알려져 있지 않다$.$

승자의 효용

The winning bidder whose bid is the true value ${\displaystyle A}$ for the item ${\displaystyle t_{j}}$, ${\displaystyle v_{i}(t_{j})=A,}$ derives maximum utility ${\displaystyle A-\left(V_{N\setminus \{b_{i}\$$}}}^{M}-V_{N\setminus \{b_{i}\}}\}^{M\setminus \{t_{j}\}}\오른쪽).$$}$

예

2개 품목, 3개 입찰자

세 입찰자들 사이에서 두 개의 사과가 경매에 부쳐지고 있다고 가정해보자.

• 입찰자 A는 사과 한 개를 원하며 기꺼이 5달러를 지불할 것이다.
• 입찰자 B는 사과 한 개를 원하며 기꺼이 2달러를 지불할 것이다.
• 입찰자 C는 사과 두 개를 원하며 두 개를 모두 갖기 위해 6달러를 지불할 용의가 있지만 다른 한 개만 사지 않고 사는 데는 관심이 없다.

첫째로, 경매의 결과는 입찰의 최대화로 결정되는데, 5달러 + 2달러 = 7달러의 합계가 6달러만 지불할 의향이 있는 입찰자 C의 사과 두 개에 대한 입찰보다 크기 때문이다. 따라서 경매 이후 입찰자 A가 달성한 가치는 5달러, 입찰자 B가 달성한 가치는 2달러, 입찰자 C가 획득한 가치는 0달러(C가 얻는 것이 없기 때문에)이다. 승자의 결정은 본질적으로 배낭 문제라는 점에 주목하라.

다음으로 지급 결정을 위한 공식은 다음과 같다.

• 입찰자 A: A가 요구하는 낙찰 대금은 다음과 같이 결정한다. 첫째로, 입찰자 A를 제외한 경매에서, 사회 복지 극대화의 결과는 두 사과를 모두 입찰자 C에게 총 6달러의 사회적 가치를 부여할 것이다. 다음으로, A의 값을 제외한 원래의 경매의 총 사회적 가치는 $7 - $5 = $2로 계산된다. 마지막으로 첫 번째 값에서 두 번째 값을 뺀다. 따라서 A에 필요한 지급액은 $6 - $2 = $4이다.
• 입찰자 B: 위와 유사하게, 입찰자 B를 제외한 경매의 가장 좋은 결과는 두 사과를 모두 6달러에 입찰자 C에게 할당한다. 원래 경매에서 B의 몫을 뺀 사회적 가치는 총 5달러다. 따라서 B에 필요한 지급액은 $6 - $5 = $1이다.
• 마지막으로, 입찰자 C에 대한 지불은 (5달러 + 2달러) - (5달러 + 2달러) = 0달러다.

경매 후, A는 이전보다 1달러가 더 잘 나간다(공과금 5달러를 얻기 위해 4달러를 지불하는 것), B는 이전보다 1달러가 더 잘 나간다(공과금 2달러를 얻기 위해 1달러를 지불하는 것), C는 중립적이다(아무것도 당첨되지 않은 것).

입찰자 2명

$b$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$$},$ ${\displaystyle {b\mathrm{}}_{}}$ 2 {\$displaystyle$ $b_$${2$}},$$$t{\displaystyle {}_{}}$ 1 ${\$ $t$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ 2개의 입찰자가 있다고 가정하고, 각 입찰자는 1개의 품목을 획득할 수 있다. We let ${\displaystyle v_{i,j}}$ be bidder ${\displaystyle b_{i}}$'s valuation for item ${\displaystyle t_{j}}$. Assume ${\displaystyle v_{1,1}=10}$, ${\displaystyle v_{1,2}=5}$, ${\displaystyle v_{2,1}=5}$, and ${\$$displaystyle v_{2,2}=3$ $우리$는 b 1 ${\$ b ${\displaystyle {2\mathrm{}}_{}}$ ${\$모두 t ${\displaystyle 1_{}}$을 받는 것을 선호하지만$,$ 사회적으로 최적의 할당으로 t ${\displaystyle 1_{}}$을$입찰자$ b 1 {\$displaystyt_{1$}에 부여한다($$따라서 $v1}).$alue는 ${\displaystyle 10}$ ${\displaystyle 10$이고 t $2{\displaystyle {}_{}}$ ${\$ 입찰자$$ $b{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}($$따라서 달성된 가치는 $3{\displaystyle \mathrm{}}$ ${\displaystyle 3}).$ 따라서 달성된 총 값은 ${\displaystyle 13}$ $[\displaystyle 13$ 이므로 최적이다.

사람 $b{\displaystyle {}_{}}$ ${\$}}명이 경매에 나오지 않았다면$$$,$ 사람 b 1 ${\$$displaystyle t_{1$}에 여전히 사람 $b{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$${\$displaystytle t_$\{$1}에 ${\displaystyle {할당}_{}}$되었을 것이고$$, 따라서 $사람{\displaystyle {}_{}}$ b ${\displaystyle {1\mathrm{}}_{}}$ ${\$1}는 더 이상 얻을 수 없다$$. 현재 결과는 ${\displaystyle 10}$ ${\displaystyle 10}$이다$.$ 따라서 ${\displaystyle {b\mathrm{}}_{}}$ 2 ${\$ ${\displaystyle 10}$- ${\displaystyle 10}$= ${\displaystyle 0}$ {\$displaystyle 10-10=0}$이(가$)$ 충전된다$.$

사람 $b{\displaystyle {}_{}}$ ${\$}이 경매에 나오지$$ 않은 경우 $t{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$1}가 ${\displaystyle {b\mathrm{}}_{}}$ 2 ${\$$2$}}에 할당되고$$ 평가 $5{\displaystyle \mathrm{}}$ ${\displaystyle 5}$가 된다$.$ 현재 결과는 3이므로 b $1{\displaystyle {}_{}}$ ${\$}가 5${\displaystyle }$- 3${\displaystyle }$= 2 ${\displaystyle 5-3=2$} 충전됨$.$

예 #3

$각각{\displaystyle }$ 집을 한 채씩 받는 n ${\displaystyle n}$ 입찰자에게$$ n ${\displaystyle n}$주택의$$ 경매를 고려하십시오. ${\displaystyle {\stackrel{}{v}}_{}}$~ ${\displaystyle i_{}}$ ${\displaystyle j_{}}$ ${\$은$($는) $하우스{\displaystyle }$ j ${\displaystyle$ $j}$에 대해$$ 갖는 가치플레이어 $i{\displaystyle }$ ${\displaystyle$ $i}$을(를) 나타내며$,$ 가능한 결과는 사람과 집을 페어링하는 초당적 매칭으로 특징지어진다. 우리가 그 가치를 안다면, 사회 복지를 극대화하는 것은 최대 무게 양분 매칭을 계산하는 것으로 줄어든다.

If we do not know the values, then we instead solicit bids ${\displaystyle {\tilde {b}}_{ij}}$, asking each player ${\displaystyle i}$ how much they would wish to bid for house ${\displaystyle j}$. Define ${\displaystyle b_{i}(a)={\tilde {b}}_{ik}}$ if bidder ${\$$displaystyle i$$}$이(가) ${\displaystyle a}$과(와) 일치하는$$ $하우스{\displaystyle }$ k ${\$$displaystyle$ a$^{*}$을(를) 수신함$$$.$ 이제 입찰에 대한 최대 중량 쌍당 $일치인$${\displaystyle {\ast }^{}}$ ${\$ a^}을(를) 계산하고 계산함

${\displaystyle p_{i}=\left[\max _{a\in A}\sum _{j\neq i}b_{j}(a)\right]-\sum _{j\neq i}b_{j}(a^{*})}$.

첫 번째 용어는 또 다른 최대 중량 초당적 매칭이며, 두 번째 용어는 $∗{\$ a$^{*}$에서 쉽게 계산할 수 있다$.$

진실된 입찰의 최적성

다음은 경매된 물건에 대해 자신의 진정한 가치를 입찰하는 것이 최적이라는 증거다.^[6]

각 입찰자 $b{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$에 대해$$v ${\displaystyle i_{}}$ ${\$를 항목 ${\displaystyle i_{}}$ ${\$$i}$에 대한 진정한 평가로$$ 간주하고, b ${\displaystyle i_{}}$ ${\$$i$$}}$가 $진정$한 평가서를 제출하는 즉시$$ ${\$에 이긴다고 가정한다. 그러면 b ${\displaystyle i_{}}$ ${\$가 획득한$$ 순 효용 ${\displaystyle U_{}}$ i ${\$는 자신이 획득한 품목에 대한 자체 평가에서 지불한 가격을 뺀 값으로 주어진다$$.

${\displaystyle {\reasoned}U_{i}&=v_{i}-\왼쪽(V_{N\setminus \{b_{i}\}\}^{M}-V_{N\setminus \{b_{i}\}^{M\setminus \{t_{i}\}\}\}\오른쪽)\\&=\sum _{j}v_{j}-\sum _{j\neq i}v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}-V_{N\setminus \{b_{i}\}}^{M}\\&=\sum _{j}v_{j}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}-V_{N\setminus \{b_{i}\}}^{M}\\&=\sum _{j}v_{j}-V_{N\setminus \{b_{i}\}.}^{M}\end{aigned}}}$

As ${\displaystyle V_{N\setminus \{b_{i}\}}^{M}}$ is independent of ${\displaystyle v_{i}}$, the maximization of net utility is pursued by the mechanism along with the maximization of corporate gross utility ${\displaystyle \sum _{j}v_{j}}$ for the declared bid ${\disp$$레이스타일 v_{i}}$.

To make it clearer, let us form the difference ${\displaystyle U_{i}-U_{j}=\left[v_{i}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right]-\left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right$$]}$ 진실된 입찰에 ${\displaystyle {따라}_{}}$ b i$$${\$의 순 효용 U $i {\$$displaystyle v_{$$}$과$($와) 입찰자 ${\displaystyle b_{}}$ i ${\$$displaystytle t_$${i}$ 사이의$$$$ $순{\displaystyle {}_{}}$ 효용 $U{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$$displaystystytype b_{i$$}}}$ 사이에 ]}}}}}}}}}}}이 있다.${\displaystyle v_{}}$ ${\displaystyle i_{}^{}}$$$${{\$$displaystyle t_{i}$ 항목에 대한$$ v ′{\displaystyle v$'_{i}}$는 ${\displaystyle {True}_{}}$ 유틸리티 $v{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ {\$displaystyle v_$${j}$에 항목 t j$$${\$$displaystytle$ $t_${j$}}}$를 얻었다$.$

${\displaystyle [}$ ${\displaystyle v{}_{}}$ ${\displaystyle j_{}}$+ ${\displaystyle {}_{}^{}}$ ${\displaystyle N_{}^{}}$ ${\displaystyle {\setminus }_{}^{}}${ ${\displaystyle {b_{}}_{}^{}}$ i${\displaystyle {{}_{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {\setminus }_{}^{}}${ t ${\displaystyle {j_{}}_{}^{}}$ ${\displaystyle {{}_{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$\setminus$\{t_{$j}\}\}\$rig}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$은(으)은(으)은(으)은(으(으 그러나 b ${\displaystyle i_{}}$ ${\$$displaystyle t_{j}$에 $t{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$$displaystyle t_{i}}$을(를) 할당하는 할당은 최대(참) 총 기업 효용을 얻는$$ ${\displaystyle t_{}}$ ${\displaystyle i_{}}$ ${\$에 할당하는 것과 다르다$$. Hence ${\displaystyle \left[v_{i}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right]-\left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right]\geq 0}$ and ${\displaystyle U_{i}\geq U_{j$$}}$Q$$.E.D.

참고 항목

• 비크리-클라크-그로브스 메커니즘
• 비크리 경매
• 선호도 표시

참조