蔡天慧,楊 濤,胡 波
(1.復旦大學 信息科學與工程學院 電子工程系,上海 200433;2.復旦大學 信息科學與工程學院 智慧網(wǎng)絡與系統(tǒng)研究中心,上海 200433)
圖1 基于位置服務的類型Fig.1 Types of location based service
移動智能設備的廣泛使用以及互聯(lián)網(wǎng)技術的快速進步促進了基于位置服務(Location Based Service, LBS)技術的蓬勃發(fā)展.LBS技術不僅可以應用于出行定位導航,還可以應用于用戶興趣點(Points of Interest, POI)推薦、社交圈信息共享等多個領域,如圖1所示.然而,用戶通過主動上報地理位置給服務提供方(Service Provider, SP)獲取所需服務的同時,個人信息不可避免地遭到泄露,對用戶的生活、工作造成了一些影響.盡管用戶暴露給服務提供方的位置信息是零星分散的,服務提供方仍然可以從這些信息中挖掘用戶的生活習慣、興趣愛好以及社交網(wǎng)絡等個人信息進而獲得收益[1-3].故在LBS場景中,大部分用戶具有隱私保護觀念.用戶利用LBS系統(tǒng)平臺發(fā)送服務請求時,包括尋找附近美食等興趣點推薦、附近的好友以及當?shù)厥录龋瑫扇∠鄳奈恢眯畔㈦[藏策略[4-7],主要包括對真實位置加擾動、模糊位置區(qū)域以及發(fā)送虛假位置等方式.可見,系統(tǒng)中的用戶希望暴露更少的個人位置信息,又希望獲得更高的服務質量.
從商業(yè)角度分析,服務提供方希望通過提供服務換取用戶位置信息獲益,而用戶則通過上報自身位置信息獲得所需的服務等級,雙方均可從LBS系統(tǒng)中獲益.但在實際的服務方和被服務方所構成的聯(lián)合體中雙方都被視為理性個體,即雙方各自傾向于自身收益的最大化.此外,不同用戶對服務水平和位置隱私的偏好存在差異,而服務提供方對特定用戶的真實偏好類型未知,導致信息的不對稱,所以服務提供方在提供服務時難以實現(xiàn)更好的個性化服務,從而獲得最佳收益.合同理論是解決信息不對稱場景的一種有效機制[8],本文從服務提供方角度出發(fā),研究在位置信息挖掘中如何基于合同理論方法設計合適的差異化服務機制來獲取最大化收益.
現(xiàn)有的位置信息挖掘領域的研究工作中,文獻[9-10]提出了基于張量分解的轉移概率矩陣法推斷用戶各個地點的出現(xiàn)概率,該方法將位置劃分為M個區(qū)域,構建M×M維轉移矩陣,根據(jù)用戶歷史位置簽到信息估計下一時刻用戶出現(xiàn)的位置.然而這類算法無法應用于用戶歷史位置信息未知的場景.文獻[11-12]針對LBS用戶暴露的個人位置信息的零散、稀疏等特性,提出了最大似然估計算法.但上述文獻均僅對用戶簽到數(shù)據(jù)進行建模分析,未考慮用戶本身對服務水平和個人位置隱私存在偏好以及服務提供方無法準確獲知每個用戶的真實偏好等實際問題.文獻[13]中,Shokri等從實時單點位置挖掘的角度出發(fā),考慮不同用戶對服務水平下降的容忍閾值不同,分別建立了用戶方和服務提供方的優(yōu)化目標函數(shù).其中,用戶最大化個人期望位置隱私,服務提供方最大化位置信息挖掘的準確性,利用了斯坦克爾伯格貝葉斯博弈模型學習用戶和服務方策略.但是該文只是考慮用戶服務水平的下降存在最低忍受閾值,并且只以位置隱私最大化作為目標收益,未考慮用戶對服務水平和位置隱私的偏好差異.此外,在服務提供方無法獲知用戶偏好類型的不完全信息場景下,博弈模型很難求解,因為用戶偏好未知,導致逆向歸納法無法直接回代求解斯坦克爾伯格博弈模型中領導者的最優(yōu)值.而本文提出的基于合同理論的算法,可以很好地彌補博弈模型在建模求解過程遇到的困難,當用戶偏好類型未知導致雙方信息不對稱,即博弈模型中的不完全信息場景時,基于合同理論的機制算法可以通過為不同偏好類型設計各自所屬的最優(yōu)合同來最大化收益,所設計的最優(yōu)合同將使得各個類型用戶都無法通過選擇其他合同而提高收益.
作為經(jīng)濟學理論的一個重要的分支,同博弈論、拍賣理論一樣,合同理論得到了十分廣泛的應用.合同理論研究的是當其中一方知道某些信息而另一方不知道這些信息時,如何設計合理的合同契約來解決這一信息不對稱問題.通常合同理論的建立基于以下2個條件[14]:
1) 合同契約雙方存在一定的利益沖突;
2) 合同契約雙方之間存在信息不對稱問題.
因此,許多場景也可以運用合同理論來解決偏好未知等信息不對稱問題.比如如何針對小區(qū)緩存系統(tǒng)中視頻內(nèi)容提供商的實際偏好類型未知的問題,構建服務提供商和視頻內(nèi)容提供商的收益函數(shù)以及最優(yōu)合同[15-16];無線通信網(wǎng)絡資源分配以及頻譜定價的場景,如何針對網(wǎng)絡中不同偏好類型的用戶,分別設計頻譜質量與價格的最優(yōu)合同組合[17].而本文在位置信息挖掘過程中,針對LBS系統(tǒng)中的服務提供方無法獲知每個用戶的真實偏好導致的信息不對稱問題,引入了合同理論算法,將服務提供方和用戶之間的交易建模為合同理論模型.由服務提供方給用戶提供一份合同,在合同中規(guī)定用戶需要提供的個人位置隱私以及用戶可以獲得的服務等級.該算法機制針對用戶對服務水平和個人位置隱私偏好的差異性,分析位置隱私與位置信息的模糊程度的關系,分別為用戶和服務提供方建立與位置信息的模糊程度有關的收益函數(shù),考慮用戶的個體理性和激勵兼容兩個特性,構建逆向選擇[8]的優(yōu)化問題,為各個不同偏好類型的用戶設計各自的最優(yōu)合同,以實現(xiàn)雙方收益最大化.此外,本算法機制所設計的最優(yōu)合同可激勵用戶在使用LBS服務過程中上報更多的個人位置信息以提高自身收益.
本文研究的主要內(nèi)容及創(chuàng)新點如下:
1) 考慮LBS場景下不同用戶對服務水平和位置隱私的偏好存在差異,針對偏好的差異性設計合適的機制,使得服務提供方的收益最大化;
2) 針對LBS場景下的信息不對稱問題,提出使用合同理論方法,為不同偏好類型的用戶設計不同的最優(yōu)合同組合,建立最優(yōu)合同模型并使用拉格朗日乘子法進行求解,提供差異化的服務.
用戶在使用LBS系統(tǒng)中通常具有隱私保護意識,本文假設用戶普遍采取的位置信息保護策略為模糊法[13].當用戶在某個地點時,可以找到與該地點相近并且符合服務水平要求的其他k-1個地點,然后以1/k的概率隨機選擇其中任意一個地點作為用戶位置,來獲取所需的服務.其中k是模糊等級(k=1,2,3,…),顯然k越大,用戶地理位置的不確定性越大,用戶使用LBS服務過程中位置隱私的暴露程度越低.同時,位置信息的模糊程度k與用戶獲取的服務質量也緊密相關,通常上報的位置信息越精確用戶所能獲得的服務也越好.因此,本文在系統(tǒng)建模過程中,從位置信息的模糊程度不同的角度出發(fā),定義服務提供方和用戶方的收益函數(shù)模型.此外,本文所提算法并不局限于模糊法,也可應用于其他保護策略.
假設存在N種不同偏好類型的用戶,這里偏好類型指的是對服務水平的偏好Π={π1,π2,…,πi,…,πN},所有偏好類型πi(i∈{1,2,…,N})滿足條件: 0≤π1<π2<…<πi<…<πN≤1,i∈{1,2,…,N}.當πi=0時,表示該類型用戶只偏好個人位置信息隱私;當πi=1時,表示該類型用戶只偏好服務水平.
假設服務提供方無法準確獲取每個用戶的具體偏好信息,但可以知道用戶的服務水平偏好分布情況.針對服務提供方對用戶偏好類型未知引起的信息不對稱性問題,提出使用合同理論方法,對服務提供方和N種偏好類型的用戶進行建模分析.
A. 服務提供方模型
服務提供方制定合同組合為{P,SL},由服務水平和用戶享受服務時需要提供的個人位置隱私組成.其中SL代表服務方提供的服務水平,而P代表LBS用戶方使用服務時需要付出的個人位置隱私的等級.P={P1,P2,…,PN},SL={SL1,SL2,…,SLN},在合同組合中用戶需要付出的位置隱私Pi都一一對應一個可獲得的服務水平SLi,N種用戶偏好類型對應N種合同類型(Pi,SLi).每個用戶可以自由選擇是否享受服務以及享受何種等級的服務.
服務提供方的收益主要來源于用戶在使用服務時付出的個人位置信息.假設服務提供方獲取用戶位置信息的單位收益為Φ,提供服務水平需要的單位成本為Ψ,則服務提供方為偏好類型πi的用戶提供服務時,所獲收益為U(i)=Φ·logePi-Ψ·SLi,i=1,2,…,N.這里位置隱私Pi=a·(1/ki),a是位置系數(shù),ki是用戶在采取模糊法時的策略參數(shù),ki越大,服務提供方越難獲取準確的位置信息.對Pi取對數(shù)體現(xiàn)了邊際收益的思想.此時服務提供方的總期望收益可以表示為:
(1)
B. 用戶方模型
用戶的收益主要來源于所獲得的服務,不同用戶對服務等級的偏好不同,因而單位服務水平帶給不同用戶的收益也有差異,假設偏好類型πi的用戶的收益權重為f(πi).用戶享受服務時提供的個人位置信息則作為成本,同理,用戶偏好不同,成本權重也存在差異.假設某偏好類型πi的用戶的成本權重為g(πi),則用戶的收益函數(shù)為f(πi)·SLi-g(πi)·Pi,將上式的左右兩邊同時除以f(πi),定義h(πi)=g(πi)/f(πi),則偏好類型πi用戶收益可表示為:
V(i)=SLi-h(πi)·Pii=1,2,…,N,
(2)
其中:h(πi)是偏好類型πi用戶享受服務時提供隱私的單位成本;h(πi)·Pi則是享受服務所需付出的總成本;SLi是合同規(guī)定用戶可以獲得的回報,即所需求的服務.更加偏好服務水平的用戶,個人位置隱私的暴露成本的影響權重越小,即πi越大,h(πi)越小.顯然,h(πi)需要滿足以下2個條件:
1)h(πi)>0;
2) ?h(πi)/?πi<0.
所以h(πi)是關于πi的嚴格減函數(shù).對于給定的收益函數(shù),用戶會選擇使得自身收益值最大的合同,即選擇屬于自己類型的合同.
考慮到LBS系統(tǒng)中用戶對服務等級和位置隱私的偏好類型不同,服務提供方也無法準確獲知各自偏好信息,故提出構建最優(yōu)合同模型.合同理論作為不完全信息場景的有效機制算法,可以解決信息不對稱問題.服務提供方的目標是如何為各個偏好類型的用戶設計一系列最優(yōu)的合同組合,使得每個類型的用戶只能選擇其中一種最優(yōu)合同最大化自身收益.在設計最優(yōu)合同過程中,考慮N種類型的用戶滿足個體理性(Individual Rationality, IR)和激勵兼容(Incentive Compatibility, IC)[8],以保證合同的可行性,實現(xiàn)服務提供方的收益最大化.下面分別針對這兩個特性,提出可行性約束條件,構建逆向選擇優(yōu)化問題.
定義1個體理性[8]: 假設各個偏好類型πi的用戶都是理性的,所以每個偏好類型的用戶不會接受收益為負的合同,即
V(i)=SLi-h(πi)·Pi≥0 ?i∈{1,2,…,N}.
(3)
定義2激勵兼容[8]: 每種偏好類型πi的用戶都無法通過拒絕屬于自身偏好類型而設計的合同(Pi,SLi),而選擇其他任意一種類型合同來提升自身的收益,即:
SLi-h(πi)·Pi≥SLj-h(πi)·Pj?i≠j,i,j∈{1,2,…,N}.
(4)
基于IR和IC約束條件,最優(yōu)合同模型描述如下:
(5)
基于文獻[18],在LBS場景下,為實現(xiàn)差異化服務,使得各種偏好類型的用戶所對應的最優(yōu)合同收益最大.因此,服務提供方所設計的最優(yōu)合同中,除了滿足個體理性IR和激勵兼容IC的約束條件,根據(jù)用戶方模型中定義的收益函數(shù)V(i)=SLi-h(πi)·Pi,以及單位成本h(πi)的非負和嚴格減函數(shù)的特性,可推導獲得用戶方與服務提供方之間的合同組合{P,SL}同時滿足以下引理:
引理1LBS場景下,對于用戶方與服務提供方之間的任意一個可行合同(Pi,SLi),當且僅當Pi>Pj,有SLi>SLj.
證 根據(jù)激勵兼容IC的約束條件,偏好類型πi滿足下式:
SLi-h(πi)·Pi≥SLj-h(πi)·Pj?i≠j,i,j∈{1,2,…,N}.
(6)
當Pi>Pj時,由于函數(shù)h(πi)數(shù)值滿足非負性,則用戶方獲得的服務水平滿足SLi>SLj.
引理2LBS場景下,對于用戶方與服務提供方之間的任意一個可行合同(Pi,SLi),當且僅當πi>πj時,滿足Pi>Pj;當且僅當Pi>Pj時,滿足πi>πj.
證 根據(jù)激勵兼容IC的約束條件獲得偏好類型πi和πj滿足條件:SLi-h(πi)·Pi≥SLj-h(πi)·Pj以及SLj-h(πj)·Pj≥SLi-h(πj)·Pi,經(jīng)過計算可得:
(Pj-Pi)·(h(πi)-h(πj))≥0 ?i≠j,i,j∈{1,2,…,N}.
(7)
由于函數(shù)h(πi)滿足?h(πi)/?πi<0性質,即h(πi)為嚴格減函數(shù),并且i≠j,所以當用戶方在使用服務時所付出的個人位置信息滿足Pi>Pj,可以得到πi>πj;同理當用戶對服務水平的偏好類型滿足πi>πj時,可以得到Pi>Pj,即更偏好服務水平的人,相對來說更愿意付出個人位置信息.
引理3LBS場景下,用戶方與服務提供方之間的任意一個可行合同(Pi,SLi),各種偏好類型的用戶收益滿足以下條件:
0≤V(1) (8) 證 如果用戶對服務水平的偏好類型為πi>πj,則可得: V(i)=SLi-h(πi)·Pi≥SLj-h(πi)·Pj>SLj-h(πj)·Pj=V(j). (9) 故用戶使用LBS服務過程中,當服務水平的偏好類型滿足πi>πj條件,用戶方的效用滿足V(i)>V(j). 本小節(jié)是對逆向選擇問題(5)進行求解.為了降低求解的復雜度,首先減少約束條件的個數(shù),在減少的同時需要保證問題解的準確性. 從優(yōu)化問題(5)中可以發(fā)現(xiàn)最優(yōu)合同模型總共有N個IR約束條件,下面通過消除其中的N-1個IR約束條件簡化優(yōu)化問題. 根據(jù)激勵兼容IC條件,對于偏好類型為πi的用戶,滿足以下不等式: SLi-h(πi)·Pi≥SL1-h(πi)·P1≥SL1-h(π1)·P1, 即對于任意偏好類型πi≠π1的用戶,其收益都不小于偏好類型π1的用戶,所以當偏好類型π1用戶滿足式(10)條件時,其他N-1個IR約束條件可以忽略: V(1)=SL1-h(π1)·P1=0. (10) 此時,式(3)個體理性約束條件可轉化為式(10),最低偏好類型的用戶將獲得零收益.文獻[15-17,19]給出了相似的結論. 從激勵兼容約束條件以及優(yōu)化問題(5)中發(fā)現(xiàn),本模型總共有N2-N個IC約束條件,下面通過減少IC約束條件簡化優(yōu)化問題. 考慮偏好類型為πi與πi-1用戶滿足的2個LUICs(Local Upward Incentive Constraints)條件[8]: SLi+1-h(πi)·Pi+1≤SLi-h(πi)·Pi,SLi-1-h(πi)·Pi-1≤SLi-1-h(πi-1)·Pi-1. (11) 根據(jù)式(11),可得以下條件: SLi+1-h(πi-1)·Pi+1≤SLi-h(πi-1)·Pi≤SLi-1-h(πi-1)·Pi-1. (12) 同理,考慮偏好類型為πi與πi+1的用戶滿足的2個LDICs(Local Downward Incentive Constraints)條件[8]: SLi+1-h(πi+1)·Pi+1≥SLi-h(πi+1)·Pi,SLi-h(πi)·Pi≥SLi-1-h(πi)·Pi-1. (13) 根據(jù)式(13),可得以下條件: SLi+1-h(πi+1)·Pi+1≥SLi-h(πi+1)·Pi≥ SLi-1-h(πi+1)·Pi-1≥ …≥ SL1-h(πi+1)·P1. (14) 根據(jù)上述LUICs和LDICs條件(12)和(14),可將激勵兼容IC約束條件進行轉化,得到: SLi-1+h(πi)·(Pi-Pi-1)≤SLi≤SLi-1+h(πi-1)·(Pi-Pi-1). (15) 提供更好的服務水平需要更高的成本,服務提供方在最大化自身收益時,必須滿足用戶個體理性條件與激勵兼容條件,再盡量降低自身提供服務的成本,即提供的服務水平在符合條件的情形下應取最小值.故根據(jù)上式(15),不等式的下界是理性的服務提供方在確定服務水平SLi時的最優(yōu)解,即: SLi-h(πi)·Pi=SLi-1-h(πi)·Pi-1. (16) 經(jīng)過上述IC和IR約束條件的減少,原始優(yōu)化問題(5)的約束條件變更為(10)和(16),新的最優(yōu)合同模型定義為: (17) 對于優(yōu)化問題(17),采取拉格朗日乘子法[20]進行求解.最優(yōu)合同表明,對服務等級偏好最低的用戶將不產(chǎn)生收益.現(xiàn)引入拉格朗日乘子ω,υi(i=2,…,N),定義優(yōu)化問題(17)所對應的拉格朗日函數(shù)為: (18) 針對上述優(yōu)化問題,分別考慮i=1,i=2,3,…,N-1和i=N3種情況,迭代求解最優(yōu)合同.下面首先分別對變量求偏導數(shù),令偏導數(shù)為0,求解式(18)的最大值,即優(yōu)化問題(17)的最優(yōu)解: (19) 1) 當i=N時,分別對PN與SLN進行求導,可得: (20) 根據(jù)式(20),可求得用戶在使用服務時上報的個人位置隱私Pi(i=N)的最優(yōu)解為: (21) 根據(jù)式(20)、(21)還可以計算出i=N時,υN的最優(yōu)解. 2) 當i=2,3,…,N-1時,對式(19)進行求解,可得: (22) 3) 當i=1時,對式(19)進行求解,可得: (23) (24) 求得個人位置隱私Pi(i=1,2,3,…,N)的最優(yōu)解后,代入優(yōu)化問題(17)的約束條件,迭代求解服務提供方給出的服務水平SLi(i=1,2,3,…,N)的最優(yōu)值. 對本文所提出的最優(yōu)合同機制進行仿真實驗,以驗證合同理論在LBS場景下的性能.假設用戶位置信息的單位收益與服務的單位成本之比Φ/Ψ=3.為簡單起見,假設LBS用戶的偏好類型服從均勻分布,即αi=1/N. 圖2 不同偏好類型的最優(yōu)合同F(xiàn)ig.2 Optimal contract for different preferences 首先設定用戶對服務水平的偏好類型數(shù)N=5,參考文獻[21]中對用戶偏好類型的設定,5類偏好類型{πi}(i=1,2,…,5)={0.25,0.4,0.55,0.7,0.9}.從圖2中左圖可以看出,當用戶對服務水平有更強的偏好時,用戶傾向于付出自己更多的位置信息以獲得更高水平的服務.圖2中右圖體現(xiàn)服務提供方的服務水平根據(jù)用戶自身的偏好類型的變化而變化,最優(yōu)合同的服務等級隨著用戶偏好類型的提升而提高. 在下面的實驗仿真中,設定用戶對服務等級的偏好類型數(shù)N=12,且這12(i=1,2,…,12)種偏好類型呈現(xiàn)遞增趨勢.圖3~圖6分別將信息不對稱情形(即服務提供方無法獲知用戶的偏好類型)時設計的最優(yōu)合同與完全信息(服務提供方了解每一個用戶的偏好類型)時進行仿真對比. 圖3描述的是不同用戶偏好類型下用戶保護策略模糊法中的模糊等級(策略k的選擇)以及最優(yōu)合同中用戶所能獲得服務等級.可以發(fā)現(xiàn),當用戶對服務等級的偏好程度增強時,用戶更愿意付出自己的部分位置隱私,此時模糊等級k的數(shù)值越來越小,即用戶在上報自身位置時的模糊程度降低,而所能獲得的服務等級越來越高. 圖4描述的是信息不對稱與完全信息兩種情形時用戶收益與用戶偏好類型的關系.從圖中發(fā)現(xiàn),完全信息時,用戶方的收益始終為0,這是因為此時的服務提供方了解每個用戶的偏好,所以設計合同時,為了最大化自身收益,使得每個用戶的獲得的收益均為0.相反,當LBS用戶的偏好類型未知時,用戶方可以從隱藏的位置信息中獲得非負的收益,從圖可知用戶對服務水平的偏好類型越高,所能獲得的收益也越高,這一結果也正好驗證了引理3所給出的結論.圖5(見第248頁)描述的是服務提供方的收益與用戶偏好類型之間的關系,在信息不對稱時服務方所獲得的收益一直低于完全信息情形.同樣,這也是因為用戶對服務等級和個人位置隱私的偏好類型未知時,服務提供方在不完全信息下所設計的合同無法達到完全信息情形下的理想收益,導致部分收益損失. 圖6見第248頁描述的是雙方總收益與用戶偏好類型的關系,可以發(fā)現(xiàn),本文所設計的信息不對稱情形下最優(yōu)合同的總收益接近完全信息時的總收益.由于完全信息情形下,服務提供方直接為每個用戶設計最大化自身收益的合同,使得每個用戶收益均為0;而信息不對稱情形下,服務提供方只能根據(jù)個體理 圖3 不同偏好類型的模糊等級與服務水平Fig.3 Obfuscation level, service level for different preferences 圖4 不同偏好類型的用戶收益Fig.4 Users’ utility for different preferences 圖5 不同偏好類型的服務提供方收益Fig.5 SP’s utility for different preferences 圖6 不同偏好類型的雙方總收益Fig.6 Total utility for different preferences 性和激勵兼容性質為各個類型用戶設計合理的合同,使得非最低偏好類型的用戶均能獲得比最低偏好類型用戶更高的收益.因此,隱藏的具體偏好信息幫助用戶方從服務提供方獲得信息收益,完全信息情形下總收益略高于信息不對稱情形,圖4和圖5也可驗證這一點.因而,從雙方總收益角度可以發(fā)現(xiàn),本文利用合同理論為各個偏好類型所設計的最優(yōu)合同是可行并且有效的. 本文針對LBS系統(tǒng)中服務提供方與用戶之間的信息不對稱問題,在位置信息挖掘過程中,提出了基于合同理論的差異化服務的算法機制設計.該算法機制提出為每一種偏好類型的用戶分別設計各自的最優(yōu)合同,使得用戶方在收益非負的情況下無法通過選擇其他類型的合同提高自身收益,從而實現(xiàn)服務提供方和用戶方各自收益的最大化.仿真結果表明,當用戶對服務水平的偏好上升時,用戶愿意共享更多的個人位置隱私以獲得更高的服務水平,同時獲得的收益也隨之提升.可見,本算法機制同時可以激勵LBS用戶共享更多個人位置隱私.此外,通過比較發(fā)現(xiàn),不對稱信息下雙方的總收益接近完全信息下的總收益,也驗證了算法的可行性和有效性.因此,本文所設計的基于合同理論的差異化服務機制可以有效地解決基于位置服務場景中的用戶偏好未知問題,同時對其他研究領域中信息不對稱問題也具有一定的參考價值.2.2 最優(yōu)合同求解
3 實驗結果與分析
4 結 語