曾鋒，王潤華，彭佳，陳志剛

?

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

曾鋒1，王潤華1，彭佳2，陳志剛1

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

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

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

1 引言

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

文獻(xiàn)[9-10]針對眾包任務(wù)具有位置約束的分配問題進(jìn)行研究，文獻(xiàn)[9]提出一個(gè)兩階段的優(yōu)化方法，包括采用隱匿位置的全局優(yōu)化方法和采用精確位置的局部優(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ù)分配問題，進(jìn)一步針對感知任務(wù)分配的問題提出一種基于粒子群優(yōu)化的最優(yōu)算法。Chen等[11]研究了具有位置依賴的任務(wù)分配問題，考慮眾包任務(wù)的地理特性和移動(dòng)用戶時(shí)空限制性，設(shè)計(jì)了高效的近似算法LRBA和基于討價(jià)還價(jià)理論的定價(jià)機(jī)制。近似算法LRBA將任務(wù)分配問題分解成若干子問題，在單次迭代過程中重塑收益函數(shù)，該算法具有良好的可執(zhí)行性，定價(jià)機(jī)制考慮了行為成本和市場需求。

文獻(xiàn)[12-14]對眾包任務(wù)具有時(shí)效性限制的任務(wù)分配問題進(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)用戶集，沒有考慮用戶群的動(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)眾包市場的任務(wù)分配問題提出上下文相關(guān)的bandit規(guī)劃方法。bandit方法中任務(wù)分配過程分階段進(jìn)行，在確定用戶的可靠性并初始化權(quán)值后對用戶進(jìn)行選擇。該方法試圖最大化眾包人在有限預(yù)算下的收益，從眾包人的單一角度分析任務(wù)的分配問題，忽視了用戶的收益情況。文獻(xiàn)[16]研究了異構(gòu)空間眾包任務(wù)分配問題，建立了一種與分配過程相匹配的用戶遷移行為預(yù)測模型，提出了有效的啟發(fā)式方法，其中包括多輪線性權(quán)值優(yōu)化和增強(qiáng)多目標(biāo)粒子群優(yōu)化算法，實(shí)現(xiàn)了眾包任務(wù)的局部最優(yōu)分配。

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

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

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

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

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

3.1.1 市場交互

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

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

3) 移動(dòng)用戶感知眾包任務(wù),并維護(hù)自己的邀請列表，以便眾包人對移動(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ù)和邀請列表到眾包平臺(tái)。

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

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

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

3.1.2 用戶邀請機(jī)制

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

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

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

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

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

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

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

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

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

3.2.1 用戶行為

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

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

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

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

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

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

3.2.2 用戶效應(yīng)

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

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

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

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

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

接下來，本文分別針對一級(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 斯塔克伯格均衡

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

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

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

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

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

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

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

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

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

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

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

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

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)用戶的最佳對策

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

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

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

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

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

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

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

圖9展現(xiàn)了一級(jí)博弈的斯塔克伯格均衡。二級(jí)博弈要考慮領(lǐng)導(dǎo)者的邀請者類別，圖10描述了領(lǐng)導(dǎo)者設(shè)定其邀請者進(jìn)行DM模式任務(wù)感知時(shí)的斯塔克伯格均衡，圖11描述了領(lǐng)導(dǎo)者設(shè)定其邀請者進(jìn)行WoM模式任務(wù)感知時(shí)的斯塔克伯格均衡。對比這幾種不同的斯塔克伯格均衡發(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ù)推薦值對用戶效應(yīng)和最佳對策的影響

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

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

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

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

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

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

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

圖18 回報(bào)率和對二級(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é)束語

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

接下來的工作將考慮從眾包人的角度分析WoM模式移動(dòng)眾包市場中的博弈問題，設(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

國家自然科學(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)與人工智能等。

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

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

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