검색 엔진 회사가 검색어로 수익을 내는 방법 (Ad-Auctions Problem)

Photo by Nathana Rebouças on Unsplash

물론 그 외에도 다양한 방안이 있겠지만, 다음이나 네이버와 같은 검색 엔진(search engine) 회사들이 수익을 내는 가장 기본적인 방법은 광고입니다. 하지만 이들의 광고 방식은 정해진 지면에 싣거나 정해진 시간에 방송하는 전통적인 광고와는 다른 점이 있죠. 바로 각 사용자의 정보를 알고 이를 토대로 각각에게 알맞는 광고를 보여줄 수 있다는 것입니다. 이들이 활용할 수 있는 정보는 매우 다양하지만, 그 중에서도 검색 엔진 회사가 가장 쉽게 이용할 수 있는 것은 사용자의 검색어입니다. 사용자가 어떤 특정한 검색어를 입력하면, 해당 검색어에 알맞는 광고를 보여주는 것이죠. 여러분들도 검색 엔진에서 무언가를 찾을 때 이와 연관된 광고가 결과 페이지에 함께 나타나는 것을 본 경험이 있을 것입니다.

 

회사마다 검색어 광고의 수익 모델이 다르겠지만(게다가 자세한 내용은 회사 기밀이겠죠.) 이번에 우리가 함께 고민할 모델은 다음과 같습니다. 먼저 각 광고주는 검색 엔진 회사에 다음 세 가지를 제출합니다.

• 검색어 목록 : 자신의 광고와 밀접한 관련이 있는 검색어의 목록. 만약 어떤 사용자가 이 중 한 검색어를 입력했을 때, 사용자의 결과 페이지에 해당 광고가 게재될 수 있다.
• 입찰가 : 만약 어떤 사용자의 결과 페이지에 자신의 광고가 게재되었을 때 회사에 지불하는 금액.
• 예산 : 회사로 보낼 수 있는 최대 금액.

이제 사용자가 어떤 검색어를 입력하면, 회사는 결과 페이지에 광고를 보여주지 않을 수도 있고 해당 검색어와 관련된 광고 중 하나를 골라 이를 보여줄 수도 있습니다. 만약 광고가 게재되었다면 해당 광고주는 회사에 미리 제출한 입찰가만큼의 금액을 지불합니다. 만약 광고주에게 남은 예산이 입찰가보다 적은 경우에는 남은 금액을 모두 보내는 것으로 퉁칩니다. 당연한 말이겠지만 위 작업은 번복할 수 없습니다. 다시 말해, 사용자에게 어떤 광고를 게재하고 난 후에 다른 광고를 대신 게재할 수 없습니다. 시간을 되돌릴 수는 없는 노릇이니까요. 이러한 상황에서 회사의 목표는 당연 최대로 수익을 얻는 것입니다.

 

회사의 입장에서는 미래에 어떤 검색어가 들어올지 아는 방법은 없습니다. 설령 어느 정도는 예측을 할 수 있다고 하여도, 최악의 경우에도 가능한 높은 수익을 올릴 수 있는 방법을 고민하는 것은 매우 중요한 일입니다. 따라서 우리는 위 모델을 일종의 온라인 문제(online problem)로 생각할 수 있습니다. 따라서 우리의 목표도 좋은 경쟁비(competitive ratio)를 갖는 온라인 알고리즘(online algorithm)을 구상하는 것이 되겠죠.

 

위 모델이 많은 검색 엔진 회사의 검색어 광고 수익 모델을 대변한다고 말하기에는 다소간 단순한 면이 없지 않지만, 그럼에도 꽤나 합리적인 수익 모델이라는 점은 여러분들도 인정하시리라 생각합니다. 실제로, 이 모델은 Mehta, Saberi, Vazirani, & Vazirani[1]에 의해 처음 제시되었으며^ㄱ, 이후 수많은 학자들과 엔지니어들에 의해 깊이 연구되었습니다. 그 중에서도 이번 포스트에서 보여드릴 분석은 Buchibinder, Jain, & Naor[2]의 것입니다.^ㄴ 구체적으로 아래에서 소개할 내용은 입찰가에 비해 예산의 액수가 매우 큰 경우 \(1-1/e\)의 경쟁비를 갖는 알고리즘이 존재한다는 것입니다. 실제로도 각 광고주들이 광고 한두 개만 보여주고 끝내지는 않을 것이므로 예산이 입찰가보다 액수가 현저히 크다는 가정은 그리 나쁜 가정은 아닙니다.

문제 정의 및 유용한 부등식

광고 경매 문제를 수학적인 기호와 함께 다시 정의해보도록 하겠습니다. 맨 처음에 우리에게는 광고주의 집합 \(N\)이 입력으로 주어집니다. 각 광고주 \(i \in N\)는 자신들이 지불할 수 있는 예산 \( B_i \in \mathbb{Q}_+\)를 갖습니다. 이후 매 단계마다 검색어가 주어집니다. 이때, 모든 광고주 \(i \in N\)에 대해서, \(i\)의 광고가 검색어 \(j\)의 결과 페이지에 게재되었을 때 이 광고주가 지불할 입찰가 \(b_{ij} \in \mathbb{Q}_+\)가 함께 주어지게 됩니다. 참고로, 위 설명에서는 각 광고주마다 검색어 목록을 받는다고 하였지만, 이번에는 모든 광고주가 가능한 모든 검색어에 입찰가를 냈다고 가정하겠습니다. 만약 광고주가 관심이 없는 검색어라면 \(b_{ij} = 0\)으로 보면 됩니다.

 

매번 검색어 \(j\)가 들어왔을 때, 우리는 광고를 최대 하나 게재할 수 있습니다. 만약 광고주 \(i\)의 광고를 올린다면 우리는 \(b_{ij}\)의 수익을 얻고, 그 금액만큼 \(i\)의 예산이 감소합니다. 단, \(i\)의 가용 예산이  \(b_{ij}\)보다 적은 경우에는 남은 예산을 모두 지불하는 것으로 퉁칩니다. 다시 말해, 각 광고주가 매번 광고를 게재하여서 지불하는 금액의 총합은 언제든지 미리 정한 예산을 넘지 않습니다. 어떤 검색어에는 광고를 게재하지 않을 수 있으며, 이 경우에 벌어들이는 수익은 없다고 가정합니다. 마지막으로, 광고를 게재할지 말지, 그리고 게재한다면 어느 광고를 올릴지는 검색어가 들어온 즉시 결정해야 하며, 한번 결정되면 이후에 다시는 번복될 수 없습니다. 우리의 목표는 이 모델에서 최대한 높은 수익을 올리는 것입니다.

 

들어가기에 앞서 아래 분석에서 요긴하게 사용될 부등식을 소개하겠습니다.

정리 1. 유용한 부등식

---

임의의 두 양수 \(a, b \in \mathbb{R}_+\)(단, \(a \leq b\))에 대해 \( (1+a) \geq (1+b)^{\frac{a}{b}} \)

[증명] 함수 \( y = \frac{\ln (1 + x)}{x} \)는 \(x > 0\)에 대해 감소함수입니다. 따라서, \[ \frac{\ln(1+a)}{a} \geq \frac{\ln(1+b)}{b} \Rightarrow \ln(1+a) \geq \frac{a}{b} \ln(1+b) \]를 만족하게 됩니다. \( y = \ln x \)는 \( x > 0 \)에 대해 증가함수이므로 정리의 부등식을 얻을 수 있습니다. ■

선형 계획법으로 표현하기

이전에 다룬 스키 대여 문제(ski rental problem)에서도 문제를 선형 계획법(linear programming)으로 표현하면 분석이 가능한 좋은 온라인 알고리즘을 얻는 데 큰 도움이 되었습니다.

2020/03/16 - [온라인 알고리즘/Ski rental] - [스키 대여 문제 / Ski Rental Problem] 선형 계획법을 이용한 Randomized Algorithm

[스키 대여 문제 / Ski Rental Problem] 선형 계획법을 이용한 Randomized Algorithm

이에 비추어, 이번에도 위 문제를 선형 계획법으로 먼저 표현해보도록 하겠습니다. 먼저 결정 변수(decision variable) \(x_{ij}\)는 검색어 \(j\)의 결과 페이지에 광고주 \(i\)의 광고를 게재한 경우 \( x_{ij} = 1 \)을, 그렇지 않은 경우에는 \(x_{ij} = 0\)을 갖는 변수로 정의하겠습니다. 그러면 우리는 문제를 다음과 같이 표현할 수 있습니다. 아래에서 \(M\)은 지금까지 들어온 검색어의 집합을 의미합니다.

\[ \begin{array}{lrll} \text{maximize} & \displaystyle \sum_{i \in N} \sum_{j \in M} b_{ij} x_{ij} & & \\ \text{subject to} & \displaystyle \sum_{i \in N} x_{ij} & \leq 1, & \forall j \in M,\\ & \displaystyle \sum_{j \in M} b_{ij} x_{ij} & \leq B_i, & \forall i \in N,\\ & x_{ij} & \geq 0, & \forall i \in N, j \in M. \end{array} \tag{P} \]

첫 번째 제약 조건(constraint)는 각 검색어에는 최대 하나의 광고를 게재할 수 있다는 것을 나타낸 것이고, 두 번째는 각 광고주는 자신의 예산만큼만 지불한다는 것을 나타내고 있습니다. 마지막은 원래 \( x_{ij} \in \{0, 1\} \)이어야 하겠지만, 이를 완화(relax)하여 적었습니다. 스키 대여 문제에서도 같은 작업을 진행했으니 참고하시기 바랍니다.

 

이 문제는 온라인 문제이므로 매번 검색어 \(j\)가 새로 입력될 때마다 문제 P가 점점 커진다는 것을 알 수 있습니다. 정확히 말하면, 그때마다 \(j\)와 연관된 새로운 결정 변수 \(\{ x_{ij} \}_{i \in N}\)와 첫 번째 제약 조건에 해당하는 \( \sum_{i \in N} x_{ij} \leq 1 \)이 생성되며, 두 번째 제약 조건의 좌변에는 \(b_{ij}x_{ij}\)가 추가됩니다. 그후 우리는 이번에 새로 생긴 결정 변수들의 값을 곧바로 정해주어야 하고, 이는 비번복성에 의해 이후에는 절대 바뀌지 않습니다. 당연한 얘기지만, 값이 정해진 후에도 제약 조건은 계속 만족해야 합니다.

 

쌍대성(duality)은 선형 계획법에서 매우 중요한 개념으로, 온라인 알고리즘을 분석할 때에도 많이 활용됩니다. 자세한 내용은 아래를 참조하세요.

2019/07/15 - [수학적 도구/Linear programming] - [선형 계획법] 쌍대성(Duality)

[선형 계획법] 쌍대성(Duality)

문제 P의 쌍대 문제(dual program)는 다음과 같이 정의됩니다.

\[ \begin{array}{lrll} \text{minimize} & \displaystyle \sum_{i \in N} B_i y_i + \sum_{j \in M} z_j & & \\ \text{subject to} & b_{ij}y_i + z_j & \geq b_{ij}, & \forall i \in N, j \in M, \\ & y_i & \geq 0, & \forall i \in N, \\ & z_j & \geq 0, & \forall j \in M. \end{array} \tag{D} \]

앞에서와 마찬가지로 매번 검색어 \(j\)가 들어왔을 때 이 문제도 점점 불어나게 됩니다. 정확히는 결정 변수 \(  z_j \)와 임의의 \(i \in N\)에 대해 제약 조건 \( b_{ij}y_i + z_j \geq b_{ij} \)가 새로 생성됩니다.

 

다음 정리는 선형 계획법의 쌍대성을 통해 온라인 알고리즘의 경쟁성을 증명할 수 있다는 사실을 보여줍니다. 다음 정리와 비슷한 정리를 스키 대여 문제를 다룬 글에서도 소개한 적이 있습니다.(해당 글의 정리 2) 관심이 있으시면 해당 문서를 참조하시기 바랍니다.

정리 2. 쌍대성을 이용한 경쟁성

---

광고 경매 문제를 경쟁적으로 해결하는 알고리즘이 매번 다음 세 가지를 만족하면, 그 알고리즘은 \(\alpha\)-competitive algorithm이다.

1. 알고리즘의 출력은 \(x\)로 표현되며, 이는 원 문제 P에서 가능한 해(feasible solution)이다.
2. 동시에 알고리즘이 쌍대 문제 D에서 가능한 \((y, z)\)를 유지한다.
3. 매 단계마다 원 문제의 목적 함수(objective function)의 증가량은 쌍대 문제 목적 함수의 증가량의 \(\alpha\) 배보다 항상 크거나 같다.

[증명] 어느 순간까지 얻을 수 있는 최대 수익을 \( \mathsf{OPT} \)라고 하겠습니다. 조건 B와 선형 계획법의 약한 쌍대성에 의하여 \[ \sum_{i \in N} B_i y_i + \sum_{j \in M} z_j \geq \mathsf{OPT} \]임을 알 수 있습니다. 그러면 조건 C에 의해 \[ \sum_{i \in N}\sum_{j \in M} b_{ij} x_{ij} \geq \alpha \cdot \left[ \sum_{i \in N} B_i y_i + \sum_{j \in M} z_j \right] \geq \alpha \cdot \mathsf{OPT}\]가 성립하게 됩니다. ■

알고리즘 및 분석

이제 알고리즘을 소개하도록 하겠습니다. 알고리즘에서는 적절하게 고른 상수 \(c\)가 사용되는데, 이는 다음과 같이 정의됩니다. 먼저 입찰가에서 예산을 나눈 비율 중 가장 큰 값을 \(r\)로 정의합니다. 다시 말해, \( r := \max_{i \in N, j \in M} \frac{b_{ij}}{B_i} \)입니다. 그다음, \(c := (1 + r)^{\frac{1}{r}} \)로 정의하겠습니다. 모든 광고주는 미리 검색어마다의 입찰가를 제시할 것이므로 \(r\)과 \(c\)는 검색어를 입력 받기 전부터 구할 수 있습니다.

알고리즘 1. An online algorithm for maximizing ad-auctions revenue

---

초기 입력: 광고주 \(N\), 각 광고주 \(i\)의 초기 예산 \(B_i\)

출력: 매 검색어마다 광고 게재 방법

 

1. 모든 광고주 \(i \in N\)에 대해, \( y_i \gets 0 \).
2. 매번 검색어 \(j\)가 들어올 때마다 다음을 수행한다.
   1. \(b_{ij} (1 - y_i)\)의 값이 가장 큰 광고주 \(i\)를 찾는다.
   2. 만약 \(y_i \geq 1\)이라면 광고를 게재하지 않고 여기서 끝낸다. 그렇지 않다면 아래로 진행한다.
   3. 검색어 \(j\)에 광고주 \(i\)의 광고를 게재한다. 광고주 \(i\)는 예산에서 \(b_{ij}\)를 지불한다. 만약 남은 예산이 부족하면 남은 금액으로 퉁친다.
   4. \( x_{ij} \gets 1 \)
   5. \( z_j \gets b_{ij} (1 - y_i) \)
   6. \( y_i \gets y_i \left( 1 + \frac{b_{ij}}{B_i} \right) + \frac{b_{ij}}{(c - 1) B_i}  \)

앞에서 설명한 대로 이 알고리즘의 경쟁성을 정리 2에 의거하여 보이도록 하겠습니다. 먼저 해당 정리의 조건 B가 만족한다는 것을 증명하도록 하죠.

정리 3. 쌍대 문제의 가능한 해를 유지하는 성질

---

알고리즘 1의 \( (y, z) \)는 계속 쌍대 문제 D의 가능한 해이다.

[증명] 알고리즘이 시작할 때에는 들어온 검색어가 없으므로 문제 D에는 \(y_i \geq 0\)에 해당하는 제약 조건만 존재합니다. 알고리즘의 단계 1에서 모든 광고주 \(i \in N\)에 대해 \( y_i = 0 \)으로 설정하였으므로 정리의 명제가 성립합니다.

 

이제 어떤 검색어 \(j\)가 들어왔다고 가정하겠습니다. 그러면 문제 D에 \(z_j \geq 0\)과 모든 \(i \in N\)에 대해 \( b_{ij}y_i + z_j \geq b_{ij} \)에 해당하는 제약 조건이 새로 추가됩니다. 알고리즘이 진행하는 동안 \(y_i\)의 값은 증가하기만 하므로, 매번 검색어 \(j\)가 들어왔을 때 새로 생긴 제약 조건이 만족한다는 것만 보이면 정리의 명제가 성립한다는 것을 알 수 있습니다.

 

단계 2-a에서 알고리즘은 \( b_{ij}(1 - y_i) \)의 값이 가장 큰 \(i\)를 찾고, 단계 2-e에서 \(z_j = b_{ij} (1 - y_i) \)로 둡니다. 따라서, 임의의 \(i' \in N\)에 대해, \[ b_{i' j} (1 - y_{i'}) \leq b_{ij} (1 - y_i) = z_j \]가 성립합니다. 이를 정리하면 이번에 새로 생긴 제약 조건은 모두 만족하게 됩니다. ■

 

다음은 조건 C가 만족한다는 것을 보이겠습니다.

정리 4. 두 해의 증가량

---

매번 \(x\)에 의한 원 문제의 목적 함수 증가량은 \( (y, z) \)에 의한 쌍대 문제의 목적 함수 증가량의 \( 1-1/c \) 배보다 크거나 같다.

[증명] 만약 알고리즘이 이번에 들어온 검색어 \(j\)에 광고를 게재하지 않는다고 결정하면 \(x\)와 \( (y, z) \)는 그대로이므로 자명하게 정리의 명제가 만족합니다. 따라서 \(j\)에 광고주 \(i\)의 광고를 올린다고 가정하겠습니다. 단계 2-d에 의해 정확히 \( x_{ij} \)의 값이 \( 0 \)에서 \(1\)로 바뀌므로, \(x\)에 의한 원 문제의 목적 함수 증가량은 정확히 \( b_{ij} \)입니다.

 

이제 쌍대 문제의 목적 함수 증가량을 따져 보도록 하겠습니다. 값이 변하는 원소는 \(y_i\)와 \(z_j\)뿐입니다. 먼저, \(z_j\)는 이번에 새로 생성된 변수이므로 \(0\)에서 \( b_{ij} (1 - y_i) \)로 증가합니다. \(y_i\)는 정확히 \( \frac{b_{ij} y_i}{B_i} + \frac{b_{ij}}{(c - 1) B_i} \)만큼 증가한다는 것을 알 수 있습니다. (값에서 쓰인 \(y_i\)는 단계 2-f를 처리하기 전의 \(y_i\)의 값을 나타냅니다.) 따라서 증가량은 \[ B_i \cdot \left[ \frac{b_{ij} y_i}{B_i} + \frac{b_{ij}}{(c - 1) B_i} \right] + b_{ij} (1 - y_i) = b_{ij} \cdot \left( 1 + \frac{1}{c - 1} \right)\]가 됩니다. 이를 통해 정리의 명제가 성립한다는 것을 쉽게 확인할 수 있습니다. ■

 

마지막으로 조건 A가 성립한다는 것을 보여야 합니다. 하지만 안타깝게도 알고리즘을 수행하다 보면 \(x\)가 이 조건을 만족하지 못하는 경우가 발생하는데요. 대신 그럼에도 \(x\)가 '거의' 만족한다는 사실을 보이고자 합니다. 이를 보이기 위해서는 먼저 다음의 흥미로운 성질을 확인해야 합니다.

정리 5. 광고주가 과도한 지출을 하지 않는 이유

---

임의의 광고주 \(i\)에 대해서 알고리즘이 진행되는 동안 다음을 항상 만족한다.

\[ y_i \geq \frac{1}{c - 1} \left[ c^{\frac{\sum_{j \in M} b_{ij} x_{ij}}{B_i}} - 1 \right] \]

[증명] 수학적 귀납법으로 보이겠습니다. 알고리즘이 시작할 당시에는 입력된 검색어가 없으므로 괄호 안 \(c\)의 지수가 \(0\)이 되며, 따라서 우변이 \(0\)이 됩니다. 처음에 \(y_i = 0\)으로 설정되므로 정리의 명제가 만족하게 됩니다.

 

언젠가 검색어 \(k\)가 들어오고, \(k\)가 \(i\)의 광고를 게재한 경우에는 \(y_i\)의 값이 다음과 같이 증가하게 됩니다. 구분을 위해 증가한 후의 \(y_i\)를 \(y_i'\)으로 표현하겠습니다. 즉, \(y_i\)는 증가하기 전의 값을 의미합니다.

\[ y_i' = y_i \left( 1 + \frac{b_{ik}}{B_i} \right) + \frac{b_{ik}}{(c - 1) B_i} \geq \frac{1}{c-1} \left[ c^{\frac{\sum_{j : j < k} b_{ij} x_{ij}}{B_i}} - 1 \right] \cdot \left( 1 + \frac{b_{ik}}{B_i} \right) + \frac{b_{ik}}{(c - 1) B_i} \]

여기서 \(j < k\)는 \(j\)가 \(k\)보다 먼저 입력되었다는 것을 의미하고, 부등식은 귀납 가설(induction hypothesis)를 통해 유도됩니다. 우변을 정리하면 다음을 이끌어낼 수 있습니다.

\[ y_i' \geq \frac{1}{c - 1} \left[ c^{\frac{\sum_{j : j < k} b_{ij} x_{ij}}{B_i}} \left( 1 + \frac{b_{ik}}{B_i} \right) - 1 \right] \]

여기서 \(r\)의 정의에 의해 \( 0 \leq \frac{b_{ik}}{B_i} \leq r \)이고, 정리 1에 \( a := \frac{b_{ik}}{B_i}, b := r \)을 넣으면, \[ (1 + \frac{b_{ik}}{B_i}) \geq (1 + r)^{\frac{b_{ik}}{r B_i}} = c^{\frac{b_{ik}}{B_i}} \]를 얻을 수 있습니다.(등식은 \(c\)의 정의로부터 얻을 수 있습니다.) 이를 원래 부등식에 적용하면,

\[ y_i' \geq \frac{1}{c - 1} \left[ c^{\frac{\sum_{j : j < k} b_{ij} x_{ij}}{B_i}} \cdot c^{\frac{b_{ik}}{B_i}} - 1 \right] = \frac{1}{c - 1} \left[ c^{\frac{\sum_{j \in M} b_{ij} x_{ij}}{B_i}} - 1 \right]  \]

임을 보일 수 있습니다. 등식은 \(x_{ik} = 1\)이라는 점에서 유도할 수 있습니다. 이것으로 모든 증명이 완성됩니다. ■

 

이제 \(x\)가 원 문제의 제약 조건들을 거의 만족한다는 사실을 보이도록 하죠.

정리 6. 원 문제에 거의 가능한 해를 유지하는 성질

---

알고리즘 1의 \(x\)는 원 문제 P의 제약 조건들을 거의 만족한다. 자세히 말하자면, 두 번째 제약 조건이, 임의의 광고주 \(i \in N\)에 대해, \[ \sum_{j \in M} b_{ij} x_{ij} \leq B_i + \max_{j \in M} b_{ij} \]를 대신 만족하는 것으로 약간 어긋나게 된다. 나머지 제약 조건은 원 문제에 명시된 대로 만족한다.

[증명] 각 검색어에 대해서 알고리즘은 최대 하나의 광고를 게재하므로 두 번째 제약 조건을 제외한 나머지 제약 조건들은 모두 만족한다는 것을 쉽게 알 수 있습니다. 임의의 광고주 \(i \in N\)에 대해, 정리 5를 통해 알 수 있는 사실은, 언젠가 \( \sum_{j \in M} b_{ij} x_{ij} \geq B_i \)가 되면, 반드시 \( y_i \geq 1 \)이 된다는 것입니다. 따라서 \( \sum_{j \in M} b_{ij} x_{ij} \geq B_i \)를 만족하게 된 후부터는 알고리즘의 단계 2-b에 의해 \(i\)의 광고가 어떤 검색어에도 올라가지 않게 됩니다. 좌변이 한번에 증가할 수 있는 최대 양은 \( \max_{j \in M} b_{ij} \)이므로, 정리의 명제가 성립한다는 것을 알 수 있습니다. ■

 

이것으로 알고리즘 1이 좋은 경쟁비를 갖는 온라인 알고리즘이라는 사실을 분석할 수 있습니다.

정리 7. 알고리즘 1의 경쟁성

---

알고리즘 1은 \( (1 - 1/c) \cdot ( 1 - r ) \)의 경쟁비를 갖는 알고리즘이다. 만약 입찰가에 비해 예산 액수가 현저히 크다면, 즉 \(r \rightarrow 0\)이라면, 이 알고리즘은 \( 1- 1/e \)의 경쟁비를 갖는다.

[증명] 임의의 광고주 \(i\)에 대해, \[ \frac{B_i}{B_i + \max_{j \in M} b_{ij}} \geq 1 - \frac{\max_{j \in M} b_{ij}}{B_i} \geq 1 - r\]이 성립하므로 정리 6에 의해 \( x' := (1 - r) x \)는 원 문제 P의 모든 제약 조건을 만족시킵니다. 흥미로운 사실은 \( \sum_{i \in N} \sum_{j \in M} b_{ij} x'_{ij} \)가 알고리즘이 실제로 광고주들로부터 벌어들이는 수익의 하한(lower bound)을 이룬다는 점입니다. 왜냐하면, 알고리즘이 어떤 광고주의 예산을 초과하여 광고를 할당한 경우에는 광고주의 예산 전체를 수익으로 가져오므로, 각 광고주 \(i \in N \)마다 적어도 \[ \left[ \sum_{j \in M} b_{ij} x_{ij} \right] \cdot \frac{B_i}{B_i + \max_{j \in M} b_{ij}} \geq \left[ \sum_{j \in M} b_{ij} x_{ij} \right] \cdot ( 1 - r ) = \sum_{j \in M} b_{ij} x'_{ij} \]만큼의 수익을 챙기기 때문입니다. 정리 4에 의해 매번 \(x'\)에 의한 원 문제의 목적 함수 증가량은 \( (y, z) \)에 의한 쌍대 문제의 목적 함수 증가량의 \( (1-1/c) \cdot (1 - r) \) 배보다 크거나 같습니다. 따라서 \(x'\)과 \( (y, z) \)를 정리 2에 대입하면 우리 알고리즘이 목표로 하는 경쟁비를 갖는다는 것을 확인할 수 있습니다. ■

마치며

이것으로 검색 엔진 회사들이 검색어를 통해 광고 수익을 올리고자 할 때 어떻게 하면 어떠한 상황에서도 괜찮은 수익을 얻을 수 있는지에 대해서 알아보았습니다. 간단히 정리하면, 예산의 액수가 입찰가에 비해 현저히 큰 상황에는 검색어가 어떻게 들어오든지 간에 벌어들일 수 있는 최대 수익에 적어도 \( 1 - 1/e \) 배 만큼은 벌어들이는 방법이 존재한다는 것을 보였습니다.

 

본문에서는 크게 언급을 하지 않았지만, 사실 이 문제는 온라인 매칭 문제(online matching problem)의 한 변형입니다. 위 문제의 답을 검색어와 광고주 사이의 일종의 매칭(matching)으로 볼 수 있기 때문입니다. 다음에는 해당 문제들의 원형 격인 온라인 이분 매칭 문제(online bipartite matching problem)에 대해서 알아보도록 하겠습니다.

 

혹시 글에 잘못된 점이 있거나, 궁금하신 점이 있으시면 댓글로 알려주시기 바랍니다. 고맙습니다. :)

각주

ㄱ. 이 저자들의 모델 이름은 애드워즈(AdWords)입니다.

 

ㄴ. 이 저자들은 이 모델을 광고 경매(ad-auctions)라고 부릅니다. 이 글에서는 이 저자들의 분석 방법을 소개하므로 글의 제목도 애드워즈 대신 광고 경매로 지었습니다.

참조

[1] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. "Adwords and generalized online matching." Journal of the ACM (JACM) 54, no. 5 (2007)

 

[2] Niv Buchbinder, Kamal Jain, and Joseph (Seffi) Naor. "Online primal-dual algorithms for maximizing ad-auctions revenue." In European Symposium on Algorithms (ESA), pp. 253-264. Springer, Berlin, Heidelberg, 2007.