GSP出價方案：[17]
通過簡單的建模，對對偶問題求解 很容易得出GSP條件下bid的optimal solution：[在GFP條件下逊桦，此解不是最優(yōu)解，需要預(yù)估m(xù)arket price.[5]]
（這種方式其實(shí)并不是truth-telling出價[8][10][11][12]议泵，反對意見[14]）(關(guān)于在限制條件下直接按ecpm出價是否最優(yōu)[19])
通過歷史數(shù)據(jù)能求解出最優(yōu)lambda熏纯，但根本問題是環(huán)境變化，每天流量的變化很大，每天別人出價不同壮锻，導(dǎo)致[market price]的變化也很大琐旁。所以通常，lambda通過反饋數(shù)據(jù)控制做approximation（PID或者RL）
比如一個可行的做法是：
離線求解lambda0猜绣，以及分時的期望budget消耗（消耗比例）灰殴，然后在線通過pid控制改變實(shí)時的lambda，來逼近這個budget消耗掰邢。
關(guān)于GFP出價的優(yōu)化
1牺陶、對winning function進(jìn)行建模。出價為時辣之，競價成功的概率為
[15]
2掰伸、將winning function帶入求解。這種方式下怀估，biding的analytical solution形式取決于winning function的形式狮鸭。在[2]中有對形式的求解，[1]中的3.2.2節(jié)有對更復(fù)雜的情況求解方案多搀。
3歧蕉、 一個實(shí)例化的求解過程
根據(jù)業(yè)務(wù)中market price數(shù)據(jù)分布情況，我們可以設(shè)計出成功率函數(shù)：酗昼，這里的
為常數(shù)，
等于最高成功率梳猪。根據(jù)成功率的定義麻削，
，對
求導(dǎo)春弥，可以得到bid的概率分布：
呛哟，將此公式帶入KKT 條件等式[18]，化簡得到一元二次方程
匿沛，得到解：
作為GFP的出價扫责。
參數(shù)求解：
1、我們通過歷史競價數(shù)據(jù)計算出和
逃呼，這里非線性回歸可以求倒數(shù)轉(zhuǎn)化為線性回歸鳖孤。
2、再對歷史數(shù)據(jù)帶入以及
的出價公式抡笼，根據(jù)成功率函數(shù)
與總體Budget:
苏揣，利用公式
求解出
。
延伸
其實(shí)上述這種方案其實(shí)也有一定的局限性推姻，因?yàn)閜(win|bid)這種建模方式本身假設(shè)是有些偏差的平匈，因?yàn)閷?shí)際上market price也很大程度上depending on 流量本身。應(yīng)該是p(win|bid,x)：x為我們認(rèn)知的流量的特征空間。所以[6]中提出了我們直接對Market Price進(jìn)行預(yù)估增炭，然后根據(jù)Budget（容量）忍燥，MP（重量），ECPM（價值）將這個原問題轉(zhuǎn)化為dynamic knapsack問題來求解隙姿。
【當(dāng)然梅垄，[6]這篇論文的2.3章節(jié)中，用了一個更直覺的例子來告訴你原方案中bidding function的表達(dá)能力是不足以達(dá)到最優(yōu)解的孟辑。其實(shí)這個這個問題的本質(zhì)還是哎甲，winning function的假設(shè)過于簡單（過強(qiáng)假設(shè)），因?yàn)閣inning function本身的形式饲嗽，決定了bidding function 的形式】
理論擴(kuò)展
加入kpi的constraint：
bid optimization by multivariable control in display advertising（有別的constraint）
Refer：
[1]:Optimal Real-Time Bidding for Display Advertising炭玫，用非離散的模型建模
[2]:Optimal real-time bidding frameworks discussion，證明GSP條件下bid=ecpm/lambda最優(yōu)貌虾，以及GFP條件下bid的optimal
[3]:Discrete-variable extremum problems 具體離線求解lambda的方法：離散變量建模吞加，lambda求解，greedy approximation
[4]:RL的一些手段https://www.pianshen.com/article/17871751889/
[5]:關(guān)于預(yù)估winning price估計censored regression：Predicting
winning price in real time bidding with censored data
[6]:加上winning price的預(yù)估尽狠，證明[1],[2]中的方案不是最優(yōu)解衔憨，動態(tài)Knapsack Problem：Combining powers of two predictors in optimizing real-time bidding strategy under constrained budget。其實(shí)整體的思路很簡單袄膏，即轉(zhuǎn)化為KP践图，優(yōu)先競得“性價比”最高的imp opportunity。類似方案：Dynamic Knapsack Optimization Towards Efficient Multi-Channel Sequential Advertising
[7]:Budget Constrained Bidding by Model-free Reinforcement
Learning in Display Advertising沉馆，RL方式的設(shè)計码党。
[8]: 直接bid=ecpm才是Truth-telling的出價。見論文[2]斥黑。GSP為激勵兼容的條件：無budget constraint揖盘，或者單物品拍賣。
[9]: 其他有意思的思路：Statistical Arbitrage Mining for Display Advertising
[10]: 在買家足夠的情況下锌奴，GFP與GSP穩(wěn)態(tài)的均衡點(diǎn)是一致的兽狭，對賣家來說收益也是一致的。但是GFP容易造成系統(tǒng)的不穩(wěn)定鹿蜀，由于買家需要去猜別人的價格箕慧，所以會有出價的更大波動。
[11]：在budget constraint下茴恰，auction 機(jī)制的設(shè)計销钝，如何設(shè)計出truthful 的機(jī)制Multi-unit auctions with budget-constrained bidders
[12]：機(jī)制設(shè)計，VCG auctions也不是truth-telling的機(jī)制：Budget-Constrained Auctions
[13]：激勵兼容琐簇，即賣家與買家的目標(biāo)函數(shù)相同蒸健。VCG：http://www.iterduo.com/posts/84554
[14]: 論文[6]的2.3節(jié)認(rèn)為Lin與ORTB都是一種廣義上的truth-telling出價座享，因?yàn)榍罢遙id與ecpm是線性關(guān)系，后者也是單調(diào)關(guān)系似忧≡眩【我對此持一定的保留態(tài)度，雖然買方賣方的目標(biāo)函數(shù)都是與價值單調(diào)關(guān)系盯捌，但是涉及到market price的估計本身就已經(jīng)不是truth-telling了淳衙，雖然LIN與ORTB對mp的估計隱含在winning price分布函數(shù)的求解中】當(dāng)然，只要能拿到足夠多的budget饺著，就可以當(dāng)作是不限budget的情況箫攀，這種狀態(tài)下，確實(shí)是“truth telling”：lambda=1
[15]:這里[2]論文中假設(shè)市場market price是一個隨機(jī)變量幼衰，并且不受到我們策略機(jī)制的影響靴跛，p(win=1|bid)等價于p(bid>mp)的概率。所以對market price的分布進(jìn)行統(tǒng)計（通常情況下可能差不多是log-normal的）渡嚣，那么winning function 就是它的CDF函數(shù)梢睛。可以對其CDF做非線性函數(shù)的近似识椰，然后來求解其參數(shù)绝葡。
[16]:關(guān)于winning price的預(yù)估：Predicting Winning Price in Real Time Bidding with Censored Data
[17]:對于GSP定價來說，其實(shí)可以通過很簡單的離散定義的方式來建模腹鹉，并且能得到相同的解藏畅。注：這里需要用到Linear Programming的duality，即對于LP來說功咒，總有強(qiáng)對偶：https://en.wikipedia.org/wiki/Dual_linear_program
[18]Optimal real-time bidding frameworks discussion中的(13)(14)
[19]非truth-telling：Real-Time Bidding Algorithms for Performance-Based Display Ad Allocation
見： this naive mechanism is suboptimal under a constrained setting where demand-side constraints exist.
