[소프트웨어 응용] Auctions

 

bidder: 경매에 참여하는 사람들 

seller: 경매 물건을 파는 사람 

 

Auctions의 네 가지 종류

-> 최종 가격이 어떻게 결정되는지!

---

1. Ascending-bid auctions

• English auctions
• interactively in real time - 실시간으로 가격 경쟁을 함 (대면 or 비대면 가능) 
• 가장 낮은 가격에서 시작 -> 모든 bidder들이 손을 들고 있는 상태에서 
• seller가 가격을 계속 올림 - bidder가 한 명만 남을 때까지 
• 최종 가격: bidder가 한 명 남았을 때의 가격

 

2. Descending-bid auctions

• Dutch auctions (네덜란드에서 많이 하던 거라고 ..) 
• interactive in real time 
• 가장 높은 가격에서 시작 -> 모든 bidder들이 손을 내리고 있는 상태에서 
• seller가 가격을 계속 내림 -> 처음 bidder 한 명이 손을 들 때까지 
• 최종 가격: 한 bidder가 최초로 손을 들었을 때의 가격 

 

 

3. First-price sealed-bid auctions

• bidder들은 동시에 본인의 "sealed bid"를 제출
• 서로가 서로의 bid 가격을 알 지 못 함. 
• seller는 sealed bids 중 가장 높은 가격을 선택함.
• 가장 높은 가격을 제출한 사람이 win 
• 최종 가격: sealed bids 중 가장 높은 가격

동시에 seller에서 가격 제시 - 서로 못 봄

4. Second-price sealed-bid auctions

• bidder들은 동시에 "sealed bid"를 제출 
• 서로가 서로의 bid 가격을 알 지 못 함. 
• seller는 sealed bids 중 가장 높은 가격을 제출한 사람을 선택함
• seller는 sealed bids 중 가장 두번째로 높은 가격을 선택함. 
• 가장 높은 가격을 제출한 사람이 두번째로 높은 가격에 사감 
• 최종 가격: sealed bids 중 두번째로 높은 가격

 

 

 

각 경매 종류를 비교해보자.

 

 

Veiw1. (1&2) vs. (3&4)

---

1 ascending-bid & 2 descending-bid 

- interative auction format.

- bidder들이 서로의 가격(손을 들었는지 내렸는지)를 알 수 있음 

- seller는 가격을 높이거나, 내리면서 경매를 진행함. 

 

3 first-price & 4 second-price 

- sealed bids

- 동시에 희망 가격 제출

- bidder들은 서로의 가격을 모름 

- seller는 sealed bids가 모두 제출되면 바로 낙찰 결정 

 

 

 

 

View2. (2&3) vs. (1&4) 

---

2 descending-bid & 3 first-price 

- 낙찰자는 본인이 내기로 했던 그 가격 그대로 냄 

 

- descending-bid: bidder는 100을 생각하고 있었으면, seller가 200-180-150-..-100으로 가격을 낮춘 순간 바로 손을 들게 됨. 

본인이 생각했던 가격인 100에 낙찰가가 결정됨 

- first-price: bidder는 100을 생각하고 있었으면, 100을 적어 sealed bid 제출. 이게 최고가였으면, bidder 본인이 생각했던 가격인 100에 낙찰가가 결정됨. 

 

=> 두 가지 auctions 모두 낙찰자 본인이 생각했던 가격이 낙찰가로 결정됨

 

1 ascending-bid & 4 second-price 

- 낙찰자는 두번째로 높은 가격을 냄 

 

- acsending-bid: 마지막 남은 두 bidder가 한 명은 200을 생각하고 있었고 한 명은 100을 생각하고 있었다면,

seller가 계속 가격을 올리면서 이 둘만 남아있고, 

seller가 100을 부르면 100을 생각하던 bidder는 손을 내리게 되고, 그 가격에 낙찰됨 

낙찰자는 본인이 생각한 200보다 저렴한 가격에 낙찰받음 

 

- second-price: 두 bidder가 각각 200, 100을 써서 냈다면, 200을 적은 bidder는 100에 낙찰가가 결정. 

낙찰자 본인이 생각한 200보다 저렴한 가격에 낙찰받음 

 

=> 두 가지 auctions 모두 낙찰자 본인이 생각했던 가격이 아닌 두번째 가격으로 낙찰가가 결정됨. 

 

 

---

 

🧐 왜 두번째로 높은 가격으로 낙찰가를 결정하는지 ?

ascending-bid

두 명이 남아있는 상태에서 가격을 한 번 더 올리게 되면, 두번째로 높은 가격을 생각하던 bidder는 떨어져 나감.

두번째 bidder가 떨어져 나간 가격은 그가 생각하던 가격, 즉 그의 true value이고, 

남은 사람이 가장 높은 가격을 생각하던 한 명 뿐이므로 가격을 더 올리지 않음. 

두번째 bidder가 떨어져 나간 가격 = 두번째로 높은 가격 => 낙찰가로 결정. 

 

2등이 포기한 가격에 사면되지, 거기서 가격을 더 올려서 살 필요가 없기 때문

 

second-price 경매도 똑같음. 차이점은 real-time interaction or not 

 

---

 

🧐 뒤에서 두번째 bidder가 떨어진 가격이 왜 그의 true value? 

 

본인이 생각한 가격(true value)까지만 손을 들고 있는 것이 dominant strategy이기 때문! 

(dominant stategy: 상대방의 전략이 뭐든, 이 전략보다 더 이득을 가져다 주는 전력이 없는 전략!, 바꿀 인센티브가 ㄴㄴ)

 

If (true value보다 높은 가격까지 손 들고 있는 경우)

    -> 만약 100을 생각하다가 다음 가격 200에 낙찰되어 버리면 100을 더 주고 사는 것이기 때문에 그 만큼 손해 

else if (true value보다 낮은 가격에 손을 내리는 경우) 

   -> 이 경우, 낙찰될 수 있었는데 손을 내려 낙찰 안 될 수 - 그럼 그냥 암 것도 없음 nothing 

 

그래서 본인의 true value 가격까지 손을 들고 있는 것이 가장 좋은 전략이다. 

second price auction에서 dominant starategy: bidding your true value !!

 

---

 

🧐 seller 입장에서 second price는 손해 아닌가?

 

낙찰자가 가장 높은 가격에 물건을 가져가는 것보다 두번째로 높은 가격에 가격에 가져가는 것이 seller입장에서 그 차이만큼 손해 아닌가? 생각할 수 있다. 그런데 그렇지 않음.

 

why? 사람들이 bid 가격을 똑같이 내지 않음. 

사람들은 first price auction을 하면, second price auction보다 bid가격을 다들 낮게 냄.

얼마나 낮게 내냐? - first price의 가장 높은 가격과 second price의 두번째 가격이 비슷해질 정도로 딱 냄 

결론적으로 seller가 받아가는 금액은 비슷함

 

 

Second-Price Auction

---

실제로 많이 사용되는 경매의 형태는 Second price auction

- eBay, search engine에서 키워드 기반 광고 가격 정할 때, ... 

 

여기에 Game Theory 를 적용해보자. 

(게임의 구성요소는 - player, starategy, payoff)

player	starategy	payoff
bidder	bid 가격	tru value에 비해 얼마나 싸게 낙찰받았는가

 

bidder i 에 대해서 

vi : bidder i의 true value 

bi : bidder i의 bid 가격

bj : second price (낙찰가) 

라고 한다면, 

 

starategy: vi를 가지고 결정한 bi 

payoff: bj - vi 

(얼마나 가격 이득을 보았는지, 만약 낙찰 안되면 payoff = 0)

 

Truthful bidding 

dominant strategy : bi = vi 

 

bi를 vi보다 높이면? - 2등 가격이 그대로라면 이득이 없다. 

낮추면? - 너무 낮춰서 1등을 못하면 꽝 

 

-> vi가 아니도록 바꿔봤자 낙찰을 못 받을 정도로 낮추면 payoff = 0, 그게 아니라면 payoff는 안 변함. 

 

좀 더 자세히 살펴보자. - 1, 2등이 bid 바꾸는 경우에 대해 

case1) bi' > vi 

true value보다 높인 경우, payoff가 변하는 경우는 2등이 1등이 된 경우 뿐이다. 

그럼 원래 1등이었던 가격 bj는  bi' > bj > bi(=vi) 이렇게 가운데에 위치하게 됨. 

이 경우 i는 낙찰가가 second price인 bj로 정해지고

payoff = bi - bj < 0 가 되어 원래 2등이어 낙찰을 못 받은 경우보다 손해를 보게 됨다. 

 

case2) bi'' < vi

true value보다 낮춘 경우, payoff가 변하는 경우는 1등이 2등이 된 경우 뿐

원래 2등 가격이 bk였다고 한다면, bi(=vi) > bk > bi'' 이렇게 될 것이다. 

원래의 payoff = bi - bk >=  0 이었다가, 2등이 되면서 낙찰을 받지 못해 payoff = 0 이 됨. 손해

 

=>>> true value로 비딩하자 

 

Second price auction에서 Bid는 ...

낙찰이 될 지 안 될 지만 결정하고 얼마를 내야하는지는 결정하지 않는다. 

 

 

 

First-Price Auctions

---

first-price에 대해서도 Game theory 적용해보자. 

 

player	starategy	payoff
bidder	bid 가격	tru value에 비해  얼마나 싸게 낙찰받았는가

 

똑같다.

 

차이점은 더이상 true value != Dominant strategy  라는 것 ! 

- 낙찰 안받으면 payoff = 0

- true value로 비딩하고 낙찰되어도 payoff = bi - vi = 0 

 

그럼 어떻게 해야 payoff가 올라갈까? - bid를 낮춘다! shade 

아까 사람들은 second price에 비해 first price의 bid 를 낮춘다고 했다. 

 

얼마나 낮춰야 할까 ? 

- 너무 조금만 낮추면: payoff가 별로 안커짐

- 너무 많이 낮추면: payoff 커질 수 있지만, 아예 낙찰이 안 될 수 있음

 

payoff 높이기 <-> winning ... complex problem ! 

-> 다른 비더들의 가격에 영향을 받을 수 밖에 없음

 

 

Auctions with Common Values & The Winner's Curse 

---

지금까지 살펴본 경우에 biddr가 item에 대해 가지는 true value의 크기 자체는 우리 관심사가 아니었음. 

각각의 개인이 생각하는 가치이기 때문에, auction 자체와는 독립적으로 생각되는 것이라고 고려했음. 

 

그러나, 다시 되팔 것을 생각하면서 하는 auction의 경우는 이 true value도 살펴볼 필요가 있음. 

이럴 때는 해당 item의 common eventual value 를 고려해야 함. 

 

각각의 비더들은 common value, v에 대해 개인적인 정보들을 가지고 있고, 그를 토대로 그 가치에 대해 vi라는 가치를 측정함.

일반적으로 이 vi 값은 잘못 측정되는 경우가 많음. 그리고 비더들끼리도 이 값에 서로서로 영향을 줌.

 

bidder들은 common value에 대해 estimate -> 자신들의 생각하는 가치 vi를 통해 bid 결정하고 낙찰받음. 

이런 경우 보통 낙찰받은 bidder는 over한 비드를 걸었을 확률이 큼. 

common value에 대해 과하게 평가(over-estimate) 하고 값을 제시했기 때문에

 

-> 예시로 축구 선수를 생각해볼 수 있다. 선수의 고정된 실력 (common value, v)가 있고 각 구단들은 이 선수에 대해 vi라는 가치를 측정함. 이 선수를 낙찰받은 팀은 보통 과하게 가치를 평가(vi = v + x, x만큼 과대평가)해서 over한 금액을 내고 낙찰받는 경우가 많음. 

-> 그럼 이 선수를 다시 되팔때 손해를 보게 됨. 돈을 많이 써서 데려왔기 때문에 

-> 승자(낙찰 받은 팀)의 저주

 

 

Seller Revenue 

---

경매에는 bidder와 seller가 존재.

지금까지 bidder 위주로 살펴봤으니까 seller도 한번 보자. 

 

seller는 first-price, second-price 중 뭐가 더 돈을 많이 벌 수 있게 할까?

 

n 명의 bidder들이 [0,1] 사이의 true value를 가진다고 하자. (각각 독립적으로 결정됨) 

seller의 revenue는 가장 높은, 그리고 두번째로 높은 bid가 얼마인가에 달려있다. 

-> 이 크기가 어느정도일지? 기댓값이 얼마인지

 

n개의 true balue를 작->큰 것 순으로 정렬했을 때, k 번째 기댓값은 k/(n+1)이다. 

(0~1 까지 랜덤하게 n 개의 값이 분포, 각 값들이 차이가 일정하다고 가정하면,

k 번째값은 1을 (n+1)개로 나눈 것 중 k번째 값 = 1* (k/n+1)) 

 

이 상태에서 second-price auction을 하면, bidder들은 dominant strategy -> true value = bid

그럼 낙찰가는 뒤에서 두번째 가격, 즉 (n-1)/(n+1) 

 

 

first-price auction을 한다면, 보통 true vlaue의 (n-1/n) 배를곱한 값을 bidding 함 (증명은 어려움)

그럼 이 때 가장 높은 가격을 제시한 bidder 가격은 (n-1/n) * (n/n+1) = (n-1/n+1) 

 

-> first나 second나 기대 수익이 똑같네요!