理性外包计算的博弈论机制*

岳朝跃,田有亮,张铎,王琳杰,王缵

1.贵州大学 数学与统计学院,贵阳 550025

2.贵州大学 公共大数据国家重点实验室,贵阳 550025

3.贵州大学 计算机科学与技术学院,贵阳 550025

1 引言

在当今以数据为中心的世界中,为了提供更优质的服务,许多应用程序会收集大量的用户数据.然而,处理所收集的数据往往是一项非常复杂的任务,这要求处理数据的公司或者个体必须具备强大的计算能力.随着分布式计算和云计算的快速发展,出现了新型的计算模式:分包计算及外包计算.这类计算模式将任务外包给远程服务器使得公司或个体不再受自身计算和存储能力的限制.它已成为云计算时代解决此类问题的主要方案.在外包计算中,面临两个主要问题:一是计算结果的完整性,对用户而言,服务器可能返回一些虚假的计算结果,如作弊计算、猜测结果等;二是计算任务的隐私性,对不可信的第三方,云服务器获取了用户的输入及输出,如何保证用户隐私信息的安全性.

目前,在传统外包计算方案中,为了验证计算结果的完整性、可靠性,已经设计了许多验证机制.但对于传统的外包计算主要是基于计算复杂性理论和基于密码技术构造.基于计算复杂性的外包计算方案构造中主要应用的工具是交互式证明系统[1,2]、PCP定理[3]等.基于密码技术构造的外包计算方案中,使用的密码工具主要有全同态加密[4,5]、同态MAC/签名[6]等.在这些传统的外包计算方案中,用户需要依据服务器的可靠证据对计算结果进行验证.但是,一般验证过程很复杂且通信复杂度较高.同时,传统的外包计算一般都是假设参与者要么是诚实,要么是恶意的行为.然而,在实际生活中,参与者都具有一定的偏好取向.因此,引入理性参与者,通过效用函数来保证服务器计算结果的完整性,构造外包计算博弈模型更具有实际意义和研究价值.

近年来,从理性的视角出发研究理性参与者的外包计算受到越来越多学者的关注.为了确保计算结果的完整性,1999年,Monrose[7]等设计了一个验证方案,要求重新执行部分计算任务.2011年,Canetti[8]等利用多个代理人的冗余来验证外包计算结果,要求至少有一个代理人是诚实的.2014年,Vaidya[9]等设计了一个博弈论框架来改进现有的验证机制,该机制只考虑到服务器的决策模型,没有考虑到用户的策略.Pham[10]等从经济学的角度对外包验证计算进行研究,并建立了确定外包合同价格最优模型,分析了一个和多个服务器的情况,要求服务器完全诚实,但这并不完全符合实际情况.为此,Khouzani[11]等进一步研究了在允许多服务器共谋情况下设计了外包验证方案的最佳设置,该文献也未考虑用户可以容许有一定错误率.2017年,Pejó[12]等设计了一个外包计算博弈论框架,并使外包商的效益最大化,同时确保外包计算的完整性达到所期望满足的完整性水平,要求在检测结果没有错误时强制执行罚款,且罚款为事先给定的常数,这导致不能很好的激励服务器诚实计算,并且要保证计算结果满足用户期望的完整性,用户必须验证该返回的结果.

针对目前研究现状中,惩罚函数设计不足以及服务器返回结果必须要经过本地验证等问题.本文将外包计算与博弈论相结合提出理性外包计算的新模型.在博弈论框架下,分析外包计算中用户和服务器的偏好,提出了外包计算的扩展式博弈,定义了一个新的支付矩阵和效用函数,根据博弈的纳什均衡给出了理性外包计算模型的形式化定义;并通过实验仿真分析了理性外包计算模型中线性函数的选取条件,确保参与者达到纳什均衡时用户不再验证外包计算结果,也可以确保服务器计算的结果满足用户期望的完整性水平.

本文的结构如下:第2节简要介绍博弈论、外包计算扩展式博弈;第3节基于外包计算扩展式博弈,定义一个新的支付矩阵和效用函数;第4节理性外包计算模型的形式化定义;第5节对外包计算博弈模型进行仿真实验与分析;第6节总结全文内容.

2 准备知识

本节概述博弈和扩展式博弈、纳什均衡[13]等基础知识.

2.1 博弈概念

定义1(博弈)博弈表达的基本形式由局中人P、策略空间S和效用函数u三个要素组成,即G={P,S,u},其中P={P1,P2,···,Pn},S={S1,S2,···,Sn},u={u1,u2,···,un}.效用函数ui:S→R(代表实数空间),它表示第i位局中人在不同策略组合下所得到的效益.

2.2 扩展式博弈

一个扩展式博弈(extensive game)是一个五元组(P,Q,p,(Ii)i∈p,(≤i)i∈p),其中,

(1)P代表参与者集合;

(2)Q代表行动序列集合,且满足如下的性质:

若q是有限行动序列即a是一个行动,则q·a记为行动a为q的直接后继行动.如果q∈Q行动是无限的或者它的直接后继行动为Ø,则称其为终端(termianal).由终端序列组成的集合记为Z.对于任意的q∈Q,A(q)={a:q·a∈Q}为q的所有可能后继行动组成的集合.

(3)p是参与者函数,它赋给每一个非终端序列(q∈Q的元素)一个P的元素.

(4)Ii代表参与者i∈P的信息集,它表示参与者进行选择时所知道的信息.

(5)≤i代表参与者的偏好关系:对于每一个i∈P有一个Z上的偏序关系.

扩展博弈的解释如下:每一个Q中行动序列代表博弈的可能历史.空序列Ø代表博弈的开始节点.当达到任何非终端行动序列q∈Q后,参与者p(q)从A(q)中选择行动a,从而序列q被行动a扩展,此时博弈的历史变成q·a.终端集合Z代表博弈所有可能的结果(outcome).若q,q′∈Z和q≤i q′,则参与者i∈P更偏向于q′.参与者的偏序关系依其效用函数而定:一个实向量y(q)=(yi(q))i∈P被赋值到每一个终端序列下,并有任意q,q′∈Z和i∈P,q≤i q′,当且仅当y(q)≤i y(q′).

通常来说,一个扩展博弈可以看成一棵博弈树,博弈树的边和节点分别对应博弈行动和行动序列.空序列Ø代表该树的根.博弈始于空序列及终于终端节点(也称树叶).参与者p(q)从A(q)中选择行动,从而序列q被行动a扩展,此时博弈的历史变成q·a.当一个行动序列达到终端节点时,则博弈结束.终端节点(叶子)用收益向量标识以代表参与者之间的偏好关系.

2.3 纳什均衡

定义2(纳什均衡)一个策略组合s∗=()是博弈G={P,S,u}的一个纳什均衡,如果对于每一个局中人Pi(i=1,···,n),对于所有的sj∈Si,不等式都成立.

直观理解,如果每一个参与者i/=j遵从策略,则参与者j也不会背离,因为它背离该策略得不到任何好处.一般情况下,一个博弈可能存在多个纳什均衡.

3 外包计算博弈模型

3.1 模型参数

本文中使用的模型参数如表1所示.

表1 本文所使用的参数Table 1 Parameters used in this study

假设用户拥有计算任务A和计算函数f(·).计算任务A的价值为B.用户将计算任务外包给服务器,服务器诚实计算该任务的成本为M.计算输出的结果为0＜K∈Z,这些输出结果由用户单独验证,如在推荐算法[14,15]中,这K个结果表示服务器为用户最终预测的结果.从博弈论的观点来看,理性外包计算实际上用户和服务器之间的博弈.将这问题转化为模型化,用户的一方希望不需要验证就可以保证计算结果满足用户期望的完整性,而服务器一方希望通过诚实计算获得更大的奖励或者节约成本以来实现自己利益最大化.由于用户和服务器之间处于信息不对称状态,用户无法对服务器的行为进行监管和控制,也无法观测到服务器的作弊程度.基于此我们分别考虑用户和服务器的验证策略a和作弊策略b,假设a,b为输出K个结果的百分比,记为

简单来看,可以将理性外包计算模型分成两部分,即用户和服务器.建立外包计算博弈机制的目的就是保证外包计算结果的完整性和可靠性,同时及时检测服务器的作弊情况,并将服务器的作弊率降到最低.这一过程中可能会出现以下的情况,服务器作弊了,但是用户未检测到P0,我们称为检测率.反之为检测到作弊的概率记为P1,下面我们在方程式(1)分别定义了用户没有检测到服务器作弊的概率P0(a,b)和检测到作弊的概率P1(a,b)为:

在外包计算任务中保证计算结果正确性和可靠性是“没有免费的午餐”,我们必须付出一定的“代价”而得到相应的安全计算服务.对于用户来说,有些不重要的计算任务容许有一定作弊计算,设该容忍度为用户的容忍率θ.为保证计算质量,用户需要给予适当的报酬来激励服务器诚实计算.设用户给服务器的支付费用为W(b),其中W(b)是关于b的线性单调减函数;同时为了保证计算结果的正确性、可靠性.用户可能选取部分结果在本地执行验证,这里的验证是指用户重新计算,验证的成本V(a)为是关于a线性增函数,且满足V(0)=0,V(1)=M.为了保证用户愿意外包计算任务,假设B-V(a)-W(b)≥0.否则就会失去外包计算的意义.对于服务器而言,它可能通过节约成本或者诚实计算获得的奖励来增加自己的收益.我们设置了一个惩罚机制,以防止服务器有作弊的动机.假设F(b)是用户在验证返回的结果中发生作弊时对服务器的惩罚,其中罚款是关于服务器作弊概率b的增函数.如果合同本身没有约束力,这种罚款可以通过引入第三方来强制执行.

服务器作弊计算,对于用户来说就会存在一定的损失,我们称为用户的损失因子.如果作弊被捕获到,我们设捕获到作弊时对用户利益的损失设为km(b),即用户此时的利益为B-km(b);如果作弊未被捕获到时对用户利益的损失设为λm(b),即用户此时的利益为B-λm(b),其中λm(b)和km(b)都是关于b的线性单调增函数,且满足km(0)=λm(0)=0,λm(1)≥km(1)≥m,即没有作弊就没有损失;完全作弊(b=1)的损失至少是用户的纯收入m,同时这里还必须满足:对于任意的b∈[0,1],有km(b)≤λm(b),如果未捕获到作弊的损失因子λm(b)小于捕获到作弊的损失因子km(b),即是“无知就是幸福”,这是不切实际的.

3.2 参与者偏好

在理性外包计算中,参与者存在差异性和特殊性,因此必须遵守自身效益最大化这一原则.服务器诚实计算时,用户收益最大,即服务器不作弊时的收益高于欺骗时的收益.此时,用户的效用函数满足如下不等式:

同时,服务器也期望自己的收益最大.而服务器的收益来源于诚实计算时用户给予的支付及节约的成本.因此,服务器作弊的概率不超过用户的容忍率.即作弊概率为容忍率θ时的收益超过作弊概率∀b≥θ的收益.此时,服务器的效用函数满足如下不等式:

3.3 博弈模型设计

两方或者多方之间的外包计算可以看作是两方或多方实体间并遵守一定规则的交互计算集合,在外包计算过程中,为了达到某种计算目的(如计算结果完整性、可靠性),他们必须一次或者多次遵守所规定的交互规则,若有实体违背这些规则,最终导致外包计算的目的失败.我们把这样的一个交互过程看成是一个扩展式博弈,如图1所示:

图1 外包计算的扩展式博弈Figure 1 Expansive game of outsourcing computing

在图1中,顶点的实心圆代表初始历史,即博弈的起始点.用户首先行动,其边的标记是该行动的名称.即开始用户的行动就是外包(O)计算任务或者不外包(No)计算任务,其后服务器的行动为拒绝(¬R)或者接受(R)该外包任务,b表示服务器作弊的概率,a表示用户验证概率.其叶子端点代表收益向量.

我们分别把m,θ,B,C和km(b),λm(b),W(b),F(b)看作预先约定常数和函数,只有验证率a和作弊率b当作变量.同时,用户和服务器都是自私的非合作参与者,且它们都是风险中性的,即它们在期望效用和期望值的效用之间没有严格偏好.根据外包计算的扩展式博弈,我们把用户和服务器的效用函数看成是花费成本和收益的线性函数.并定义了一个新的支付矩阵,结果和收益如表2所示:

表2 支付矩阵Table 2 Payoffmatrix

根据以上支付矩阵,定义参与者的效用函数如下:

用户检测到作弊时的期望收益是:

用户没有检测到作弊时的期望收益是:

用户总的期望收益是:

服务器被检测作弊时的期望收益是:

服务器没有被检测作弊时的期望收益是:

服务器总的期望收益是:

4 理性外包计算的形式化定义

本节基于博弈的纳什均衡给出理性外包计算的形式化定义.一个两方的理性外包计算的过程可以看成是一些交互规则的集合,我们认为外包计算结果的完整性与各参与方的效用函数相关.各理性参与者为了获得最佳收益就必须遵守这些规则,任何违背这些规则的参与者都会获得较差的收益.这就和博弈论中纳什均衡的概念是类似的.我们将据此先给出理性外包计算模型的形式化定义.

假设T={(A1,f1(·)),(A2,f2(·)),···}是用户外包任务集合,其中每一个(Ai,fi(·))我们解释如下:Ai代表用户的计算任务,f(·)代表外包任务的计算函数.我们将依据纳什均衡来构造理性外包计算的交互博弈规则.

定义3(理性外包计算形式化定义)设T={(A1,f1(·)),(A2,f2(·)),···}是用户的外包任务集合,用户需要将该计算任务和计算函数外包给服务器,该外包计算的博弈记为(T),其中C代表用户,S代表服务器,a表示用户的验证概率,b表示服务器的作弊概率,T的计算结果是完整的当且仅当:

(1)()是博弈(T)的纳什均衡,且策略组合()产生的结果为o=(a,b),且a和b是使参与者收益取得最大值时相对应的策略;

(2)对该博弈的任何纳什均衡(s1,s2),都有ui(s1,s2)≤ui(),即()是纳什均衡集中最佳的纳什均衡集.

下面证明如下的事实: 产生结果o=(a,b)的策略组合集合是外包计算博弈模型的纳什均衡集; 该集合是最佳的纳什均衡集,即上述条件(2)成立.

5 模型仿真与分析

基于以上的外包计算的扩展式博弈,根据纳什均衡条件,通过实验仿真与分析理性外包计算模型的最佳线性函数的选取.首先在保证理性外包计算激励相容的前提条件下固定线性函V(a),W(b)数值,通过改变惩罚函数分析各参与者效用函数问题;其次,选取最佳的惩罚函数,同样固定W(b),分析验证成本对效用函数的变化情况,最后,通过分析得出最佳的V(a),F(b),进一步分析支付成本对参与者效用函数的影响.为通过实验仿真选取最佳的线性参数,下面我们做如下的假设:

假设计算输出的结果K=10000,B=3,M=1,这三个值都是用户和服务器共同的知识.又设km(b)=(1+m)b,λm(b)=2(1+m)b,用户容许服务器作弊的阈值θ=0.01,W(b)=k-b.1≤k≤3,k为常数,V(a)=ha(h＞0,h为常数)和惩罚F(b)=lb(l为常数).下面通过模型仿真与分析选取V(a),W(b),F(b)这三个线性函数最佳参数设置.

5.1 惩罚与效用函数的关系

定理1在上述的假设下,设W(b)=2.8-b,V(a)=如果惩罚函数F(b)=lb(l为一个常数),若l≥10000时,则该理性外包计算模型存在纳什均衡点,并且达到纳什均衡点时外包计算结果是完整.

证明:如图2所示,纵坐标表示效用值,横坐标表示为惩罚函数的系数l,加菱形的线条表示用户的收益,加星形的线条表示服务器的收益.从图像容易看出,随着l的增大,用户的效用函数没有变化,即用户没有偏好的动机,也就是说用户收益达到最大.从表3易得出,用户收益最大化时纳什均衡点的验证策略a=0;对服务器来说,当0＜l≤10000时,随着l的增大,服务器收益逐渐增大,它仍需要改变策略来最大化自己的收益.当l≥10000时,服务器的收益不再发生变化,即服务器改变自己的策略不会增加自己的收益.故服务器的收益已达到最大化,并且由表4可知,服务器收益最大时的最佳策略为b=0.综上所述,当l≥10000时,参与方的收益达到纳什均衡,且收益最大化的纳什均衡点是用户的验证率a=0,服务器的作弊率b=0,故外包结果是完整的.

表3 l与效用函数uC的关系Table 3 Relationship between l and utility function uC

表4 l与效用函数uS的关系Table 4 Relationship between l and utility function uS

图2 l效用函数u的关系Figure 2 Relationship between l and utility function u

推论1在上述的假设下,如果惩罚函数F(b)=c(c为常数),若c＞10000时,则该理性外包模型存在纳什均衡点,并且达到纳什均衡点时外包计算结果是正确的.

5.2 验证成本与效用函数的关系

定理2在上述的假设下,设惩罚函数F(b)=10001b,W(b)=2.8-b,假设V(a)=ha(0＜h≤1的常数),若0＜h≤时,则该外包计算博弈模型存在纳什均衡,且达到纳什均衡时服务器计算的结果满足用户期望满足的水平.

证明:如图3所示,纵坐标表示效用值,横坐标表示为验证成本函数的系数h,加菱形的线条表示用户的收益,加星形的线条表示服务器的收益.从图像易看出,用户的效用随着h的增大而减小.故易得出当0＜h≤时,此时用户的收益达到最大值,也就是说用户收益达到纳什均衡,由表5可知达到纳什均衡时用户最佳验证策略为a=0.同时,服务器的收益也随着h的增大而减小,当0＜h≤,服务器的收益达到纳什均衡.即h的取值满足h∈(0,)时,服务器选择的策略为最佳策略.由表6易得,服务器收益达到纳什均衡时服务器作弊策略b=0.01.由我们的假设用户容忍的阈值为θ=0.01,服务器的作弊率b=0.01≤θ=0.01,故参与者收益达到纳什均衡时时服务器计算的结果满足用户期望满足的水平.

表5 h与效用函数uC的关系Table 5 Relationship between h and utility function uC

5.3 支付与效用函数的关系

定理3在上述假设下,设惩罚函数和验证成本分别为F(b)=10 001b,V(a)=,用户的支付函数为W(b)=k-b(1≤k＜3的常数),若当1≤k＜2时,则该外包计算博弈模型达到纳什均衡,且达到纳什均衡时服务器计算的结果是正确的.

表6 h与效用函数uS的关系Table 6 Relationship between h and utility function uS

图3 h与效用函数u的关系Figure 3 Relationship between h and utility function u

证明:如图4所示,该图的纵坐标表示效用值,横坐标表示为变化常数k,加菱形的线条表示用户的收益,加星形的线条表示服务器的收益.从图像易看出,用户的效用随着的增大而减小.当k=1时,用户的收益达到最大值,即用户收益达到纳什均衡,由表7(选取纳什均衡点附近的点)可知达到纳什均衡时用户最佳验证策略为a=0.对于服务器来说,它的收益也随着h的增大而减小,当k=1,服务器的收益也达到纳什均衡.由表8(选取纳什均衡点附近的点)易得,服务器收益达到纳什均衡时的服务器的作弊策略b=0.故参与者收益达到纳什均衡时服务器计算的结果是正确的.

表7 k与效用函数uC的关系Table 7 Relationship between k and utility function uC

表8 k与效用函数uS的关系Table 8 Relationship between k and utility function uS

由定理1可以得出,当惩罚足够大的时候,服务器就没有欺骗的动机.从图3、4仿真实验分析可知,只要惩罚很高的时候,服务器只要接受外包任务,就可以保证服务器诚实计算外包计算的任务,同时,用户也不用验证.故在该模型下外包计算结果是完整的.本文设计的模型不仅为用户提供了一种预算设置,而且还能够最大限度减少外包商的费用.

图4 k与效用函数u的关系Figure 4 Relationship between k and utility function u

6 总结

如今,将计算任务外包给云服务提供商是非常普遍的做法.保证这些计算结果的正确性通常由验证机制来完成.本文首先分析了理性外包计算中参与者的偏好;其次,根据博弈论的框架提出了一个理性外包计算扩展式博弈,并定义一个新的支付矩阵和效用函数;最后,通过设置效用函数中参数的最佳选择条件,确保参与者达到纳什均衡时用户不需要验证外包计算结果,也可以确保服务器诚实计算.这就大大减少验证成本和通信复杂度.该模型还最大限度地减少了用户的费用.

本文中预先约定的函数都是假设为线性的,这种假设在现实中可能较为特殊,如用户验证成本有可能随着外包数据集的类型及外包算法等因素的影响可能是一个非线性的函数.这种假设是文章的不足之处.因此,在未来研究中可以对预先确定的函数一般化,也可以通过引入声誉系统来构造外包计算的博弈模型.