순차 경매

순차 경매란 여러 품목이 차례로 같은 그룹의 잠재적 구매자에게 팔리는 경매다. 순차적 1가 경매(SAFP)에서는 개별 품목을 1가 경매를 이용해, 순차적 2가 경매(SASP)에서는 개별 품목을 2가 경매를 이용해 판매한다.

순차 경매는 많은 품목이 동시에 경매되고 대리인이 물건 묶음에 입찰할 수 있는 조합 경매와는 다르다. 순차 경매는 시행하기가 훨씬 더 간단하고 실제로 더 흔하다. 그러나 각 경매의 입찰자들은 향후 경매가 있을 것이라는 것을 알고 있으며 이는 그들의 전략적 고려에 영향을 미칠 수 있다. 여기 몇 가지 예가 있어요.

예 1.^[1] 판매 품목은 두 가지, 잠재 구매자는 두 가지다. 앨리스와 밥은 다음과 같은 가치를 지닌다.

앨리스는 각 항목을 5로, 두 항목 모두 10으로 평가한다(즉, 그녀의 평가는 가법적이다).
밥은 각 항목을 4로, 두 항목을 모두 4로 평가한다(즉, 그의 평가는 단위 수요).

SASP에서는 각 품목이 2차 가격 계산에 들어간다. 보통 그러한 경매는 진실된 메커니즘이기 때문에 각 품목이 분리되어 팔리면 앨리스는 두 품목을 모두 낙찰하고 각 품목에 대해 4를 지불하면 총 지불액은 4+4=8이고 순 효용은 5 + 5 - 8 = 2이다. 그러나 앨리스가 밥의 가치를 안다면 그녀는 더 나은 전략을 가지고 있다. 밥이 첫 번째 품목을 낙찰하게 할 수 있다. 그러면 밥은 2차 경매에 전혀 참여하지 않을 것이기 때문에 앨리스는 2차 경매에서 낙찰되어 0을 지불하게 되고, 순유효율은 5 - 0 = 5가 된다.

비슷한 결과가 SAFP에서 발생한다. 각 품목을 따로따로 팔면 앨리스가 4보다 약간 높게 입찰해 이기는 내시 평형이 있고, 순 효용성은 2보다 약간 낮다. 그러나 앨리스가 밥의 가치를 안다면 1라운드에서 밥이 승리할 수 있도록 하는 전략으로 이탈해 2라운드에서 0을 약간 넘는 가격에 승리할 수 있다.

예 2.^[2] 동일한 물건이 여러 개 경매되고, 대리점들은 예산 제약이 있다. 입찰자가 경쟁자가 지불한 가격을 인상하고 예산을 삭감하여 두 번째 물건을 더 낮은 가격에 얻을 수 있도록 하기 위해 하나의 물건에 공격적으로 입찰하는 것이 유리할 수 있다. 사실상, 입찰자는 다른 시장에서 우위를 점하기 위해 한 시장에서 "상대방의 비용을 인상"하고자 할 수 있다. 그러한 고려사항은 연방통신위원회가 실시하는 무선 주파수 면허 경매에 중요한 역할을 한 것으로 보인다. 경쟁 입찰자들의 예산 제약에 대한 평가는 GTE 입찰팀의 입찰 전 준비의 주요 요소였다.

나시 평형

순차 경매는 순차 게임의 특별한 경우다. 그런 게임을 요구하는 당연한 질문은 순수 전략(SPEPS)에 서브게임 퍼펙트 평형(subgame perfect balance)이 존재할 때다. 선수가 전체 정보를 갖고 있을 때(즉, 경매 순서를 미리 알고 있다) 각 라운드에서 단일 품목이 판매될 때, SAFP는 선수의 평가와 상관없이 항상 SPEPS를 가진다. 그 증거는 다음과 같은 역유도를 통해 확인할 수 있다.^[1]^{: 872–874}

마지막 라운드에서 간단한 1차 가격 경매가 있다. 차상위권보다 약간 높은 입찰로 최고가 에이전트가 이기는 순수 전략 나시 평형을 갖췄다.
이전 매 라운드마다 상황이 외부성을 앞세운 1순위 경매의 특수한 경우다. 이러한 경매에서 각 대리인은 자신이 당첨되었을 뿐만 아니라 다른 대리인이 당첨되었을 때도 가치를 얻을 수 있다. In general, the valuation of agent $i$ is represented by a vector $v_{i}[1],\dots ,v_{i}[n]$ , where $v_{i}[j]$ is the value of agent $i$ when agent $j$ wins. 순차 경매에서 외부성은 향후 라운드의 평형 결과에 의해 결정된다. 도입 예에서는 두 가지 가능한 결과가 있다.
- 앨리스가 1라운드에서 우승하면 2라운드 평형 결과는 앨리스가 5달러짜리 물건을 4달러에 사들인다는 것이므로 ^[3]순이익은 1달러다. 따라서 1라운드 우승에 대한 그녀의 총 가치는 v $v_{\text{Alice}}[{\text{Alice}}]=5+1=6$ [ $v_{\text{Alice}}[{\text{Alice}}]=5+1=6$ $v_{\text{Alice}}[{\text{Alice}}]=5+1=6$ = $v_{\text{Alice}}[{\text{Alice}}]=5+1=6$ + $v_{\text{Alice}}[{\text{Alice}}]=5+1=6$ = 6 ${\displaystyle v_{\text$ {\text ${$ $앨리스}}[{\text{$ $앨리스}]=5+1=6}$ .
- 밥이 1라운드에서 우승하면 2라운드 평형 결과는 앨리스가 5달러짜리 물건을 0달러에 사들인다는 것이므로 순이익은 5달러다. 따라서 밥이 우승하도록 한 그녀의 총 가치는 $v_{\text{Alice}}[{\text{Bob}}]=0+5=5$ $v_{\text{Alice}}[{\text{Bob}}]=0+5=5$ [ $v_{\text{Alice}}[{\text{Bob}}]=0+5=5$ $v_{\text{Alice}}[{\text{Bob}}]=0+5=5$ = 0 $v_{\text{Alice}}[{\text{Bob}}]=0+5=5$ + $v_{\text{Alice}}[{\text{Bob}}]=0+5=5$ = $v_{\text{Alice}}[{\text{Bob}}]=0+5=5$ $[\displaystyle v_{\text$ {\text $}$ 이다. $앨리스}[{\text{Bob}}]=0+5=5$ .
외부성이 있는 각각의 초가 경매는 순수한 전략의 나시 평형을 가지고 있다.^[1] 위의 예에서 1라운드 평형은 밥이 이기고 1달러를 지불하는 것이다.
따라서, 역유도 방식으로 각 SAFP에는 순수 전략 SPE가 있다.

주의:

존재 결과는 또한 SASP를 지탱한다. 사실, 외부성이 있는 1차 가격 경매의 어떤 평형도 같은 외부성을 가진 2차 가격 경매의 평형 출시가 된다.
존재 결과는 입찰자의 가치에 관계없이 유지된다. 즉, 그들은 분리할 수 없는 상품에 대해 임의의 효용 기능을 가질 수 있다. 이와는 대조적으로 모든 경매가 동시에 이루어진다면 입찰자가 하위 부가 효용 함수를 가지고 있더라도 순수 전략 나시 평형이 항상 존재하는 것은 아니다.^[4]

사회복지

일단 우리가 서브게임 퍼펙트 평형이 존재한다는 것을 알게 되면, 다음 자연스러운 질문은 그것이 얼마나 효율적인가 하는 것이다 – 그것은 최대의 사회복지를 얻을 것인가? 이것은 최악의 평형상태에서 사회복지에 대한 최대 달성 가능한 사회복지 비율인 무정부 상태(PoA)의 가격으로 정량화된다. 입문 사례 1에서 달성 가능한 최대 사회복지는 10(앨리스가 두 가지 항목을 모두 획득할 때)이지만 평형 복지는 9(밥이 첫 번째 항목을 이기고 앨리스가 두 번째 항목을 이긴다)이므로 PoA는 10/9이다. 일반적으로 순차 경매의 PoA는 입찰자의 효용 기능에 따라 달라진다.

첫 다섯 가지 결과는 완전한 정보를 가진 에이전트에 적용된다(모든 에이전트는 다른 모든 에이전트의 가치를 알고 있다).

사례 1: 동일한 항목.^[5]^[6] 몇 가지 동일한 항목이 있다. 입찰자가 두 명 있다. 그 중 적어도 하나는 오목한 가치평가함수(수익감소)를 가지고 있다. SASP의 PoA는 최대 $1/(1-e)\approx 1.58$ / $1/(1-e)\approx 1.58$ ( $1/(1-e)\approx 1.58$ - $1/(1-e)\approx 1.58$ ) $1/(1-e)\approx 1.58$ 1. $[\디스플레이스타일 1/(1-e)\$ 약 $1.58}$ 이며 $1/(1-e)\approx 1.58$ 수치 결과 오목한 평가 기능을 가진 입찰자가 많을 때는 이용자 수가 증가할수록 효율손실이 감소한다.

사례 2: 적층 입찰자.^[1]^{: 885} 품목이 다르고, 모든 입찰자가 모든 품목을 독립 상품으로 간주하기 때문에 부가가치 집합 기능이다. SASP의 PoA는 한이 없다 – SPEPS의 복지는 임의로 작을 수 있다.

사례 3:^[1] 단위 수요 입찰자 모든 입찰자들은 모든 품목을 순수한 대체재로 간주하기 때문에 그들의 가치는 단위 수요다. SAFP의 PoA는 최대 2 – SPEPS의 복지는 최소 절반 이상이다(혼합된 전략이 허용되는 경우 PoA는 최대 4). 이와는 대조적으로, SASP의 PoA는 다시 한 번 구속되지 않는다.

이런 결과는 놀랍고 각 라운드에서 (2차 경매보다는) 1차 경매 방식을 사용하는 디자인 결정의 중요성을 강조한다.

사례 4:^[1] 서브모듈러 입찰자 입찰자의 평가는 임의의 서브모듈러 세트 기능이다(첨가물과 단위 수요는 서브모듈의 특별한 경우라는 점에 유의한다). 이 경우 입찰자가 4명뿐인데도 SAFP와 SASP의 PoA는 한이 없다. 직관은 고부가가치 입찰자가 향후 그가 직면할 수 있는 경쟁을 줄이기 위해 저부가가치 입찰자가 이기도록 하는 것을 선호할 수 있다는 것이다.

사례 5: 가법+UD.^[7] 일부 입찰자는 부가 가치를 갖는 반면, 다른 입찰자는 단위 수요 가치를 가진다. SAFP의 PoA는 $\min(n,m)$ ( $\min(n,m)$ , $\min(n,m)$ ) $\min(n,m)$ 일 수 있다 $\min(n,m)$ 여기서 m은 품목 수, n은 입찰자 수입니다. 게다가, 약하게 지배하는 전략의 반복적인 제거에도 불구하고 비효율적인 평형주의는 지속된다. 이는 다음을 포함한 많은 자연 환경에 대한 선형 비효율성을 의미한다.

대체 평가액이 총액인 입찰자
용량성 평가,
예산에 따른 평가,
지불에 엄격한 예산 제약이 있는 부가 가치.

사례 6: 불완전한 정보를 가진 단위 수요 입찰자.^[8] 대리점들은 다른 대리점의 가치를 알지 못하지만, 그들의 평가가 도출되는 확률분포만 알고 있다. 순차 경매는 베이지안 게임이며, 그것의 PoA는 더 높을 수 있다. 모든 입찰자가 단위 수요 평가를 할 때, SAFP에서 베이지안 내시 평형의 PoA는 최대 3이다.

수익 극대화

여러 품목을 판매하는 판매자들에게 중요한 실무 질문은 그들의 수익을 극대화하는 경매를 어떻게 설계하느냐 하는 것이다. 다음과 같은 몇 가지 질문이 있다.

1. 순차경매를 이용하는 것이 좋을까, 동시경매를 이용하는 것이 좋을까? 입찰이 나중에 팔릴 물건의 가치에 대한 정보를 전달할 수 있기 때문에 판매 사이에 발표된 순차 경매는 더 바람직해 보인다. 경매 문헌을 보면 이러한 정보효과는 승자의 저주를 줄여주기 때문에 판매자의 예상 수익을 증가시킨다는 것을 알 수 있다. 그러나 순차적 판매에서 전개되는 기만 효과도 있다. 만약 입찰자가 그의 현재 입찰이 나중의 물건에 대한 정보를 밝힐 것이라는 것을 안다면, 그는 입찰 가격을 낮출 동기가 있다.^[9]
2. 순차 경매를 사용할 경우, 판매자의 수익을 극대화하기 위해 어떤 순서로 상품을 판매해야 하는가?

두 가지 항목이 있고 예산 제약을 받는 입찰자 그룹이 있다고 가정합시다. 이 물체는 모든 입찰자에게 공통의 가치를 가지지만 동일할 필요는 없으며, 상품을 보완하거나 대체재일 수 있다. 전체 정보가 포함된 게임:^[2]

(1) 순차 경매는 다음과 같은 경우, ⑴ 품목의 가치 차이가 크거나 ⑵ 유의적인 보완성이 있는 경우, 동시 상승 경매보다 더 많은 수익을 산출한다.
하이브리드 동시순서 형태는 순차 경매보다 높은 수익을 낸다.
2. 일련의 공개 오름차순 경매를 통해 사물이 판매되는 경우, 더 가치 있는 사물을 먼저 판매하는 것이 항상 최적이다(사물의 가치가 상식이라고 가정한다).

게다가 예산 제약은 내생적으로 발생할 수 있다. 즉, 입찰 회사는 회사 자체의 지출이 훨씬 더 많음에도 불구하고 대표자에게 "이 경매에 최대 X까지 지출할 수 있다"고 말할 수 있다. 미리 예산을 제한하는 것은 입찰자들에게 전략적인 이점을 준다.

여러 개의 물건을 팔 때, 예산 제약은 예상치 못한 결과를 가져올 수 있다. 예를 들어, 예비가격은 결코 평형상태에서 구속되지 않을 정도로 낮은 수준에서 책정되어도 판매자의 수익을 올릴 수 있다.

구성 가능한 메커니즘

순차 측정과 동시 측정은 둘 다 동일한 입찰자가 몇 가지 다른 메커니즘에 참여하는 보다 일반적인 설정의 특별한 경우다. Syrgkanis와^[10] Tardos는 플레이어가 동시에 또는 순차적으로 복수의 메커니즘에 참여하는 경우에도 양호한 특성이 보장된 효율적인 메커니즘 설계를 위한 일반적인 프레임워크를 제안한다. 대략적인 시장 정리 가격을 발생시키는 메커니즘인 매끄러운 메커니즘의 등급은 전체 정보 설정에서뿐만 아니라 참여자에 대한 불확실성과의 베이시안 평형에서도 높은 품질의 결과를 초래한다. 매끄러운 메커니즘은 잘 구성된다: 각 메커니즘에서 국소적으로 매끄러움이란 글로벌 효율성을 의미한다. 좋은 성과에 따라 입찰자가 가치 이상으로 입찰하지 않아야 하는 메커니즘의 경우, 비크리 경매와 같이 약하게 매끄러운 메커니즘을 사용할 수 있다. 그것들은 과대입찰이 없는 가정하에서 대략적으로 효율적이며, 또한 약한 평활도 특성도 구성에 의해 유지된다. 일부 결과는 참가자가 예산 제약이 있을 때도 유효하다.

참조

^ ^a ^b ^c ^d ^e ^f Leme, Renato Paes; Syrgkanis, Vasilis; Tardos, Eva (2012). "Sequential Auctions and Externalities". Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. p. 869. arXiv:1108.2452. doi:10.1137/1.9781611973099.70. ISBN 978-1-61197-210-8.
^ ^a ^b Benoit, J.-P.; Krishna, V. (2001). "Multiple-Object Auctions with Budget Constrained Bidders". The Review of Economic Studies. 68: 155. doi:10.1111/1467-937X.00164.
^ 사실 앨리스는 4달러보다 약간 더 지불할 수도 있다(예를 들어, 입찰 가격이 전부인 경우 앨리스는 4.01달러를 지불할 수도 있다). 간단히 말해서, 우리는 이 극소수의 차이를 무시한다.
^ Hassidim, Avinatan; Kaplan, Haim; Mansour, Yishay; Nisan, Noam (2011). "Non-price equilibria in markets of discrete goods". Proceedings of the 12th ACM conference on Electronic commerce – EC '11. p. 295. arXiv:1103.3950. doi:10.1145/1993574.1993619. ISBN 9781450302616.
^ Bae, Junjik; Beigman, Eyal; Berry, Randall; Honig, Michael; Vohra, Rakesh (2008). "Sequential Bandwidth and Power Auctions for Distributed Spectrum Sharing". IEEE Journal on Selected Areas in Communications. 26 (7): 1193. doi:10.1109/JSAC.2008.080916.
^ Bae, Junjik; Beigman, Eyal; Berry, Randall; Honig, Michael L.; Vohra, Rakesh (2009). "On the efficiency of sequential auctions for spectrum sharing". 2009 International Conference on Game Theory for Networks. p. 199. doi:10.1109/gamenets.2009.5137402. ISBN 978-1-4244-4176-1.
^ Feldman, Michal; Lucier, Brendan; Syrgkanis, Vasilis (2013). "Limits of Efficiency in Sequential Auctions". Web and Internet Economics. Lecture Notes in Computer Science. Vol. 8289. p. 160. arXiv:1309.2529. doi:10.1007/978-3-642-45046-4_14. ISBN 978-3-642-45045-7.
^ Syrgkanis, Vasilis; Tardos, Eva (2012). "Bayesian sequential auctions". Proceedings of the 13th ACM Conference on Electronic Commerce – EC '12. p. 929. arXiv:1206.4771. doi:10.1145/2229012.2229082. ISBN 9781450314152.
^ Hausch, Donald B. (1986). "Multi-Object Auctions: Sequential vs. Simultaneous Sales". Management Science. 32 (12): 1599. doi:10.1287/mnsc.32.12.1599.
^ Syrgkanis, Vasilis; Tardos, Eva (2013). "Composable and efficient mechanisms". Proceedings of the 45th annual ACM symposium on Symposium on theory of computing – STOC '13. p. 211. arXiv:1211.1325. doi:10.1145/2488608.2488635. ISBN 9781450320290.

[lst12-1] ^ ^a ^b ^c ^d ^e ^f Leme, Renato Paes; Syrgkanis, Vasilis; Tardos, Eva (2012). "Sequential Auctions and Externalities". Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. p. 869. arXiv:1108.2452. doi:10.1137/1.9781611973099.70. ISBN 978-1-61197-210-8.

[bk01-2] Benoit, J.-P.; Krishna, V. (2001). "Multiple-Object Auctions with Budget Constrained Bidders". The Review of Economic Studies. 68: 155. doi:10.1111/1467-937X.00164.

[3] 사실 앨리스는 4달러보다 약간 더 지불할 수도 있다(예를 들어, 입찰 가격이 전부인 경우 앨리스는 4.01달러를 지불할 수도 있다). 간단히 말해서, 우리는 이 극소수의 차이를 무시한다.

[hkmn11-4] Hassidim, Avinatan; Kaplan, Haim; Mansour, Yishay; Nisan, Noam (2011). "Non-price equilibria in markets of discrete goods". Proceedings of the 12th ACM conference on Electronic commerce – EC '11. p. 295. arXiv:1103.3950. doi:10.1145/1993574.1993619. ISBN 9781450302616.

[bbbhv08-5] Bae, Junjik; Beigman, Eyal; Berry, Randall; Honig, Michael; Vohra, Rakesh (2008). "Sequential Bandwidth and Power Auctions for Distributed Spectrum Sharing". IEEE Journal on Selected Areas in Communications. 26 (7): 1193. doi:10.1109/JSAC.2008.080916.

[bbbhv09-6] Bae, Junjik; Beigman, Eyal; Berry, Randall; Honig, Michael L.; Vohra, Rakesh (2009). "On the efficiency of sequential auctions for spectrum sharing". 2009 International Conference on Game Theory for Networks. p. 199. doi:10.1109/gamenets.2009.5137402. ISBN 978-1-4244-4176-1.

[fls13-7] Feldman, Michal; Lucier, Brendan; Syrgkanis, Vasilis (2013). "Limits of Efficiency in Sequential Auctions". Web and Internet Economics. Lecture Notes in Computer Science. Vol. 8289. p. 160. arXiv:1309.2529. doi:10.1007/978-3-642-45046-4_14. ISBN 978-3-642-45045-7.

[st12-8] Syrgkanis, Vasilis; Tardos, Eva (2012). "Bayesian sequential auctions". Proceedings of the 13th ACM Conference on Electronic Commerce – EC '12. p. 929. arXiv:1206.4771. doi:10.1145/2229012.2229082. ISBN 9781450314152.

[h86-9] Hausch, Donald B. (1986). "Multi-Object Auctions: Sequential vs. Simultaneous Sales". Management Science. 32 (12): 1599. doi:10.1287/mnsc.32.12.1599.

[st13-10] Syrgkanis, Vasilis; Tardos, Eva (2013). "Composable and efficient mechanisms". Proceedings of the 45th annual ACM symposium on Symposium on theory of computing – STOC '13. p. 211. arXiv:1211.1325. doi:10.1145/2488608.2488635. ISBN 9781450320290.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Search

순차 경매

네임스페이스

더

목차

나시 평형

사회복지

수익 극대화

구성 가능한 메커니즘

참조