Eliciting Information from Heterogeneous Mobile Crowdsourced Workers Without Verification

这篇和Strategic Information Revelation in Crowdsourcing Systems Without Verification是同一批作者的，针对的问题一样，内容方法看着也差不多，希望别一模一样……

Abstract

问题：无验证的信息提取（IEWV）

思路：激励workers高质量和如实报告

常规方法：多数投票——符合多数解决方案的workers获得报酬

存在问题：未考虑workers的异构性

本文方法：两阶段Stackelberg博弈

1. Introduction

本文场景：

1. workers求解准确率异构（即，不同workers以不同概率生成高质量数据）
2. 考虑数据质量与平台成本之间的平衡

本文方法：多数投票机制

需要解决的问题：

1. 给定奖励，多数投票机制下，异构workers会如何行动；
2. workers的异构性如何影响平台的最优奖励设计和均衡；
3. 在提升平台均衡方面，知道workers异构方案准确性有什么价值。

本文的两阶段博弈：

1. 平台决定多数投票机制的奖励等级，目标是最大化收益，该收益考虑了workers解决方案质量和平台总支出之间的均衡；
2. 每个worker选择自己的努力等级和报告策略，目标是最大化自己收益。

本文考虑两种情况：

1. 不完全信息博弈（平台不知道workers的准确率）
2. 完全信息博弈（平台知道workers的准确率）

Key Contributions

1. 分析了IEWV问题中异构workers场景下的平台均衡
2. 分析了多均衡共存的场景
3. 刻画了workers的最优策略
4. 刻画了workers异构性对平台均衡的影响
5. 刻画了得知workers异构性的价值

2. Related Work

Information Elicitation

略

Information Aggregation

略

3. Model

Workers’ Decision Problem

Workers and Task

集合：$N=\{1,2,…,N\}$表示到达平台的workers

待求解问题的答案是二选一，记作$X=\{-1,1\}$

$x\in X$表示该任务的正确答案

$x_i^{estimate}\in X$表示第$i$个worker对任务答案的估计值

$x_i^{estimate}\in X$表示第$i$个worker向平台上报的任务答案

Worker Effort Exertion and Reporting Strategy

workers的任务质量依赖于努力程度，记作$e_i\in \{0,1\}$

workers可通过付出一定代价来努力从而提高任务质量（即准确率）

第$i$个worker的求解方案准确率记作$p_i\in (0.5,1])$

$$P(x_i^{estimate}=x)=\left\{ \begin{matrix} p_i,\ \ &if\ \ e_i=1\ \ with\ \ a\ \ cost\ \ c_i\geq 0, \\ 0.5,\ \ &if\ \ e_i=0. \end{matrix} \right.$$

workers异构性的体现：$N$个workers中有$k$个高质量的求解准确率为$p_h$，和$N-k$个低质量的求解准确率为$p_l$，$0.5<p_l<p_h\leq 1$

workers的上报策略：$v_i=\{1,-1,rd\}$，其中，努力的workers可以选择$\{1,-1\}$分别表示如实报告和谎报；而不努力的workers可以选择$rd$表示以0.5的概率随机上报

$$x_i^{report}= \left\{ \begin{matrix} x_i^{estimate},\ \ &if\ \ v_i=1\\ -x_i^{estimate},\ \ &if\ \ v_i=-1\\ 1\ \ or\ \ -1\ \ with\ \ an\ \ equal\ \ probability,\ \ &if\ \ v_i=rd. \end{matrix} \right.$$

本文不考虑多个workers共谋等情况。

workers的策略记作$s_i=(e_i,v_i)$，属于集合$S_i=\{(0,rd),(1,1),(1,-1)\}$

Internal Reward for Truthful Reports

第$i$个worker如果努力且如实上报，则会得到内在奖励$l_i\geq 0$

反之，谎报会得到内在惩罚$-l_i$

不努力的worker会随机上报，他的内在奖励为0

Consistency Reward for Output Agreement

一致性奖励记作$R\geq 0$

除了第$i$个worker以外，其余workers的多数投票方案记作$x_{-i}^{majority}$

从第$i$个worker的角度来看，多数投票方案是：

$$x_{-i}^{majority}= \left \{ \begin{matrix} 1,\ \ if\ \ \sum_{j\in N,j\neq i}x_j^{report}>0,\\ -1,\ \ if\ \ \sum_{j\in N,j\neq i}x_j^{report}<0,\\ tie,\ \ if\ \ \sum_{j\in N,j\neq i}x_j^{report}=0. \end{matrix} \right.$$

第$i$个worker的上报值与多数投票方案一致或者多数投票方案是tie的情况下，该worker会得到奖励；反之则不会。

第$i$个worker得到奖励R的概率记作$P_i(R,p,s)$，$p=(p_j,\forall j\in N)$，$s=(e,v)$，$e=(e_j,\forall j \in N)$，$v=(v_j,\forall j \in N)$

Worker Payoff Maximization Problem

worker的收益函数：$u_i(R,s)=R*P_i(R,p,s)+v_il_i-e_ic_i$

博弈1：$\Omega_1=(N,S,u)$，其中：

1. $N$：N个workers的集合

2. $S$：第$i$个worker的策略空间为$s_i\in S_i=\{(0,rd),(1,1),(1,-1)\}$。所有workers的策略记作$s=(s_i,\forall i\in N)$，所有workers的可行策略集合记作$S=\prod_{i\in N}S_i$。

   这里应该是集合的笛卡尔积，不过这个表达不太确定是否正确。

3. $u$：向量$u=(u_i,\forall i \in N)$包含了所有workers的收益

该博弈中，给定报酬$R$和其他workers的决策$s_{-i}=(e_{-i},v_{-i})=((e_j,v_j),\forall j \neq i)$，第$i$个worker需要求解下述优化问题。

问题1： 第$i$个worker的收益最大化

$max\ \ u_i(R,s,s_{-i})$

$var.\ \ s_i\in\{(0,rd),(1,1),(1,-1)\}.$

定义1： 纳什均衡：在给定$R$的情况下，如果对于所有$s_i’\in S_i$，和所有$i\in N$，都有$u_i(R,s_i^,s_{-i}^)\geq u_i(R,s_i’,s_{-i}^)$，则认为策略$s^=\prod_{i\in N}s_i^*$构成了博弈$\Omega_1$的一个纳什均衡。

注意：第$i$个worker的策略选择是前面问题1的优化解决方案，是与平台支付报酬$R$和其他worker策略$s_{-i}$相关的函数。

Platform’s Reward Design Problem

Accuracy of Aggregated Estimate

平台根据所有workers的上报值进行多数投票猜测最终的值

$$x_p^{estimate}= \left \{ \begin{matrix} 1,\ &if\ \sum_{i=1}^Nx_i^{report}>0,\\ -1,\ &if\ \sum_{i=1}^Nx_i^{report}<0,\\ 1\ or\ -1\ with\ an\ equal\ probability,\ &if\ \sum_{i=1}^Nx_i^{report}=0. \end{matrix} \right.$$

$P_a(R,p,N)$表示上述公式得到的聚合解决方案是正确的概率

假设：N是基数且$N\geq 4$

Expected Consistency Rewards.

workers总一致性奖励期望记作$E[R^T]$

Platform’s Payoff Maximization Problem

平台收益函数：

$$\prod(R)=\beta P_a(R,p,N)-E[R^T]$$

$\beta>0$表示平台对准确率分配的权重

问题2： 平台的收益最大化：

$max \prod(R)$

$var. R\geq0$

Two-Stage Game

阶段1：平台决定R

阶段2：workers选择努力和上报策略

博弈求解方法：逆向归纳

符号表达：

$X$：任务类型空间

$x$：任务真实类型

$x_i^{estimate}$：第$i$个worker的估计值

$x_i^{report}$：第$i$个worker的上报值

$x_{-i}^{majority}$：除了第$i$个worker以外，剩下workers的多数投票方案

$x_p^{estimate}$：平台的聚合估计值

$s_i\triangleq(e_i,v_i)$：第$i$个worker的策略（努力策略和上报策略）

$c_i$：第$i$个worker的努力成本

$l_i$：第$i$个worker的内部奖励

$p_i$：第$i$个worker努力时的准确率

$R$：平台的一致性奖励

$\beta$：平台对聚合准确率的权重

$E[R^T]$：所有workers一致性奖励的期望

4. Incomplete Information

每个worker的准确率只有自己知道，其他workers和平台都不知道。

Workers’ Decisions at Stage II

Workers’ Heterogeneity

workers异构性的体现：

1. 准确率异构——>$k$个高准确率$p_h$workers，用集合$N_h$表示，$N-k$个低准确率$p_l$，用集合$N_l$表示，$1\leq k\leq N-1,0.5<p_l<p_h\leq 1$，这些参数的数值是公开信息。
2. 努力时的成本和内在奖励/惩罚相同——>$c_i=c,l_i=l,l<c$

Workers’ Equilibrium Behaviors

假设：同类型worker（准确率相同）会选择相同的策略

定义2： 对称纳什均衡（SNE）

1. n-SNE：所有workers都不努力和如实报告
2. f-SNE：所有workers都努力和如实报告
3. p-SNE：高质量workers努力和如实报告，低质量workers则相反

命题1： workers之间的SNE

1. 当$R\geq 0$时一定存在一个n-SNE
2. 存在一个阈值$R_f\geq 0$，当$R\geq R_f$时，一定存在一个f-SNE
3. 当$k\geq k_1$时，存在两个阈值$0<R_p^l\leq R_p^h$，使得在$R_p^l\leq R \leq R_p^h$时，一定存在一个p-SNE

阈值之间的关系取决于$k$的大小：当$k$较小时，$R_f\leq R_p^l$；当$k$较大时，$R_f>R_p^l$。

由命题1可得：

1. 对于任意非负一致性奖励$R$，一定存在一个n-SNE，所有workers都没有动机努力和如实报告；努力worker的收益是$\frac{R}{2}+l-c$，不努力worker的收益是$\frac{R}{2}$，由于$l<c$，显然不努力更好。
2. 当一致性奖励足够大时，存在f-SNE，所有workers都会努力和如实报告。
3. workers准确率的异构性允许我们通过机制来使不同准确率的workers采取不同策略，当一致性准确率在合适范围内时，存在p-SNE使得高准确率workers努力且如实报告，而低准确率workers不努力并随机报告。

各均衡解存在性与参数的关系：

1. $k<k_1:$ 高准确率workers很少时，不存在p-SNE。
2. $k_1\leq k\leq k_2:$ 高准确率workers人数适量时，存在p-SNE，但平台报酬$R$的下限很高（$R_p^l>R_f$）。
3. $k\geq k_2:$ 高准确率workers足够多时，存在p-SNE，且$R_p^l<R_f$。当k很大时，高质量workers在p-SNE得到报酬的概率与在f-SNE得到报酬的概率相近，低质量workers也会被激励选择(1,1)策略。

帕累托最优均衡解：

命题2： 给定一致性奖励$R$，一定存在一个帕累托最优均衡解。

这意味着可以通过调整一致性奖励来引导worker的努力策略和上报策略。

命题3： 策略空间（$s_i^*=(0,rd),\forall i\in N_h,s_j=(1,1),\forall i\in N_l$）不存在均衡解。

这意味着不会出现低质量workers努力而高质量workers随机的场面。对于给定的R，高质量workers有更高的概率拿到奖励。在努力成本不变的前提下，高准确率workers更愿意选择(1,1)的策略。换言之，多数投票方案更能吸引高准确率workers。然而，在完全信息的场景下这一条并不成立。

Platform’s Reward Design at Stage I

$P_f,P_p,P_n:$ workers在三种均衡下的聚合准确率

$E[R_f^T],E[R_p^T],E[R_n^T]:$ 三种均衡下的总期望一致性奖励

$\eta_f,\eta_p,\eta_n:$ 三种均衡下的效率（是指一致性奖励的效率）

效率计算方式：

$\eta_f=\frac{P_f-P_n}{E[R_f^T]}$

$\eta_p=\frac{P_p-P_n}{E[R_p^T]}$

$\eta_n=\frac{P_n-P_n}{E[R_n^T]}=0$

上面这个计算式反过来（也就是$\frac{1}{\eta_f}$）的含义是：对于单位准确率而言，从均衡n-SNE提高到f-SNE所需要支出的平均一致性奖励。$\eta_p$也是类似的含义。

平台的最优决策R：

定理1： 给定任意参数$(\beta,N,c,l,p_l,p_h,k)$，平台可以引导workers达到f-SNE和对应的效率$\eta_f$

1. 如果p-SNE存在，且$\eta_p\geq \eta_f$，平台的最优一致性奖励为：

   $$R^* = \left\{ \begin{matrix} 0,\ &if\ \beta<\frac{1}{\eta_p}, \\ R_p^l,\ &if\ \frac{1}{\eta_p}\leq\beta<\frac{E[R_f^T]-E[R_p^T]}{P_f-P_p}\\ R_f,\ &if\ \beta \geq \frac{E[R_f^T]-E[R_p^T]}{P_f-P_p};\\ \end{matrix} \right.$$

2. 其他情况下的平台最优一致性奖励为：

   $$R^*= \left \{ \begin{matrix} 0,&\ if\ \beta<1/\eta_f,\\ R_f,&\ if\ \beta\geq1/\eta_f. \end{matrix} \right.$$

分析定理1可得：

1. 当p-SNE存在，且效率高于f-SNE，对应图4中的$k>k^{THR}$区域，平台会根据$\beta$来引导均衡从而最大化收益。当$\beta$较小时，由于较低的准确率评价，平台不会提供任何激励，R=0，从而n-SNE是帕累托最优，对应图3中$k>k^{THR}$区域中下面的白色部分。当$\beta$合适时，即图3中的蓝色区域，平台会选择$R=R_p^l$从而得到p-SNE。当$\beta$很大时，即图3中的灰色区域，平台会选择$R=R_f$，得到f-SNE，同时在一致性奖励方面支出很大。
2. 当p-SNE不存在，或其效率低于f-SNE，对应图4中的$k<k^{THR}$区域，类似前面的分析，$\beta$较小时，是n-SNE；反之则是p-SNE。

5. Complete Information: Weighted Aggregation

每个worker的准确率$p_i$是公开信息

Workers’ Decisions

这一步和前面的博弈1、命题1一样。

Platform’s Reward Design

平台使用加权多数规则（weighted majority rule）来决定最终的聚合准确率：

$$x_p^{estimate}= \left\{ \begin{matrix} 1,\ &if\ \sum_{i=1}^Nw_i(p_i,s_i)x_i^{report}>0\\ -1,\ &if\ \sum_{i=1}^Nw_i(p_i,s_i)x_i^{report}<0\\ 1\ or\ -1\ with\ equal\ prob.,\ &if\ \sum_{i=1}^Nw_i(p_i,s_i)x_i^{report}=0 \end{matrix} \right.$$

其中，

$$w_i(p_i,s_i)=log\frac{\rho(p_i,s_i)}{1-\rho(p_i,s_i)}, \\ \rho(p_i,s_i)= \left\{ \begin{matrix} 0.5,\ &if\ s_i=(0,rd), \\ p_i,\ &if\ s_i=(1,1), \\ 1-p_i,\ &if\ s_i=(1,-1). \end{matrix} \right.$$

权重公式既能提高聚合准确率，又会显著影响平台决定的报酬。

第$i$个worker的权重$w_i(p_i,s_i)$由其准确率和策略共同决定，因此：

1. 在f-SNE时（所有workers都选择(1,1)策略），高质量workers有更高权重，高低质量的权重都是正数；
2. 在p-SNE时（高质量workers采取(1,1)而低质量workers采取(0,rd)），高质量workers权重为正数，低质量workers权重为0；
3. 在n-SNE时（所有workers都选择(0,rd)策略），大家权重都是0，平台随机得到最终答案。

数字符号定义如下：

1. $P_f^{wm},P_p^{wm},P_n^{wm}$分别表示在加权多数规则情况下，f-SNE、p-SNE和f-SNE对应的聚合准确率；
2. $\eta_f^{wm},\eta_p^{wm},\eta_n^{wm}$分别表示在加权多数规则情况下，f-SNE、p-SNE和f-SNE对应的效率。

计算方式：

$\eta_f^{wm}=(P_f^{wm}-P_n^{wm})/E[R_f^T]$

$\eta_p^{wm}=(P_p^{wm}-P_n^{wm})/E[R_p^T]$

$\eta_n^{wm}=(P_n^{wm}-P_n^{wm})/E[R_n^T]=0$

workers的均衡解行为和不完全信息一致，每种均衡对应的总一致性奖励（$E[R_f^T],E[R_p^T],E[R_n^T]$）也一致。

命题4： 给定参数$(\beta,N,c,l,p_l,p_h,k)$，如果f-SNE和p-SNE共存，则$P_f^{wm}\geq P_p^{wm}$

证明： 在p-SNE，低准确率workers采取(0,rd)，高准确率workers采取(1,1)，根据计算权重的公式，低质量workers权重为0，高质量workers权重为正数，基于此可计算得到$P_p^{wm}$。在f-SNE，所有workers采取(1,1)，按照p-SNE分配权重是可行的，此时$P_f^{wm}= P_p^{wm}$。由于权重计算公式是最优的，因此可得$P_f^{wm}\geq P_p^{wm}$。

补充：这个证明没看懂，个人对命题4的理解是说，两个均衡解共存时，f-SNE是所有workers都努力并如实报告，p-SNE是只有高质量workers努力并如实报告，显然f-SNE多了低质量workers努力贡献的准确率，因此总的准确率会更高。

由此，可以刻画平台的最优决策，和定理1一样，只有符号表达替换了。

图5是新的均衡图解。蓝色区域更大了，也就是说在完全信息的场景下，平台更可能只让高质量workers努力和正确上报。

定理2： 令$\prod^{inc}$和$\prod^{com}$表示平台在不完全信息和完全信息情况下对应的最优收益。给定参数$(\beta,N,c,l,p_l,p_h,k)$，可得：$\prod^{com}\geq \prod^{inc}$。

6. Complete Information: Discriminatory Reward Policy

第5章中，平台给不同准确率的workers相同的奖励；本章中则采取有差别的奖励策略，即便是和多数一致方案相同，也会因为准确率不同而得到不同的奖励：低准确率得到的奖励是$R_{low}$，高准确率得到的奖励是$R_{high}$。

Workers’ Decisions

命题5：workers的SNE是

1. $R_{low}$和$R_{high}$都大于等于0时，$s_i^*=(0,rd),\forall i$是一个SNE；
2. 存在两个阈值$R_f^l$和$R_f^h$均大于0，使得当$R_{low}\geq R_f^l$且$R_{high}\geq R_f^h$时，$s_i^*=(1,1),\forall i$是一个SNE；
3. 存在两个阈值$R_p^l$和$R_p^h$均大于0，使得当$R_{low}\leq R_p^l$且$R_{high}\geq R_p^h$时，高质量workers采取$(1,1)$而低质量workers采取$(0,rd)$是SNE；
4. 存在两个阈值$R_{pl}^l$和$R_{pl}^h$均大于0，使得当$R_{low}\geq R_{pl}^l$且$R_{high}\leq R_{ph}^h$时，低质量workers采取$(1,1)$而高质量workers采取$(0,rd)$是SNE。

Platform’s Optimal Reward Design

定理3：

1. 使用$\prod_{UP}^{com}$和$\prod_{DP}^{com}$表示平台在均等奖励和差分奖励的情况下的最优支出，则有：$\prod_{DP}^{com}\geq\prod_{UP}^{com}$
2. 存在阈值$\bar{\beta}$，使得当$\beta\geq \bar{\beta}$时，如果UP的最优SNE是n-SNE，且DP的最优SNE不是f-SNE、p-SNE或者pl-SNE，则DP的社会财富比UP高。

定理3说明从平台来看，采取差分奖励策略会带来不比均等奖励策略糟糕的支出和社会财富。DP并不一定会损害社会财富，反而会带来双赢的场面。

7. Numerical Results

分析高质量workers的数量$k$和高质量workers准确率$p_h$对平台与workers收益的影响。

Incomplete Information

Complete Information

8. Conclusion