摘要
本文提出了一种名为隐私保护的协作在线匹配（Privacy-preserving Cooperative Online Matching(PCOM)）的框架，可以保护用户和工人在各自平台上的隐，并基于两种不同的隐私保护策略提出了两种不同的 PCOM 算法。
本文主要贡献如下：
- 制定了 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 这样的分配算法为请求分配一个合适的工人；如果没有，则进入协作处理，如下图：
协作处理有如下5个步骤：
- 为了保证隐私，本地平台（Platform A）根据 Geo-I 机制对 $ r $ 的位置进行扰动并将扰动后的请求发送给所有协作平台（Platform B, C）
- 每个协作平台根据请求 $ r $ 的位置和上面提到的约束条件寻找可用工人。有可用工人的平台将通过 $ \epsilon_2 - DP $ 估计 $ r $ 的对外支付（Outer Payment）$ \nu_r^\prime $，并将其发送给本地平台
- 当收到所有合作平台返回的外部支付后，选择 $ \nu_r^\prime $ 最小的一个进行合作（Platform B）
- 被选择的合作平台根据可用的合作工人的接受概率来选择要服务 $ r $ 的工人，接受概率可通过【ICDE 2020 Real Time Cross Online Matching in Spatial Crowdsourcing】中的方法进行计算，假设合作平台会告知它的工人此请求来自外部平台，合作工人有权拒绝服务
- 一旦有愿意服务 $ 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 算法会将请求优先发送给本地工人。算法描述如下：
D-PCOM 也有两个缺点：
- 可能会分配过多的本地工人来执行价值较小的请求
- 在处理外部支付的过程中，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 算法描述如下：
实验评估
上图为实验中用到的真实数据集，其中 $ R $ 为请求数，$ W $ 为工人数，$ rad $ 为工人的服务半径
上图为实验用到的合成数据集，随即从其他日期选择 500-50k 个请求和 100-10k 个工人，组成一个包含 1000-1000k 个请求和 200-20k 个工人的数据集。
本章将 D-PCOM，S-PCOM，没有合作的匹配算法 TOTA 和最新的 RamCOM 进行了对比
- 总收入
两种 PCOM 算法均增加了每日平均收入 - 服务请求数
D-PCOM 算法服务的请求数最大，因为它将每个可能的请求都分配给本地工人，而 S-PCOM 的请求数虽然小于 D-PCOM，但是其收入却高于 D-PCOM，因为 S-PCOM 偏向于更高价值的请求 - 合作请求数
因为 D-PCOM 算法优先考虑本地匹配，所以合作请求数小于 S-PCOM 算法，而 S-PCOM 算法又因为位置扰动导致合作请求数小于 RamCOM - 接收率
D-PCOM 的接收率比 S-PCOM 小，这代表 S-PCOM 考虑工人偏好的策略是有效果的
上图是一些关于算法可扩展性的实验结果
实验结果表明位置的隐私水平对两种 PCOM 算法匹配的准确性和完整性有直接的影响，而定价的隐私水平影响不大。当合理选择隐私预算（$ \epsilon = 0.7 $）时，S-PCOM 的表现和最优合作匹配算法相当。
相关工作
- 空间众包匹配
- 激励机制问题
- 空间众包中的隐私保护任务分配