MENU

VLDB 22 Privacy-preserving Cooperative Online Matching over Spatial Crowdsourcing Platforms

• February 24, 2023 • Read: 3818 • VLDB

摘要

本文提出了一种名为隐私保护的协作在线匹配(Privacy-preserving Cooperative Online Matching(PCOM))的框架,可以保护用户和工人在各自平台上的隐,并基于两种不同的隐私保护策略提出了两种不同的 PCOM 算法。

The matching results in different Spatial Crowdsourcing Problems

本文主要贡献如下:

  • 制定了 PCOM,并提出了 PCOM 框架,在考虑敏感数据隐私的情况下将各平台收益最大化
  • 证明了 PCOM 框架满足差分隐私性质,并提出了两种求解 PCOM 的算法
    • 基于平台历史数据对请求的收益进行定价
    • 综合考虑收益和请求被接受的概率进行定价
  • 在真实和合成数据集上验证了算法的有效和高效性

问题说明

问题定义

  • 请求(Request)
    一个空间众包平台上的请求 $ r $ 定义如下:$ r = \langle t_r, l_r, d_r, \nu_r \rangle $,其中 $ t_r $ 为请求发出的时间,$ l_r $ 是在二维地图上请求发出的地点,$ d_r $ 是完成请求所需要的距离,$ \nu_r $ 是完成请求可以获得的收益

  • 工人(Worker)
    一个空间众包平台上的工人 $ w $ 定义如下:$ w = \langle t_w, l_w, rad_w \rangle $,其中 $ t_w $ 为工人出现的时间,$ l_w $ 为在二维地图上工人出现的地点,$ rad_w $ 为二维空间上工人服务的半径

  • 本地/合作平台(Local/Cooperative Platform)
    一个平台的描述如下:$ p = \langle R, W \rangle $,其中 $ R $ 是平台 $ p $ 上请求的集合,$ W $ 是在平台 $ p $ 上注册的工人集合。对于一个给定的请求 $ r $,请求发出的平台称为请求 $ r $ 的本地平台(Local Platform),相反,合作平台(Cooperative Platform)是合作中除了本地平台以外的任意平台。在本地平台上的工人称为本地工人(local worker),记为 $ w_{loc} $,在合作平台上的工人称为合作工人(cooperative worker),记为 $ w_{cop} $

  • 对外支付(Outer Payment)
    当一个合作工人需要服务一个请求 $ r $,他想获得一笔报酬 $ \nu_r^\prime \in (0, \nu_r] $,其中 $ \nu_r^\prime $ 称为对外支付

  • 收入(Revenue)
    当请求 $ r $ 由本地工人服务时,平台将收到 $ \nu_r $ 的报酬,当请求 $ r $ 由合作工人服务时,平台将收到 $ \nu_{r_i} - \nu_{r_i}^\prime $ 的报酬。假设有一个可行匹配 $ M $,$ M_{loc} $ 为满足本地工人服务的匹配,$ M_{cop} $ 为满足合作工人服务的匹配,则平台的总收入定义如下:
    $$ \operatorname{Rev}=\sum_{i=1}^{\left|M_{l o c}\right|} v_{r_i}+\sum_{i=1}^{\left|M_{c o p}\right|}\left(v_{r_i}-v_{r_i}^{\prime}\right) $$

  • 隐私保护协作在线匹配(Privacy-preserving Cooperative Online Matching)(PCOM)
    给定一组愿意参与合作的空间众包平台 $ P $,每个平台 $ p \in P $ 包含请求和工人,工人和请求依次出现。
    PCOM 将为每个平台找到一个受益 $ Re\nu $ 最大的匹配结果 $ M $,并且满足以下约束:

    • 时间约束:一个请求只能由发出之前就存在的工人来完成
    • 1对1约束:一个请求同时只能由一个工人进行服务,反之亦然
    • 不变约束:一旦某个工人被分配到某个请求,则该分配不可被更改或取消
    • 范围约束:一个工人只能服务位置在服务半径内的请求
    • 隐私约束:实时数据隐私(请求精确位置不应泄露给平台)和历史数据隐私(用户请求的出现、结束位置和时间不应泄露给合作平台)

评价准则

  • 差分隐私(Differential Privacy)

  • 地理不可分(Geo-indistinguishability)
    假设 $ \mathcal{X} $ 是一个精确位置的集合,给定一个随机算法 $ A $,$ Range(A) $ 是可能报告的输出的集合,当对所有的 $ x, x^\prime \in \mathcal{X} $,$ z \in Range(A) $,$ d(x, x^\prime) \leq r $,有
    $$ \operatorname{Pr}[A(x)=z] \leq e^{\varepsilon d\left(x, x^{\prime}\right)} \operatorname{Pr}\left[A\left(x^{\prime}\right)=z\right] $$
    则称 $ A $ 是 $ (\epsilon, r) - Geo-indistinguishability $
    Geo-I 使得具有相同输出的两个输入位置不可取分

PCOM 问题框架

当一个请求 $ r $ 出现在本地平台 $ p_{loc} $ 后,$ p_{loc} $ 基于 $ r $ 的位置确定是否有本地工人。如果有,则通过如 TOTA 和 FTOA 这样的分配算法为请求分配一个合适的工人;如果没有,则进入协作处理,如下图:

The Cooperative Process in PCOM Framework

协作处理有如下5个步骤:

  1. 为了保证隐私,本地平台(Platform A)根据 Geo-I 机制对 $ r $ 的位置进行扰动并将扰动后的请求发送给所有协作平台(Platform B, C)
  2. 每个协作平台根据请求 $ r $ 的位置和上面提到的约束条件寻找可用工人。有可用工人的平台将通过 $ \epsilon_2 - DP $ 估计 $ r $ 的对外支付(Outer Payment)$ \nu_r^\prime $,并将其发送给本地平台
  3. 当收到所有合作平台返回的外部支付后,选择 $ \nu_r^\prime $ 最小的一个进行合作(Platform B)
  4. 被选择的合作平台根据可用的合作工人的接受概率来选择要服务 $ r $ 的工人,接受概率可通过【ICDE 2020 Real Time Cross Online Matching in Spatial Crowdsourcing】中的方法进行计算,假设合作平台会告知它的工人此请求来自外部平台,合作工人有权拒绝服务
  5. 一旦有愿意服务 $ r $ 的合作工人出现,本地平台以精准位置释放 $ r $,随后合作工作者可验证 $ r $ 是否满足范围约束,如果满足,则服务 $ r $ ,否则拒绝 $ r $。如果成功服务,合作平台将收到 $ \nu_r^\prime $,本地平台将收到 $ \nu_r - \nu_r^\prime $

该框架被证明为符合 $ \left(\left(\epsilon_1+\epsilon_2\right) * \max _{p \in P}\left|p_W\right|\right)-DP $,其中 $ \left|p_W\right| $ 为平台 $ p $ 的工人个数

Direct PCOM(D-PCOM)算法

D-PCOM 算法使用贪婪方式来解决 PCOM 问题。为了最大化本地平台收益,D-PCOM 算法会将请求优先发送给本地工人。算法描述如下:

2023-02-23T10:58:26.png

2023-02-24T07:14:17.png

D-PCOM 也有两个缺点:

  1. 可能会分配过多的本地工人来执行价值较小的请求
  2. 在处理外部支付的过程中,D-PCOM 考虑了平台上所有工人的历史请求,但是忽略了可用工人对请求的偏好,因此对于全局计算的 $ \nu_r^\prime $,在一些单价较高的地区,可用工人接受请求的概率较小,在一些单价较低的地区可能出现 $ \nu_r^\prime > \nu_r $ 导致请求被拒绝

Selectable PCOM(S-PCOM)算法

为了克服 D-PCOM 的第一个缺点,S-PCOM 通过一个随机阈值来过滤请求,收入大于阈值的请求将基于本地匹配进行分配,小于的将基于合作匹配进行分配

为了克服 D-PCOM 的第二个缺点,在合作匹配过程中,S-PCOM 首先根据扰动过的地理位置寻找可用合作工人,并基于计算可用合作工人的接受概率计外部支付。合作平台的外部支付越高,则被本地平台选择的概率就越小。工人 $ w $ 的外部支付期望为
$$ \mathbb{E}\left(v_i, w\right)=v_i *\left(1-\operatorname{Pr}\left(v_i, w\right)\right) $$
其中 $ \operatorname{Pr}\left(v_i, w\right) $ 为 $ w $ 想要以外部支付 $ w $ 来服务请求的概率。

S-PCOM 算法描述如下:

The S-PCOM Algorithm

Optimal Pricing Algorithm

实验评估

Real Datasets

上图为实验中用到的真实数据集,其中 $ R $ 为请求数,$ W $ 为工人数,$ rad $ 为工人的服务半径

Synthetic Datasets

上图为实验用到的合成数据集,随即从其他日期选择 500-50k 个请求和 100-10k 个工人,组成一个包含 1000-1000k 个请求和 200-20k 个工人的数据集。

本章将 D-PCOM,S-PCOM,没有合作的匹配算法 TOTA 和最新的 RamCOM 进行了对比

experiment result

  • 总收入
    两种 PCOM 算法均增加了每日平均收入
  • 服务请求数
    D-PCOM 算法服务的请求数最大,因为它将每个可能的请求都分配给本地工人,而 S-PCOM 的请求数虽然小于 D-PCOM,但是其收入却高于 D-PCOM,因为 S-PCOM 偏向于更高价值的请求
  • 合作请求数
    因为 D-PCOM 算法优先考虑本地匹配,所以合作请求数小于 S-PCOM 算法,而 S-PCOM 算法又因为位置扰动导致合作请求数小于 RamCOM
  • 接收率
    D-PCOM 的接收率比 S-PCOM 小,这代表 S-PCOM 考虑工人偏好的策略是有效果的

Scalability of Privacy-preserving Cooperative Online Matching Algorithms

上图是一些关于算法可扩展性的实验结果

实验结果表明位置的隐私水平对两种 PCOM 算法匹配的准确性和完整性有直接的影响,而定价的隐私水平影响不大。当合理选择隐私预算($ \epsilon = 0.7 $)时,S-PCOM 的表现和最优合作匹配算法相当。

相关工作

  • 空间众包匹配
  • 激励机制问题
  • 空间众包中的隐私保护任务分配

参考文献