BSD：Auction with ROI constraints

之前關(guān)于BSD的討論：http://www.reibang.com/p/5edf15c787ed [1]

問(wèn)題建模Modeling：

類似[1]中的方案远舅，此處為以無(wú)偏winning rate建模的方式最優(yōu)化期望收益）
當(dāng)然噩咪，這種modeling的一大問(wèn)題是脓鹃，真實(shí)的成功率與無(wú)偏隨機(jī)數(shù)據(jù)是有差距的提揍，因?yàn)槲覀兂鰞r(jià)與市場(chǎng)價(jià)并不互相獨(dú)立脾拆。 $OurBid \not\perp Others'Bid$
形式化：
$u(r)$ 為utility夜惭， $g(r)$ 為預(yù)估的用以計(jì)算roi的收益苦银。
$\max_{b(r)} \int_r u(r) w(b(r)) p(r) dr$
s.t.1： $\int_r b(r) w(b(r)) p(r) dr \leq B$
s.t.2： $\frac {\int_r g(r) w(b(r)) p(r)dr } {\int_r b(r) w(b(r)) p(r) dr} \geq ROI$
得到：
$L(b(r),\lambda_1,\lambda_2) = \int_{r}^{} \left[ -u(r) w(b(r)) + \lambda_1b(r)w(b(r)) + \lambda_2 ROI w(b(r)) b(r) - \lambda_2 w(b(r)) g(r) \right]p(r) dr - \lambda_1 B$

Solution:

KKT condition：

對(duì) $b(r)$ 偏導(dǎo)為0：
$-u(r) \frac{\partial w(b(r))} {\partial b(r)} + (\lambda_1 + \lambda_2ROI)\left[ \frac{\partial w(b(r))} {\partial b(r)} b(r) + w(b(r)) \right] - \lambda_2 \frac{\partial w(b(r))} {\partial b(r)}g(r) = 0$ （1）
給定win函數(shù):
$w(b) = \frac 啸胧 {l + c*b}$ （2）
其中 $l,c$ 為擬合成功率的常數(shù)
求導(dǎo)可得：
$\frac{\partial w(b(r))} {\partial b(r)} = \frac {l}{(l + c*b)^2}$ （3）
將（2）（3）帶入（1）化簡(jiǎn)可得：
$b^2 + \frac {2l} {c} *b - \frac {lu + \lambda_2lg }{c(\lambda_1 + \lambda_2ROI)} = 0$
解得： $b = \sqrt {\frac {l^2}{c^2} + \frac {lu + \lambda_2lg }{c(\lambda_1 + \lambda_2ROI)}} - \frac {l}{c}$
原約束與系數(shù)約束：
$\lambda_1,\lambda_2 \geq 0$
$\int_r b(r) w(b(r)) p(r) dr \leq B$
$\frac {\int_r g(r) w(b(r)) p(r)dr } {\int_r b(r) w(b(r)) p(r) dr} \geq ROI$
budegt互補(bǔ)松弛條件：
$\lambda_1 [\int_r b(r)w(b(r))p(r) dr - B ]=0$
roi互補(bǔ)松弛條件：
$\lambda_2 [ROI\int_r b(r) w(b(r)) p(r) dr -\int_r g(r) w(b(r)) p(r)dr ] = 0$

參數(shù)解法：

Qualification-LICQ：因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=b(r)%20%5Cin%20R%5E1" alt="b(r) \in R^1" mathimg="1">赶站，所以當(dāng)且僅當(dāng)在其解 $x^*$ 處，激活條件對(duì) $x$ （此處即 $b(r)$ ）梯度向量 $\triangledown g \neq 0$ 時(shí)滿足LICQ纺念。
很顯然
1贝椿、在只有一個(gè)限制條件激活時(shí)，只要極值處限制條件對(duì) $b(r)$ 的導(dǎo)數(shù)不為0陷谱，則這個(gè)條件就是滿足的烙博。
2、在多個(gè)限制條件激活時(shí)烟逊，肯定是不滿足的渣窜。
Qualification-SC：對(duì)于多條件激活。判定是否滿足SC宪躯，即優(yōu)化目標(biāo) $f$ 與限制函數(shù) $g$ 图毕，是否都是convex的。判斷方式需要求其二階變分 $\delta ^2 L \geq 0$ 則滿足SC眷唉。
為了簡(jiǎn)化問(wèn)題予颤，我們可以將當(dāng)前假設(shè)的解帶入，即在當(dāng)前假設(shè)下冬阳，是否滿足SC蛤虐。
帶入式子（2）得到如下：
$\frac{\partial^2 {w(b(r))} } {\partial {b(r)^2} } = \frac {-2lc} {(l+cb)^3}$ （4），根據(jù)成功率函數(shù)的圖像肝陪，是恒小于0的驳庭。

Convexity of functional：[1]
a、目標(biāo)函數(shù)的二階變分：
$\delta^2 f = \int [u(r) \frac {2lc} {(l+cb)^3}]p(r)dr$
帶入擬合出來(lái)的常數(shù) $l,c$ 氯窍，在實(shí)際區(qū)間上積分大于等于0
b饲常、預(yù)算限制的二階變分：
$\delta^2 g_1 = \int [\frac {2l}{(l + c*b)^2} + \frac {-2lcb} {(l+cb)^3}]p(r)dr$
$= \int [\frac {2l^2}{(l + c*b)^3}]p(r)dr$
帶入擬合出來(lái)的常數(shù) $l,c$ ，其積分顯然大于等于0
c狼讨、ROI限制的二階變分：
$\delta^2 g_2 =\frac {\delta^2 \int [ROI*b(r) - g(r) ]w(b(r)) p(r)dr} {\delta b(r)^2}$
$= \int [\frac {2l^2ROI+2lcg(r)}{(l+cb)^3}]p(r)dr$
帶入擬合出來(lái)的常數(shù) $l,c$ 贝淤，其積分也顯然大于等于0
所以，由此可以得出政供，當(dāng)前問(wèn)題在兩個(gè)約束都生效時(shí)播聪，滿足SC

情況0： $\lambda_1=0, \lambda_2=0$
則 $b(r) \rightarrow inf$ ，明顯不滿足條件布隔。
情況1： $\lambda_2 = 0$
這種情況下离陶，等價(jià)于只有budget預(yù)算限制。
所以將 $b(r)$ 的解帶入（將 $\lambda_2=0$ 帶入衅檀，其中僅包含 $\lambda_1$ ）招刨，解如下問(wèn)題即可：
$\int_r b(r)w(b(r))p(r) dr - B =0$
觀察 $b(r)$ 解的形式與 $w(b)$ 的形式，可輕易得出 $\lambda_1$ 與預(yù)算消耗成反比 $b(r) \propto \frac {u}{\lambda_1}$
在這個(gè)問(wèn)題中哀军，由于無(wú)論 $\lambda_1$ 如何變化沉眶，排序是不變的打却。所以可以直接將數(shù)據(jù)帶入，求方程的數(shù)值解即可沦寂。
當(dāng)然学密，由于本身也是單調(diào)的淘衙，通過(guò)二分搜索也可以較容易地獲得數(shù)值解传藏。

情況2： $\lambda_1 = 0$
類似地，將 $b(r)$ 的解帶入彤守，求解ROI剛好滿足的狀態(tài)即可毯侦。
$ROI\int_r b(r) w(b(r)) p(r) dr -\int_r g(r) w(b(r)) p(r)dr = 0$
得到 $b(r) \propto (\frac {u}{\lambda_2} + g)$ ，可以看出 $\lambda_2$ 就是u的反向權(quán)重具垫。 $\lambda_2$ 越大侈离，越傾向于用g（收益）來(lái)排序，即參與競(jìng)價(jià)的ad的 $g(r)$ 越大筝蚕，且總體出價(jià)越低（成本低）卦碾，則ROI越大。
所以ROI對(duì) $\lambda_2$ 單調(diào)遞增起宽，可以通過(guò)二分搜索以獲得數(shù)值解洲胖。
（這種情況下，由于 $\lambda_2$ 的變化會(huì)影響排序坯沪，所以無(wú)法將數(shù)值全部帶入直接求其數(shù)值解绿映，當(dāng)然，改寫整個(gè)方程腐晾，將排序過(guò)程加入也是可以的叉弦，但是求解速度也并不一定會(huì)很快）
情況3： $\lambda_1 \neq 0,\lambda_2 \neq 0$
條件：如果上述兩種方式求解出來(lái)分別的ROI，Budget不滿足邊界條件的（即都超出邊界）藻糖。
此時(shí)兩個(gè)KKT乘子都不為0淹冰，
即最優(yōu)解在ROI剛好滿足，Budget也剛好滿足的邊界上巨柒，KKT multiplier等價(jià)于Lagrangine multiplier榄棵。
將 $w(b(r))$ 帶入松弛條件（同拉格朗日，等式約束潘拱，即偏導(dǎo)為0）疹鳄，求解如下方程組：
$\lambda_1,\lambda_2\begin{cases} \int_r b(r)w(b(r))p(r) dr - B =0 \\ ROI\int_r b(r) w(b(r)) p(r) dr -\int_r g(r) w(b(r)) p(r)dr = 0 \end{cases}$
化簡(jiǎn)后無(wú)特殊形式，不易求出解析解可由數(shù)值解法解出芦岂。
當(dāng)然瘪弓，這個(gè)方程組求解的最大問(wèn)題同樣在于，由于 $\lambda_1,\lambda_2$ 會(huì)影響排序禽最，所以很難直接用傳統(tǒng)的數(shù)值優(yōu)化的方程組解法得到解腺怯。（TODO）

問(wèn)題分析：

以下分析針對(duì)我們對(duì)泛函最優(yōu)化的解法其中的排序問(wèn)題的討論袱饭。
由于增加了ROI限制情況下，本身目標(biāo)為u呛占，限制目標(biāo)的函數(shù)g虑乖。

$u(r)$ 和 $g(r)$ 都跟流量具體的分布相關(guān)。

$u(r)$ 和 $g(r)$ 的數(shù)值晾虑，本身會(huì)影響排序疹味。從而影響我們最優(yōu)化問(wèn)題中的具體的數(shù)值分布。

雖然在當(dāng)前體系下帜篇，由于其單調(diào)性（單約束）糙捺，我們能搜索出最優(yōu)解，但是其預(yù)估本身的誤差會(huì)影響排序的結(jié)果（從而影響不同 $\lambda$ 下 $u(r)$ 和 $g(r)$ 的分布笙隙，導(dǎo)致計(jì)算出來(lái)的roi與budget都有偏差）洪灯。

通俗點(diǎn)解釋：
1、如果 $u(r)$ 和 $g(r)$ 相同竟痰，由于biding函數(shù)是對(duì)其單調(diào)遞增的签钩，所以我們離線模擬時(shí)只需要得到按u排序top1即可，搜索不同的 $\lambda$ 參數(shù)時(shí)坏快，也不影響排序铅檩。

2、如果 $u(r)$ 和 $g(r)$ 不同假消，則 $\lambda$ 參數(shù)的變化會(huì)影響其順序柠并，所以我們離線模擬的時(shí)候需要記錄每次競(jìng)價(jià)的候選列表。計(jì)算復(fù)雜度大大提升富拗。

Refer:
[1]
INTEGRALS WHICH ARE CONVEX FUNCTIONALS

最后編輯于：2021.12.09 16:10:05

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末臼予，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子啃沪，更是在濱河造成了極大的恐慌粘拾，老刑警劉巖，帶你破解...
沈念sama閱讀 211,042評(píng)論 6贊 490
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件创千，死亡現(xiàn)場(chǎng)離奇詭異缰雇，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)追驴，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 89,996評(píng)論 2贊 384
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門械哟，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人殿雪，你說(shuō)我怎么就攤上這事暇咆。” “怎么了？”我有些...
開(kāi)封第一講書人閱讀 156,674評(píng)論 0贊 345
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵爸业，是天一觀的道長(zhǎng)其骄。經(jīng)常有香客問(wèn)我，道長(zhǎng)扯旷，這世上最難降的妖魔是什么拯爽？我笑而不...
開(kāi)封第一講書人閱讀 56,340評(píng)論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮钧忽，結(jié)果婚禮上毯炮，老公的妹妹穿的比我還像新娘。我一直安慰自己惰瓜，他們只是感情好否副，可當(dāng)我...
茶點(diǎn)故事閱讀 65,404評(píng)論 5贊 384
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布汉矿。她就那樣靜靜地躺著崎坊，像睡著了一般。火紅的嫁衣襯著肌膚如雪洲拇。梳的紋絲不亂的頭發(fā)上奈揍，一...
開(kāi)封第一講書人閱讀 49,749評(píng)論 1贊 289
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音赋续，去河邊找鬼男翰。笑死，一個(gè)胖子當(dāng)著我的面吹牛纽乱，可吹牛的內(nèi)容都是我干的蛾绎。我是一名探鬼主播，決...
沈念sama閱讀 38,902評(píng)論 3贊 405
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼鸦列，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼租冠！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起薯嗤，我...
開(kāi)封第一講書人閱讀 37,662評(píng)論 0贊 266
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤顽爹，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后骆姐，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體镜粤，經(jīng)...
沈念sama閱讀 44,110評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,451評(píng)論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年玻褪，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了肉渴。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,577評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡带射，死狀恐怖同规，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情庸诱，我是刑警寧澤捻浦，帶...
沈念sama閱讀 34,258評(píng)論 4贊 328
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布晤揣，位于F島的核電站，受9級(jí)特大地震影響朱灿，放射性物質(zhì)發(fā)生泄漏昧识。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,848評(píng)論 3贊 312
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一盗扒、第九天我趴在偏房一處隱蔽的房頂上張望跪楞。院中可真熱鬧，春花似錦侣灶、人聲如沸甸祭。這莊子的主人今日做“春日...
開(kāi)封第一講書人閱讀 30,726評(píng)論 0贊 21
一樁弒父案褥影，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)池户。三九已至，卻和暖如春凡怎，著一層夾襖步出監(jiān)牢的瞬間校焦，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書人閱讀 31,952評(píng)論 1贊 264
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工统倒，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留寨典，地道東北人。一個(gè)月前我還...
沈念sama閱讀 46,271評(píng)論 2贊 360
代替公主和親
正文我出身青樓房匆，卻偏偏與公主長(zhǎng)得像耸成，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子浴鸿，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,452評(píng)論 2贊 348

BSD：Auction with ROI constraints

問(wèn)題建模Modeling：

Solution:

參數(shù)解法：

問(wèn)題分析：

推薦閱讀更多精彩內(nèi)容