Descending bid auction : 고액에서 내려가며 최초의 1인이 가져가는 경매
First price sealed bid auction : 봉투에 자기만 아는 입찰 금을 적고, 전체 입찰자 중 가장 높은 금액을 쓴 입찰자가 낙찰받는 경매
Second price sealed bid auction : 마찬가지, 근데 젤 높은 금액 쓴 사람이 낙찰 받지만 그 사람이 내는 금액은 2등 입찰자의 입찰금액만큼만 내는 경매
Descending , First price auction : 전체 입찰자 중 가장 높은 금액을 생각한 입찰자가 침묵을 깨고 낙찰을 받게 된다.
Ascending, Second price auction : 전체 입찰자 중 가장 높은 금액을 생각한 입찰자가 두번째로 높은 금액을 생각한 입찰자가 포기하는 순간 낙찰을 받게된다. 근데, 모든 입찰자는 자신이 생각한 금액보다 높아지면 포기하기에 결국 최종 낙찰자는 2등 입찰자의 금액을 지불하고 낙찰받게 된다.
자신의 true value를 bidding하는게 dominant strategy임
(second price라고 부를 애들은 다 second price sealed bid auction임)
first price가 second price보다 seller에게 가는 이득이 더 많을 것이라는 생각을 할 수 있음
모든 buyer는 자신의 payoff를 maximize하는 item을 잡고 있을 것 그렇기에 M은 최대의 total payoff를 가짐
Total payoff of M = Total valuation of M - Sum of all prices
여기서 sum of all prices는 고정적인 값, 따라서 M의 total valuation이 최대가 되면 total payoff또한 최대가 되고 그 역도 성립한다.
임의의(arbitrary) set of buyer valuation에서 “Auction”을 이용하면 MCP에 도달하게 된다.
seller들이 모두 자신의 아이템의 price를 0으로 설정→ buyer들이 prefer seller고름→ 만약 perfect matching 존재하면 done / 존재하지 않다면 contricted set이 존재하다는 것을 의미 →** 해당 constricted set이 원하는 item의 price를 1 올림 → perfect matching 탐색 ,, 반복
**N(S)에 있는 seller는 가격을 올린다.
만약 모든 price가 0보다크다면(strictly greater than 0) 모든 price들에서 가장 작은 price를 p라고 하면 모든 price를 price-p로 수정한다.
경매가 진행됨에 따라 potential energy는 소비되고 결국 마르게된다.
potential energy of the auction = potential of a buyer + potential of a seller
potential of a buyer : buyer’s potential payoff( current price=MCP인 경우에 해당 payoff획득)
potential of a seller : 마찬가지
Chap 15. Sponsored Search Markets
검색창에 석촌호수 치면 옆에 sponsored link( AD )가 뜨는데 그 뜨는 놈들에 대한 chapter
실제로 광고 눌러야 회사가 웹사이트에 pay
search engine이 각각의 query마다 click가격을 설정하긴 힘듬
따라서, 경매로 가격을 결정하기로 함
하나의 ad slot에 대해 sealed bid second price auction
여러개의 ad slot이 있다면 좀 복잡함..
advertiser의 valuation을 아는 경우, 이 경매는 matching market으로 나타낼 수 있음
하지만, 모르는 경우 truthful bidding을 장려해야 함
truthful bidding이 dominant strategy인 matching market에서 어떻게 가격을 정할 것인가
Not in real, VCG기술 사용(vickery clarke groves) : sigle item, second price auction의 far reaching generalization
VCG는 matching market에서 price를 정하는 자연스러운 방법이나 실제에선 적용이 힘들다.
GSP(Generalized second price auction)을 실제상황에서 사용
각각의 slot은 clickthrough rate이 있음(시간당 클릭수)
가정
advertisers 는 이걸 알고있음, slot의 위치만 고려 대상(고정적)
각각의 advertiser는 revenue per click을 가짐
유저가 광고를 눌렀을 경우의 예상 수익
특정 키워드에 대한 Matching market 만들기
기본 재료
buyer:advertiser
seller:search engine
vij: buyer j의 seller i의 item에 대한 valuation
buyer는 항상 하나만 사고 seller또한 한명에게만 판다.
Clickthrough rate of slot i = ri
Revenue per click of advertiser j = vj
benefit advertiser j get by buy slot i vij=ri*vj
만약 advertiser가 seller보다 많거나 반대라면
둘의 비율을 맞추기위해 0의 clickthrough rate을 가지는 slot을 추가하고, 반대의 경우 모든 slot에 대해 valuation이 0인 가짜 advertiser추가
이렇게 둘의 숫자가 같다면 perfect matching을 찾을 수 있음
slot의 price : pi, buyer 의 payoff = vij-pi
이걸로 preferred seller graph그리기
이 그래프가 perfect matching 이면 MCP
valuation이 결국 clickthrough rate * revenue per click의 형태이니 전체 maximum valuation은 clickthrough rate이 젤 높은애를 revenue per click이 젤 높은애한테 주고 2등을 또 2등한테주고 ..이렇게 되어야 함
이러한 MCP는 근데 search engine이 advertiser의 valuation을 아는 경우에만 가능 근데 모른다면??
advertiser가 보고하는 valuation에 의존. truthful하길 바라야 함.
초기 seach industry
first price auction 사용
입찰가 제시하고 젤 높은애한테 젤높은 click rate slot주고.. 이런식으로 진행
단점 1 : advertiser들이 under report함(클릭당 2원버는데 1.5원밖에 못번다고 구라핑)
단점 2 : auction이 끊임없이 진행되고 advertiser또한 꾸준히 자신의 입찰가를 쪼금씩만 바꿈
결과: 이렇게되니 너무 난잡한 market이 됨, 모든 쿼리에대한 가격이 끊임없이 바뀜
앞서 말했듯, single item auction이면 그냥 second price 하면 됨
multiple slot인 경우에 truthful bidding이 dominant strategy인 matching market을 만들기 위해 어떻게 가격을 결정해야 할까?
Massive generalization of second price auction
second price auction 은 social welfare 를 maximize하는 배치를 만듬
경매의 winner는 해당 item을 수령하며 다른사람들이 입은 harm의 양만큼 pay함
single item auction에서 harm을 생각해보자
bidder n명의 입찰가액을 v1~vn이라 해보자 (v1이 제일 높음)
bidder 1이 입찰하지 않았다면 item은 bidder2에게 갔을 것이고 3번~n번 bidder는 여전히 item을 획득하지 못한다
bidder2는 bidder1의 존재로 인해 낙찰받지 못하기에 v2만큼의 harm을 입게되고 3~n은 영향을 받지 않는다.
즉,3~n의 harm 은 0이다.
이 v2의 harm이 bidder1이 내야하는 금액이 된다.
개인은 자신으로 인해 발생하는 harm 을 pay해야한다는 VCG principle(in signle item, second price auction)의 central idea 를 일반화 해보자!
가정
개인은 자신의 valuation만 알고 있다
개인은 자신이 얻게되는 이득만 신경쓴다
total valuation을 최대화 하게끔 buyer에게 item을 assign한다.
그 후, buyer j가 i의 item에 대해 지불해야 할 금액을 작성한다.
해당 item을 얻게되며 다른 buyer들이 받을 harm만큼 PAY
harm==total boost in valuation buyer j가 없다고 가정했을 때 optimal matching에서 다른이들이 얻을 이득
위 처럼 x는 x가없었다면 y가 얻었을 이득(20) - 있어서 얻은 이득(10) =10, z의 harm=5-2=3 , total 13의 price를 지불해야 함
마찬가지로 y또한 5-2=3의 비용을 지불해야 함
즉, p_ij=harm=$V^S_{B-j} - V^{S-i}_{B-j}$
즉, item집합이 S인 애들 중 j를 제외한 buyer들이 얻을 수 있는 max valuation - S에서 i를빼고 buyer들이 j를 제외했을 때 얻을 수 있는 max valuation
한명의 agent (여기서는, search engine) 가 price를 세팅함
위의 과정을 누군가가 진행한다는 것
buyer들은 자신의 valuation을 agent에게 제출함.(truthful하지 않아도 됨)
근데, 이때 valuation을 truthful하게 제시하는 것이 dominant strategy임
VCG vs MCP
MCP는 posted price임 : 가격이 정해져 있다. 누가 사던 정해진 가격에 사야함
VCG는 personalized price : buyer에 따라 price가 바뀌게 된다.
MCP는 ascending auction이다 : price가 buyer에게 item이 사질 때 까지 올라감
VCG는 sealed bid second auction을 일반화 한다.(harm을 pay한다는 부분에서)
second price auction은 item이 한개인 vcg와 같음
왜 VCG에서 truthful bidding이 dominant strategy일까
buyer j가 truthful bidding을 했을 때, 아이템 i를 획득하는 경우 payoff 는 v_ij - p_ij
만약 거짓말을 하는 경우(ex, 클릭당 15원 벌지만, 10원 번다고 구라치는경우 // 20원으로는 구라를 칠 이유도 없고 쳐서도 안됨, 똑같은 걸 15원주고 살래 20원주고살래 임마)
아무런 영향이 없거나 : 가격을 낮춰서 불렀는데 똑같이 i를 낙찰받게되는 경우
payoff 변화 없음
i가 아닌 h를 얻게됨
payoff가 v_hj-p_hj로 바뀜
만약 v_ij-p_ij ≥ v_hj-p_hj 라면 truthful bidding이 dominant strategy임
