基于目標(biāo)端影響模型與次模性的預(yù)算分配博弈問(wèn)題分析?

農(nóng)慶琴， 王媛媛

(中國(guó)海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院， 山東 青島 266100)

隨著商品的市場(chǎng)競(jìng)爭(zhēng)越來(lái)越激烈，商品品牌的營(yíng)銷(xiāo)策略也越來(lái)越重要。商家在媒體渠道投放廣告是商品品牌營(yíng)銷(xiāo)的一個(gè)重要手段，例如：服裝品牌商通過(guò)在廣告牌、電視臺(tái)、網(wǎng)購(gòu)平臺(tái)等媒體渠道投放廣告來(lái)影響消費(fèi)者，期望他們變成商品的購(gòu)買(mǎi)者。然而，品牌商的推廣預(yù)算有限，如何將有限的預(yù)算在電視、報(bào)紙和網(wǎng)絡(luò)等媒體渠道進(jìn)行分配，才能最大限度地影響潛在客戶(hù)，達(dá)到增加銷(xiāo)售的目的，這是品牌營(yíng)銷(xiāo)需要解決的重要問(wèn)題。

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

在現(xiàn)實(shí)情況中，對(duì)于客戶(hù)而言，多數(shù)情況下影響其購(gòu)買(mǎi)欲的原因不在于通過(guò)何種渠道看到廣告，而在于他們看到的廣告本身。由此看來(lái)，目標(biāo)端影響模型雖然復(fù)雜，但它更貼近現(xiàn)實(shí)中的廣告?zhèn)鞑ミ^(guò)程。因此，本文對(duì)文獻(xiàn)[1]中提出的目標(biāo)端影響模型進(jìn)行調(diào)整——假設(shè)同一個(gè)物品的廣告不管消費(fèi)者是第幾次看到它，該物品的吸引力都是相同的；并基于調(diào)整后的影響模型來(lái)研究預(yù)算分配影響最大化問(wèn)題。

Alon[1]探討的問(wèn)題的前提假設(shè)是在市場(chǎng)中只有單個(gè)品牌商，然而在現(xiàn)實(shí)的渠道市場(chǎng)中，通常有許多擁有同類(lèi)可比產(chǎn)品的品牌商，他們彼此競(jìng)爭(zhēng)，都想通過(guò)在媒體渠道投放廣告的營(yíng)銷(xiāo)方式將潛在客戶(hù)轉(zhuǎn)化為自己的忠實(shí)買(mǎi)家。在這種場(chǎng)景下，多個(gè)品牌商競(jìng)爭(zhēng)情況下的預(yù)算分配問(wèn)題形成了一個(gè)非合作博弈問(wèn)題，各品牌商即為博弈的局中人，他們均是獨(dú)立、理性的，只在乎個(gè)體效用是否最優(yōu)而不在乎全局效用是否最優(yōu)。在沒(méi)有管理機(jī)構(gòu)的情況下，這些品牌商自私的行為結(jié)果能給社會(huì)帶來(lái)多少效用？能否實(shí)現(xiàn)“社會(huì)最優(yōu)”？要研究這些問(wèn)題就需要分析缺乏管理者協(xié)調(diào)的代價(jià)，也就是系統(tǒng)的效率。

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

1 預(yù)備知識(shí)

1.1 整數(shù)格上的次模函數(shù)

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

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

易知，整數(shù)格上的次模函數(shù)的非負(fù)組合仍是次模函數(shù)。

如果函數(shù)f是整數(shù)格上的次模函數(shù)，則稱(chēng)-f為整數(shù)格上的超模函數(shù)。

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

其中es表示在分量s處值為1、在其余分量處值為0的|V|維單位向量，則稱(chēng)函數(shù)f滿(mǎn)足分量凹性。

1.2 納什均衡

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

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

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

則稱(chēng)局勢(shì)S是一個(gè)納什均衡。

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

2 基于目標(biāo)端影響模型的預(yù)算分配問(wèn)題

2012年Alon等[1]研究了品牌商通過(guò)在媒體渠道投放廣告向潛在客戶(hù)推廣產(chǎn)品的問(wèn)題，分析了媒體渠道分配問(wèn)題，提出了目標(biāo)端影響模型。

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

本節(jié)對(duì)初始的目標(biāo)端模型進(jìn)行調(diào)整——假設(shè)客戶(hù)t每次看到廣告時(shí)被激活的概率相同，記為pt。這個(gè)假設(shè)來(lái)源于廣告?zhèn)鞑サ膶?shí)際情況：同一個(gè)物品的廣告不管消費(fèi)者是第幾次看到它，該物品的吸引力都是相同的，所以對(duì)于消費(fèi)者的影響概率也是相同的。

在目標(biāo)端影響模型下，品牌商的效用函數(shù)為：

2.2 基于目標(biāo)端影響模型的預(yù)算分配問(wèn)題(Channel advertising budget allocation problem)

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

滿(mǎn)足以上約束的分配x稱(chēng)為可行分配。

接下來(lái)，對(duì)該規(guī)劃目標(biāo)函數(shù)的性質(zhì)進(jìn)行分析。

引理1基于目標(biāo)端影響模型的預(yù)算分配問(wèn)題的目標(biāo)函數(shù)f(x)是整數(shù)格上的次模函數(shù)。

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

對(duì)于任意的可行分配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)滿(mǎn)足超模函數(shù)定義，從而P(x,t)=1-g(x)=1-(1-pt)xt是次模函數(shù)。由于次模函數(shù)的非負(fù)組合仍然是次模函數(shù)，因此，f(x)=∑t∈T(1-(1-pt)xt)是整數(shù)格上的次模函數(shù)。

引理2基于目標(biāo)端模型的預(yù)算分配問(wèn)題的目標(biāo)函數(shù)f(x)滿(mǎn)足分量凹性。

證明 設(shè)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。

因此，基于目標(biāo)端模型的預(yù)算分配問(wèn)題的目標(biāo)函數(shù)f(x)滿(mǎn)足分量凹性。

3 基于目標(biāo)端影響模型的預(yù)算分配博弈

在現(xiàn)實(shí)的媒體渠道市場(chǎng)中，通常有許多擁有同類(lèi)可比產(chǎn)品的品牌商，他們彼此競(jìng)爭(zhēng)，都想通過(guò)在媒體渠道投放廣告的營(yíng)銷(xiāo)方式將潛在客戶(hù)轉(zhuǎn)化為自己的忠實(shí)買(mǎi)家。從而，理性的品牌商面對(duì)激烈的市場(chǎng)競(jìng)爭(zhēng)，需要對(duì)復(fù)雜的競(jìng)爭(zhēng)市場(chǎng)進(jìn)行合理的策略博弈分析。本節(jié)將單個(gè)品牌商的預(yù)算分配問(wèn)題推廣到多個(gè)品牌商競(jìng)爭(zhēng)情形——基于目標(biāo)端模型的預(yù)算分配博弈。

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

3.1 純納什均衡的存在性

納什均衡是博弈中的一個(gè)穩(wěn)定局勢(shì)。對(duì)于品牌商來(lái)說(shuō)，當(dāng)目前配置不是納什均衡時(shí)，他就可以通過(guò)改變自己的策略來(lái)提高他的效用。1951年Nash[13]證明了有限非合作n人博弈存在納什均衡。這里的納什均衡指的是混合策略納什均衡，并不能證明純策略納什均衡的存在性，而博弈中是否存在純策略納什均衡是一直以來(lái)的研究熱點(diǎn)。下面探討基于目標(biāo)端影響模型的預(yù)算分配博弈是否存在純策略納什均衡。

1996年Shapley等[14]提出了一類(lèi)特殊的博弈類(lèi)型——?jiǎng)莶┺?Potential games)，并且證明了此類(lèi)博弈一定存在純納什均衡。下面將通過(guò)證明基于目標(biāo)端影響模型的預(yù)算分配博弈是勢(shì)博弈來(lái)證明它一定存在純策略納什均衡。

定義4(勢(shì)博弈)[14]在博弈([n],{Si}i∈[n],{fi}i∈[n])中，如果存在函數(shù)p:S→R，對(duì)于所有的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，

則稱(chēng)函數(shù)p為博弈的勢(shì)函數(shù)，該博弈稱(chēng)為勢(shì)博弈。

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

定理2基于目標(biāo)端影響模型的預(yù)算分配博弈是勢(shì)博弈，從而存在純策略納什均衡。

對(duì)于每一個(gè)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)

由此可得

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

3.2 基于目標(biāo)端影響模型的預(yù)算分配博弈的無(wú)秩序代價(jià)

2015年Maehara等[8]將文獻(xiàn)[15]中的有效效用系統(tǒng)(Valid utility system)擴(kuò)展到整數(shù)格中，稱(chēng)一個(gè)博弈為整數(shù)格上的單調(diào)有效效用系統(tǒng)(Monotone utility system on the integer lattice)，如果該博弈滿(mǎn)足下列三個(gè)條件：

(1)社會(huì)效用函數(shù)是整數(shù)格上的次模函數(shù)并且滿(mǎn)足分量凹性；

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

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

Maehara等[8]同時(shí)證明了整數(shù)格上的單調(diào)有效效用系統(tǒng)的無(wú)秩序代價(jià)至多為2。

定義5(無(wú)秩序代價(jià)PoA)在非合作博弈中，當(dāng)純策略納什均衡存在時(shí)，稱(chēng)最佳社會(huì)效用和最差純納什均衡的社會(huì)效用之間的比值為無(wú)秩序代價(jià)，記為

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

定理3[8]整數(shù)格上的單調(diào)有效效用系統(tǒng)的無(wú)秩序代價(jià)PoA≤2。

定理4基于目標(biāo)端影響模型的預(yù)算分配博弈是一個(gè)整數(shù)格上的單調(diào)有效效用系統(tǒng)，它的無(wú)秩序代價(jià)至多為2。

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

所以，預(yù)算分配博弈滿(mǎn)足條件(2)。

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

最后，設(shè)函數(shù)

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

斷言：當(dāng)a∈[0,1],函數(shù)Si(x,t;a)是關(guān)于變量a的單調(diào)遞減函數(shù)。

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

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

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

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

所以，預(yù)算分配博弈滿(mǎn)足條件(3)。

綜上所述，基于目標(biāo)端影響模型的預(yù)算分配博弈是一個(gè)整數(shù)格上的單調(diào)有效效用系統(tǒng)，從而它的無(wú)秩序代價(jià)至多為2。

4 結(jié)語(yǔ)

本文將基于目標(biāo)端影響模型的單個(gè)品牌商的預(yù)算分配問(wèn)題擴(kuò)展到整數(shù)格上，證明了該問(wèn)題的目標(biāo)函數(shù)是整數(shù)格上的單調(diào)次模函數(shù)；將單個(gè)品牌商的目標(biāo)端影響模型擴(kuò)展到多個(gè)品牌商，提出了基于目標(biāo)端影響模型的預(yù)算分配博弈,證明了該博弈具有純策略納什均衡,且該預(yù)算分配博弈的無(wú)秩序代價(jià)至多為2。