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

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

?

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

3 WoM模式下的移動眾包市場框架

3.1 WoM模式移動眾包市場模型

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

3.1.1 市場交互

WoM模式移動眾包市場中眾包人、眾包平臺和移動用戶間的交互行為如下。

1) 眾包人在眾包平臺上發(fā)布眾包任務(wù)和報酬評估情況。

3) 移動用戶感知眾包任務(wù),并維護自己的邀請列表，以便眾包人對移動用戶的貢獻進行評估。參與眾包任務(wù)的用戶決定感應(yīng)數(shù)據(jù)的貢獻量并上傳感應(yīng)計劃到眾包平臺。

4) 眾包人從眾包平臺獲取并記錄移動用戶的感應(yīng)計劃。

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

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

7) 眾包人支付用戶報酬到眾包平臺，移動用戶通過平臺獲取報酬。

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

3.1.2 用戶邀請機制

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

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

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

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

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

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

圖1 一個WoM模式移動眾包市場

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

3.2 移動用戶模型

3.2.1 用戶行為

WoM模式移動眾包市場中移動用戶的行為如下。

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

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

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

移動用戶從眾包平臺獲取報酬。

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

3.2.2 用戶效應(yīng)

4 移動用戶的博弈分析

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

4.1 移動用戶博弈的斯塔克伯格模型

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

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

接下來，本文分別針對一級博弈和二級博弈展開建模分析。

1) 一級博弈

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

2) 二級博弈

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

4.2 斯塔克伯格均衡

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

1) 一級博弈分析

2) 二級博弈分析

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

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

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

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

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

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

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

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

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

4.4 移動用戶均衡算法

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

算法1 計算斯塔克伯格均衡算法

10) else

13) else

15) end if

16) end if

17) else:

19) end if

20) end for

5 仿真實驗

5.1 仿真環(huán)境

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

5.2 移動用戶的最佳對策

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

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

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

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

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

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

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

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

圖9 一級博弈的斯塔克伯格均衡

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

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

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

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

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

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

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

5.5 回報率、對斯塔克伯格均衡的影響

圖16 回報率和對一級博弈斯塔克伯格均衡的影響

圖17 回報率和對二級博弈斯塔克伯格均衡的影響情況1

圖18 回報率和對二級博弈斯塔克伯格均衡的影響情況2

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

6 結(jié)束語

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

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

[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é)基金資助項目（No.61672540, No.61502159）

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

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

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

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

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