[소프트웨어 응용] Sponsored Search Markets

slot: 광고가 게재되는 영역 

advertiser: 광고를 싣고 싶은 광고주 

search engine: 광고 slot을 파는 seller 

 

search engine 회사들이 거는 광고들 

- 내가 검색한 검색어에 따라 광고를 보여주는 keyoword-based advertising 

-> 이러한 광고의 가격 어떻게 결정되는지 볼 것임. 

 

 

 

광고 slot이 여러 개가 존재하는데, 그중 선호도가 높은 슬럿이 존재함.

광고를 원하는 광고주들이 있고, 광고를 넣는 공간, slot이 여러 개 존재.

누가 어떤 광고 슬럿을 가져갈까? 

-> auction을 통해서

-> matching market 

 

---

paying per click 

광고 가격 중에는 클릭 횟수당 받는 가격이 있다. -> paying per click. 

사람들이 클릭을 한다는 것은 해당 컨텐츠에 대해 강한 관심을 가지고 있다는 것을 뜻함. 

단순히 검색을 한 것에 비해서. 

-> 그래서 광고주들은 기꺼이 클릭에 대해서 비용을 지불함. 

 

 

각각의 query에 일일이 클릭 당 가격 정하기? 😡

-> 어려움 

- 검색 가능한 키워드나, 키워드들의 조합의 수가 너어어어무 많음. 

- 키워드 개수가 엄청나게 많은 것에 비해, 광고를 걸만한 키워드는 적음. (광고 시장이 작고, 광고회사가 적다)

- 광고주들의 요구는 계속 변함. 거기에 맞춰 계속 가격이 달라지는데 이런 걸 유지하는 게 힘듦. 

 

-> 그래서 대신, auction을 통해 가격을 정함 

 

 

Designing an Auction

---

• 만약 search engine 회사가 광고주들이 click당 가지는 valuations을 알고 있다면, 바로 matching market 만들면 된다. 
• 모른다면, 그들이 truthful bidding(or untruthful bidding)을 하도록 하는 방법을 생각해야 함. 
  • 서치 엔진 회사 입장에서는, 광고주들이 truthful bidding을 하게 하고 싶음 (돈 많이 벌려고) 
  • 이를 위한 방법 - VCG
  • untruthful bidding을 하게 하는 방법 - GSP
•  Vickery-Clarke-Groves (VCG) mechanism
  • second-price auction 을 일반화한 거임
  • 원래 하나의 아이템에 대해 하는 second price auction을 여러 item(slot)에 대해서 진행하도록!
• Generalized Second-Price Auction (GSP)
  • VCG보다 이론적으로는 덜 탄탄함. 아직 연구가 진행 중. 
  • 하지만 실제 서치 엔진에서는 이거 사용함. - 기대 수익이 더 높을 것이라 예상되어서 
  • 방법은 간단함, 결과는 complex. - untrithful bidding, socially non-optimal outcomes

 

 

광고주들이 광고로 인한 기대 수익을 계산하기 위해 알아야 하는 것들 

-> 각 slot의 특성 - clickthrough rate

-> 광고주들의 특성 - revenue per click 

 

clickthrough rate

: 해당 slot에 대한 시간당 클릭 수 

 

- 클릭 수가 slot에 대해 완전히 의존적인 특성인지 의문이 들 수 있다. 어떤 광고인지, 주변에 무엇이 있는지에 달라지는 거 아닌가 할 수 있지만 여기서는 고려하지 않음. slot에 의해 결정되는 특성이라고 가정한다. 

 

revenue per click 

: 해당 slot에 대해 클릭 당 기대 수익

 

- 광고를 클릭한 이후에 생기는 수익은 광고주에게 달려있는 특성이다. 광고를 보고 구매로 이어졌을 때 얻는 수익은 광고주마다 다름. ex. 연필 광고와 비행기 표 광고 중 클릭 후 구매로 이어졌을 때, 수익이 더 큰 건 비행기 광고 

 

-> 두 값을 곱하면 슬럿에 대해 시간 당 기대 수익을 알 수 있다. 

 

 

constructing a matching market for a particular keyword 

---

키워드 별로 광고를 달아줌 

- 키워드 별로 slot에 대한 광고 가격을 결정해야 함 

- 가격은 auction을 통해 결정함 

- matching market을  구성함! 

 

 

matching market으로 따지자면 

sellers (item): slots

buyers: advertisers

& perfect matching - 모두 다른 slot을 하나씩 할당받음 

& slot 개수와 advertiser 개수가 같다고 가정하자

(안맞으면 가상으로 그냥 채움 - clickthrough rate = 0 or valuation = 0 for all slots) 

 

pi: slot i의 가격 

vij : buyer j 가 seller i에 대해 가지는 valuation. 

ri : slot i 가 가지는 clickthrough rate 

vj : advertiser j가 가지는 revenue per click

 

=> advertiser j 가 slot i를 할당받았을 때의 얻는 이익은 = ri * vj 

=> 이 값이 valuation vij  = ri * vj 

 

payoff는 내가 생각한 가치보다 얼마나 싸게 샀는지 

= vij - pi 

 

 

Obtaining Market-Clearing Prices

---

matching market 구조로 만들었으니까, MCP 구하자 

 

1. 슬럿 가격 pi 초기화하고

2. 광고주들 자신들의 payoff 계산하고 (true value - price = vij - pi)

3. preferred-seller garph 그리고

4. perfect matching 될 때까지 가격 조정하고 

5. perfect matchign 되면 MCP 결정된다. 

 

market-clearing price

=> total payoff, total valuation을 극대화한다! 

=> advertising market에서, MCP는 바람직한 특성을 보여줌 

- 광고주들은 각기 다른 slot을 선호함. 결과적으로 할당받은 광고 슬럿은 전체 valuation을 극대화함

 

- valuation = clickthrough rate * revenue per click 이것들의 합이 극대화되려면 큰 애들은 큰 애들끼리 !

-> 그럼 가장 clickthrough rate가 높은 슬럿은 revenue per click 을 가지는 광고주에게 할당되어야 최대가 되고, 

-> 두 번째 clickthrough rate - 두번째 revenue per click 광고주와 매칭되고, ...

=> 결국 sorting 된 순서대로 matching 되게 됨. 

 

그러나 이러한 구조는 서치 엔진 회사가 광고주들의 valuation을 알고 있어야 MCP를 찾을 수 있음. 

현실적으로는 이걸 모르는 경우가 더 많음. 

광고주들이 제시한 자신들의 valuation이 사실인지 아닌지 서치 엔진 회사 입장에서 알 수 없음. 

이런 경우에는 어떻게 ? 

 

 

초기 검색 산업에서 사용된 방법은 first price auction 

문제점

- 광고주들이 실제 생각하는 truth value보다 낮게 적어서 냄. 

- 가격도 깨작깨작 올림

- 조금만 가격을 올리면 1등이 됨 - 계속 무한 반복

- 1등이 계속 바뀌면서 광고도 계속 바뀌게 됨 

 

-> truth bidding 하게 하고 싶음 

-> second-price auction for a single-item의 경우, dominant strategy = truthful bidding

-> 광고 마켓에서는 slot이 여러 개, 즉 multiple-items 

-> second-price auction을 일반화해서 사용하자. 

 

The VCG Principle 

---

item 수가 많기 때문에, 곧장 일반화시키기는 어려움. 

1. second-price auction -> miximizes social welfare

2. the winner of the auction -> 그가 아이템을 낙찰받음으로써 다른 비더들에게 "harm"을 끼치는 만큼의 금액을 낸다. 

 

갑자기 "harm"?? 

single-item auction에서 봐보자.

- bidders' values를 v1 부터 큰 순서대로 나열해 놓은 상태에서 

- bidder 1이 없다면, bidder 2가 아이템을 낙찰받게 됨. 이 외에 비더들은 달라지는 게 없음. 

- bidder 2의 harm은 v2. 정확히 bidder 1이 내야 하는 금액이다.

=> 기존에 알고 있던 second-price 에도 적용이 되는 개념임!

=> item 개수가 많이 지면, bidder2 뿐만이 아니라 bidder3, 4,... 모두 줄줄이 harm을 가지게 됨.

 

광고주들로 하여금 truthful bidding을 장려하는 법칙

- 각각의 개인들은 그들이 나머지에게 야기하는 harm 만큼을 내야 한다.

-각각의 개인들은 본인이 없었을 때, 다른 모두가 더 얻을 수 있는 이익의 전체 양만큼을 내야 한다. 

-> 이게 Vickrey-Clarke-Groves(VCG) principle

 

 

Applying to matching markets

---

가정: 바이어들은 독립적이고 본인만 아는 value를 가짐

- 각각의 바이어들은 본인의 valuations은 알지만 다른 바이어와 셀러는 알지 못 함. 

- 각각의 바이어들은 그가 받는 아이템에만 관심이 있음. 다른 바이어들이 할당받은 것들에 관심 ㄴ

 

VCG 법칙에서 

1. 바이어한테 아이템을 할당하는 것은 total valuation을 극대화하기 위함임

2. 바이어 j가 아이템 i를 사기 위해 지불해야 하는 금액은 그가 아이템 i를 가져감으로써 나머지 바이어들에게 야기하는 harm의 크기임.

= total boost - 바어어 j가 없다고 가정했을 때, optimal matching을 했을 때의 다른 모든 이들의 valuation 합 

 

이 상태에서 market matching -> 결과적으로

x -> a

y -> b 

z -> c

이렇게 매칭됨. (정렬된 순서대로 매칭) 여기서 x가 없다고 해보면, 

y -> a

z -> b

이렇게 매칭이 된다. 

 

y는 b를 할당받을 경우에 비해 a를 할당받는 경우 20 - 10 = 10 만큼의 valuation 이득이 있고, 

z는 c를 할당 받을 경우에 비해 b를 할당 받는 경우 5 - 2 = 3 만큼의 valuation 이득이 있다. 

합은 10 + 3 = 13. 

x가 없음으로 인해 y와 z는 total 13 만큼의 이득을 보는 것 

x가 있음으로써 item a를 가져가게 됨으로써 y와 z는 total 13만큼의 harm을 가지는 것 

=> x는 이 그래프에 끼어들고 싶으면 13을 내라 ! 

이번엔 y를 없애보자. 

x -> a

z -> b

이렇게 매칭이 된다. 

x는 y가 있든 없든 a에 매칭이 되기 때문에, valuation의 이득이나 손해가 없다. 

그러나 z의 경우 c를 할당받을 때에 비하여 b를 할당 받을 경우 5 -2 = 3 만큼의 이득을 본다. 

y가 없어지면 얻는 나머지 (x, z)의 총 이득은 3

y가 있음으로 인해 item b를 가져가게 되면서 나머지가 가지는 harm = 3 

-> y는 3을 내라! 

 

정리하면, 

buyer j 가 item i에 대해 내야 하는 가격은, 

j가 빠졌을 때, 나머지 바이어들이 가질 수 있는 최대 total valuation 과 

j가  item i를 가짐으로써, 나머지 바이어들이 가질 수 있는 최대 total valuation의 차이만큼이다. 

 

= j가 i를 가져감으로써 나머지 바이어들이 가지는 harm의 총합만큼이다! 

 

가격이 물건에 의해서만 정해지는 것이 아닌, 누가 사느냐에 의해서도 달라질 수 있다. 

 

 

VCG Price-Setting procedure for Matching Markets 

---

single agent가 컨트롤한다고 가정. 여기서는 서치엔진 회사. 

 

순서

1. 바어이들에게 아이템들에 대한 valuation을 물어봄. 

2. 그 값을 토대로 socially optimal assignment 하게 매칭 (전체 valuation을 극대화하는 perfect matching을 한다.)

3. 바이어들은 책정된 VCG 가격만큼 지불. 

 

 

바이어의 입장에서 valuation 어떻게 대답할까?

Game으로 보자. 

buyer들을 strategy를 선택해야 함. payoff = valuation - price 

지금 이 상황은 truth-telling이 dominant strategy! 

 

VCG prices vs. market-clearing prices 

가장 큰 차이점 

• market-clearing price are posted prices :  누가 봐도 같은 가격임. 어떤 바이어가 사느냐에 따라 가격이 달라지지 않음. 
• VCG prices are personalized prices : 누가 뭘 사느냐에 따라 가격이 달라짐. 

 

-> market-clearing price는 ascending auction을 일반화한 거 

가격이 step-by-step으로 증가함. 

-> VCG prices는 sealed-bid second auction을 일반화 한 거 

harm-done-to-others 가 적용됨. second-price auction은 VCG procedure의 특별한 케이스임 

 

 

위에서, VCG에서는 truth telling = dominant strategy라고 함. 

왜일까?

 

만약에 buyer j 가 자신의 true value를 솔직하게 말하면, item i를 할당받는다고 하자. 

그럼 buyer j의 payoff = vij - pij 

 

그런데  j가 거짓으로 valuation을 말한다고 해보자. 

두 가지 경우가 있을 수 있음 

 

1. j가 할당받는 item이 변하지 않는 경우.

- j의 payoff가 변하지 않음. 

- 가격 pij는 j를 제외한 나머지 buyer들에 의하여 결정되는 값이기 때문 

- vij(그대로) - pij(그대로) = 그대로 

 

2. j가 i가 아닌 다른 아이템 h를 할당받는 경우 

- 새로운 payoff = vhj - phj 

- if (vij - pij) > (vhj - phj) 라면, j는 strategy를 바꿀 incentive가 없다! 

 

proving ( vij - pij ) > ( vhj - phj )

앞서 가격 pij 는 다음과 같이 구해진다고 함 

 

 

그런데 왼쪽의 경우 아래 그림에서 (a) 이고

 

 

(a)는 optimal matching 

- 전체 Slot, Buyer에 대해 total valuation이 최대 

 

오른쪽 식은 (b)에 해당하는데, V^{S-h}_{B-j}의 경우는 j가 i를 할당받은 조건을 가지고

maximum total valuation 을 가지는 매칭을 정해지게 됨. 

-> 이건 전체 모든 가능한 경우 중 optimal 한 결과인 (a) 보다 작거나 같을 수밖에 없음.

 

 

-> 결국 j는 i가 아닌 다른 아이템 h로 바뀔 인센티브가 없음. 

 

-> truth value가 아닌 다른 어떤 값을 낼 인센티브가 없음 

결국 모든 buyer들이 truty value를 내게 됨 

 

 

정리하자면, 

여러 개의 광고 slot(item)을 여러 advertiser(buyer)에게 할당하고 싶음. 

market matching 방법대로 적용해서 Market Clearingn Price를 구하자.

그럼 optimal perfect matching ->  total valuation도 최대가 됨. 

그런데 이 방법은 광고주들의 valuation을 알아야 가능. 

 

하지만 일반적으로 그걸 다 알고 있을 수 없음.

그래서 광고주들로 하여금 truth telling을 하게 하는 방법을 생각해냄. 그게 VCG. 

 

어떻게 VCG는 truth telling을 하게 할까

 

1. matching은 중앙관리자, 즉 search engine (회사)이 함.

2. 가격은 각 buyer가 matching에 참여함으로써 다른 바이어들에게 끼치는 harm의 크기로 정함 

=> 이렇게 했더니 buyer들의 dominant strategy = truth bidding이 되더라.

3. 그럼 그 valuation 가지고 search engine 은 total valuation이 최대가 되도록 매칭함. (sorting 해놓고 매 칭하면 됨)

 

가격 정하는 방법은, second-price auction에서 dominant strategy = truth bidding인 걸 이용해서 이걸 일반화해서 정한 거.

 

 

Generalized Second Price Auction (GSP)

---

대부분의 서치 엔진에서 적용한 방법은 VCG가 아니라 GSP 

 

GSP는 특정 부분에 대해서만 일반화됨.  근데 걍 씀 

 

• 각 광고주 j는 각자 본인들의 bid b_j를 제시함.
• b_j: 기꺼이 지불할 클릭 당 가격 
• slot i 는 i번째로 높은 가격을 제시한 bidder에게 할당하고, 이때 가격은 i+1번째로 높은 가격으로 책정함. 

 

GSP and VCG

• slot이 하나일 땐, 둘 다 second-price auction이랑 같은 결과임
• slot이 여러 개 일 땐, 각각 다른 결과가 나오게 됨. 

가격 결정 방법

VCG

바이어 j가 아이템 i를 가져감으로써 다른 바이어가 가지는 harm의 크기로 결정

 

GSP

bids per click - b1, b2, ... 큰 것부터 정렬시키고, i에 대한 다음 사람의 가격 bi+1을 가지고 결정함.

price = ri * b(i+1) 

ri : i가 가지는 클릭당 revenue

 

GSP 특징

• 구글이 개발함 
• advertiser -> player
• bid -> strategy
• payoff -> revenue - price
• Nash equilibira -> 어떤 광고주도 본인의 bid를 바꿀 인센티브가 없는 상황! 을 추구함 

 

• truth-telling이 nash equilibria를 구성하는 건 아님 
• 여러 개의 equilibria가 존재 가능. 그중에는 total valuation을 최대화하지 않는 것도 있음 

 

• 반드시 적어도 하나의 nash equlibrium set 존재 
• 여러 equlibria 중 total advertiser valuation을 극대화시키는 것이 하나 있음 

 

• GSP는 Nash equilibria를 구성하지만, VCG의 몇 가지 좋은 특징들은 없음.
• 서치 엔진 회사가 관심 있는 것은 결국 그들의 revenue를 극대화하는 것 
• 어떤 GSP가 좋고 나쁜지는 명확하지 않음 - open question

 

 

Truth-telling may not be an equilibrium for GSP

- 만약 각 광고주들이 true value를 bid로 제시한다고 해보자. 

sorting -> 순서대로 가져간다.

x는 a는 두 번째로 큰 y의 revenue per click에 해당하는 가격 10*6에 사간다.

x에게 a의 true valuation = 10*7 = 70이기 때문에, payoff = 70-60 = 10

 

만약, x가 거짓으로 bid=5로 제시한다고 해보자. 

x는 그럼 두번째 슬럿인 b를 가져가게 되고, 이때 가격은 z의 가격 4*1 = 4이다. 

x가 b에 대해 가지는 valuation = 4*7 = 28이기 때문에 payoff = 28-4 = 24이다. 

 

-> x는 거짓으로 bid를 제시하는 것이 더 이득이다!

-> truth telling != nash equilibrium 

 

Multiple and Non-Optimal Equilibria 

• 하나 이상의 equilibrium set of bid 존재 가능함. 
• 일부는 socially non-optimal assignment한 결과를 내기도 함. 

 

Revenue of GSP and VCG 

- GSP는 여러 가지의 equilibria 존재 가능 

- GSP 가격은 VCG 가격(고정)보다 높을 수도 있고, 낮을 수도 있음 

- 서치 엔진은 최대치가 더 높으니까 GSP 씀

 

 

x, y, z의 bid가 각각 5, 4, 2 일 때 - 각자 내는 금액은 10*4, 4*2, 0, 합치면 48 = 서치 엔진이 버는 돈 

만약 bid가 각각 3, 5, 1일 때 - 각자 내는 금액은 4*1, 10*3, 0, 합하면 34 = 서치 엔진이 버는 돈 

advertiser들의 true valuation이 저렇게 될 때, VCG 가격

x가 없으면, y=60-24=36만큼, z=4-0=4만큼 이득을 봄. x의 가격은 40

y가 없으면,  z = 4-0만큼 이득을 봄. y의 가격은 4

총 합 44가 서치 엔진이 버는 돈. 

 

GSP는 48 또는 34

VCG는 44

-> 48을 벌 수도 있기 때문에 서치 엔진은 GSP를 쓴다~ 

 

GSP에서 socially optimal assignment를 보장할 수 없을까 ? 

market-clearing price를 생각해 보자. 

MCP가 결정되면 그때의 매칭 결과는 socially optimal 하다. 

 

maket clearing price (40, 4, 0)를 계산하고, 이 가격을 클릭 당 가격으로 바꿔줌.

각 슬럿의 시간당 클릭 수는 10, 4, 0 이므로 나눠주면 (4, 1, 0) 0은 걍 0.

그리고 4, 1은 y와 z의 bid가 됨. x는 4 이상만 내면 된다. 

 

 

정리하면, 

GSP는 buyer들로부터 하나의 bid 를 받고, 가격 순으로 매칭시킴.

그리고 낙찰가는 second price, 즉 하나 더 낮은 가격으로 매김.

valuation이 고정된 상태에서, 여러 bid가격 집합에 의해 nash equilibria 만들어질 수 있음. 

적어도 하나의 equilibrium은 존재함. 

그리고 그중 하나는 반드시 socially optimal 한 결과를 가짐. 

 

GSP 가격은 VCG 가격보다 높을 수도 있고, 낮을 수도 있음. 높을 수도 있기 때문에 GSP를 쓴다.