基于目標端影響模型與次模性的預算分配博弈問題分析?

農慶琴， 王媛媛

(中國海洋大學數學科學學院， 山東 青島 266100)

隨著商品的市場競爭越來越激烈，商品品牌的營銷策略也越來越重要。商家在媒體渠道投放廣告是商品品牌營銷的一個重要手段，例如：服裝品牌商通過在廣告牌、電視臺、網購平臺等媒體渠道投放廣告來影響消費者，期望他們變成商品的購買者。然而，品牌商的推廣預算有限，如何將有限的預算在電視、報紙和網絡等媒體渠道進行分配，才能最大限度地影響潛在客戶，達到增加銷售的目的，這是品牌營銷需要解決的重要問題。

2012年Alon等[1]研究了品牌商如何通過在媒體渠道投放廣告(分配預算)的問題，提出了兩個影響模型：源端影響模型(Source-side influence model)和目標端影響模型(Target-side influence model)，將預算約束下的分配問題表述成目標為被激活客戶的期望數量最大化的優化問題。

在現實情況中，對于客戶而言，多數情況下影響其購買欲的原因不在于通過何種渠道看到廣告，而在于他們看到的廣告本身。由此看來，目標端影響模型雖然復雜，但它更貼近現實中的廣告傳播過程。因此，本文對文獻[1]中提出的目標端影響模型進行調整——假設同一個物品的廣告不管消費者是第幾次看到它，該物品的吸引力都是相同的；并基于調整后的影響模型來研究預算分配影響最大化問題。

Alon[1]探討的問題的前提假設是在市場中只有單個品牌商，然而在現實的渠道市場中，通常有許多擁有同類可比產品的品牌商，他們彼此競爭，都想通過在媒體渠道投放廣告的營銷方式將潛在客戶轉化為自己的忠實買家。在這種場景下，多個品牌商競爭情況下的預算分配問題形成了一個非合作博弈問題，各品牌商即為博弈的局中人，他們均是獨立、理性的，只在乎個體效用是否最優而不在乎全局效用是否最優。在沒有管理機構的情況下，這些品牌商自私的行為結果能給社會帶來多少效用？能否實現“社會最優”？要研究這些問題就需要分析缺乏管理者協調的代價，也就是系統的效率。

1999年Koutsoupias和Papadimitriou[7]提出用最佳社會效用和最差納什均衡下社會效用之間的比值來衡量系統的效率，這個比值稱為“無秩序代價”(Price of anarchy，PoA)。2015年Maehara等[8]擴展了文獻[1]中的源端影響模型，將單個品牌商的預算分配問題推廣到多個品牌商的預算分配問題，并且分析了納什均衡的存在性及無秩序代價。Hatano等[9]從匹配者的角度探究了將媒體渠道分配給多個品牌商的問題，提出了一種基于拉格朗日分解的算法。2019年Sessa等[10]研究了基于源端影響模型的連續預算分配博弈，證明了PoA至少是2。

1 預備知識

1.1 整數格上的次模函數

f(x)+f(y)≥f(x∨y)+f(x∧y),

其中(x∨y)i=max{xi,yi}，(x∧y)i=min{xi,yi}，i∈[n]，則稱函數f為整數格上的次模函數。

易知，整數格上的次模函數的非負組合仍是次模函數。

如果函數f是整數格上的次模函數，則稱-f為整數格上的超模函數。

f(x+es)-f(x)≥f(x+2es)-f(x+es)，

其中es表示在分量s處值為1、在其余分量處值為0的|V|維單位向量，則稱函數f滿足分量凹性。

1.2 納什均衡

策略式的n人博弈(簡稱“博弈”)可以用三元組([n],{Si}i∈[n],{fi}i∈[n])表示，其中[n]={1,…,n}為局中人的集合，Si表示局中人i的策略空間，令S=S1×…×Sn為局勢集合；fi:S→R是局中人i的個人效用函數。每個局中人i具有個人理性的，其目標是最大化自己的效用函數fi。給定局勢s=(s1,…,sn)∈S，記si=(s1,…,si,0,…，0)，S-i=(s1,…,si-1,si+1,…，sn)。

定義3(納什均衡)[13]在博弈局勢s=(s1,…,sn)∈S下，如果對于任意一個局中人i，都滿足以下不等式

fi(si,s-i)≥fi(s′i,s-i)， ?s′i∈Si，

則稱局勢S是一個納什均衡。

由納什均衡的定義可以看出:在納什均衡局勢下，任何局中人都不能通過單獨改變自己的策略獲得更好的收益，因此，納什均衡是非合作博弈的一個穩定局勢。

2 基于目標端影響模型的預算分配問題

2012年Alon等[1]研究了品牌商通過在媒體渠道投放廣告向潛在客戶推廣產品的問題，分析了媒體渠道分配問題，提出了目標端影響模型。

2.1 目標端影響模型(Target-side influence model)

本節對初始的目標端模型進行調整——假設客戶t每次看到廣告時被激活的概率相同，記為pt。這個假設來源于廣告傳播的實際情況：同一個物品的廣告不管消費者是第幾次看到它，該物品的吸引力都是相同的，所以對于消費者的影響概率也是相同的。

在目標端影響模型下，品牌商的效用函數為：

2.2 基于目標端影響模型的預算分配問題(Channel advertising budget allocation problem)

品牌商在預算限制下從各渠道之間選擇一個投放廣告分配x，從而激活(或受影響)的最多客戶數量f(x)。該問題可描述為以下規劃：

滿足以上約束的分配x稱為可行分配。

接下來，對該規劃目標函數的性質進行分析。

引理1基于目標端影響模型的預算分配問題的目標函數f(x)是整數格上的次模函數。

證明 令g(x)=(1-pt)xt≥0,下面證明g(x)是一個整數格上的超模函數。

對于任意的可行分配x=(x(s1),…,x(sk)),y=(y(s1),…,y(sk)),有

x∧y=(x(s1)∧y(s1),…,x(sk)∧y(sk))，

x∨y=(x(s1)∨y(s1),…,x(sk)∨y(sk))，

則有

(x∧y)t=∑s∈γ(t)(x(s)∧y(s))，

(x∨y)t=∑s∈γ(t)(x(s)∨y(s))=
∑s∈γ(t)[(x(s)+y(s))-(x(s)∧y(s))]=
xt+yt-(x∧y)t，

g(x∧y)=(1-pt)(x∧y)t，

即g(x)滿足超模函數定義，從而P(x,t)=1-g(x)=1-(1-pt)xt是次模函數。由于次模函數的非負組合仍然是次模函數，因此，f(x)=∑t∈T(1-(1-pt)xt)是整數格上的次模函數。

引理2基于目標端模型的預算分配問題的目標函數f(x)滿足分量凹性。

證明 設x,x+es,x+2es均為可行分配。

若(s,t)?E,f(x+2es)=f(x+es)=f(x),則(f(x+es)-f(x))-(f(x+2es)-f(x+es))=0。

若(s,t)∈E，易知(x+es)t=xt+1，(x+2es)t=xt+2。

因此，基于目標端模型的預算分配問題的目標函數f(x)滿足分量凹性。

3 基于目標端影響模型的預算分配博弈

在現實的媒體渠道市場中，通常有許多擁有同類可比產品的品牌商，他們彼此競爭，都想通過在媒體渠道投放廣告的營銷方式將潛在客戶轉化為自己的忠實買家。從而，理性的品牌商面對激烈的市場競爭，需要對復雜的競爭市場進行合理的策略博弈分析。本節將單個品牌商的預算分配問題推廣到多個品牌商競爭情形——基于目標端模型的預算分配博弈。

當多個品牌商同時嘗試激活客戶t時，他們將以隨機順序激活客戶t，激活規則是先入為主。記[n]排列集合為Δn，對于任意局勢x=(x1,x2,…,xn),考慮一個隨機排序τ∈Δn，所有品牌商按照τ中的排序依次嘗試激活t。品牌商i激活客戶t的概率是Pi(xi,t)∏jτi(1-Pj(xj,t)),即在排序τ中排在i前面的品牌商都激活失敗而i激活成功的概率。品牌商i的個人效用函數可以表示為

3.1 純納什均衡的存在性

納什均衡是博弈中的一個穩定局勢。對于品牌商來說，當目前配置不是納什均衡時，他就可以通過改變自己的策略來提高他的效用。1951年Nash[13]證明了有限非合作n人博弈存在納什均衡。這里的納什均衡指的是混合策略納什均衡，并不能證明純策略納什均衡的存在性，而博弈中是否存在純策略納什均衡是一直以來的研究熱點。下面探討基于目標端影響模型的預算分配博弈是否存在純策略納什均衡。

1996年Shapley等[14]提出了一類特殊的博弈類型——勢博弈(Potential games)，并且證明了此類博弈一定存在純納什均衡。下面將通過證明基于目標端影響模型的預算分配博弈是勢博弈來證明它一定存在純策略納什均衡。

定義4(勢博弈)[14]在博弈([n],{Si}i∈[n],{fi}i∈[n])中，如果存在函數p:S→R，對于所有的i∈[n]，s∈S，都有下列等式成立

fi(si,s-i)-fi(s′i,s-i)=
p(si,s-i)-p(s′i,s-i)，s′i∈Si，

則稱函數p為博弈的勢函數，該博弈稱為勢博弈。

定理1[14]所有的勢博弈都存在純策略納什均衡。

定理2基于目標端影響模型的預算分配博弈是勢博弈，從而存在純策略納什均衡。

對于每一個i∈[n],x-i=(x1,…,xi-1,xi+1,…,xn)，

p(xi,x-i)-p(x′i,x-i)=

fi(xi,x-i)-fi(x′i,x-i)=

(1)

由此可得

因此函數p(x)是基于目標端影響模型的預算分配博弈的勢函數。從而，基于目標端影響模型的預算分配博弈是一個勢博弈，一定存在純策略納什均衡。

3.2 基于目標端影響模型的預算分配博弈的無秩序代價

2015年Maehara等[8]將文獻[15]中的有效效用系統(Valid utility system)擴展到整數格中，稱一個博弈為整數格上的單調有效效用系統(Monotone utility system on the integer lattice)，如果該博弈滿足下列三個條件：

(1)社會效用函數是整數格上的次模函數并且滿足分量凹性；

(2)局中人i的個人效用至少是i參與博弈與不參與博弈帶來的社會效用的變化量；

(3)所有局中人的個人效用之和不高于社會效用。

Maehara等[8]同時證明了整數格上的單調有效效用系統的無秩序代價至多為2。

定義5(無秩序代價PoA)在非合作博弈中，當純策略納什均衡存在時，稱最佳社會效用和最差純納什均衡的社會效用之間的比值為無秩序代價，記為

其中,L為非合作博弈的所有實例，OPT(I)為實例I的最佳社會效用。

定理3[8]整數格上的單調有效效用系統的無秩序代價PoA≤2。

定理4基于目標端影響模型的預算分配博弈是一個整數格上的單調有效效用系統，它的無秩序代價至多為2。

證明 首先，設激活序列τ={τ1,τ2,…,τn}∈Δn，

所以，預算分配博弈滿足條件(2)。

其次，由引理1可知Pi(xi,t)是整數格上的次模函數，那么1-Pi(xi,t)就是整數格上的超模函數。Topkis在文獻[12]中證明了整數格上的超模函數的乘積仍然是整數格上的超模函數，所以∏i∈[n](1-Pi(xi,t))仍然是超模函數，那么F(x)則是整數格上的次模函數。因為fi(x)是滿足分量凹性的單調遞減函數(證明同引理2)，其非負組合也是滿足分量凹性的單調遞減函數，故F(x)=∑t∈T(1-∏i∈[n](1-Pi(xi,t)))也滿足分量凹性且單調遞增。所以，預算分配博弈滿足條件(1)。

最后，設函數

顯然，Si(x,t;a)≥0，?a∈[0,1]。

斷言：當a∈[0,1],函數Si(x,t;a)是關于變量a的單調遞減函數。

下面證明斷言的正確性。已知lnSi(x,t;a)與Si(x,t;a)的單調性相同，由lnSi(x,t;a)的單調性可以得到Si(x,t;a)的單調性。令

由斷言可知min{Si(x,t;a),a∈[0,1]}=Si(x,t;1)。

下面討論fi(x)和F(xi,x-i)-F(0,x-i)的關系。由F(x)的定義可得

由定理2的證明中的(1)式可得

所以，預算分配博弈滿足條件(3)。

綜上所述，基于目標端影響模型的預算分配博弈是一個整數格上的單調有效效用系統，從而它的無秩序代價至多為2。

4 結語

本文將基于目標端影響模型的單個品牌商的預算分配問題擴展到整數格上，證明了該問題的目標函數是整數格上的單調次模函數；將單個品牌商的目標端影響模型擴展到多個品牌商，提出了基于目標端影響模型的預算分配博弈,證明了該博弈具有純策略納什均衡,且該預算分配博弈的無秩序代價至多為2。