Landscape na powierzchni zewnętrznej

Sformułowanie problemu

Problem optymalizacyjny:

$$\begin{array}{rl}\underset{b_i}{\max }& \sum _i\mathbb{P}[{\text{win}}_i\mid b_i]\cdot v_i\\ \text{s.t.}& \underset{\text{przychody}}{\underbrace{\sum _i\mathbb{P}[{\text{win}}_i\mid b_i]\cdot v_i}}\ge \underset{\text{wydatki}}{\underbrace{\sum _i\mathbb{P}[{\text{win}}_i\mid b_i]\cdot b_i}}\end{array}$$

gdzie:

• $v_i$ to oczekiwany przychód z $i$-tego bid-requesta (wartość $i$-tego bid-requesta)
• $b_i$ to cena, którą biddujemy $i$-ty bid-request

Intuicja

Rozważmy pojedynczy bid-request i funkcję prawdopodobieństwa wygrania od ceny, którą zabidujemy:

2024.02.06 Planowanie H1 2024 Drawing 2024-01-31 10.23.37.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

Link to original

Wyróżnijmy dwie sytuacje:

• sytuacja A - przesunięcie się w lewo po krzywej - duża zmiana $b_i$ powoduja małą zmianę $\mathbb{P}[{\text{win}}_i|b_i]$
• sytuacja B - przesunięcie się w prawo po krzywej - mała zmiana $b_i$ powoduje dużą zmianę $\mathbb{P}[{\text{win}}_i|b_i]$

Konkrety

Oznaczenia

$\mathcal{W}$ - wydatki gdybyśmy grali jak dotychczas $\mathcal{P}$ - przychody gdybyśmy grali jak dotychczas $\gamma =\frac{\mathcal{P}}{\mathcal{W}}$

Marża

Zakładamy, że $\frac{\mathcal{P}}{\mathcal{W}}=\gamma >0$. W HIG najczęściej $\gamma <1$. Uwaga: $\gamma =\text{margin}+1$

Analiza zmienności

Zamodelowanie całej funkcji zależności win-ratio od ceny jest trudne, więc możemy uprościć problem i zastanowić się jak zmienią się przychody i wydatki dla konkretnego bid-requestu i konkretnej ceny, którą chcemy zabidować, jeśli zmodyfikujemy bidowaną cenę o $ϵ$.

Jak więc zmieniają się oczekiwane przychody i wydatki gdy zmienimy $b_i$ o ${ϵ}_i\in \mathbb{R}$?

$$\begin{array}{rl}\Delta {\text{przychod}}_i& =\mathbb{P}[{\text{win}}_i\mid b_i+{ϵ}_i]\cdot v_i-\mathbb{P}[{\text{win}}_i\mid b_i]\cdot v_i\\ & =v_i\cdot (\mathbb{P}[{\text{win}}_i\mid b_i+{ϵ}_i]-\mathbb{P}[{\text{win}}_i\mid b_i])\end{array}$$ $$\begin{array}{rl}\Delta {\text{wydatki}}_i& =\mathbb{P}[{\text{win}}_i\mid b_i+{ϵ}_i]\cdot (b_i+{ϵ}_i)-\mathbb{P}[{\text{win}}_i\mid b_i]\cdot b_i\\ & =b_i\cdot (\mathbb{P}[{\text{win}}_i\mid b_i+{ϵ}_i]-\mathbb{P}[{\text{win}}_i\mid b_i])+{ϵ}_i\cdot \mathbb{P}[{\text{win}}_i\mid b_i+{ϵ}_i]\end{array}$$

Możemy zwięźle napisać

$$\begin{array}{rl}\Delta {\text{wydatki}}_i& =b_i{\beta }_i+{\alpha }_i\\ \Delta {\text{przychody}}_i& =v_i{\beta }_i\end{array}$$

gdzie

$$\begin{array}{rl}{\beta }_i& =\mathbb{P}[{\text{win}}_i\mid b_i+{ϵ}_i]-\mathbb{P}[{\text{win}}_i\mid b_i]\\ {\alpha }_i& ={ϵ}_i\cdot \mathbb{P}[{\text{win}}_i\mid b_i+{ϵ}_i]\end{array}$$

Pierwsza nierówność - maksymalizacja wydatków

Chcemy maksymalizować wydatki, więc chcemy:

$$\begin{array}{rl}\mathcal{W}+\sum _i\Delta {\text{wydatki}}_i& \ge \mathcal{W}\\ \sum _i{b}_i{\beta }_i+{\alpha }_i& \ge 0\end{array}$$

Druga nierówność - marża

Lemat: Marża będzie zachowana wtedy i tylko wtedy gdy będzie spełniona poniższa nierówność: ${\sum }_i{\alpha }_i+{\beta }_i(b_i-\frac{v_i}{\gamma })\le 0$

Dowód: Po interwencji landscapu, marża powinna być zachowana:

$$\begin{array}{rl}\frac{\mathcal{P}-\mathcal{W}}{\mathcal{W}}& \le \frac{\mathcal{P}+{\sum }_i\Delta {\text{przychody}}_i-(\mathcal{W}+{\sum }_i\Delta {\text{wydatki}}_i)}{\mathcal{W}+{\sum }_i\Delta {\text{wydatki}}_i}\\ \frac{\gamma \mathcal{W}-\mathcal{W}}{\mathcal{W}}& \le \frac{\gamma \mathcal{W}+{\sum }_i\Delta {\text{przychody}}_i}{\mathcal{W}+{\sum }_i\Delta {\text{wydatki}}_i}-1\\ \gamma & \le \frac{\gamma \mathcal{W}+{\sum }_i\Delta {\text{przychody}}_i}{\mathcal{W}+{\sum }_i\Delta {\text{wydatki}}_i}\\ \gamma (\mathcal{W}+\sum _i\Delta {\text{wydatki}}_i)& \le \gamma \mathcal{W}+\sum _i\Delta {\text{przychody}}_i\\ \gamma \sum _i\Delta {\text{wydatki}}_i& \le \sum _i\Delta {\text{przychody}}_i\\ \sum _i\gamma (b_i{\beta }_i+{\alpha }_i)& \le \sum _i{v}_i{\beta }_i\\ \sum _i{b}_i{\beta }_i+{\alpha }_i-{\beta }_i\frac{v_i}{\gamma }& \le 0\\ \sum _i{\alpha }_i+{\beta }_i(b_i-\frac{v_i}{\gamma })& \le 0\end{array}$$

Jeśli w pierwszej i drugiej nierówności wprowadzimy oznaczenia:

$$\begin{array}{rl}{\tau }_i& ={\alpha }_i+{\beta }_i(b_i-\frac{v_i}{\gamma })\\ {\omega }_i& ={\beta }_i\frac{v_i}{\gamma }\end{array}$$

to możemy przeformułować nasz problem optymalizacyjny w poniższy sposób:

$$\begin{array}{rl}\max & \sum _i{\tau }_i+{\omega }_i\ge 0\\ \text{s.t. }& {\tau }_i\le 0\end{array}$$

Uwaga: Jeśli model $\mathbb{P}[{\text{win}}_i\mid b_i]$ jest dobrze skalibrowany to dla $b_i$ jak i dla $b_i+{ϵ}_i$ to oszacowanie $\Delta {\text{wydatki}}_i$ też powinno być dobrze skalibrowane. Na pewno??

Jak zoptymalizować powyższy problem?

Niech ${\mathcal{T}}_k={\sum }_{i\le k}{\tau }_i$ oraz ${\Omega }_k={\sum }_{i\le k}{\omega }_i$. Chcemy maksymalizować ${\Omega }_{\infty }+{\mathcal{T}}_{\infty }$ przy założeniu ${\mathcal{T}}_{\infty }\le 0$.

Przypadek (1)

${ϵ}_i=0$

Wówczas ${\alpha }_i={\beta }_i=\Delta {\text{wydatki}}_i=\Delta {\text{przychody}}_i={\tau }_i={\omega }_i=0$

Przypadek (2)

${ϵ}_i>0$

wówczas ${\alpha }_i\ge 0,{\beta }_i\ge 0,\Delta {\text{wydatki}}_i\ge 0,\Delta {\text{przychody}}_i\ge 0$ ${\omega }_i={\beta }_i\cdot \frac{v_i}{\gamma }\ge 0,{\tau }_i+{\omega }_i={\alpha }_i+b_i{\beta }_i\ge 0$ I tu mamy dwa podprzypadki:

1. ${\tau }_i<0$; w takiej sytuacji zawsze opłaca się grać, bo $\mathcal{T}$ maleje, a $(\Omega +\mathcal{T})$ rośnie
2. ${\tau }_i\ge 0$

Przypadek (3)

${ϵ}_i<0$

wówczas ${\alpha }_i\le 0,{\beta }_i\le 0,\Delta {\text{wydatki}}_i\le 0,\Delta {\text{przychody}}_i\le 0$ ${\omega }_i={\beta }_i\cdot \frac{v_i}{\gamma }\le 0,{\tau }_i+{\omega }_i={\alpha }_i+b_i{\beta }_i\le 0$

I tu mamy dwa podprzypadki:

1. ${\tau }_i>0$; tak nigdy nie chcemy grać, bo pogarsza zarówno pierwszą jak i drugą nierówność
2. ${\tau }_i\le 0$

Dzielimy bidowanie na 2 fazy:

• faza 1, wydatkowanie (expending)
• faza 2, oszczędzanie (saving)

Model win-ratio

$\hat{y}=\text{sigmoid}\left(f(X)+\underset{\ge 0}{\underbrace{g(X)}}\cdot 1[ϵ>0]-\underset{\ge 0}{\underbrace{h(X)}}\cdot 1[ϵ<0]\right)$ gdzie $X$ to cechy, a $f,g,h$ są estymowane przez sieć neuronową.