位置信息挖掘中的差异化服务机制设计

蔡天慧，杨 涛，胡 波

(1.复旦大学 信息科学与工程学院 电子工程系，上海 200433；2.复旦大学 信息科学与工程学院 智慧网络与系统研究中心，上海 200433)

图1 基于位置服务的类型Fig.1 Types of location based service

移动智能设备的广泛使用以及互联网技术的快速进步促进了基于位置服务(Location Based Service, LBS)技术的蓬勃发展.LBS技术不仅可以应用于出行定位导航，还可以应用于用户兴趣点(Points of Interest, POI)推荐、社交圈信息共享等多个领域，如图1所示.然而，用户通过主动上报地理位置给服务提供方(Service Provider, SP)获取所需服务的同时，个人信息不可避免地遭到泄露，对用户的生活、工作造成了一些影响.尽管用户暴露给服务提供方的位置信息是零星分散的，服务提供方仍然可以从这些信息中挖掘用户的生活习惯、兴趣爱好以及社交网络等个人信息进而获得收益[1-3].故在LBS场景中，大部分用户具有隐私保护观念.用户利用LBS系统平台发送服务请求时，包括寻找附近美食等兴趣点推荐、附近的好友以及当地事件等，会采取相应的位置信息隐藏策略[4-7]，主要包括对真实位置加扰动、模糊位置区域以及发送虚假位置等方式.可见，系统中的用户希望暴露更少的个人位置信息，又希望获得更高的服务质量.

从商业角度分析，服务提供方希望通过提供服务换取用户位置信息获益，而用户则通过上报自身位置信息获得所需的服务等级，双方均可从LBS系统中获益.但在实际的服务方和被服务方所构成的联合体中双方都被视为理性个体，即双方各自倾向于自身收益的最大化.此外，不同用户对服务水平和位置隐私的偏好存在差异，而服务提供方对特定用户的真实偏好类型未知，导致信息的不对称，所以服务提供方在提供服务时难以实现更好的个性化服务，从而获得最佳收益.合同理论是解决信息不对称场景的一种有效机制[8]，本文从服务提供方角度出发，研究在位置信息挖掘中如何基于合同理论方法设计合适的差异化服务机制来获取最大化收益.

现有的位置信息挖掘领域的研究工作中，文献[9-10]提出了基于张量分解的转移概率矩阵法推断用户各个地点的出现概率，该方法将位置划分为M个区域，构建M×M维转移矩阵，根据用户历史位置签到信息估计下一时刻用户出现的位置.然而这类算法无法应用于用户历史位置信息未知的场景.文献[11-12]针对LBS用户暴露的个人位置信息的零散、稀疏等特性，提出了最大似然估计算法.但上述文献均仅对用户签到数据进行建模分析，未考虑用户本身对服务水平和个人位置隐私存在偏好以及服务提供方无法准确获知每个用户的真实偏好等实际问题.文献[13]中，Shokri等从实时单点位置挖掘的角度出发，考虑不同用户对服务水平下降的容忍阈值不同，分别建立了用户方和服务提供方的优化目标函数.其中，用户最大化个人期望位置隐私，服务提供方最大化位置信息挖掘的准确性，利用了斯坦克尔伯格贝叶斯博弈模型学习用户和服务方策略.但是该文只是考虑用户服务水平的下降存在最低忍受阈值，并且只以位置隐私最大化作为目标收益，未考虑用户对服务水平和位置隐私的偏好差异.此外，在服务提供方无法获知用户偏好类型的不完全信息场景下，博弈模型很难求解，因为用户偏好未知，导致逆向归纳法无法直接回代求解斯坦克尔伯格博弈模型中领导者的最优值.而本文提出的基于合同理论的算法，可以很好地弥补博弈模型在建模求解过程遇到的困难，当用户偏好类型未知导致双方信息不对称，即博弈模型中的不完全信息场景时，基于合同理论的机制算法可以通过为不同偏好类型设计各自所属的最优合同来最大化收益，所设计的最优合同将使得各个类型用户都无法通过选择其他合同而提高收益.

作为经济学理论的一个重要的分支，同博弈论、拍卖理论一样，合同理论得到了十分广泛的应用.合同理论研究的是当其中一方知道某些信息而另一方不知道这些信息时，如何设计合理的合同契约来解决这一信息不对称问题.通常合同理论的建立基于以下2个条件[14]：

1) 合同契约双方存在一定的利益冲突；

2) 合同契约双方之间存在信息不对称问题.

因此，许多场景也可以运用合同理论来解决偏好未知等信息不对称问题.比如如何针对小区缓存系统中视频内容提供商的实际偏好类型未知的问题，构建服务提供商和视频内容提供商的收益函数以及最优合同[15-16]；无线通信网络资源分配以及频谱定价的场景，如何针对网络中不同偏好类型的用户，分别设计频谱质量与价格的最优合同组合[17].而本文在位置信息挖掘过程中，针对LBS系统中的服务提供方无法获知每个用户的真实偏好导致的信息不对称问题，引入了合同理论算法，将服务提供方和用户之间的交易建模为合同理论模型.由服务提供方给用户提供一份合同，在合同中规定用户需要提供的个人位置隐私以及用户可以获得的服务等级.该算法机制针对用户对服务水平和个人位置隐私偏好的差异性，分析位置隐私与位置信息的模糊程度的关系，分别为用户和服务提供方建立与位置信息的模糊程度有关的收益函数，考虑用户的个体理性和激励兼容两个特性，构建逆向选择[8]的优化问题，为各个不同偏好类型的用户设计各自的最优合同，以实现双方收益最大化.此外，本算法机制所设计的最优合同可激励用户在使用LBS服务过程中上报更多的个人位置信息以提高自身收益.

本文研究的主要内容及创新点如下：

1) 考虑LBS场景下不同用户对服务水平和位置隐私的偏好存在差异，针对偏好的差异性设计合适的机制，使得服务提供方的收益最大化；

2) 针对LBS场景下的信息不对称问题，提出使用合同理论方法，为不同偏好类型的用户设计不同的最优合同组合，建立最优合同模型并使用拉格朗日乘子法进行求解，提供差异化的服务.

1 基于位置服务的用户方与服务提供方系统模型

用户在使用LBS系统中通常具有隐私保护意识，本文假设用户普遍采取的位置信息保护策略为模糊法[13].当用户在某个地点时，可以找到与该地点相近并且符合服务水平要求的其他k-1个地点，然后以1/k的概率随机选择其中任意一个地点作为用户位置，来获取所需的服务.其中k是模糊等级(k=1,2,3,…)，显然k越大，用户地理位置的不确定性越大，用户使用LBS服务过程中位置隐私的暴露程度越低.同时，位置信息的模糊程度k与用户获取的服务质量也紧密相关，通常上报的位置信息越精确用户所能获得的服务也越好.因此，本文在系统建模过程中，从位置信息的模糊程度不同的角度出发，定义服务提供方和用户方的收益函数模型.此外，本文所提算法并不局限于模糊法，也可应用于其他保护策略.

假设存在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是位置系数，ki是用户在采取模糊法时的策略参数，ki越大，服务提供方越难获取准确的位置信息.对Pi取对数体现了边际收益的思想.此时服务提供方的总期望收益可以表示为：

(1)

B. 用户方模型

用户的收益主要来源于所获得的服务，不同用户对服务等级的偏好不同，因而单位服务水平带给不同用户的收益也有差异，假设偏好类型πi的用户的收益权重为f(πi).用户享受服务时提供的个人位置信息则作为成本，同理，用户偏好不同，成本权重也存在差异.假设某偏好类型πi的用户的成本权重为g(πi)，则用户的收益函数为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是合同规定用户可以获得的回报，即所需求的服务.更加偏好服务水平的用户，个人位置隐私的暴露成本的影响权重越小，即πi越大，h(πi)越小.显然，h(πi)需要满足以下2个条件：

1)h(πi)>0;

2) ∂h(πi)/∂πi<0.

所以h(πi)是关于πi的严格减函数.对于给定的收益函数，用户会选择使得自身收益值最大的合同，即选择属于自己类型的合同.

2 最优合同模型的设计与求解

考虑到LBS系统中用户对服务等级和位置隐私的偏好类型不同，服务提供方也无法准确获知各自偏好信息，故提出构建最优合同模型.合同理论作为不完全信息场景的有效机制算法，可以解决信息不对称问题.服务提供方的目标是如何为各个偏好类型的用户设计一系列最优的合同组合，使得每个类型的用户只能选择其中一种最优合同最大化自身收益.在设计最优合同过程中，考虑N种类型的用户满足个体理性(Individual Rationality, IR)和激励兼容(Incentive Compatibility, IC)[8]，以保证合同的可行性，实现服务提供方的收益最大化.下面分别针对这两个特性，提出可行性约束条件，构建逆向选择优化问题.

2.1 合同的可行性分析

定义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约束条件，最优合同模型描述如下：

(5)

基于文献[18]，在LBS场景下，为实现差异化服务，使得各种偏好类型的用户所对应的最优合同收益最大.因此，服务提供方所设计的最优合同中，除了满足个体理性IR和激励兼容IC的约束条件，根据用户方模型中定义的收益函数V(i)=SLi-h(πi)·Pi，以及单位成本h(πi)的非负和严格减函数的特性，可推导获得用户方与服务提供方之间的合同组合{P,SL}同时满足以下引理：

引理1LBS场景下，对于用户方与服务提供方之间的任意一个可行合同(Pi,SLi)，当且仅当Pi>Pj，有SLi>SLj.

证 根据激励兼容IC的约束条件，偏好类型πi满足下式：

SLi-h(πi)·Pi≥SLj-h(πi)·Pj∀i≠j,i,j∈{1,2,…,N}.

(6)

当Pi>Pj时，由于函数h(πi)数值满足非负性，则用户方获得的服务水平满足SLi>SLj.

引理2LBS场景下，对于用户方与服务提供方之间的任意一个可行合同(Pi,SLi)，当且仅当πi>πj时，满足Pi>Pj；当且仅当Pi>Pj时，满足πi>πj.

证 根据激励兼容IC的约束条件获得偏好类型πi和πj满足条件：SLi-h(πi)·Pi≥SLj-h(πi)·Pj以及SLj-h(πj)·Pj≥SLi-h(πj)·Pi，经过计算可得：

(Pj-Pi)·(h(πi)-h(πj))≥0 ∀i≠j,i,j∈{1,2,…,N}.

(7)

由于函数h(πi)满足∂h(πi)/∂πi<0性质，即h(πi)为严格减函数，并且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).

2.2 最优合同求解

本小节是对逆向选择问题(5)进行求解.为了降低求解的复杂度，首先减少约束条件的个数，在减少的同时需要保证问题解的准确性.

从优化问题(5)中可以发现最优合同模型总共有N个IR约束条件，下面通过消除其中的N-1个IR约束条件简化优化问题.

根据激励兼容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]给出了相似的结论.

从激励兼容约束条件以及优化问题(5)中发现，本模型总共有N2-N个IC约束条件，下面通过减少IC约束条件简化优化问题.

考虑偏好类型为π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)

根据式(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)

根据式(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)

根据上述LUICs和LDICs条件(12)和(14)，可将激励兼容IC约束条件进行转化，得到：

SLi-1+h(πi)·(Pi-Pi-1)≤SLi≤SLi-1+h(πi-1)·(Pi-Pi-1).

(15)

提供更好的服务水平需要更高的成本，服务提供方在最大化自身收益时，必须满足用户个体理性条件与激励兼容条件，再尽量降低自身提供服务的成本，即提供的服务水平在符合条件的情形下应取最小值.故根据上式(15)，不等式的下界是理性的服务提供方在确定服务水平SLi时的最优解，即：

SLi-h(πi)·Pi=SLi-1-h(πi)·Pi-1.

(16)

经过上述IC和IR约束条件的减少，原始优化问题(5)的约束条件变更为(10)和(16)，新的最优合同模型定义为：

(17)

对于优化问题(17)，采取拉格朗日乘子法[20]进行求解.最优合同表明，对服务等级偏好最低的用户将不产生收益.现引入拉格朗日乘子ω,υi(i=2,…,N)，定义优化问题(17)所对应的拉格朗日函数为：

(18)

针对上述优化问题，分别考虑i=1,i=2,3,…,N-1和i=N3种情况，迭代求解最优合同.下面首先分别对变量求偏导数，令偏导数为0，求解式(18)的最大值，即优化问题(17)的最优解：

(19)

1) 当i=N时，分别对PN与SLN进行求导，可得：

(20)

根据式(20)，可求得用户在使用服务时上报的个人位置隐私Pi(i=N)的最优解为：

(21)

根据式(20)、(21)还可以计算出i=N时，υN的最优解.

2) 当i=2,3,…,N-1时，对式(19)进行求解，可得：

(22)

3) 当i=1时，对式(19)进行求解，可得：

(23)

(24)

求得个人位置隐私Pi(i=1,2,3,…,N)的最优解后，代入优化问题(17)的约束条件，迭代求解服务提供方给出的服务水平SLi(i=1,2,3,…,N)的最优值.

3 实验结果与分析

对本文所提出的最优合同机制进行仿真实验，以验证合同理论在LBS场景下的性能.假设用户位置信息的单位收益与服务的单位成本之比Φ/Ψ=3.为简单起见，假设LBS用户的偏好类型服从均匀分布，即αi=1/N.

图2 不同偏好类型的最优合同Fig.2 Optimal contract for different preferences

首先设定用户对服务水平的偏好类型数N=5，参考文献[21]中对用户偏好类型的设定，5类偏好类型{πi}(i=1,2,…,5)={0.25,0.4,0.55,0.7,0.9}.从图2中左图可以看出，当用户对服务水平有更强的偏好时，用户倾向于付出自己更多的位置信息以获得更高水平的服务.图2中右图体现服务提供方的服务水平根据用户自身的偏好类型的变化而变化，最优合同的服务等级随着用户偏好类型的提升而提高.

在下面的实验仿真中，设定用户对服务等级的偏好类型数N=12，且这12(i=1,2,…,12)种偏好类型呈现递增趋势.图3～图6分别将信息不对称情形(即服务提供方无法获知用户的偏好类型)时设计的最优合同与完全信息(服务提供方了解每一个用户的偏好类型)时进行仿真对比.

图3描述的是不同用户偏好类型下用户保护策略模糊法中的模糊等级(策略k的选择)以及最优合同中用户所能获得服务等级.可以发现，当用户对服务等级的偏好程度增强时，用户更愿意付出自己的部分位置隐私，此时模糊等级k的数值越来越小，即用户在上报自身位置时的模糊程度降低，而所能获得的服务等级越来越高.

图4描述的是信息不对称与完全信息两种情形时用户收益与用户偏好类型的关系.从图中发现，完全信息时，用户方的收益始终为0，这是因为此时的服务提供方了解每个用户的偏好，所以设计合同时，为了最大化自身收益，使得每个用户的获得的收益均为0.相反，当LBS用户的偏好类型未知时，用户方可以从隐藏的位置信息中获得非负的收益，从图可知用户对服务水平的偏好类型越高，所能获得的收益也越高，这一结果也正好验证了引理3所给出的结论.图5(见第248页)描述的是服务提供方的收益与用户偏好类型之间的关系，在信息不对称时服务方所获得的收益一直低于完全信息情形.同样，这也是因为用户对服务等级和个人位置隐私的偏好类型未知时，服务提供方在不完全信息下所设计的合同无法达到完全信息情形下的理想收益，导致部分收益损失.

图6见第248页描述的是双方总收益与用户偏好类型的关系，可以发现，本文所设计的信息不对称情形下最优合同的总收益接近完全信息时的总收益.由于完全信息情形下，服务提供方直接为每个用户设计最大化自身收益的合同，使得每个用户收益均为0；而信息不对称情形下，服务提供方只能根据个体理

图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也可验证这一点.因而，从双方总收益角度可以发现，本文利用合同理论为各个偏好类型所设计的最优合同是可行并且有效的.

4 结 语

本文针对LBS系统中服务提供方与用户之间的信息不对称问题，在位置信息挖掘过程中，提出了基于合同理论的差异化服务的算法机制设计.该算法机制提出为每一种偏好类型的用户分别设计各自的最优合同，使得用户方在收益非负的情况下无法通过选择其他类型的合同提高自身收益，从而实现服务提供方和用户方各自收益的最大化.仿真结果表明，当用户对服务水平的偏好上升时，用户愿意共享更多的个人位置隐私以获得更高的服务水平，同时获得的收益也随之提升.可见，本算法机制同时可以激励LBS用户共享更多个人位置隐私.此外，通过比较发现，不对称信息下双方的总收益接近完全信息下的总收益，也验证了算法的可行性和有效性.因此，本文所设计的基于合同理论的差异化服务机制可以有效地解决基于位置服务场景中的用户偏好未知问题，同时对其他研究领域中信息不对称问题也具有一定的参考价值.