一種基于多Agent系統(tǒng)的在線廣告競(jìng)價(jià)模型

張文明 王小平

(同濟(jì)大學(xué)電子與信息工程學(xué)院 上海 200092)

一種基于多Agent系統(tǒng)的在線廣告競(jìng)價(jià)模型

張文明 王小平

(同濟(jì)大學(xué)電子與信息工程學(xué)院 上海 200092)

針對(duì)在線廣告競(jìng)價(jià)這一具體應(yīng)用場(chǎng)景，本文在價(jià)高者得的傳統(tǒng)競(jìng)價(jià)原則上，結(jié)合競(jìng)價(jià)雙方的相似度閾值控制，提出一種適用于在線廣告交易的競(jìng)價(jià)模型，即SMOBM(the Similarity-based Multi-agent Online-advertising Bidding Model)模型。該模型使用多Agent系統(tǒng)建模，根據(jù)市場(chǎng)角色設(shè)計(jì)相應(yīng)Agent，并設(shè)計(jì)出需求聚合Agent組織和資源聚合Agent組織。買賣雙方使用回合制的拍賣協(xié)商方法進(jìn)行連續(xù)叫價(jià)，并在系統(tǒng)全局時(shí)鐘的控制下產(chǎn)生交易結(jié)果。最后，使用Repast Simphony仿真軟件對(duì)模型進(jìn)行實(shí)現(xiàn)，將基于組織模型和不基于組織模型這兩種情況進(jìn)行對(duì)比，結(jié)果表明在選擇合適的相似度閾值時(shí)，基于組織模型的交易成功率高，且在存在惡性競(jìng)爭(zhēng)時(shí)整體交易表現(xiàn)出較好的魯棒性。

多Agent系統(tǒng) 在線廣告競(jìng)價(jià) Agent組織 相似度

0 引 言

在線廣告不同于傳統(tǒng)線下廣告，后者方式單一且受眾用戶面狹窄;前者不僅為廣告主創(chuàng)造了多樣化的廣告方式，且?guī)?lái)了精準(zhǔn)的受眾用戶廣告投放技術(shù)，也為互聯(lián)網(wǎng)媒體服務(wù)商提供了流量變現(xiàn)的手段，其媒體形態(tài)和交互方式上的差異使得它們的交易方式也呈現(xiàn)分化。近年來(lái)，隨著媒體商不斷提高的流量變現(xiàn)的需求，以及廣告主的廣告投放向精細(xì)化發(fā)展，在線廣告交易從早期的廣告位合約和展示量合約方式，發(fā)展到搜索廣告中的一般競(jìng)價(jià)方式，再到實(shí)時(shí)競(jìng)價(jià)交易方式，使得競(jìng)價(jià)成為了在線廣告交易的主要手段。穩(wěn)定的市場(chǎng)規(guī)則、良好的出價(jià)策略和高效率的買賣雙方匹配機(jī)制能夠帶來(lái)一個(gè)健壯、均衡的在線廣告交易市場(chǎng)，而如何設(shè)計(jì)這些市場(chǎng)規(guī)則和策略是一個(gè)困難的問題。

在線廣告的競(jìng)價(jià)是雙邊拍賣的一種具體應(yīng)用，而拍賣是經(jīng)濟(jì)學(xué)規(guī)律在日常經(jīng)濟(jì)生活中的一種直觀體現(xiàn)，賣方有需要拍賣的物品，買方有購(gòu)買物品的需求，雙方根據(jù)市場(chǎng)規(guī)則出價(jià)協(xié)商交易，并且通過相應(yīng)匹配策略確定最后的交易成功者和成交價(jià)。拍賣交易因其簡(jiǎn)單易行、公平高效等特性而逐漸受到學(xué)術(shù)界和業(yè)界的廣泛關(guān)注，針對(duì)在線拍賣的特性，研究者們提出了一系列新的拍賣方法，多Agent系統(tǒng)中使用拍賣的方式來(lái)解決任務(wù)與資源分配、虛擬數(shù)字產(chǎn)品的定價(jià)等問題，已經(jīng)有很多研究成果。如AbdolkarimSadrieh[1]提出了一種回合制的雙邊拍賣協(xié)商方法，賣方和買方交易一定數(shù)量的同種物品，雙方分別按回合來(lái)輪次叫價(jià)，直至價(jià)格匹配交易成功；Shi B等[2-3]分析了雙邊拍賣市場(chǎng)中連續(xù)類型的交易智能體的報(bào)價(jià)行為，使用泛化的fictitious play算法來(lái)解決貝葉斯博弈問題，并詳細(xì)分析了市場(chǎng)智能體的收費(fèi)行為對(duì)報(bào)價(jià)策略的影響。當(dāng)今社會(huì)的一些問題存在較大復(fù)雜性，對(duì)抗與合作并存，多Agent系統(tǒng)能利用組織的形式去體現(xiàn)這類行為，如徐晉暉等[4]提出了一種面向結(jié)構(gòu)的組織形成方法和體現(xiàn)組織中個(gè)體的思維傾向的演化機(jī)制；張偉等[5]提出了一種Agent組織的遞歸模型，繼承并進(jìn)一步拓寬了以角色為中心的組織建模方式；Renna P[6]使用多Agent技術(shù)去模擬在競(jìng)爭(zhēng)和合作關(guān)系下的可動(dòng)態(tài)變化的網(wǎng)絡(luò)，以及組織協(xié)作。在線廣告中的廣告位的拍賣交易有其自身特性，即為了保證最后投放廣告的點(diǎn)擊率，競(jìng)價(jià)成功的廣告主所投放的廣告需與受眾用戶具有較高的相似度，同時(shí)，在線廣告的競(jìng)價(jià)具有較高的時(shí)效性，其以廣告位和人群為標(biāo)的的拍賣方式也不同與其它傳統(tǒng)雙邊拍賣。

考慮在線廣告的雙邊拍賣這一具體應(yīng)用場(chǎng)景的上述特性，本文提出一種基于相似度的多Agent在線廣告競(jìng)價(jià)模型SMOBM。計(jì)算廣告主投放目標(biāo)人群和廣告位受眾用戶之間的相似度，大于相似度閾值的雙方進(jìn)行拍賣協(xié)商，在該模型中，廣告主和互聯(lián)網(wǎng)媒體商能夠使用回合制的雙邊拍賣協(xié)商方法達(dá)成交易，并提高個(gè)體與整個(gè)市場(chǎng)的收益和交易效率。

1 SMOBM模型

所有互聯(lián)網(wǎng)媒體商需要發(fā)布的廣告位和人群標(biāo)的AP(Advertising and People)統(tǒng)稱為資源，所有廣告主的廣告投放要求(目標(biāo)人群信息)統(tǒng)稱為需求。AP的固有特性分為兩個(gè)方面，廣告位本身的價(jià)值和受眾信息，可將量化后的自身價(jià)值和人群屬性值相同的AP看作是同一種資源。買方的投放需求是根據(jù)自身的廣告選擇需要投放的人群，可將投放人群相同的需求看作同一種需求。本文包括四種獨(dú)立Agent，分別是廣告主Agent、互聯(lián)網(wǎng)媒體商Agent、交易平臺(tái)Agent和中介Agent。它們?cè)谀Ｐ椭蟹謩e承擔(dān)相應(yīng)的角色，而Agent組織是Agent的集合，用于描述Agent間的合作與對(duì)抗等交互關(guān)系和行為，本文定義了兩種Agent組織，分別是需求聚合Agent組織和資源聚合Agent組織。前者是一個(gè)買方組織，買方可選擇加入該組織，并聚合到同需求小組，委托買方中介代為協(xié)商，后者是一個(gè)賣方組織，賣方可選擇加入該組織，并聚合到同資源小組，委托賣方中介代替協(xié)商。

本文提出的SMOBM模型結(jié)構(gòu)如圖1所示。互聯(lián)網(wǎng)媒體商是拍賣的發(fā)起者，可以加入資源聚合Agent組織中的同資源小組，并承擔(dān)委托者角色。中介將拍賣信息發(fā)布到交易平臺(tái)中，代替小組成員進(jìn)行拍賣協(xié)商。廣告主有投放廣告創(chuàng)意的需求(選擇需要投放的人群)，可以加入需求聚合Agent組織中的同需求小組。中介將需求發(fā)布到交易平臺(tái)中，交易平臺(tái)計(jì)算買賣雙方需求與資源的相似度，只有相似度大于給定閾值的雙方才能進(jìn)行協(xié)商(廣告主若同時(shí)參加多個(gè)協(xié)商需先進(jìn)行預(yù)算分配)，協(xié)商方法為雙方回合制連續(xù)叫價(jià)，直到協(xié)商成功或超時(shí)。

圖1 SMOBM模型結(jié)構(gòu)

SMOBM模型可以描述為一個(gè)十元組的形式。

SMOBM=

(1)

其中：

1)T為拍賣協(xié)商雙方參與者的集合。包括買方M1和賣方M2，即廣告主、賣方和買方中介，以及互聯(lián)網(wǎng)媒體商。

2)G為互聯(lián)網(wǎng)媒體商所提供的競(jìng)拍標(biāo)的集合。即廣告位和人群標(biāo)的。

3)O為競(jìng)價(jià)前的AP所屬關(guān)系。表明每個(gè)AP在競(jìng)價(jià)前屬于哪個(gè)互聯(lián)網(wǎng)媒體商，表示形式為G→M2。

4)S為相似度集合。每個(gè)AP拍賣前，需計(jì)算其與每個(gè)廣告主需求的相似度。即?g∈G，m∈M1，所有的AP和廣告主需求的相似度集合S={Sgm|S(g×m)=Sgm}。

5)R為拍賣協(xié)商結(jié)果集合。包括每個(gè)AP最后的交易成功者和交易價(jià)格，表示形式為G→M1(c)|M2(0)。交易的結(jié)果有兩種，交易成功時(shí)AP所屬關(guān)系發(fā)生改變，AP由賣方轉(zhuǎn)為買方，c表示交易價(jià)格；交易未成功時(shí)AP所屬關(guān)系不變，交易價(jià)格默認(rèn)為0。

6)P為回合制拍賣協(xié)商規(guī)則。本文使用有限狀態(tài)機(jī)來(lái)定義，記拍賣協(xié)商過程中的所有狀態(tài)集合為Status，包括開始狀態(tài)Ss_start、中間狀態(tài)Sb_mid和Ss_mid、結(jié)束狀態(tài)Stimeout和Ssuccess，即Status={Ss_start,Sb_mid,Ss_mid,Stimeout,Ssuccess}。Status中定義的Agent可采取的通信動(dòng)作原語(yǔ)分為四種，分別為Start(開始)，Accept(接受)，Refuse(拒絕)和Timeout(超時(shí)失敗)。每個(gè)Agent的后繼狀態(tài)和采取的動(dòng)作由當(dāng)前狀態(tài)和輸入決定。

7)K為模型知識(shí)庫(kù)。主要包含模型參數(shù)，賣方和買方的知識(shí)：

(1) 可以調(diào)節(jié)的模型參數(shù)。如，相似度控制的閾值θ等，針對(duì)不同的應(yīng)用場(chǎng)合需設(shè)定不同的參數(shù)。

(2) 買賣雙方知識(shí)。買方知識(shí)庫(kù)保存買方關(guān)于其它買方的出價(jià)概率分布(信念)，賣方知識(shí)庫(kù)保存賣方關(guān)于其他賣方的出價(jià)概率分布(信念)，雙方在每回合出價(jià)中都會(huì)更新信念，即每回合的出價(jià)是基于當(dāng)前知識(shí)。雙方的出價(jià)策略均是采用貝葉斯博弈的方式，使用泛化的FP(Fictitiousplay)算法，算法思想是在買賣雙方當(dāng)前回合的出價(jià)概率分布基礎(chǔ)上，通過計(jì)算回合最優(yōu)反應(yīng)出價(jià)函數(shù)得到回合最優(yōu)出價(jià)，并且更新下一回合FP信念。

8)U是期望效用函數(shù)。對(duì)于賣方和買方Agent都存在一個(gè)期望效用函數(shù)，如式(6)所示，它們出價(jià)的目的都是為了使得期望效用最大。

9)H是拍賣協(xié)商交易歷史信息的集合。拍賣歷史集合保存了每次拍賣協(xié)商的交易結(jié)果，包括買賣雙方的出價(jià)、組合的數(shù)量和最終交易狀態(tài)(原語(yǔ)Timeout和Accept)。

10)C是模型限制條件的集合。限制條件為協(xié)商的最長(zhǎng)交易時(shí)間。

1.1 相似度計(jì)算與閾值調(diào)控

SMOBM模型應(yīng)用于在線廣告拍賣這一具體場(chǎng)景，其中需要計(jì)算需求與資源的相似度。而在線廣告中的受眾用戶信息與廣告投放需求之間的相似度由其屬性值的相似程度計(jì)算得來(lái)，本文模型采用相似系統(tǒng)理論[7-9]來(lái)計(jì)算，將廣告位的受眾用戶信息和廣告主的投放需求人群信息看作兩個(gè)相似系統(tǒng)，具體的屬性要素如地域、性別、年齡段和興趣類別。在相似度的計(jì)算中，記某個(gè)廣告位的受眾用戶信息為A，某位廣告主的投放需求人群為B，A和B之間的相似屬性個(gè)數(shù)為n，對(duì)于不同類型的屬性其相似度計(jì)算方法也不同。

(1) 對(duì)于模型中區(qū)間類型的屬性，假設(shè)其A和B的某一區(qū)間屬性i(如年齡段)的值為[a1,b1]和[a2,b2]，其中a1,b1,a2,b2∈[y1,y2]，則根據(jù)文獻(xiàn)[10]中的相似度計(jì)算方法來(lái)計(jì)算相似度Si：

(2)

(2) 對(duì)于模型中概念類型的屬性(如地域)，則采用文獻(xiàn)[11]的概念語(yǔ)義相似度計(jì)算方法來(lái)計(jì)算相似度Si：

(3)

其中，Lcs(i1,i2)表示距i1和i2最近的共同父概念，Deepth(Lcs(i1,i2))表示A和B的該屬性的特征值i1和i2距離最近的共同父概念的深度，Deepth(Ci1)和Deepth(Ci2)表示i1和i2各自父概念的深度。

(3) 對(duì)于枚舉類型的屬性，根據(jù)枚舉值是否相同來(lái)確定相似度，若其枚舉值相同，則相似度為k，若不同，則相似度為0。

(4) 對(duì)于布爾類型的屬性，可看作枚舉類型的特例，若其布爾值相同，則相似度定為b，若不同，則相似度為0。

最后，A和B的整體相似度SAB為：

(4)

本文模型的屬性有地域、性別、年齡段和興趣類別，一般而言，廣告投放首先考慮投放人群的興趣類別，其次考慮地域，最后考慮性別和年齡段。可通過設(shè)定不同的相似度閾值來(lái)調(diào)節(jié)系統(tǒng)中參與拍賣的Agent的個(gè)數(shù)和買賣雙方的相似程度，即，若SAB≥θ，則A和B匹配成功，可以進(jìn)行本次拍賣協(xié)商；若SAB<θ，則A和B匹配不成功，不能進(jìn)行協(xié)商。

1.2 獨(dú)立Agent和期望效用

SMOBM模型中的四種獨(dú)立Agent各自承擔(dān)相應(yīng)的社會(huì)功能，分別是：

(1) 賣方：互聯(lián)網(wǎng)媒體商Agent和賣方中介Agent

拍賣協(xié)商的發(fā)起者，擁有大量互聯(lián)網(wǎng)媒體廣告位和用戶信息，能夠根據(jù)自身信念進(jìn)行多回合內(nèi)獨(dú)立出價(jià)進(jìn)行協(xié)商，并能自主選擇加入或退出資源聚合Agent組織。賣方中介為賣方組織管理者，目的是使協(xié)商雙方盡可能達(dá)成交易，調(diào)控市場(chǎng)供需平衡。

(2) 交易平臺(tái)Agent

買方和賣方的交易平臺(tái)，對(duì)賣方的AP和買方的需求計(jì)算相似度，并能夠調(diào)節(jié)相似度閾值，初始化最長(zhǎng)協(xié)商時(shí)間等全局參數(shù)，進(jìn)行系統(tǒng)全局調(diào)控。

(3) 買方：廣告主Agent和買方中介Agent

拍賣協(xié)商的參與者，有需要投放的廣告創(chuàng)意，能夠根據(jù)自身信念和預(yù)算進(jìn)行多回合內(nèi)獨(dú)立出價(jià)協(xié)商，并能夠委托中介Agent代為競(jìng)價(jià)，自主選擇加入或退出需求聚合Agent組織。買方中介是買方組織管理者，能夠代替買方交易協(xié)商，調(diào)控市場(chǎng)。

U(k,i,βb,λb,Ψb,Ψs,vk,Ski)=

(5)

其中，α1、α2、α3為不同的權(quán)值因子，且(α1+α2+α3)=1。在實(shí)際應(yīng)用中，交易者通常優(yōu)先考慮預(yù)算，其次考慮廣告位的固有價(jià)值，本文模型中設(shè)計(jì)了一個(gè)需求與資源之間的相似度，因?yàn)橘I賣雙方開始協(xié)商之前已經(jīng)進(jìn)行了相似度的閾值控制，雙方的相似度不再是出價(jià)考慮的主要因素，因此交易者最后考慮的是相似度。

上面僅考慮了買方i在某一固定出價(jià)位置下的期望效用。因此，考慮i所有可能的出價(jià)(出價(jià)不能高于預(yù)算)位置集合Posi，計(jì)算其他買方的出價(jià)比其低的概率，若買方i不出價(jià)，則效用為0，則此時(shí)考慮所有情形下的買方i的期望效用如下所示：

(6)

賣方的期望效用與買方類似，出價(jià)目標(biāo)都是使期望效用最大化。

1.3 基于需求聚合和資源聚合的Agent組織

賣方和買方為了獲取更多的利益和減少冗余繁雜的拍賣市場(chǎng)開銷，買方可自主選擇加入或退出需求聚合Agent組織，賣方可自主選擇加入或者退出資源聚合Agent組織，買賣雙方均可在組織內(nèi)加入同需求或同資源小組，組織內(nèi)采用委托中介的方式統(tǒng)一協(xié)商拍賣。本文的Agent組織結(jié)構(gòu)為樹狀模式[12]，如圖2所示，每一顆子樹為一個(gè)子組織，葉子節(jié)點(diǎn)為不可再分的特殊子組織，將其稱為角色(角色也包括其它非葉節(jié)點(diǎn)，非葉節(jié)點(diǎn)為各子組織或組織的管理者)，角色由具體的Agent來(lái)實(shí)例化。

SMOBM模型中的資源聚合Agent組織的管理者角色由賣方中介Agent來(lái)承擔(dān)，媒體商Agent可以加入資源聚合Agent組織，并加入到同資源的小組，承擔(dān)委托者角色，委托賣方中介Agent代為拍賣其AP，而一個(gè)遞歸的樹狀組織結(jié)構(gòu)可描述為如式(7)所示：

(7)

圖2 樹狀組織結(jié)構(gòu)

每一個(gè)媒體商Agent的目標(biāo)都是拍賣其AP，但為了獲取更多利益和避免自身冗余繁雜的拍賣協(xié)商操作，這些Agent可以有選擇地加入資源聚合Agent組織，由賣方中介代售。將媒體商Agent的目標(biāo)記為T，則任務(wù)T可以分解完成，即首先確定同資源小組中的所有AP的心理最低價(jià)中的最高價(jià)，記為T1，然后由賣方中介與買方進(jìn)行回合制協(xié)商，記為T2。則T的分解結(jié)構(gòu)為{(T,(seq,T1,T2))},其中seq表示任務(wù)順序執(zhí)行。由此可知，資源聚合Agent組織的角色Ro={R,R1,R2}，其中R為最高管理者角色，R1為委托者角色，R2為小組管理者角色，角色關(guān)系集合Re={(cmd,R,T,R1,T1),(cmd,R,T,R2,T2),(bef,R1,T1,R2,T2)}，如圖3所示。其中cmd表示兩個(gè)角色在完成角色目標(biāo)時(shí)的父子關(guān)系，前者對(duì)后者擁有控制權(quán)，bef表示兩個(gè)角色在完成角色目標(biāo)時(shí)需要進(jìn)行異步協(xié)調(diào)，后者需要在前者完成之后開始，目標(biāo)集合O_g={T}，管理者角色集合Ma={R,R2}，其中R和R2分別為最高管理者和小組管理者。

圖3 角色關(guān)系說(shuō)明

資源聚合Agent組織是由媒體商Agent和賣方中介Agent按照組織結(jié)構(gòu)組成的整體，媒體商Agent和賣方中介Agent分別對(duì)資源聚合Agent組織中的角色進(jìn)行實(shí)例化，承擔(dān)相應(yīng)的任務(wù)，因此，一個(gè)完整的資源聚合Agent組織應(yīng)為一個(gè)四元組形式，如式(8)所示：

Org=

(8)

其中，Org_id是用于唯一標(biāo)識(shí)組織；Agents是Agent的集合，這里具體包括媒體商Agent和賣方中介Agent；OS為組織結(jié)構(gòu)描述；Ins為具體的Agent與角色的實(shí)例化對(duì)應(yīng)關(guān)系。

需求聚合Agent組織是由廣告主Agent和買方中介Agent組成的聯(lián)合買方交易整體，廣告主Agent和買方中介Agent分別承擔(dān)相應(yīng)的角色，并負(fù)責(zé)完成相應(yīng)的子任務(wù)，需求聚合Agent組織的四元組形式與資源聚合Agent組織相同。

1.4 回合制的雙邊拍賣協(xié)商方法

本文使用回合制的雙邊拍賣協(xié)商方法，即對(duì)于互聯(lián)網(wǎng)媒體商發(fā)布的某一AP(廣告位和人群標(biāo)的)，由相似度大于某一閾值參數(shù)的廣告主和中介來(lái)進(jìn)行競(jìng)價(jià)，賣方和買方輪流叫價(jià)，直至一個(gè)買方和賣方達(dá)成交易，或者因超時(shí)未協(xié)商成功而交易失敗，導(dǎo)致流拍。

回合制拍賣的協(xié)商過程可以概括為：媒體商通過向交易平臺(tái)發(fā)布一個(gè)AP來(lái)發(fā)起一次協(xié)商，或者加入資源聚合Agent組織，由賣方中介發(fā)起協(xié)商。首先由交易平臺(tái)計(jì)算該AP與所有的買方需求的相似度，媒體商或賣方中介再向所有相似度大于某一閾值的買方發(fā)送一個(gè)提議的價(jià)格，每個(gè)買方收到這一議價(jià)之后則輪到買方回合，由買方對(duì)賣方的議價(jià)作出反饋，接受或提交自己的出價(jià)，賣方收到所有買方反饋后再進(jìn)入賣方回合，賣方處理所有買方的反饋后，對(duì)買方作出反饋，經(jīng)過這樣多輪回合協(xié)商之后會(huì)產(chǎn)生協(xié)商結(jié)果。

回合制的拍賣協(xié)商規(guī)則如圖4所示。

圖4 拍賣協(xié)商規(guī)則狀態(tài)圖

共有五種狀態(tài)，Ss_start表示協(xié)商開始，由賣方(媒體商或賣方中介)發(fā)起一次協(xié)商，是賣方的第0回合；Sb_mid和Ss_mid分別表示買方和賣方中間回合；結(jié)束狀態(tài)包括Stimeout和Ssuccess。協(xié)商過程中的通信原語(yǔ)有四種，分別為Start、Refuse、Accept和Timeout，其中Start表示發(fā)起一次協(xié)商，使用在賣方第0回合，參數(shù)包括(發(fā)送方，輪次0，出價(jià)，接收方)；Refuse表示拒絕對(duì)方的提議，并給出自己的出價(jià)，用在賣方除第0回合之外的回合和買方的所有回合，參數(shù)包括(發(fā)送方，輪次i，出價(jià)，接收方)；Accept表示接受對(duì)方的提議，用在賣方除第0回合之外的回合和買方所有回合，參數(shù)包括(發(fā)送方，輪次i，接收方)；Timeout表示超時(shí)，在全局時(shí)鐘下達(dá)到最長(zhǎng)交易時(shí)間時(shí)強(qiáng)制發(fā)送，參數(shù)包括(發(fā)送方，輪次i，接收方)，此時(shí)則協(xié)商失敗。

對(duì)于買方和賣方的出價(jià)，本文使用泛化的FP算法[13]來(lái)計(jì)算，以買方為例，在某一FP信念(Ψb和Ψs)下，買方的出價(jià)是為了使期望效用最大，因此對(duì)應(yīng)的最優(yōu)出價(jià)函數(shù)如式(9)所示：

F(βb,Ψb,Ψs,vk,Ski)=argmaxλb∈ΛU(βb,λb,Ψb,Ψs,vk,Ski)

(9)

因?yàn)榕馁u協(xié)商有最長(zhǎng)交易時(shí)間的限制，協(xié)商進(jìn)度應(yīng)隨著時(shí)間增長(zhǎng)而相對(duì)加快，因此對(duì)于買方每回合的出價(jià)，本文在最佳反應(yīng)報(bào)價(jià)的基礎(chǔ)上加上一個(gè)時(shí)間增強(qiáng)項(xiàng)t，其初始值為0，并且隨著交易時(shí)間的增大而增大，本文取t為時(shí)間的線性函數(shù)值(對(duì)于賣方，t為時(shí)間衰退項(xiàng)，初始值為0，并且隨著時(shí)間的增大而減小)，則回合最優(yōu)出價(jià)如式(10)所示：

G(t,βb,Ψb,Ψs,vk,Ski)=t+F(βb,Ψb,Ψs,vk,Ski)

(10)

綜合上述分析，給出SMOBM模型的回合制拍賣協(xié)商算法，如算法1所示。

算法1 回合制拍賣協(xié)商算法

輸入 廣告位的固有價(jià)值V，AP和需求屬性值，初始FP信念Ψb和Ψs，初始輪次h=0

輸出 協(xié)商結(jié)果(交易雙方，最終交易價(jià)格，最終交易回合)

Do

1.進(jìn)入賣方第h回合，在當(dāng)前FP信念Ψs下，計(jì)算回合最優(yōu)報(bào)價(jià)函數(shù)G(t,βs,Ψb,Ψs,νk,Ski)；

2.產(chǎn)生最優(yōu)回合報(bào)價(jià)λs對(duì)應(yīng)的預(yù)算段，并計(jì)算λs為所有賣方出價(jià)最低的概率Prob(Ψs)；

5.若λb>λs，則協(xié)商成功，達(dá)成交易，并結(jié)束；否則執(zhí)行下一步；

6.進(jìn)入買方第h回合，在當(dāng)前FP信念Ψb下，計(jì)算回合最優(yōu)出價(jià)函數(shù)G(t,βb,Ψb,Ψs,νk,Ski)；

7.產(chǎn)生回合最優(yōu)出價(jià)λb對(duì)應(yīng)的預(yù)算段，并計(jì)算λb為所有買方出價(jià)最高的概率Prob(Ψb)；

10.h=h+ 1；

While(λb<λs&&未到最長(zhǎng)協(xié)商交易時(shí)間)

2 實(shí)驗(yàn)分析

2.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)

本文使用Repast Simphony 2.3仿真軟件[14]和Matlab2014b來(lái)對(duì)模型進(jìn)行實(shí)驗(yàn)驗(yàn)證。Repast軟件由芝加哥大學(xué)的社會(huì)科學(xué)計(jì)算研究所與美國(guó)Argonne國(guó)家實(shí)驗(yàn)室的研究人員共同開發(fā)，主要用于多Agent系統(tǒng)的離散建模仿真。實(shí)驗(yàn)數(shù)據(jù)本文采用iPinYou公司發(fā)布的數(shù)據(jù)集[15]，此數(shù)據(jù)用于其自身算法優(yōu)化[16-17]，包含較全的展示類廣告數(shù)據(jù)。數(shù)據(jù)集分為三輪，其格式稍有不同，本文選用第一輪的數(shù)據(jù)，其采集區(qū)間為一個(gè)星期，共記錄了7天的真實(shí)數(shù)據(jù)，主要包括競(jìng)價(jià)日志、展示日志和點(diǎn)擊日志，特征屬性共有22個(gè)，主要包括時(shí)間戳、地理位置(如所在城市)、參與競(jìng)價(jià)的出價(jià)價(jià)格和最終成交價(jià)(RMB/CPM)(iPinYou發(fā)布數(shù)據(jù)集時(shí)對(duì)出價(jià)進(jìn)行了修改，在價(jià)格上乘了一個(gè)因子進(jìn)行線性變換，因此與真實(shí)數(shù)據(jù)可能有所偏差，但本文是在出價(jià)概率分布上計(jì)算回合最優(yōu)出價(jià)，并得出整體交易成功率，因此價(jià)格的線性變換對(duì)本文并無(wú)影響)等。本文從第一輪數(shù)據(jù)集中選取部分?jǐn)?shù)據(jù)進(jìn)行實(shí)驗(yàn)，并去掉無(wú)關(guān)的屬性，如iPinyou ID和IP等，在此基礎(chǔ)上進(jìn)行實(shí)驗(yàn)仿真。

2.2 模型初始化

使用Repast軟件來(lái)執(zhí)行本文的SMOBM模型，需先設(shè)置一些參數(shù)并對(duì)其初始化，本文模型需設(shè)置的參數(shù)主要分為以下四個(gè)方面：

(1) 各種Agent的個(gè)數(shù)，SMOBM模型中的Agent有媒體商Agent、廣告主Agent、交易平臺(tái)Agent、以及買方和賣方中介Agent，分別設(shè)置其Agent個(gè)數(shù)。本文根據(jù)數(shù)據(jù)集中的買賣雙方比例分布來(lái)選取部分?jǐn)?shù)據(jù)進(jìn)行實(shí)驗(yàn)。在數(shù)據(jù)集中，對(duì)于每個(gè)廣告位平均約有10個(gè)廣告主參與競(jìng)價(jià)，因此按照買賣雙方10∶1的比例來(lái)選取數(shù)據(jù)，取媒體商Agent和廣告主Agent數(shù)量分別為50個(gè)和500個(gè)，交易平臺(tái)Agent數(shù)量對(duì)實(shí)驗(yàn)無(wú)影響，設(shè)為1個(gè)即可，而買賣雙方中介Agent則根據(jù)需求和資源數(shù)量分別取100個(gè)和10個(gè)。

(2) 設(shè)置限制集，模型中主要有交易時(shí)間限制，即最長(zhǎng)拍賣協(xié)商時(shí)間。在本文中，由于實(shí)驗(yàn)方式為計(jì)算機(jī)軟件來(lái)模擬拍賣協(xié)商，協(xié)商交易在很短的時(shí)間內(nèi)完成，因此本文實(shí)驗(yàn)對(duì)最長(zhǎng)拍賣協(xié)商時(shí)間不作限制。

(3) 設(shè)置模型相似度閾值和預(yù)算分配參數(shù)值，分別用來(lái)控制參與交易的買賣雙方的最低相似度和廣告主同時(shí)參與多個(gè)協(xié)商的預(yù)算分配情況。在本模型中對(duì)預(yù)算分配策略不作優(yōu)化，設(shè)定預(yù)算分配參數(shù)為1，即φ=1時(shí)，表示按照相似度S和廣告位固有價(jià)值V的大小來(lái)按比例分配預(yù)算。而相似度閾值θ的取值根據(jù)圖7獲得。

(4) 交易者期望效用函數(shù)的權(quán)值因子和相似度屬性權(quán)值。根據(jù)本文模型和實(shí)際應(yīng)用情況，通常優(yōu)先考慮交易者的預(yù)算，其次考慮廣告位的固有價(jià)值，最后考慮相似度，因此本文實(shí)驗(yàn)分別設(shè)定其權(quán)值因子為0.45、0.35和0.2。而相似度屬性一般先考慮人群興趣類別，其次考慮地域，最后考慮性別和年齡段，因此分別設(shè)定其權(quán)值分別為0.35、0.25、0.2和0.2。部分模型參數(shù)設(shè)置如表1所示。

表1 模型參數(shù)值設(shè)置

2.3 模型組織演化

在對(duì)模型初始化后，就可以執(zhí)行模型。本文SMOBM模型中存在需求聚合Agent組織和資源聚合Agent組織，它們分別由買方和賣方聚合形成，廣告主和媒體商可委托中介代替進(jìn)行拍賣協(xié)商，即這些Agent可以加入組織并聚合到某個(gè)子組織，中介進(jìn)行統(tǒng)一協(xié)商。本文模型初始化后開始執(zhí)行時(shí)Agent分布如圖5所示。

圖5 模型開始執(zhí)行時(shí)Agent分布示意圖

圖5中分別使用圓形表示買方中介Agent，方形表示賣方中介Agent，星形表示媒體商Agent，三角形表示廣告主Agent，為了便于觀察組織演化，其他Agent未予以顯示。在模型執(zhí)行之初，由圖5可知模型未發(fā)生任何演化且Agent間未進(jìn)行任何交互。

圖6 模型執(zhí)行后的Agent分布示意圖

Repast軟件是以tick數(shù)來(lái)表示時(shí)間，在模型執(zhí)行了1 975個(gè)Tick后，Agent組織分布如圖6所示。可以看到，一些買方中介Agent和廣告主Agent發(fā)生了聚合(即圖6中圓形和三角形)，廣告主選擇加入需求聚合Agent組織并聚合到同需求子組織，相同的，也有一些媒體商選擇了加入資源聚合Agent組織(即圖6中方形和星形)。但是，仍有部分單個(gè)的紅色方形和藍(lán)色方形游離，這是因?yàn)橛行V告主和媒體商沒有選擇加入Agent組織來(lái)委托中介協(xié)商，以上是對(duì)本文SMOBM模型中組織演化的一種直觀表示。

2.4SMOBM模型拍賣協(xié)商分析

本文采用的是回合制的拍賣協(xié)商方法，由賣方發(fā)起一次拍賣，經(jīng)過相似度計(jì)算和閾值控制后選出參與拍賣的買方，然后賣方和買方回合制連續(xù)叫價(jià)，直到交易結(jié)束。本文利用相似度閾值控制，統(tǒng)計(jì)所有進(jìn)行了拍賣協(xié)商的媒體商的AP，得出不同閾值下的模型整體拍賣交易成功率。本文利用整體拍賣交易成功率來(lái)進(jìn)行性能評(píng)價(jià)，整體交易成功率的計(jì)算如式(11)所示：

(11)

其中，As表示模型中的拍賣成功的次數(shù)，Aa表示模型總的拍賣次數(shù)，γ表示成功次數(shù)占總次數(shù)的比例。且分別仿真了基于組織(資源聚合Agent組織和需求聚合Agent組織)的模型和不基于組織的模型，并對(duì)比它們?cè)诓煌嗨贫乳撝迪碌恼w拍賣交易成功率。

不同的相似度閾值下的整體拍賣交易成功率如圖7所示，基于組織模型和不基于組織模型整體交易成功率均呈現(xiàn)先上升后下降的趨勢(shì)，這是因?yàn)殡S著閾值θ的逐漸增大，拍賣經(jīng)過篩選后去掉了低相似度的交易者，相似度較高的交易者有更大的機(jī)會(huì)協(xié)商成功，而隨著θ增大到一定程度時(shí)，會(huì)導(dǎo)致參與拍賣的交易者數(shù)量急劇減少，使得整體交易成功率降低。當(dāng)θ在0.5到0.6區(qū)間附近時(shí)，交易成功率達(dá)到峰值且相對(duì)穩(wěn)定，如圖7所示。

圖7 SMOBM的基于組織和不基于組織交易成功率

由圖7可知，在回合制協(xié)商實(shí)際出價(jià)基礎(chǔ)上，基于組織相比不基于組織的SMOBM模型在一定程度上增加了整體拍賣交易成功率，整體交易成功率的提高率的計(jì)算如式(12)所示：

(12)

其中，γo表示基于組織模型的交易成功率，γwo表示不基于組織模型的交易成功率。本文根據(jù)θ=0.5和θ=0.6時(shí)的交易成功率的提高率的平均值來(lái)得到基于組織相對(duì)不基于組織模型的提高率，因此，在選取了合適的相似度閾值的情況下，本文基于組織的SMOBM模型比不基于組織的SMOBM模型交易成功率提高了約8.22%。

在實(shí)際拍賣中，可能存在某些賣者個(gè)體通過惡意出價(jià)來(lái)哄抬價(jià)格或者某些買者聯(lián)合其他部分買者壓低價(jià)格，這是一種惡性競(jìng)爭(zhēng)的現(xiàn)象。本文為了模擬這一市場(chǎng)行為對(duì)模型的影響，在部分媒體商個(gè)體和廣告主個(gè)體的回合制協(xié)商出價(jià)中，通過對(duì)出價(jià)進(jìn)行一定比例的線性變換來(lái)達(dá)到篡改部分賣方和買方的行為的效果，即對(duì)于買方和賣方出價(jià)，修改方法對(duì)應(yīng)的計(jì)算如式(13)所示：

(13)

圖8 不同異常出價(jià)比例下的交易成功率

從圖8可見，本文分別選取了不同比例的出價(jià)進(jìn)行變換，達(dá)到異常出價(jià)的目的，并得到不同比例異常出價(jià)時(shí)基于組織模型和不基于組織模型的整體交易成功率。兩種模型的成功率曲線走勢(shì)大致相同，其中基于組織的SMOBM模型要比不基于組織的模型更加穩(wěn)定。這是因?yàn)榻M織在模型中起到一個(gè)調(diào)控市場(chǎng)的作用，盡管有部分賣方和買方個(gè)體出價(jià)異常，但是對(duì)于加入組織的買賣雙方都能盡可能地達(dá)成一致，使得協(xié)商成功率相對(duì)穩(wěn)定。在異常出價(jià)占5%時(shí)，前者比后者交易成功率增加了9.59%，異常出價(jià)占30%時(shí)，交易成功率增加了24.85%。由此可知，當(dāng)市場(chǎng)存在惡性競(jìng)爭(zhēng)時(shí)，基于組織的SMOBM模型相比不基于組織更加穩(wěn)定，且至少能提高約9.59%的整體拍賣交易成功率。

綜上所述，在選擇合適的相似度閾值時(shí)，能提高一定比例的整體交易成功率，并對(duì)比基于組織的模型和不基于組織的模型，前者相比后者約能提高8.22%的整體交易成功率，并且在存在惡性競(jìng)爭(zhēng)的情況下，前者能保持相對(duì)穩(wěn)定，一般至少能提高9.59%的成功率。

3 結(jié) 語(yǔ)

本文將多Agent系統(tǒng)應(yīng)用到在線廣告競(jìng)價(jià)這一具體場(chǎng)景，基于在線廣告競(jìng)價(jià)交易的特點(diǎn)，設(shè)計(jì)出SMOBM模型，采用相似度閾值控制與拍賣協(xié)商相結(jié)合的方式，使得在價(jià)高者得這一傳統(tǒng)競(jìng)價(jià)模式下，還能在一定程度上保證投放廣告與投放人群和廣告位之間的相關(guān)性。SMOBM模型模擬人類社會(huì)中實(shí)際雙邊拍賣方式，使用Agent組織來(lái)交互演化，模型中設(shè)計(jì)出資源聚合Agent組織和需求聚合Agent組織，將買賣雙方聚合，委托中介協(xié)商，其交易方式采用回合制的拍賣協(xié)商使得買賣雙方輪次連續(xù)叫價(jià)，叫價(jià)策略采用泛化的FP算法，在每一回合計(jì)算出最佳反應(yīng)出價(jià)，多回合后在全局時(shí)鐘的控制下產(chǎn)生交易結(jié)果。實(shí)驗(yàn)結(jié)果表明在選定合適的相似度閾值時(shí)，基于組織的模型相比不基于組織的模型整體交易成功率更高，且魯棒性更好。

下一階段的工作將會(huì)對(duì)SMOBM模型進(jìn)一步細(xì)化，本文的SMOBM模型簡(jiǎn)化了一些方面復(fù)雜度，如廣告主同時(shí)參與多個(gè)競(jìng)價(jià)時(shí)的預(yù)算分配，本文按照相似度和廣告位固有價(jià)值來(lái)按比例分配，未來(lái)的工作中會(huì)對(duì)其進(jìn)行策略優(yōu)化。模型中設(shè)置了較多參數(shù)，后期工作會(huì)對(duì)其進(jìn)一步調(diào)優(yōu)，同時(shí)，對(duì)組織模型進(jìn)行更深入的研究。

[1]SadriehA.TheAlternatingDoubleAuctionMarket:AGameTheoreticandExperimentalInvestigation[J].LectureNotesinEconomicsandMathematicalSystems,2001,71(1):84-86.

[2]ShiB,GerdingEH,VytelingumP,etal.Anequilibriumanalysisofcompetingdoubleauctionmarketplacesusingfictitiousplay[C]//Proc.ofthe19thEuropeanConf.onArtificialIntelligence,2010:575-580.

[3] 石兵.雙邊拍賣市場(chǎng)中交易者報(bào)價(jià)策略和市場(chǎng)收費(fèi)策略的博弈論分析[J].多智能體系統(tǒng)及應(yīng)用,2015:149-160.

[4] 徐晉暉,張偉,石純一,等.面向結(jié)構(gòu)的組織形成和演化機(jī)制[J].計(jì)算機(jī)研究與發(fā)展,2001,38(8):897-903.

[5] 張偉,石純一.Agent組織的一種遞歸模型[J].軟件學(xué)報(bào),2002,13(11):2149-2154.

[6]RennaP.Dynamicco-opetitivenetworkorganizationsupportedbymultiagentarchitecture[M]//BusinessOrganizationsandCollaborativeWeb:Practices,StrategiesandPatterns,PA:IGIGlobal,2011.

[7] 周美立,王浣塵.相似系統(tǒng)的分析與度量[J].系統(tǒng)工程,1996,14(4):1-6.

[8] 周美立.相似系統(tǒng)工程[J].系統(tǒng)工程理論與實(shí)踐,1997,17(9):37-43.

[9] 劉曉文,韓冰,蔣永輝,等.支持需求聚合的C2B旅游電子商務(wù)自動(dòng)談判系統(tǒng)研究[J].計(jì)算機(jī)應(yīng)用與軟件,2015,32(8):52-55.

[10] 任凱,浦金云.基于案例屬性特征區(qū)間相似度的改進(jìn)算法研究[J].控制與決策,2010,25(2):307-310.

[11]BergmannR,StahlA.Similaritymeasuresforobject-orientedcaserepresentations[C]//Proceedingofthe4thEuropeanWorkshoponAdvancesinCase-BasedReasoning,1998:25-36.

[12] 石純一,張偉.基于Agent的計(jì)算[M].北京:清華大學(xué)出版社,2007:275-320.

[13]RabinovichZ,GerdingEH,PolukarovM,etal.Generalisedfictitiousplayforacontinuumofanonymousplayers[C]//Proc.ofthe21stJointConf.onArtificialIntelligence,2009:245-250.

[14]NorthMJ,CollierNT,OzikJ,etal.ComplexadaptivesystemsmodelingwithRepastSimphony[EB/OL].[2013-01-03].http://www.casmodeling.com/content/1/1/3.pdf.

[15]iPinYou.GlobalBiddingAlgorithmCompetition[DB/OL].http://contest.ipinyou.com/data.shtml.2013.

[16]PerlichC,DalessandroB,HookR,etal.BidOptimizingandInventoryScoringinTargetedOnlineAdvertising[C]//Proceedingsofthe18thACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining,2012:804-812.

[17]ZhangC,ZhangE.Optimizedbiddingalgorithmofrealtimebiddinginonlineadsauction[C]//2014InternationalConferenceonManagementScienceandEngineering(ICMSE),2014:33-42.

AN ONLINE ADVERTISING BIDDING MODEL BASED ON MULTI-AGENT SYSTEM

Zhang Wenming Wang Xiaoping

(SchoolofElectronicsandInformationEngineering,TongjiUniversity,Shanghai200092,China)

Since the online advertising auction is becoming a new application scene, the SMOBM model based on the traditional principle of success of highest-price-offer and two sides of the transaction similarity threshold controlhave been proposed in this paper.This model uses Multi-Agent system to design, according to the market role, the corresponding Agent and Agent organization are designed, including the demands aggregation Agent organization and resources aggregation Agent organization, the buyers and sales uses a round-based negotiation method to bid for the auction, and produce the results of transactions under the control of global clock. The paper used the Repast Simphony simulation software to realize the model, the model is compared in two cases, one used the organization and the other didn’t. In the choice of a suitable similarity threshold, the results show that the former has higher transaction success rate and overall transaction showed robust in the existence of malicious competition.

Multi-Agent system Online advertising auction Agent organization Similarity

2016-05-24。張文明，碩士生，主研領(lǐng)域：機(jī)器學(xué)習(xí)和社會(huì)計(jì)算。王小平，教授。

TP399

A

10.3969/j.issn.1000-386x.2017.02.023