（信号与信息处理专业论文）vcg机制在多传感器数据融合中的应用研究.pdf

摘要 机制设计是微观经济学和博弈论中的一个子领域，如今在计算机和通信系统 已显现重要应用。v c g 机制是其中最重要的机制设计之一，在多个领域都有广泛 的应用，其中一个比较重要的应用领域就是多传感器的数据融合。在本文研究的 智能传感器网络中，每个传感器都属于一个代理且每个代理都是理性的参与人。 由于传统的v c g 机制只适用于估价函数相互独立的情况，即传感器之间的信息相 互独立，代理的估价函数只与自己的传感器对目标的估计协方差相关。而在许多 实际情况中，传感器之间的观测信息都具有相关性，这使得代理之间的估价函数 存在相依性。因此本文分析了一种相依估价的v c g 机制，它能够在估价函数相关 联的情况下，计算出一种使得整个传感器系统的利益达到最大的信息分配方式。 同时本文优化了这种相依估价的v c g 机制，使其满足贝叶斯激励相容性。另外， 虽然卡尔曼滤波融合技术在数据融合中已经得到了广泛的应用，但是当传感器之 间的观测信息存在相关性且相关性的大小未知时，卡尔曼滤波并不能为代理提供 有效的估价函数。所以本文分析了另一种信息融合算法一相交协方差算法( 简称 c i 算法) ，它虽然不能确定估价函数的大小，但是可以为代理提供估价函数的 一致估计值，满足一致估计性。 本文针对这两个方面进行深入研究，主要内容和成果如下： ( 1 ) 本文分析了机制设计的基本原理，讨论了机制设计的发展，以及制设计 的计算模型和三个重要的特性，并且分析了v c g 机制以及v c g 机制的拍卖过程。 由于传统的v c g 机制只适用于代理之间的估价函数相互独立的情况，所以当 估价函数存在相依性时传统的v c g 机制会失效，即代理可能会谎报自己的估价 值。因此本文分析了一种相依估价的v c g 机制，它能够在估价函数存在相依性时 保证代理真实报价，并最大化整个系统的效益。同时本文优化了这种v c g 机制， 使其满足贝叶斯激励相容性，它在保证代理真实报告自己的类型时有效地降低了 代理为接收到的信息所需要付的费用。 ( 2 ) 本文分析了传感器数据融合的基本原理，讨论了多传感器信息融合模 型。并且分析了数据融合中最重要的融合技术一卡尔曼滤波，包括卡尔曼滤波的 基本算法、性质，以及基于卡尔曼的融合模型。 摘要 由于本文研究的是信息相互关联的情况，而分布式卡尔曼滤波只适用于信息 相互独立的情况，所以本文分析了一种能够适用于传感器信息具有相关性且相关 性大小未知情况的相交协方差算妣i 算法，并对卡尔曼滤波和c i 算法做了仿 真比较，验证了c i 算法满足一致估计性，证明c i 算法更适用于信息相关的情况。 ( 3 ) 本文主要研究的是优化的相依估价v c g 机制在多传感器数据融合中的 运用，并用j a v a 程序模拟了一个分布式数据融合的系统。在这个系统里有多个 传感器，且每个传感器都属于一个代理，每个代理需要确定一些动态目标的位置； 同时限定通信的带宽，使得传感器必须在有限的带宽内建立通信信道，融合相互 的信息；系统的目的就是在有限的带宽内最大程度地精确这些动态目标的位置。 由于加进去的噪声干扰是随机相关的，所以每个传感器的观测信息都存在一定的 相关性。因此，本文把优化的相依估价v c g 机制应用到这种分布式数据融合的系 统中，并用c i 算法给出代理对目标的估价值的一致估计。仿真结果证明优化的 相依估价v c g 机制能够计算出保证系统利益最大化的一种信道分配方式，即使得 通信带宽得到最优化的利用的同时最大程度地精确目标的位置，并验证了优化后 的v c g 机制能够满足贝叶斯激励相容性，有效地降低了代理为接收到的信息所需 要付的费用。 关键词：机制设计v c g 机制多传感器数据融合分布式卡尔曼滤波c i 算法相依 估价的v c g 机制 i i 硕士学位论文 a b s t r a c t m e c h 锄i s md e s i 朗i st l l eb r 趾c hf i e l d so fm i c r o e c o n o m i c s 锄dg a m et l l e o 巧，n o w t l l e ya r es h o w e di i i l p o r t a n ta p p l i c a t i o n st oc o m p u t e r 锄dc o m m u n i c a t i o ns y s t e m s v c gm e c h 锄i s mi so n eo ft h em o s th n p o r t 锄tm e c h 觚i s md e s i 朗s ，s oi th a daw i d e l y u s e di 1 1m a n yf i e l d s o n e0 fm em o r ei m p o n a n tf i e l d si st h em u l t i - s e n s o rd a t a 如s i o n i l lm es e n s o rn e t 、) i r o r k ，e a c hs e n s o rb e l o n g st oa na g e n t 锄de a c ha g e n ti sam t i o n a l p a n i c i p a t i o n t r a d i t i o n a lv c gm e c h 锄i s mc 锄b eo n l ya d 印t e dt 0t h e s i t u a t i o no f i 1 1 d e p e n d e n tv a l u a t i o nm n c t i o n t h a ti s ，t l l ev a l u a t i o n 劬c t i o nb e t w e e na g e n t si s i i l d e p e n d e n t ，觚dv a l u a t i o n 劬c t i o n0 fa g e n t so n l yc o n e l a t e sw i le s t i m a t ec o v a r i 锄c e o fg o a l so b s e r v e db yh i ss e n s o r h o w e v e r ，i l lm a n yp m c t i c a ls i t u a t i o n s ，i n f o m l a t i o n b e t 、) l e e nn l es e n s o r si s r e l e v a n t ，w h i c hm a l ( et l l e v a l u a t i o nf u n c t i o no fa g e n t s i i l f l u e n c ee a c ho t h e r s ot l l i sp 印e ra n a l y z e dav c gm e c h a n i s mo fi i l t e r d e p e n d e n t v a l u a t i o n ，w h i c hc 锄c o m p u t ead i s 仃i b u t i o nm e 弱u r et l l a tc 锄m a x i n l i z et h eb e n e f i to f l ew h o l es e n s o 娼s y s t e m h la d d i t i 吼，t h i sp 印e ro p t i l l l i z e dm ev c gm e c h 孤i s mo f i i l t e r d e p e n d e n tv a l u a t i o n t 0 s a t i s 矽b a y e s i 觚 i n c e n t i v e c o m p a t i b l e h 1a d d i t i o n ， k a h n 孤f i l t e rh a daw i d e l yu s e di nd a t af u s i o n ，b u tw h e n 廿l ed a t ao fs e n s o r s 锄a l y z e d h lm i sp 印e ri s i i l t e r d e p e n d e n t 觚dt l l ec o l l r e l a t i o nc o e f f i c i e n ti su i l l m o w n ，k a l m 锄 f i l t e rc 吼tp r o v i d ee 佑c i e n tv a l u a t i o n 缸l c t i o nf o ra g e n t s s om i sp a p e r 纽a l y z e da n e wd a t am s i o na r i m m e t i c c o v 撕锄c em e r s e c t i o na 1 9 0 r i t l i l ( c ia l g o r i t h mf 0 r s h o n ) ，w h i c hc 觚tw o r ko u tn l ev a l u eo fv a l u a t i o nm n c t i o n ，b u tc 雏p r o v i d e 觚 a c c o r d a n te s t i m a t eo fv a l u a t i o n 觚ds a t i s f i e sa c c o r d 姐te s t i m a t ec h a r a c t e r i s t i c t h i sp a p e r 他s e a r c h e dt h et w 0f a c e t sr o u g h l y t h em a i nc o n t r i b u t i o n sa 他弱 f o l l o w i n g ： ( 1 ) t h i sp a p e r 鲫a l y z e db 孙i cp r i n c i p l eo fm e c h 锄i s md e s i 印，d i s c u s s e di t s d e v e l o p m e n t ，锄dd i s c u s s e dt l l ec o m p u t a t i o n a lm o d e l 觚dt h r e ei l t i p o r t 锄tp r o p e r t i e s ： i n c e n t i v ec o m p a t i b i l i t y 、i n d i v i d u a l r a t i o n a l 时锄de f f i c i e n t a n dt l l i sp a p e r 觚a l y z e d v c gm e c h 锄i s ma n dt l l e 叫c t i o np r o c e s s0 fv c gm e c h 锄i s m t l l e 仃a d i t i o n a lv c gm e c h 觚i s mc 锄o n l yb e 印p l i e dt o t l l e 访d e p e n d e n t i i i a b s 仃a c t v a l u a t i o nm n c t i o n sb e t w e e na g e n t s ，s ow h e nt h ei i l f o m a t i o nb e t w e e ns e n s o r si s r e l e v 锄t ，t l l et r a d i t i o n a lv c gm e c h 觚i s mi s u n a b l et ob ea p p l i c a b l e t i l a ti st o s a y ， a g e n t sm a yr 印o r tn o tr e a lv a l u a t i o n 劬c t i o n t h i sp a p e ra l l a l y z e dan e wk i n do f v c gm e c h 觚i s m0 fi n t e r d e p e n d e n tv a l u a t i o n ，w h i c hc a l lb ea d a p t e dt ot h es i t u a t i o no f i i l t e r d e p e n d e n tv a l u a t i o nm n c t i o nb e 铆e e na g e n t s 锄dh a sp r o v e dt h a ti ts a t i s 6 e st h r e e c h a r a c t e r i s t i c s i i l a d d i t i o n ， t l l i s p a p e ro m i m i z e dt 1 1 ev c gm e c h a n i s mo f i i l t e r d e p e n d e n t v a l u a t i o nt 0 s a t i s 匆b a y e s i 锄i n c e n t i v ec o m p a t i b l e ，w h i c hc 孤 e 行e c t i v e l yr e d u c ep 聊m e n t so fe a c ha g e n tf o rr e c e i v e di l l f l o n i l a t i o n ( 2 ) t h i sp a p e r 觚a l y z e db a s i cp r i i l c i p l eo fd a t a 向s i o nb e t 、) l ，e e ns e n s o r s ， d i s c u s s e db a s i c 丘眦e 、山r e ek i n d so fs t l l l c n l r e l e v e la 1 1 ds o m ea d v 锄t a g e s 锄d d i s a d v 锄t a g e s0 fd a t a 向s i o nb e m e 钮m u l t i - s e n s o r s a n d 锄a l y z e d0 n e0 ft i l e i l i l p o n a l l t 如s i o nt e c h i l i q u eo fd a t a 如s i o n k a l m 锄f i l t e r 1 1 1 i sp a p e ra i l a l y z e db 弱i c a r i t h m e t i c 、c h a r a c t e ro fk a l m a nf i t e ra n dm s i o nm o d eb a s e do nk a l m 锄 t i l i sp a p e r 觚a 1 ) ，z e dak i n do f i l i l p r o v e dd i s t r i b u t e dk a l m 锄f i l t e ra r i t i 蚰e t i 卜i a r i t l l m e t i c ，w h i c hi sa b l et 0b ea d a 【p t e dt ot h es i t u a t i o no fm ei i l t e r d e p e n d e n t i n f 0 肌a t i o nb e t w e e ns e n s o r s a n dp r o v e dt l l a tc ia r i t m e t i cs a t i s f i e sc o n s e n s u s e s t i m a t e s ，c o m p 躺dt h ee m u l a t i o n a ir c s u l t so f k a h n a i lf i l t e rw i t l lc ia r i t h m e t i c ( 3 ) n l i sp 印e rm a i l l l yr e s e a r c h e d 叩t i m i z e dv c gm e c h 锄i s mo fi i l t e r d e p e n d e n t v a l u a t i o nh o wt ob ea p p l i e dt 0d a t a 如s i o nb e t w e e nm u l t i s e n s o r s 觚de m u l a t e da d i s 仃i b u t e dd a t af i l s i o ns y s t e mb yaj a v ap r o 伊a m t h e r ea r em u l t i - s e n s o r si i lm i s s y s t e m 觚de a c hs e n s o rn e e d st oc o n f i r mt i l el o c a t i o no fs o m ed ) ，i l 锄i cg o a l s h lm i s s y s t e m ，t l l ec o m m u n i c a t i o n a lb a i l d w i d t l li sl i m i t t h eg o a lo fm es y s t e mi st o 仃yi t s b e s tt oc o n f i m lt l l el o c a t i o no ft h e s ed y n 锄i cg o a l s b e c a u s et h em e r f e r e dn o i s et l l a t i s 印p e n d e dt o t i l es y s t e mi ss t o c h 觞t i c 觚di i l t e r r e l a t e d ，o b s e r v a t i o ni n f o n t l a t i o n b e t 、j i ，e e ne a c hs e n s o ri si n t e l l r e l a t e d 1 1 1t h i sp a p e r c ia r i m m e t i cr e a l i z e dd a t af h s i o n b e t w e e nm u l t i - s e n s 0 倦a n dv c gm e c h 锄i s mo fi n t e r d e p e n d e n tv a l u a t i o ni sa d 印t e d t ot h i sk i n do fd i s t r i b u t e dd a t a 龟s i o ns y s t e mt ow o r ko u tak i n do f 勰s i 印i n gm e t l l o d o fc h a n n e l ，w h i c hc a nm a k eu s eo ft l l ec o m m u n i c a t i o nb a n d w i d t h 鲫df a n h e s t c o n f i r mm el o c a t i o no ft h e s e g o a l s i l la d d i t i o n ，t h i sp a p e ro p t i m i z e dt l l ev c g m e c h 觚i s mo fi n t e r d e p e n d e n tv a l u a t i o nt os a t i s 匆b a y e s i 锄i n c e n t i v ec o m p a t i b l e ， i v 硕士学位论文 w h i c hc 锄e f 诧c t i v e l yr e d u c ep a y m e n t so fe a c ha g e n tf o rr e c e i v e di n f o m l a t i o n 1 ( e y w o r d s ：m e c h 锄i s md e s i 印；v c gm e c h a i l i s m ；m u l t i s e n s o r sd a t a 向s i o n ； d i s 仃i b u t e dk a i m a l lf i l t e r ；c o v a r i 锄c ei n t e r s e c t i o na l g o r i t h m ；v c g m e c h a i l i s mo fi i l t e r d e p e n d e n tv a l u a t i o nm n c t i o n v 硕士学位论文 1 1 背景知识 第1 章绪论 随着计算机科学与技术由面向单机的计算转向面向网络计算的发展，特别是 互联网的发展，计算机科学与经济学，特别是博弈论的结合渐渐引起计算机科学 研究者与经济学研究者的关注。博弈论( g 锄et h e o 啪【1 】是研究决策主体的行为发 生直接相互作用时候的决策以及这种决策带来的均衡问题。具体到计算机科学 中，博弈论主要研究的是在多用户的计算机网络系统中，以个人利益最大化为目 标的各个用户怎样在已有信息的基础上做出理性的决策，而同时从整个系统来 看，用户们又是怎样相互影响，从而最终达到系统的最优状态或者是均衡状态。 机制设计( m e c h 龃i s md e s i 印) 2 】是微观经济学和博弈论中的一个子领域。在 一个有多个用户参与的博弈中，假定每个参与者的偏好都是只有自己知道的情形 下，机制设计研究的是怎样在满足个人利益最大化的前提下，实现一定的目标函 数。我们可以把机制设计问题看作一个输入未知的分布式优化问题。在这样的优 化问题中，一些限制条件或目标函数的某些参数是参与者个人的私有信息，也就 是说，只有当参与者把个人私有信息告知系统后，系统才能确定使系统最优化的 目标函数。近年来，机制设计在计算机科学中的传感器网络，分布式调度，以及 拍卖协议等方面有很多重要的应用。 在计算机科学家看来，机制设计问题不仅要考虑问题的博弈性质方面，同时 要考虑问题的计算可行性和复杂性。在有些情况下，从博弈论观点看的最优解决 方案同时也是计算上最好的。最明显的例子就是占优策略的实现。在这种情况下， 不管其他参与者做出怎样的选择，每个参与者都有一个最优策略。这在计算上是 非常有利的，因为参与者并不需要计算当其他博弈方做出某些选择时，他应该选 择怎样的策略。然而，我们并不总是这样幸运。在绝大多数情形下，参与者都必 须对所有可能的分配方案计算自身的受益。而所有可能的分配方案本身就可能是 代理方数目的指数。因而，我们经常遇到从博弈论的描述来看简单，但从计算机 科学的角度来看却是计算上不可行的实例。因此，一个好的机制在保持博弈属性 的同时，也应当具有较低的计算复杂性。 第l 章绪论 计算机机制设计就是一门融合经济学的博弈论和计算机技术的一门新型学 科。如今机制设计已经运用到计算机领域的多个方面，本文主要考虑的是把机制 设计原理中的v c g 机制运用到传感器网络的多传感器数据融合当中。 随着科学技术的发展，传感器性能获得了很大的提高，多传感器的数据融合 技术也成为讨论的热点之一。多传感器数据融合( m u l t i s e n s o rd a t af u s i o n ) 【3 】是把 多种传感器集中于一个统一的感知系统( 即多传感器数据融合系统) 中，从而有机 地综合利用来自多个传感器的数据和信息，以便获得对周围环境的更多或更准确 的可靠的认识。数据融合是关于协同利用多传感器信息，涉及多级别、多方面、 多层次信息检测、相关、估计并获取目标状态和特征估计的一种多级信息处理过 程。利用计算机技术对按时序获得的若干传感器的观测信息在一定准则下加以自 动分析、综合从而产生新的有意义的信息，以完成所需的估计和决策任务。而这 种新的信息是任何单一传感器所无法获得的。 1 2 研究的历史及现状 历史上，机制设计领域由社会选择理论转化而来的，主要解决投票系统、征 税政策和公共物品的分配等问题。近些年来，计算机科学家开始研究机制设计问 题。以色列希伯莱大学的n i s 肌和r o n 明首次提出了算法机制设计的概念和框架， 给出分布式优化问题机制的集中式计算的复杂度，并且把这种概念应用于计算机 科学中的一些基本问题，包括最短路径问题，最小生成树问题和不相关加工机器 的时序安排问题【4 】。耶鲁大学f e i g e n b a u m 等人进一步把机制设计作为一个方法 应用于建立有效的网络协议，也就是分布式机制的实施【5 1 。哈佛大学p 冰e s 等人 研究了在线机制设计问题，其中代理随着时间的推移而到达【6 】。卡耐基梅隆大学 的l a r s o n 和s 锄d h o l r n 研究了计算有限理性代理的机制设计问题【7 】。英国利物浦 大学p h e l p s 等人通过遗传规划和协同进化研究了拍卖机制设计【8 】【们。c o n i t z e r 和 s a n d h o l m 提出了自动机制设计方法，并且研究了其计算的复杂性【1 0 】【l l 】。麻省理 工学院的s i l v i om i c a l i 等人提出了密码学博弈论的概念，可用于分布式机制设计 【1 2 】。复旦大学朱洪和陈宁提出了一个完全真实机制的概念，它具有对输出结果 的保留值校验特性【1 3 】。 在机制设计中最为重要的一类是v i c k r e y c l 玳e - g r o v e s c g ) 机制( 或者 2 硕士学位论文 g e n e r a l i z e d c l ( r e ya u c t i o n ( g v a ) ) 【1 4 】【1 5 】【1 6 】。特别地，v c g 机制对于所有的 u t i l i t a r i 觚问题提供了非常好的解决方法。v c g 机制在传统的机制设计中有着极 其重要的意义，因为v c g 机制是唯一一种满足策略无关性质的有效机制。所谓 策略无关指的是不管其他参与者的策略是什么，每个参与者的最优策略都是揭示 给系统其真实的偏好。而有效机制是指机制能从所有可能结果中选出一个使得机 制的总体效用达到最大。传统的v c g 机制设计是以各代理拥有各自独立的估价 的假设为基础的，即代理的估价只与他自己的观测值或信号有关。但是更多的实 际情况是各代理的估价是相互影响和相互依赖，在这种情况下，代理对分布式信 息的估价是与其他代理的估价存在相依关系。因此本文改进了传统的v c g 机制， 让它能适用于各个传感器的信息存在相关性的情况，并证明它也拥有传统v c g 机制的特性。 因为本文考虑的是把v c g 机制应用到传感器数据融合技术中，所以这里也 简单介绍一下多传感器数据融合技术的发展历史以及现状。多传感器数据融合在 七十年代末开始发展起来，它首先应用在军事上，如地面站车、水上舰艇和空中 飞行器的目标检测、分类和预警系统以及战场指挥和控制系统【1 7 1 。八十年代初 期英国e a s m s 公司成功研制了第一个战场数据融合试验系统，称为炮兵智能信 息融合演示系统( a i d d ) 。另外，英国皇家信号与雷达研究院为炮兵观测站开发 了一个数据融合系统，用于分析多传感器获得的战场的观测信息。在美国由国防 高级研究计划局负责实施的战略计算机计划中，也有多个项目将战场信息融合技 术列为重大的研究课题，地空战场管理系统，海军战舰信息管理系统，自主式地 面战车等大型军事项目中都有多传感器数据融合的专题。八十年代中期，随着各 种传感器在机器人应用研究的深入，人们开始认识到各种传感器在使用中的种种 限制和不尽人意之处，并将目光转向多传感器数据融合，以期从多传感器数据融 合的角度来增强机器人对周围坏境的认识能力，解决各种使用单一传感器不能解 决或难以解决的问题。之后，多传感器数据融合在许多方面得到了应用，形成了 传感器融合( s e n s o rf u s i o n ) 和数据融合( d a t af u s i o n ) 的新学科。 1 3 研究重点及章节安排 本文主要研究的是计算机机制设计中的v c g 机制在多传感器数据融合中的 第l 章绪论 应用。传统的分布式卡尔曼滤波虽然可以融合多个传感器的数据并能较好地估计 目标的方位，但是使用卡尔曼的前提是各个传感器的数据是相互独立的。然而在 许多实际情况中，传感器之间的观测数据都是相互关联的，因此本文分析了另一 种数据融合算法c i 算法，它可以在信息之间具有相关性且相关系数未知时提 供机制中代理的估价函数的一致估计，满足一致估计性。同时考虑到观测信息之 间的相关性，传统的v c g 机制此时也无法适用。因此，本文分析了一种相依估 价的v c g 机制，它能够在估价函数相依时计算出一种使得整个传感器系统的利益 达到最大的信息分配方式，同时本文优化了这种v c g 机制，使其满足贝叶斯激 励相容性。 全文共分五章，结构如下： 第一章绪论，描述本文的研究背景、研究历史及现状以及章节安排。概述 了机制设计和多传感器数据融合的理论发展和研究现状。 第二章算法机制设计的原理，首先分析机制设计理论的基本模型，概述了 什么是机制设计；说明了机制设计要满足的三个特性并详细介绍了后面将要用到 的v c g 机制。 第三章多传感器数据融合理论，简单介绍了多传感器数据融合的一些基本 知识：包括基本概念和融合原理以及融合模型。并介绍了卡尔曼滤波的数据融合 理论，包括卡尔曼滤波器的基本算法、性质和特点以及基于卡尔曼的两种融合模 型：集中式和分布式融合模型；最后详细介绍了相交协方差算法c i 算法并证 明它满足估计一致性，并且比较了c i 算法和传统卡尔曼滤波的仿真结果，证明 c i 算法更适合于信息相关的情况。 第四章优化的相依估价v c g 机制应用于多传感器融合，详细介绍了相依 估价的v c g 机制并证明它满足机制设计的三个特性，优化了这种v c g 机制， 使其满足贝叶斯激励相容性。最后分析了优化的相依估价v c g 机制应用于多传 感器数据融合的仿真结果，证明了优化的相依估价v c g 机制能够计算出保证系统 利益最大化的一种信道分配方式，并且优化后的v c g 机制能够满足贝叶斯激励相 容性，有效地降低代理所需的费用。 第五章为总结与展望，总结本文的研究内容，提出进一步的研究方向。 4 硕士学位论文 第2 章算法机制设计的原理 机制设计理论又叫执行理论( h n p l e m e n t a t i o nt l l e o 叻，是博弈论和微观经济 学的一个分支，用来设计博弈规则( 机制) ，以获得期望的结果。机制使得参与者 有激励按照设计者希望的行为动作，从而实现这个结果【1 8 】【1 9 1 ，它研究的是多个 自利代理的协商问题。因为代理是自利的，所以他们对于世界应该是什么样子有 自己的偏好和愿望( 可以理解为博弈的结果给参与人带来的利益) 。机制设计就是 综合每个代理的偏好信息，找到一个较好的系统范围内的解( 也就是一种规则) ， 使得代理和社会的整体效益最好。机制设计理论的问题最初是来源于微观经济 学，但是采用的工具是博弈论【2 0 1 。和传统的博弈论分析方法不同。机制设计是 设计规则，传统的博弈论是在规则存在的前提下分析博弈的均衡解。机制设计理 论已成为现代经济学的核心理论，被广泛应用于拍卖、垄断性商品定价、最优税 收等多个领域。本节先介绍机制设计理论的模型并描述机制设计理论中重要的显 示原理，然后介绍机制设计的三个特性，最后描述机制设计理论最重要的成果： v c g 机制。 2 1 机制设计模型 机制设计是一种特殊的不完全信息博弈。该博弈有一个委托方和若干个代 理，由委托方来选择机制，或者说设计一个博弈规则。委托方的目标是使社会福 利最大化，也就是所有博弈的参与人的偏好之和最大化。但委托方并不知道各个 代理方的实际偏好。为了实现系统目标，委托方设计博弈规则时就必须要让设计 出来的机制满足个体理性，激励相容性和有效性。 5 第2 章算法机制设计的原理 p r i v a t et y p e i i l f o m 砒i 。n s l s 恻e g i e s i 。 il a g e n t1 i 7 p ， p a y m e n t s m e c h a n i s m s n ll en a g e n tn l 7 p n 图2 一l 机制设计理论框架 f i g 2 - l c h a r to f m e c h 觚i s md e s i 朗也e o 叮 o 图2 1 是机制设计理论框架【2 1 1 。机制设计问题概括起来讲就是在不完全信 息非合作博弈的分布式系统中来解决一个系统的优化问题。在不完全信息博弈 中，每个代理对系统分配方案的偏好都是由一个类型包o ，来确定的。假设有n 个a g e n t 和一个有限的所有可能输出结果的集合o 。对于任意d d ，每个 呼耐f 1 ，刀) 都有一个只有自己知道的估值函数m ( d ) ，记为v a l u a t i o n ，表示 他可以从输出结果d 中得到多少收益。 ，是公共知识，即所有代理都知道 ， 但是q 只有代理自己知晓。代理参与机制，会采取策略( s 廿a t e g ”。对于每个代理， 策略是其类型的函数，即：而= _ ( 岛) “s ，包o ，) 。 机制中每个代理都选择一个策略，这样就构成了一个策略组合s = ( s ，) 。 机制将策略组合作为输入，计算得到一个输出结果d = d ( s ) ，称之为机制的分配 规则。机制还根据输入的策略组合，给所有代理以转移支付( p a y m e n t ) 觑= 鼽( s ) ，( kl ，2 ，刀) 它表示每个a g e n t 得到的货币量( e g ，如果p f = 2 ，呼耐f 则付出2 个单位的货币) 。记p = ( p 。( s ) ，p 2 ( s ) ，见( s ) ( p 尺”，称为机制的支付 规则。分配规则描述了机制选择的分配结果，而支付规则用于激励自利的代理在 最大化自己效用的同时，采取系统认为的正确行为。分配规则和支付规则是一个 机制的两个组成方面。每个代理对不同的输出结果具有不同的偏好，记为v ，( d ，1 9 i ) 。 6 硕士学位论文 它是类型为岔的代理对可行结果。满意程度的数值化度量，称之为代理i 对结果 。的估值( v a l u a t i o n ) 。在机制确定的分配规则和支付规则下，代理获得的效用 ( u t i l i 妫通常都假设是拟线性的，即( d ，曰) = m ( d ，b ) 一所。由于效用依赖于代理的 私有类型信息只，因此每个参与人的效用机制并不知晓。如果代理的目的就是最 大化其效用，则称这样的代理是理性的。 机制设计的目标就是依据代理的真实类型来选择最优分配方案。这个目标在 经济学和博弈论中称之为社会选择函数。 定义2 1 1 ( 社会选择函数( s o c i a lc h o i c ef u l l c t i o n ) ) 在给定类型组合 秒= ( 幺，幺) 的情形下，社会选择函数厂：b ，见寸d 选择某个结果厂( 口) d 。 社会选择函数定义了机制设计者所希望达到的系统的全局目标，它是机制进 行决策的依据。实际上，机制设计问题是对博弈规则的确定，比如机制设计可以 规定哪些策略是合法的哪些是不合法的，也就是可以限制代理只能采取某些规定 允许的策略即_ s ；机制设计也可以决定用哪一种方法来选择社会分配方案， 也就是定义从秒到d 的映射，但是这种映射是不能任意指派的，因为要考虑到每 个代理是自私的，如果社会选择函数损害了任意一个代理的利益，该代理都可以 选择不参加博弈。 定义2 1 2 ( 机制( m e c h 锄i s m ) ) 圈【2 3 】给定输入向量参= ( 反，晓) ，其中口是 呼脚f 实际向口“订f 册p 提交的值，机制朋= ( d ，p ) 包含两部份 1 输出函数： d ( 口) d 2 支付函数：p ( p ) = ( a ，风) 注：1 在上述定义中，口g 明ff 实际提交的岛不一定与相等，因为他可以选 择不说实话。他的策略取决于怎样最大化他的“f f ，渺值。 2 一个机制被称为仰t h m l ( 或者i 1 1 c e n t i v ec o m p a t i b l e ) 是指如果对于任意 口g p 脚f 和其他所有a g e n t 实际提交的建，呼脚f 的“f 砂都在他说实话( 向机制如 7 第2 章算法机制设计的原理 实地提交他的v 口，“口f 如刀1 ，时) 最大化。t r u t h m l l l e s s 是机制设计中最为重要的概念 之一，我们下面将详细地讨论这方面的问题。 3 在不同的模型中，我们可以定义不同的输出函数即甜f 玎豇f 册问题：机制的 输出函数选择d o 以最大化目标函数g ( d ，1 ，) = = i v ，( d ) ，记为s o c i a lu t i l i t y 。 所以说，机制定义了可行的策略，并且机制规定了基于代理策略组合的分配 规则。机制设计问题就是在参与者拥有私有类型信息时，通过确定合理的支付来 激励参与者采取理性的行动，达到机制所要求由社会选择函数所制定的目标。 定义2 1 3 ( 机制的解( s o l u t i o no fm e c h 锄i s m ) ) 给定机制，代理进行博弈 满足均衡的策略组合称为机制的解。均衡可以是占优策略均衡( d o m i n a n ts 仃a t e g y e q u i l i b r i 啪) 或是贝叶斯纳希均衡( b a y e s i 觚n 笛he q u i l i b r i 啪) 。 由于代理的策略是其私有类型的函数，给机制设计问题带来难度，但是著名 的揭示原理将代理的策略空间变换为代理的类型空间，从而简化了机制的设计。 定理2 1 1 ( 揭示原理( r e v e l a t i o np r i i l c i p l e ) ) 给定任何一个机制和该机制下的 任何一个均衡策略，都存在一个直接机制，使得在这个机制下满足代理真实地报 告自己的估值是一个弱占优均衡策略以及配置结果( 分配和支付) 和给定的原始 机制的均衡所得的结果是相同的。 揭示原理表明任何二个机制所能达到的配置结果都可以通过一个激励相容 的直接揭示机制来实现。因此，可以只考虑直接机制的设计。 定义2 1 4 ( 直接揭示机制( d i r e c t r e v e l a t i o n ) ) 在一个直接显示机制中，代理 的策略就是根据自己的真实类型谚向机制报告一个类型每，茸= 岛( 岛) 。如果代理 报告的是关于自己类型的真实信息，只= 墨( q ) ，则该揭示机制是真实的( t m t i l r e v e a l i l l 曲 直接揭示机制中的“直接 指的是代理的战略空间等同于类型空间。揭示真 实的策略是基于所有可能的偏好，报告关于偏好的真实信息。所以我们在进行机 制设计时，一定要激励理性代理真实报告其类型，防止设计过程被操纵。在我们 的激励下，代理只要报告真实类型，就可以获得满意的结果。 定义2 1 5 ( 策略无关( s 仃a t e g ) ，- p r o o f ) ) 在一个直接显示机制中，如果说真 话是一个占优的策略均衡( d o m 协锄t - s n 眦e g ye q u i l i b r i u m ) ，那么该机制是策略无 硕士学位论文 关的。 策略无关无论从博弈论的角度还是从计算的角度来看都是非常有用的性质。 占优策略实现对代理来讲是非常强的假设，信息的揭示和理性的要求都能得到很 好得保证。从计算上来讲，代理无需对其他代理的偏好和策略进行分析就能做出 最优化的策略。不难看出策略无关的机制也是占优策略的激励相容机制。策略无 关是机制的一个非常重要的属性，它暗示在任何情况下，任何代理人都不能从谎 报其类型中获益。因此，满足策略无关属性的机制得到了广泛的关注。 2 2 机制设计的特性 我们在设计一个机制时，设计者应考虑机制要满足的三种特性：激励兼容性 ( h l c 跚t i v ec o m p a t i b i l 时，简称i c ) ，个体理性( i l l d i v i d u a lr a t i o n a l i t ) ，简称r ) 和有效性( e 衔c i e n t ) 。激励兼容性是指代理报告真实类型比报告错误能获得更多 的利益，个体理性约束是指代理参与博弈比不参与能获得更多的利益，而有效性 则是指机制能找到最优的分配方式。 2 2 1 激励相容性 前面我们已经提到了激励相容机制，对它已经有了一个初步的了解，现在我 们详细解释一下什么是激励相容性。激励相容机制是一个每个代理都真实向机制 汇报各自偏好的直接揭示机制。激励兼容抓住了机制设计的实质为了克服非 合作博弈中代理的自利性。在激励兼容机制中，自利的代理会选择讲真话，因为 这样可以使得他们的利益最大化。 激励相容机制有两个最常见的解的概念，占优策略( d o m i n a n ts t r a t e 斟，简 称d s ) 和贝叶斯纳什均衡( b a y e s i 觚n a s he q u i l i b r i 啪，简称b n e ) 。接下来我 盎 们定义激励兼容的概念。我们假定，代理f 的真实类型为，报告类型为6 i 。 定义2 2 1 ：一个机制被称为在占优策略d s 上执行是指，如果当其他代理 报告的类型是已知时，某代理报告真实类型是最好的选择。即对于任何代理f ， 任何类型