口碑參與模式下移動(dòng)眾包網(wǎng)絡(luò)的用戶博弈研究

曾鋒，王潤(rùn)華，彭佳，陳志剛

?

口碑參與模式下移動(dòng)眾包網(wǎng)絡(luò)的用戶博弈研究

曾鋒1，王潤(rùn)華1，彭佳2，陳志剛1

（1. 中南大學(xué)計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410000；2.空中交通管理系統(tǒng)與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210000）

研究了口碑參與模式下參與用戶之間的博弈行為，探究個(gè)體利益最大化的最佳策略。首先，給出了口碑參與模式下移動(dòng)用戶行為交互場(chǎng)景和相關(guān)定義，提出的移動(dòng)用戶效應(yīng)函數(shù)不僅考慮了用戶的數(shù)據(jù)貢獻(xiàn)量，還考慮了用戶邀請(qǐng)與合作因素，能激勵(lì)用戶之間相互合作；然后，基于博弈論斯塔克伯格模型分析了口碑參與模式下用戶的博弈過(guò)程，把用戶之間的行為交互分成兩級(jí)博弈過(guò)程，應(yīng)用逆向歸納法分析得出一級(jí)和二級(jí)博弈中用戶的最佳對(duì)策，并獲得了斯塔克伯格均衡；最后，證明了斯塔克伯格均衡的存在唯一性，提出了計(jì)算斯塔克伯格均衡的算法。數(shù)值實(shí)驗(yàn)結(jié)果驗(yàn)證了用戶效應(yīng)函數(shù)的合理性和斯塔克伯格均衡的存在唯一性。

移動(dòng)眾包；口碑參與模式；博弈論；斯塔克伯格模型

1 引言

眾包是利用群體智慧來(lái)解決各種復(fù)雜任務(wù)的一種市場(chǎng)模式[1]。隨著移動(dòng)智能設(shè)備的日益普及，依靠如GPS（global positioning system）、攝像頭、麥克風(fēng)等豐富的外部設(shè)備和傳感器，終端可以在移動(dòng)中完成眾包任務(wù)，稱之為移動(dòng)眾包，移動(dòng)眾包正成為一種新的眾包范例[2]，其市場(chǎng)有三要素：眾包人、眾包平臺(tái)和移動(dòng)用戶。眾包人通過(guò)眾包平臺(tái)向外界發(fā)布眾包任務(wù)，移動(dòng)用戶感知并考慮參與完成眾包任務(wù)。目前，移動(dòng)眾包主要應(yīng)用于解決大規(guī)模、復(fù)雜的社會(huì)感知問(wèn)題，如環(huán)境監(jiān)控、健康檢測(cè)、城市管理、公共安全和智能交通等問(wèn)題[3-4]。移動(dòng)眾包在解決大規(guī)模的社會(huì)問(wèn)題上具有快速、高效及便捷的優(yōu)勢(shì)，因此得到了工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注。

移動(dòng)眾包市場(chǎng)存在2種任務(wù)感知方式，即直接參與模式（DM，direct mode）和口碑參與模式（WoM，word of mouth mode）[5]。DM模式指移動(dòng)用戶直接通過(guò)眾包平臺(tái)感知眾包任務(wù)，這種參與方式下移動(dòng)用戶間不存在直接的信息交互，移動(dòng)用戶群的組建效率不高。WoM模式指已經(jīng)感知眾包任務(wù)的移動(dòng)用戶利用社交網(wǎng)絡(luò)、機(jī)會(huì)網(wǎng)絡(luò)或其他途徑來(lái)邀請(qǐng)其他移動(dòng)用戶參與眾包任務(wù)。與DM模式相比，WoM模式下用戶可以快速地向外擴(kuò)散眾包任務(wù)，縮短了眾包用戶群的建立時(shí)間，移動(dòng)用戶間能進(jìn)行直接的信息交流，形成邀請(qǐng)與被邀請(qǐng)的直接利益聯(lián)系。WoM模式具有良好的靈活性，依賴不同的邀請(qǐng)渠道可以滿足不同類型的眾包任務(wù)要求，如WoM模式基于社交網(wǎng)絡(luò)實(shí)現(xiàn)用戶邀請(qǐng)?jiān)诙虝r(shí)間內(nèi)擴(kuò)散眾包任務(wù)并建立移動(dòng)用戶群，這滿足了具有時(shí)效性的眾包任務(wù)要求；當(dāng)眾包任務(wù)具有地理位置約束時(shí)，移動(dòng)用戶通過(guò)機(jī)會(huì)性相遇擴(kuò)散眾包任務(wù)邀請(qǐng)，眾包人招募滿足任務(wù)地理位置要求的移動(dòng)用戶，這保證了移動(dòng)用戶群的有效性。目前，已有許多國(guó)內(nèi)外學(xué)者針對(duì)移動(dòng)眾包展開研究，然而大部分工作主要考慮DM模式下的移動(dòng)眾包市場(chǎng)，忽略了WoM模式為移動(dòng)眾包市場(chǎng)帶來(lái)的有利影響，針對(duì)WoM模式展開移動(dòng)眾包研究將會(huì)獲得更好成果。

在WoM模式移動(dòng)眾包市場(chǎng)中，眾包人發(fā)布眾包任務(wù)到眾包平臺(tái)，部分移動(dòng)用戶以DM模式感知眾包任務(wù)。成功感知眾包任務(wù)的移動(dòng)用戶決定貢獻(xiàn)多少數(shù)據(jù)量，也決定是否向外發(fā)送眾包任務(wù)邀請(qǐng)其他有關(guān)聯(lián)的用戶加入。移動(dòng)用戶完成感應(yīng)數(shù)據(jù)的采集后上傳感應(yīng)數(shù)據(jù)到眾包平臺(tái)并獲取眾包人提供的報(bào)酬。眾包人為了補(bǔ)償用戶完成眾包任務(wù)的資源消耗，根據(jù)移動(dòng)用戶提交的感應(yīng)數(shù)據(jù)貢獻(xiàn)量計(jì)算報(bào)酬。同時(shí)，眾包人為了激勵(lì)移動(dòng)用戶以WoM模式感知眾包任務(wù)，分別對(duì)市場(chǎng)中擴(kuò)散任務(wù)邀請(qǐng)的移動(dòng)用戶和積極響應(yīng)任務(wù)邀請(qǐng)的移動(dòng)用戶提供獎(jiǎng)勵(lì)。市場(chǎng)中，每個(gè)移動(dòng)用戶維護(hù)一個(gè)邀請(qǐng)列表用以記錄其成功邀請(qǐng)到的移動(dòng)用戶，在提交感應(yīng)數(shù)據(jù)到眾包平臺(tái)時(shí)一并提交邀請(qǐng)列表，眾包人核實(shí)邀請(qǐng)列表并計(jì)算相應(yīng)的報(bào)酬。WoM模式市場(chǎng)中的移動(dòng)用戶按邀請(qǐng)的時(shí)間順序做出感應(yīng)數(shù)據(jù)貢獻(xiàn)量的決策，且邀請(qǐng)者用戶與被邀請(qǐng)者用戶的決策會(huì)直接影響彼此收益，市場(chǎng)中每一個(gè)用戶都需考慮做出最佳的感應(yīng)數(shù)據(jù)貢獻(xiàn)量以最大化自身收益。市場(chǎng)中移動(dòng)用戶間就感應(yīng)數(shù)據(jù)貢獻(xiàn)量發(fā)生博弈行為，且用戶的決策存在先后順序，本文應(yīng)用斯塔克伯格博弈模型分析移動(dòng)用戶間博弈行為，研究眾包人與移動(dòng)用戶的最佳策略，為眾包人制定眾包任務(wù)及報(bào)酬評(píng)估提供參考依據(jù)。

本文針對(duì)WoM模式移動(dòng)眾包中的用戶交互問(wèn)題展開分析，主要工作如下。

1) 分析基于WoM模式移動(dòng)眾包市場(chǎng)中的用戶交互過(guò)程，對(duì)市場(chǎng)中的移動(dòng)用戶進(jìn)行分類定義。

2) 設(shè)計(jì)了移動(dòng)用戶的效應(yīng)函數(shù)，根據(jù)用戶貢獻(xiàn)的不同計(jì)算相應(yīng)的報(bào)酬，激勵(lì)用戶參與眾包任務(wù)。

3) 建立了用戶博弈的斯塔克伯格模型，基于逆向歸納法對(duì)博弈過(guò)程進(jìn)行分析，證明了斯塔克伯格博弈均衡的存在唯一性，為眾包人預(yù)測(cè)用戶貢獻(xiàn)并制定眾包任務(wù)提供有效的參考。

4) 通過(guò)數(shù)值仿真實(shí)驗(yàn)驗(yàn)證了斯塔克伯格均衡的存在唯一性，探索了相關(guān)參數(shù)對(duì)效應(yīng)函數(shù)以及均衡的影響。實(shí)驗(yàn)結(jié)果表明WoM模式任務(wù)感知和任務(wù)邀請(qǐng)?zhí)岣吡擞脩舻膮⑴c度和眾包任務(wù)的完成質(zhì)量。

2 相關(guān)工作

移動(dòng)眾包相關(guān)技術(shù)已有廣泛研究，主要包括移動(dòng)眾包市場(chǎng)的構(gòu)建、單個(gè)眾包方的任務(wù)分配、單個(gè)眾包方激勵(lì)機(jī)制設(shè)計(jì)、安全與隱私保護(hù)和移動(dòng)眾包市場(chǎng)演化機(jī)理研究等，本文研究WoM模式下單個(gè)眾包方的任務(wù)分配及其市場(chǎng)演化。單個(gè)眾包方的任務(wù)分配需要考慮眾包人、眾包任務(wù)和移動(dòng)用戶的特定需求，如眾包人的預(yù)算限制或服務(wù)質(zhì)量要求，眾包任務(wù)的位置約束或時(shí)效性，以及移動(dòng)用戶的移動(dòng)性等。

文獻(xiàn)[6]針對(duì)眾包人有預(yù)算限制提出基于代理的預(yù)算分配算法CrowdBudget，在不同的眾包任務(wù)中劃分出預(yù)算，基于真實(shí)的數(shù)據(jù)實(shí)驗(yàn)表明該算法與現(xiàn)有的算法相比降低了40%的估計(jì)誤差。但是，該算法不適用于非二元任務(wù)分類，代理人無(wú)法辨識(shí)具有分發(fā)任務(wù)能力的用戶。針對(duì)具有服務(wù)質(zhì)量要求的感應(yīng)任務(wù)分配問(wèn)題，文獻(xiàn)[7]提出了混合貪心和蜂群算法，最小化市場(chǎng)成本和最大化市場(chǎng)收益,但該研究工作為了保證穩(wěn)定的空間覆蓋，只考慮市場(chǎng)中的定期參與人，忽視了機(jī)會(huì)性參與人，無(wú)法獲取更多的感應(yīng)數(shù)據(jù)且縮小了空間覆蓋范圍；文獻(xiàn)[8]提出了一種基于和聲搜索的元啟發(fā)式分配算法，實(shí)現(xiàn)了最大化眾包平臺(tái)收益的目標(biāo)。

文獻(xiàn)[9-10]針對(duì)眾包任務(wù)具有位置約束的分配問(wèn)題進(jìn)行研究，文獻(xiàn)[9]提出一個(gè)兩階段的優(yōu)化方法，包括采用隱匿位置的全局優(yōu)化方法和采用精確位置的局部?jī)?yōu)化方法，實(shí)現(xiàn)高感應(yīng)數(shù)據(jù)覆蓋率和低成本消耗的目標(biāo)。然而，為隱匿位置的用戶分配任務(wù)時(shí)，該方法忽略了移動(dòng)用戶的可信度，導(dǎo)致獲取的感應(yīng)數(shù)據(jù)質(zhì)量較低。文獻(xiàn)[10]設(shè)計(jì)了具有局部約束的精確傳感效應(yīng)函數(shù)，最大限度地利用傳感效應(yīng)解決眾包任務(wù)分配問(wèn)題，進(jìn)一步針對(duì)感知任務(wù)分配的問(wèn)題提出一種基于粒子群優(yōu)化的最優(yōu)算法。Chen等[11]研究了具有位置依賴的任務(wù)分配問(wèn)題，考慮眾包任務(wù)的地理特性和移動(dòng)用戶時(shí)空限制性，設(shè)計(jì)了高效的近似算法LRBA和基于討價(jià)還價(jià)理論的定價(jià)機(jī)制。近似算法LRBA將任務(wù)分配問(wèn)題分解成若干子問(wèn)題，在單次迭代過(guò)程中重塑收益函數(shù)，該算法具有良好的可執(zhí)行性，定價(jià)機(jī)制考慮了行為成本和市場(chǎng)需求。

文獻(xiàn)[12-14]對(duì)眾包任務(wù)具有時(shí)效性限制的任務(wù)分配問(wèn)題進(jìn)行研究。文獻(xiàn)[12]提出高效、可信并滿足個(gè)體理性的機(jī)制，為眾包人招募合適的移動(dòng)用戶并支付合理的報(bào)酬提供了依據(jù)。文獻(xiàn)[13]以非合作博弈模型分析異質(zhì)用戶間的行為交互，提出一種分布式任務(wù)選擇算法，為移動(dòng)用戶計(jì)算任務(wù)選擇并制定移動(dòng)性方案，該文獻(xiàn)的分布式任務(wù)選擇算法是基于固定移動(dòng)用戶集，沒(méi)有考慮用戶群的動(dòng)態(tài)變化。文獻(xiàn)[14]提出了一種最小化任務(wù)總執(zhí)行時(shí)間的近似算法，將近似最優(yōu)比定義為算法執(zhí)行時(shí)間與最優(yōu)值的比值，該算法在不同的參數(shù)設(shè)置下具有良好的近似最優(yōu)比。Zhang等[15]考慮任務(wù)多樣性和任務(wù)依賴的用戶可靠性因素，為異構(gòu)眾包市場(chǎng)的任務(wù)分配問(wèn)題提出上下文相關(guān)的bandit規(guī)劃方法。bandit方法中任務(wù)分配過(guò)程分階段進(jìn)行，在確定用戶的可靠性并初始化權(quán)值后對(duì)用戶進(jìn)行選擇。該方法試圖最大化眾包人在有限預(yù)算下的收益，從眾包人的單一角度分析任務(wù)的分配問(wèn)題，忽視了用戶的收益情況。文獻(xiàn)[16]研究了異構(gòu)空間眾包任務(wù)分配問(wèn)題，建立了一種與分配過(guò)程相匹配的用戶遷移行為預(yù)測(cè)模型，提出了有效的啟發(fā)式方法，其中包括多輪線性權(quán)值優(yōu)化和增強(qiáng)多目標(biāo)粒子群優(yōu)化算法，實(shí)現(xiàn)了眾包任務(wù)的局部最優(yōu)分配。

移動(dòng)眾包市場(chǎng)演化機(jī)理研究主要考慮市場(chǎng)中眾包人和移動(dòng)用戶兩兩組合之間的競(jìng)爭(zhēng)問(wèn)題。Yang等[17]研究了在眾包人報(bào)酬確定的情況下，移動(dòng)用戶決定工作量使收益最大化的問(wèn)題，并用一輪斯塔克伯格博弈分析眾包人與移動(dòng)用戶之間的競(jìng)爭(zhēng)過(guò)程。單輪的靜態(tài)模型雖有研究意義但多輪的動(dòng)態(tài)模型更符合移動(dòng)眾包市場(chǎng)的運(yùn)作。Peng等[18]基于多輪動(dòng)態(tài)模型研究移動(dòng)眾包市場(chǎng)中的雙邊競(jìng)爭(zhēng)問(wèn)題，以非合作博弈模型對(duì)眾包人之間競(jìng)爭(zhēng)進(jìn)行建模，以演化博弈模型對(duì)移動(dòng)用戶間競(jìng)爭(zhēng)進(jìn)行建模，分析得到博弈的穩(wěn)定狀態(tài)納什均衡，并驗(yàn)證了均衡的收斂性。在移動(dòng)用戶的演化博弈中，用戶對(duì)眾包人的選擇進(jìn)行競(jìng)爭(zhēng)演化，由于該文獻(xiàn)是基于單一的DM模式眾包市場(chǎng)，忽視了移動(dòng)用戶之間對(duì)感應(yīng)數(shù)據(jù)貢獻(xiàn)量的競(jìng)爭(zhēng)。Sun等[19]對(duì)移動(dòng)用戶在一個(gè)眾包方有多個(gè)感知過(guò)程情況下的感知行為進(jìn)行研究，提出感應(yīng)過(guò)程參與博弈的框架并基于擁塞博弈模型進(jìn)行分析，設(shè)計(jì)出分布式算法求解參與人的最佳對(duì)策，并驗(yàn)證了系統(tǒng)的納什均衡。Dong等[20]在多眾包人的眾包場(chǎng)景下，以非合作博弈模型建模用戶間對(duì)眾包人選擇的競(jìng)爭(zhēng)并用精英策略動(dòng)力學(xué)求得博弈均衡結(jié)果。

綜上所述，目前針對(duì)單個(gè)眾包方的任務(wù)分配和移動(dòng)眾包市場(chǎng)演化機(jī)理的問(wèn)題已有廣泛研究，各種文獻(xiàn)從不同的角度解決問(wèn)題。但已有研究均基于單一的DM模式移動(dòng)眾包市場(chǎng)，忽略了WoM模式對(duì)市場(chǎng)的有利影響。WoM模式在建立眾包用戶群上具有高效性，并且能夠依賴不同的網(wǎng)絡(luò)通信方式實(shí)現(xiàn)用戶邀請(qǐng)，以滿足不同的眾包任務(wù)要求。與現(xiàn)有研究工作不同的是，本文研究混合DM模式和WoM模式的移動(dòng)眾包市場(chǎng)中單個(gè)眾包方的任務(wù)分配和市場(chǎng)演化機(jī)理問(wèn)題，分析移動(dòng)眾包市場(chǎng)中WoM模式下的用戶交互行為和邀請(qǐng)機(jī)制，設(shè)計(jì)移動(dòng)用戶的效應(yīng)函數(shù)，基于斯塔克伯格博弈模型研究移動(dòng)用戶間博弈行為。

3 WoM模式下的移動(dòng)眾包市場(chǎng)框架

3.1 WoM模式移動(dòng)眾包市場(chǎng)模型

一個(gè)WoM模式移動(dòng)眾包市場(chǎng)由若干眾包人、眾包平臺(tái)和大量移動(dòng)用戶所構(gòu)成。如圖1所示。眾包人負(fù)責(zé)眾包任務(wù)的制定和報(bào)酬的設(shè)計(jì)，移動(dòng)用戶對(duì)眾包任務(wù)進(jìn)行感知、參與并向其他移動(dòng)用戶發(fā)送眾包任務(wù)邀請(qǐng)，眾包平臺(tái)作為市場(chǎng)中的第三方保證平臺(tái)上信息的公開性與真實(shí)性。

3.1.1 市場(chǎng)交互

WoM模式移動(dòng)眾包市場(chǎng)中眾包人、眾包平臺(tái)和移動(dòng)用戶間的交互行為如下。

1) 眾包人在眾包平臺(tái)上發(fā)布眾包任務(wù)和報(bào)酬評(píng)估情況。

3) 移動(dòng)用戶感知眾包任務(wù),并維護(hù)自己的邀請(qǐng)列表，以便眾包人對(duì)移動(dòng)用戶的貢獻(xiàn)進(jìn)行評(píng)估。參與眾包任務(wù)的用戶決定感應(yīng)數(shù)據(jù)的貢獻(xiàn)量并上傳感應(yīng)計(jì)劃到眾包平臺(tái)。

4) 眾包人從眾包平臺(tái)獲取并記錄移動(dòng)用戶的感應(yīng)計(jì)劃。

5) 移動(dòng)用戶按照感應(yīng)計(jì)劃完成眾包任務(wù)并上傳感應(yīng)數(shù)據(jù)和邀請(qǐng)列表到眾包平臺(tái)。

6) 眾包人通過(guò)眾包平臺(tái)獲取感應(yīng)數(shù)據(jù)和用戶的邀請(qǐng)列表，核實(shí)邀請(qǐng)列表信息并計(jì)算用戶的報(bào)酬。

7) 眾包人支付用戶報(bào)酬到眾包平臺(tái)，移動(dòng)用戶通過(guò)平臺(tái)獲取報(bào)酬。

本文側(cè)重于WoM模式下移動(dòng)眾包市場(chǎng)中移動(dòng)用戶行為的分析，考慮單個(gè)眾包人、眾包平臺(tái)和若干移動(dòng)用戶的市場(chǎng)情形。

3.1.2 用戶邀請(qǐng)機(jī)制

WoM模式是一種新穎的眾包任務(wù)感知方式，移動(dòng)用戶通過(guò)其他移動(dòng)用戶的邀請(qǐng)感知眾包任務(wù)。在移動(dòng)眾包市場(chǎng)中，眾包人將眾包任務(wù)發(fā)布到眾包平臺(tái)，成功感知的移動(dòng)用戶考慮是否向其他移動(dòng)用戶擴(kuò)散眾包任務(wù)邀請(qǐng)。被邀請(qǐng)的移動(dòng)用戶決定是否接受邀請(qǐng)并考慮是否繼續(xù)擴(kuò)散眾包任務(wù)邀請(qǐng)，如此反復(fù)下去。在WoM模式移動(dòng)眾包市場(chǎng)中，成功感知眾包任務(wù)的移動(dòng)用戶可以向外擴(kuò)散任務(wù)邀請(qǐng)，因而在用戶之間形成邀請(qǐng)與被邀請(qǐng)的關(guān)系。如圖2所示，WoM模式移動(dòng)眾包市場(chǎng)的移動(dòng)用戶之間形成了類似森林結(jié)構(gòu)的關(guān)系。本文根據(jù)移動(dòng)用戶間的邀請(qǐng)關(guān)系，將市場(chǎng)中的移動(dòng)用戶定義為4種級(jí)別。

零級(jí)移動(dòng)用戶：這種移動(dòng)用戶通過(guò)眾包平臺(tái)直接感知眾包任務(wù)，與其他移動(dòng)用戶無(wú)關(guān)聯(lián)，如圖2中的移動(dòng)用戶1~3。

一級(jí)移動(dòng)用戶：這種移動(dòng)用戶以DM模式通過(guò)眾包平臺(tái)感知眾包任務(wù)，以WoM 模式向外擴(kuò)散任務(wù)邀請(qǐng)，如圖2中的移動(dòng)用戶4~5。

二級(jí)移動(dòng)用戶：這種移動(dòng)用戶以WoM模式感知眾包任務(wù)，即接受其他移動(dòng)用戶的任務(wù)邀請(qǐng)，并向外擴(kuò)散任務(wù)邀請(qǐng)，如圖2中的移動(dòng)用戶6~9。

三級(jí)移動(dòng)用戶：這種移動(dòng)用戶以WoM 模式感知眾包任務(wù)，不向外擴(kuò)散任務(wù)邀請(qǐng)，如圖2中的移動(dòng)用戶10~13。

在移動(dòng)眾包市場(chǎng)中，任何參與了眾包任務(wù)感知的移動(dòng)用戶一定屬于上述4種級(jí)別移動(dòng)用戶中的某一種。

圖1 一個(gè)WoM模式移動(dòng)眾包市場(chǎng)

圖2 WoM模式下移動(dòng)用戶的森林關(guān)系圖

3.2 移動(dòng)用戶模型

3.2.1 用戶行為

WoM模式移動(dòng)眾包市場(chǎng)中移動(dòng)用戶的行為如下。

移動(dòng)用戶感知眾包任務(wù)，用戶直接從眾包平臺(tái)或通過(guò)其他移動(dòng)用戶的邀請(qǐng)感知眾包任務(wù)。

移動(dòng)用戶制定感應(yīng)計(jì)劃，確定感應(yīng)數(shù)據(jù)貢獻(xiàn)量。本文假設(shè)市場(chǎng)中的移動(dòng)用戶是完全理性的，移動(dòng)用戶基于自身收益最大化制定感應(yīng)計(jì)劃。因此，WoM模式移動(dòng)眾包市場(chǎng)中，一級(jí)、二級(jí)和三級(jí)移動(dòng)用戶在制定感應(yīng)計(jì)劃時(shí)需要考慮其邀請(qǐng)者和被邀請(qǐng)者的感應(yīng)計(jì)劃。

移動(dòng)用戶上傳感應(yīng)計(jì)劃到眾包平臺(tái)，完成感應(yīng)數(shù)據(jù)的收集后提交感應(yīng)數(shù)據(jù)和邀請(qǐng)列表到平臺(tái)。

移動(dòng)用戶從眾包平臺(tái)獲取報(bào)酬。

圖3 移動(dòng)用戶WoM模式任務(wù)感知和任務(wù)邀請(qǐng)

3.2.2 用戶效應(yīng)

4 移動(dòng)用戶的博弈分析

本文基于博弈論研究WoM模式移動(dòng)眾包市場(chǎng)中移動(dòng)用戶間的行為交互，分析并預(yù)測(cè)市場(chǎng)中移動(dòng)用戶的貢獻(xiàn)，預(yù)測(cè)結(jié)果為眾包人設(shè)定眾包任務(wù)和預(yù)算評(píng)估提供參考。在本文所描述的眾包服務(wù)中，移動(dòng)用戶提交感應(yīng)數(shù)據(jù)量的多少由移動(dòng)用戶自身決策，由于移動(dòng)用戶之間存在邀請(qǐng)與被邀請(qǐng)的關(guān)系，所以這一決策存在先后關(guān)系，且邀請(qǐng)者的決策直接影響被邀請(qǐng)者的決策。上述的用戶交互特點(diǎn)與斯塔克伯格博弈模型特征相適應(yīng)，所以本文基于斯塔克伯格模型對(duì)WoM模式下移動(dòng)用戶間的行為交互展開分析。

4.1 移動(dòng)用戶博弈的斯塔克伯格模型

WoM 模式下的移動(dòng)用戶行為交互問(wèn)題可以建模成兩階段的斯塔克伯格博弈模型，這是一個(gè)由兩博弈方組成的完全信息博弈模型，其中，一博弈方作為領(lǐng)導(dǎo)者，另一方是追隨者[20]，第一個(gè)階段是領(lǐng)導(dǎo)者做出決策的過(guò)程，第二個(gè)階段是追隨者做出決策的過(guò)程。在WoM模式下，邀請(qǐng)者作為斯塔克伯格模型的領(lǐng)導(dǎo)者，先做決策；被邀請(qǐng)者作為一個(gè)整體為追隨者，后做決策。在WoM模式的移動(dòng)眾包市場(chǎng)中，移動(dòng)用戶間決策的先后順序由加入到眾包任務(wù)的時(shí)間順序決定。本文采用逆向歸納法分析兩階段的斯塔克伯格博弈，首先分析第二個(gè)階段追隨者的決策過(guò)程，得到追隨者的最佳對(duì)策；然后，根據(jù)第二階段的結(jié)果反推出第一階段博弈的最佳對(duì)策。假設(shè)在博弈中參與人均是完全理性且自私的，參與人只考慮最大化自身收益。在WoM模式移動(dòng)眾包市場(chǎng)中，由于邀請(qǐng)者無(wú)法知曉其被邀請(qǐng)者的后續(xù)行為，所以博弈只存在于邀請(qǐng)者與其直接被邀請(qǐng)者間。

圖4 WoM模式三級(jí)用戶關(guān)系

接下來(lái)，本文分別針對(duì)一級(jí)博弈和二級(jí)博弈展開建模分析。

1) 一級(jí)博弈

參與人的效應(yīng)函數(shù)：領(lǐng)導(dǎo)者m的收益函數(shù)為

2) 二級(jí)博弈

參與人的效應(yīng)函數(shù)：領(lǐng)導(dǎo)者m的收益函數(shù)為

4.2 斯塔克伯格均衡

本文針對(duì)以上建模的一級(jí)博弈和二級(jí)博弈分別展開分析，探索博弈是否存在唯一的斯塔克伯格均衡。

1) 一級(jí)博弈分析

2) 二級(jí)博弈分析

情況1 領(lǐng)導(dǎo)者設(shè)定其邀請(qǐng)者屬于一級(jí)用戶，有

情況2 領(lǐng)導(dǎo)者設(shè)定其邀請(qǐng)者屬于二級(jí)用戶，有

4.3 斯塔克伯格均衡的存在唯一性

本節(jié)將證明上述一級(jí)博弈和二級(jí)博弈中斯塔克伯格均衡的存在唯一性。在本文所討論的斯塔克伯格博弈中參與人有領(lǐng)導(dǎo)者和追隨者，本文分別對(duì)每個(gè)參與人的最佳對(duì)策進(jìn)行證明。在這里以一級(jí)博弈過(guò)程為例證明，二級(jí)博弈的均衡證明可同理。

定理1 斯塔克伯格均衡存在且唯一

證明 首先，本文證明斯塔克伯格博弈中參與人的最佳對(duì)策唯一。

令上述一階導(dǎo)數(shù)為0，可求得

令上述一階導(dǎo)數(shù)為0，可求得

斯塔克伯格均衡是斯塔克伯格博弈中每個(gè)參與人的最佳對(duì)策組合，如前所述，斯塔克伯格博弈中領(lǐng)導(dǎo)者和參與者都有唯一的最佳對(duì)策。因此斯塔克伯格均衡存在且唯一。證畢。

4.4 移動(dòng)用戶均衡算法

基于上述分析，本文提出計(jì)算斯塔克伯格均衡的算法，如算法1所示。

算法1 計(jì)算斯塔克伯格均衡算法

10) else

13) else

15) end if

16) end if

17) else:

19) end if

20) end for

5 仿真實(shí)驗(yàn)

5.1 仿真環(huán)境

表1 仿真參數(shù)設(shè)置

5.2 移動(dòng)用戶的最佳對(duì)策

圖5 零級(jí)用戶效應(yīng)函數(shù)

圖6 一級(jí)用戶效應(yīng)函數(shù)

圖7 二級(jí)用戶效應(yīng)函數(shù)

圖8 三級(jí)用戶效應(yīng)函數(shù)

綜上所述，WoM模式的任務(wù)感知和邀請(qǐng)行為為用戶帶來(lái)更高的效應(yīng)且提高了用戶的任務(wù)完成質(zhì)量，因此用戶將傾向于進(jìn)行WoM模式的任務(wù)感知和用戶邀請(qǐng)。

5.3 斯塔克伯格均衡的唯一性

本文以斯塔克伯格模型將WoM模式市場(chǎng)中的移動(dòng)用戶間交互建模成一級(jí)博弈和二級(jí)博弈。上文分別研究了一級(jí)博弈和二級(jí)博弈中均會(huì)存在著唯一確定的斯塔克伯格均衡。這里給出了一級(jí)和二級(jí)博弈中領(lǐng)導(dǎo)者和追隨者最佳對(duì)策的曲線，根據(jù)斯塔克伯格均衡的幾何意義，在領(lǐng)導(dǎo)者和追隨者各自最佳對(duì)策曲線的交點(diǎn)處取得斯塔克伯格均衡。

圖9展現(xiàn)了一級(jí)博弈的斯塔克伯格均衡。二級(jí)博弈要考慮領(lǐng)導(dǎo)者的邀請(qǐng)者類別，圖10描述了領(lǐng)導(dǎo)者設(shè)定其邀請(qǐng)者進(jìn)行DM模式任務(wù)感知時(shí)的斯塔克伯格均衡，圖11描述了領(lǐng)導(dǎo)者設(shè)定其邀請(qǐng)者進(jìn)行WoM模式任務(wù)感知時(shí)的斯塔克伯格均衡。對(duì)比這幾種不同的斯塔克伯格均衡發(fā)現(xiàn)二級(jí)博弈中領(lǐng)導(dǎo)者在均衡處取得的策略（數(shù)據(jù)貢獻(xiàn)量）明顯大于一級(jí)斯塔克伯格博弈。這是因?yàn)橐患?jí)博弈中領(lǐng)導(dǎo)者是以DM模式感知眾包任務(wù)，而二級(jí)博弈中領(lǐng)導(dǎo)者是以WoM 模式感知眾包任務(wù)，不同的感知方式導(dǎo)致用戶所獲得的收益不同，不同程度上激勵(lì)用戶做出感應(yīng)數(shù)據(jù)量的決策。

圖9 一級(jí)博弈的斯塔克伯格均衡

圖10 二級(jí)博弈的斯塔克伯格均衡情況1

圖11 二級(jí)博弈的斯塔克伯格均衡情況2

5.4 任務(wù)推薦值對(duì)用戶效應(yīng)和最佳對(duì)策的影響

圖12 任務(wù)推薦值對(duì)零級(jí)用戶效應(yīng)函數(shù)和最佳策略的影響

圖13 任務(wù)推薦值對(duì)一級(jí)用戶效應(yīng)函數(shù)和最佳對(duì)策的影響

圖14 任務(wù)推薦值對(duì)二級(jí)用戶效應(yīng)函數(shù)和最佳對(duì)策的影響

圖15 任務(wù)推薦值對(duì)三級(jí)用戶效應(yīng)函數(shù)和最佳對(duì)策的影響

5.5 回報(bào)率、對(duì)斯塔克伯格均衡的影響

圖16 回報(bào)率和對(duì)一級(jí)博弈斯塔克伯格均衡的影響

圖17 回報(bào)率和對(duì)二級(jí)博弈斯塔克伯格均衡的影響情況1

圖18 回報(bào)率和對(duì)二級(jí)博弈斯塔克伯格均衡的影響情況2

這種實(shí)驗(yàn)現(xiàn)象的出現(xiàn)是合理的，這是由于回報(bào)率的增加或減小會(huì)直接影響與WoM模式相關(guān)移動(dòng)用戶的效應(yīng)，眾包人給予的回報(bào)率越大可以更好地激勵(lì)WoM模式相關(guān)移動(dòng)用戶做出高質(zhì)量的數(shù)據(jù)感應(yīng)。

6 結(jié)束語(yǔ)

本文針對(duì)WoM模式移動(dòng)眾包市場(chǎng)中移動(dòng)用戶的行為交互問(wèn)題進(jìn)行分析并以斯塔克伯格博弈模型建模，用逆向歸納法分析博弈過(guò)程得到唯一確定的斯塔克伯格均衡。通過(guò)仿真實(shí)驗(yàn)評(píng)估了移動(dòng)用戶的效應(yīng)函數(shù)性能，驗(yàn)證了斯塔克伯格均衡的存在唯一性，并討論了相關(guān)參數(shù)對(duì)斯塔克伯格均衡的影響。市場(chǎng)中，眾包人通過(guò)對(duì)移動(dòng)用戶的交互行為進(jìn)行博弈建模預(yù)測(cè)用戶的感應(yīng)數(shù)據(jù)貢獻(xiàn)量并評(píng)估報(bào)酬范圍，這為眾包人制定眾包任務(wù)提供理論支持，對(duì)WoM模式移動(dòng)眾包市場(chǎng)運(yùn)行具有重要意義。

接下來(lái)的工作將考慮從眾包人的角度分析WoM模式移動(dòng)眾包市場(chǎng)中的博弈問(wèn)題，設(shè)計(jì)出有關(guān)激勵(lì)機(jī)制進(jìn)一步促進(jìn)移動(dòng)用戶以WoM模式進(jìn)行眾包任務(wù)感知，提高移動(dòng)用戶參與度。

[1] PENG J, ZHU Y, SHU W, et al. Behavior dynamics of multiple crowdsourcers in mobile crowdsourcing market[J]. IEEE Network the Magazine of Global Internetworking, 2016, 30(6):92-96.

[2] LI H, OTA K, DONG M, et al. Mobile crowdsensing in software defined opportunistic networks[J]. IEEE Communications Magazine, 2017, 55(6):140-145.

[3] LANE N D, MILUZZO E, LU H, et al. A survey of mobile phone sensing[J]. IEEE Communications Magazine, 2010, 48(9):140-150.

[4] KHAN W Z, XIANG Y, AALSALEM M Y, et al. Mobile phone sensing systems: a survey[J]. IEEE Communications Surveys & Tutorials, 2013, 15(1): 402-427.

[5] WANG Y, JIA X, JIN Q, et al. Mobile crowdsourcing: framework, challenges, and solutions[J]. Concurrency & Computation Practice & Experience, 2017, 29(3):1-17.

[6] TRAN-THANH L, VENANZI M, ROGERS A, et al. Efficient budget allocation with accuracy guarantees for crowdsourcing classification tasks[C]//International Conference on Autonomous Agents and Multi-Agent Systems. 2013:901-908.

[7] WANG Z, HUANG D, WU H, et al. QoS-constrained sensing task assignment for mobile crowd sensing[C]//IEEE Global Communications Conference (GLOBECOM’14). IEEE, 2014:311-316.

[8] AMIN R G, LI J, ZHU Y. A new harmony search based allocation algorithm for location dependent tasks in crowdsensing[C]// International Conference on Progress in Informatics and Computing. 2016: 581-585.

[9] POURNAJAF L, XIONG L, SUNDERAM V, et al. Spatial task assignment for crowd sensing with cloaked locations[C]//Proceedings of International Conference on Mobile Data Management. IEEE, 2014: 73-82.

[10] ZHAI L, WANG H. Crowdsensing task assignment based on particle swarm optimization in cognitive radio networks[J]. Wireless Communications and Mobile Computing, 2017:1-9.

[11] HE S, SHIN D H, ZHANG J, et al. Near-optimal allocation algorithms for location-dependent tasks in crowdsensing[J]. IEEE Transactions on Vehicular Technology, 2017, PP(99):3392-3405.

[12] MINDER P, SEUKEN S, BERNSTEIN A, et al. CrowdManager - combinatorial allocation and pricing of crowdsourcing tasks with time constraints[C]//ACM Conference on Electronic Commerce. ACM, 2012: 1-18.

[13] MAN H C, SOUTHWELL R, HOU F, et al. Distributed time-sensitive task selection in mobile crowdsensing[C]//The ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM, 2015:157-166.

[14] WU X, HUANG D, SUN Y E, et al. An efficient allocation mechanism for crowdsourcing tasks with minimum execution time[C]//International Conference on Intelligent Computing . 2017:156-167.

[15] ZHANG H, MA Y, SUGIYAMA M. Bandit-based task assignment for heterogeneous crowdsourcing[J]. Neural Computation, 2015, 27(11): 2447-2475.

[16] WANG L, YU Z, HAN Q, et al. Multi-objective optimization based allocation of heterogeneous spatial crowdsourcing tasks[J]. IEEE Transactions on Mobile Computing, 2017, PP(99):1637-1650.

[17] YANG D, XUE G, FANG X, et al. Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing[C]//Annual International Conference on Mobile Computing and Networking. 2012:173-184.

[18] PENG J, ZHU Y, SHU W, et al. When data contributors meet multiple crowdsourcers: Bilateral competition in mobile crowdsourcing[J]. Computer Networks, 2016, 95(11):1-14.

[19] SUN Y, ZHU Y, FENG Z, et al. Sensing processes participation game of smartphones in participatory sensing systems[C]//Annual IEEE International Conference on Sensing, Communication, and Networking. IEEE, 2014: 239-247.

[20] DONG X, ZHANG X, YI Z, et al. Incentive mechanism for crowdsensing platforms based on multi-leader stackelberg game[C]// International Conference on Communicatins and Networking. 2016: 138-147.

[21] WENNERSTROM H, SMITH D B. A game theoretic approach to sensor data communications in an opportunistic network[C]// International Conference on Communications. 2015:6306-6311.

[22] PENG J, WU M Y, ZHU Y, et al. How multiple crowdsourcers compete for smartphone contributions[C]//IEEE Conference on Computer Communications. IEEE, 2015:516-521.

Game-theoretical analysis of mobile contributors in mobile crowd sourcing network with word of mouth mode

ZENG Feng1, WANG Runhua1, PENG Jia2, CHEN Zhigang1

1. School of Computer Science and Engineering, Central South University, Changsha 410000, China 2.State Key Laboratory of Air Traffic Management System and Technology, Nanjing 210000, China

The crowdsourcer who calls for sensing service can recruit enough mobile contributors quickly with the word of mouth mode, improving the quality of sensing tasks. The behavior of mobile contributors in mobile crowdsourcing with the WoM was investigated. It was supposed that each mobile contributor was rational, seeking for the highest utility. The behavior of mobile contributors with a two-level Stackelberg game was formulated. In the first-level game, a mobile contributor who directly worked for the crowdsourcer acted as the leader, while contributors invited by first-level contributors were followers called the second-level contributors. In the second-level game, the second-level contributors were the leaders and contributors invited by them were followers. The Nash equilibrium for each Stackelberg game was proved was existed and unique, and designed an algorithm to reach the equilibrium. Backward induction approach to compute the best response of each game was adopted, and the simulation results show the correctness of theoretical analysis for the interaction among contributors in crowdsoucing with WoM.

mobile crowdsourcing, word of mouth mode, game theory, Stackelberg game

TP309

A

10.11959/j.issn.1000?436x.2019029

2018?07?11；

2018?12?29

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61672540, No.61502159）

The National Natural Science Foundation of China (No.61672540, No.61502159)

曾鋒（1977? ），男，廣東梅州人，博士，中南大學(xué)副教授，主要研究方向?yàn)檫吘売?jì)算、群智感知網(wǎng)絡(luò)、車聯(lián)網(wǎng)與人工智能等。

王潤(rùn)華（1996? ），女，安徽安慶人，中南大學(xué)碩士生，主要研究方向?yàn)橐苿?dòng)眾包網(wǎng)絡(luò)、群智感知網(wǎng)絡(luò)與博弈論等。

彭佳（1990? ），女，土家族，湖南張家界人，博士，空中交通管理系統(tǒng)與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室工程師，主要研究方向?yàn)槿褐歉兄W(wǎng)絡(luò)、博弈論與機(jī)制設(shè)計(jì)、智能交通與空中交通網(wǎng)絡(luò)優(yōu)化等。

陳志剛（1964? ），男，湖南益陽(yáng)人，博士，中南大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)及分布式計(jì)算。