（计算机软件与理论专业论文）瓦尔拉斯均衡与组合拍卖.pdf

摘要1 本文主要研究基于因 特网的组合拍卖机制设计问 题。因 特网 是一个分布式的计算 网络，存在大量具有各自 经济利益的代理 ( 代理可以是网 络用户也可以 是计算机). 过 去，网络协议的设计者们往往忽略了网络中的代理是自 利的一一这一特性，然而随着因 特网的发展，很多基于因 特网的机制设计问题一一比如网 上的组合拍卖一一变得在实际 中也是可行的，所以再也不能忽略代理的自 利性。为此，一个很重要的问题是设计激励 相 容的 协议， 使得即 使 代理 是自 利的 情形卜 ， 网 络系 统也能 卖 现系 统最 优的目 标。 对于 这一问题，本文将针对基于网络的组合拍卖探讨可行的解决方案。 本文先回顾了组合拍卖问题的经济和计算属性，讨论了设计计算上可行的 机制的一 些技术和方法。本文提出了一个线性规划层次模型: l p 1 , l p 2 , l p 3 .该层次模型通 过对组合拍卖问题逐步增加 约束从而剔除掉非整数解的办法来建立。 在此基础上，本 文得出了 在l 乃 下， 瓦尔拉斯均衡总是存在的结论。为了降低l 乃 的复杂度，本文对 l p 2 中 参加拍卖的代理方加上s i n g l e - m i n d e d 的限制从而得到 s l p 2 ，并且论证用迭代机 制实现 s l 几 确实能得到瓦尔拉斯均衡解。 关键词: 机制设计，组合拍卖，一心一意的，迭代机制，博弈论，瓦尔拉斯均衡， 赢者确定 问题 分类号: t p 3 0 1 . 6 1 木研究受剧国像自然科学书金第 6 0 2 7 3 0 4 5 号，科学技术部舀础研究，大项目前期研究专项 第2 0 0 1 c c a 0 3 0 0 号和上海市科技发展基金第0 2 5 1 1 5 0 3 2 号资助 ab s t r a c t 2 t h i s t h e s i s f o c u s o n i n t e r n e t - b a s e d c o m b i n a t o r i a l a u c t i o n . t h e i n t e r n e t e m- b o d i e s a n e w p a r a d i g m o f d i s t r i b u t e d c o m p u t e r n e t w o r k s , i n w h i c h a g e n t s - u s e r s a n d c o m - p u t a t i o n a l d e v i c e s - a r e s e l f i n t e r e s t . a s t h e d e v e l o p m e n t o f i n t e r n e t , m a n y i n t e r n e t - b a s e d me c h a n i s m d e s i g n p r o b l e m s u c h a s c o m b i n a t o r i a l a u c t i o n b a s e d o n i n t e r n e t b e c o m e f e a - s i b l e i n p r a c t i c e ,s o w e c a n n o t n e g le c t t h e e ff e c t o f s e l f i s h a g e n t s . t h u s , a f u n d a m e n t a l p r o b l e m i n b u i l d i n g t h e s e s y s t e m s i s t o d e s i g n i n c e n t i v e - c o m p a t i b l e p r o t o c o l s , w h i c h c o m - p u t e o p t i m a l s y s t e m - w i d e s o l u t i o n s d e s p i t e t h e s e l f - i n t e r e s t o f i n d i v i d u a l a g e n t s . a s f o r t h i s p r o b l e m, t h i s t h e s i s a i m t o fi n d a f e a s i b l e s o l u t i o n f o c u s e d o n c o m b i n a t o r i a l a u c t i o n . a f t e r r e v i e w i n g t h e e c o n o m i c a n d c o m p u t a t i o n a l p r o p e r t y o f c o m b i n a t o r i a l a u c t i o n , w e d i s c u s s s o m e t e c h n o l o g i e s a n d r u l e s i n d e s i g n i n g me c h a n i s m. a n d w e p r o p o s e a h i e r a r c h y o f li n e a r p r o g r a m f o r m u l a t i o n s , l p 1 , l p 2 , l p 3 , w h i c h r e t a i n t h e s e t o f i n t e g e r a l l o c a t i o n s b u t p r u n e a d d i t i o n a l f r a c t i o n a l s o l u t i o n s . 、 昵 p r o v e t h a t i n l 几， wa l r a s i a n e q u i li b r i u m a l w a y s e x i s t s . we a l s o r e s t r a i n l 几 t o s i n g l e - mi n d e d o n e , s l 几 a n d d i s c u s s t h e e f f i c i e n c y o f t h i s r e s t r i c t i o n . f i n a ll y , w e t a l k a b o u t s l p 2 s i m p l e m e n t a t i o n w i t h i t e r a t i v e me c h a n i s m. ke y wo r d s : me c h a n i s m d e s i g n , c o m b i n a t o r i a l a u c t i o n , s i n g l e - mi n d e d , i t e r a t i v e m e c h a n i s m, g a m e t h e o r y , wa l r a s i a n e q u i li r i u m , wi n n e r - d e t e r m i n a t i o n cl a s s i f i c a t i o n nu mb e r : tp3 0 1 . 6 t th is w o r k i ss u p p o r t e d b y a g r a n t f r o m t h e m i n i s t r y o f s c i e n c e a n d t e c h n o l o gy ( g r a n t # 2 0 0 1 c c a 0 3 0 0 0 ) , n a t io n a l n a t u r a l s c i e n c e f u n d ( g r a n t # 6 0 2 7 3 0 4 5 ) a n d s h a n g h a i s c i e n c e a n d t e c h n o lo gy d e v e lo p m e n t f u n d ( g r a n t # 0 2 5 1 1 5 0 3 2 ) 4 第一章 引言 1 . 1背景知识 计算 机科学中很重要的一个方而 就是研究网 络环境 特别是因 特网)中的算法和协议。 怎么使相关的网 络算法或 协议达到设计者所希望的高效率，则一直是研究者们所追求达 到的目 标。为了 使协同工作的网络系统效率最高， 就需要研究怎 样将任务分割并且分 配 到各个不同 的计算单元 ( 独立的计算机) 上去。 过去， 计算 机科学家们总是假定各个计 算单元会按照系统指定的要求工作，也就是，各计算单元如实的向 系统提供空闲c p u 时 间， 空闲的 存储单元等参数， 并且在系统把任务分配完成以 后， 完全按照系统的 指派工 作。然而，因特网作为一个无所不在信息交换平台， 它是由一个个大小不等，结构各异 的网 络自 愿连接， 构建， 运作和共同 使用的。 每个子网 代表了 一个社会经济团 体， 他们 都具有各自 的经济利益， 它们之间既存在相互竞争 又存在相互合作。同时因特网也没有 一个中央管理机构对整个网 络的运行， 维护进行管理。这样，每个子网所代表的团体为 了使他们的经济利益最大化，就很可能做出对各自 而言有利但对整个系统来说不利的决 策。简而言之，各自 利的计算单元井不会无条件的按照系统的指令去做。 为了自 身利益的最大化，系统的参与者可能会虚报参数，从而获取比讲真话更多的 利益。 为此， 我们必须设法激励侮个参与者诚实的告知系统正 确的参数，从而使得系统 在把资源或者计算任务用最优的方案分配的同时舱够满足各个单元利益最大化的要求。 怎么样使得这些团 体做出既对整个社会又对每个个体而言有利的决策就要运用现代微观 经济学中重要的数学工具一博弈论。 在博弈论中，采用支付的手段来激励参与博弈的代理 ( 可以是人也可是物)。 激励 中的 个核 心问 题是要根据实际情况设计支付函 数。 个支付函 数如果设计的不恰当， 1引言 就会使得一些参与博弈的代理有空可钻， 用虚报信息的方式使得系统整体利益受损而个 人获利增加。 因此，在任何的涉及到自 利代理的网络系统中，不仅要考虑算法和协议的设计问 题，还要考虑采用何种支付手段来激励自 利代理讲真话的问 题。只有同时考虑这两个方 面，刁能设计出理论上可行和实际中适用的算法和协议。 1 . 1 . 1博弈论 博弈论， 英文为 g a m e t h e o r y , 是研究决策士体的行为发生直接相互作用时候的决策以 及 这种决策带来的均衡问题。 具体到计算机科学中，研究的是在多代理的计算机网络系统 中，以个人利益最大化为目 标的各个代理怎样在己有的信息基础上作出 理性的决策，而 同时从整个系统来看，代理们又是怎样交互影响，最终达到系统的最优状态或者是系统 的均衡状态。 其实博弈论的概念对计算机科学家尤其是从事计算机理论研究的工作者来说并不陌 生。 在复杂性理论中，交互式证明系统就已经用到了博弈论的原理与方法。在交互式证 明系统中有一个诚实的验证者，还有一个可能有恶意的证明者。证明者通过和验证者进 行若干次信息交换来使验证者相信，证明者要向 验证者证明的问 题确实是正确的.这实 际 上就是 一 种两人博弈。 两 人博弈可以 说是 一 种重 要的 复杂性 模 型【1 1 ， 在逻辑中的 有 限模型论中也有重要应用。 一般认为博弈论开始于冯诺依曼和摩根斯坦合作的 博弈论和经济行为一书的 出版。但是现代博弈理论跟他们讲的东西关系不大， 尽管有一些概念， 特别是预期效用 理论等，都是他们创立的。上世纪5 0 年代是合作博弈发展的鼎盛时期， 在这一阶段，涌 现了包括纳什 ( 1 9 5 0 ) 和夏普里 ( 1 9 5 3 )的 “ 讨价还价” 模型，吉利斯和夏普里关于合 作博弈中的 “ 核”的概念等一批开创性的成果.随后，非合作博弈论也开始创建和发 展，纳什在1 9 5 0 年和1 9 5 1 年发表了两篇关于非合作博弈的重要文章，tuc k e r 于1 9 5 0 年提 出了著名的 “ 囚徒困境”问题.他们俩人的工作基本上奠定了现代非合作博弈论的基 石。 关于博弈论的 详细介绍 可以 参见 1 , 2 , 3 7 , 2 8 1 . 本文主要从非合作博弈的角度来研究组合拍卖问 题。 在组合拍卖中， 每个参与拍卖 的 投标人都拥有私有信息，并且因为自 利的原因，不会自 愿的将私有信息公开.为了 让 代理讲真话，需要用到博弈的机制设计工具。 1引言 1 . 1 . 2机制设计 机制设计是微观经济学和博弈论中的一个子领域。 在一个有多个参与人的博弈中， 假定 疥个参与者的偏好都是只有自己知道的情形下， 机制设计研究的就是怎样在满足个人利 益最大化的前提下，优化整个机制1 的目 标。近年来， 机制设计在计算机科学中的电子 商务，分布式调度问题，以及组合拍卖等方面有很多重要的应用。 我们可以 把机制设计问题看做一个输入未知的 分布式优化问 题。在这样的 优化问 题 中， 一些限 制条件或目 标函 数的某些参数是参与者个人的私有信息， 也就是说，只有当 参与者把个人私有信息告知系统后，系统才能确定使系统最优化的目 标函数。如果不知 道目 标函数是什么，系统的优化就无从谈起。 为了加深理解，我们举网络路由的例子来进行说明。在这样一个例子中， 机制的优 化目 标是合理安排数据包在网络中传输的路径。使得所有数据包在网络中传输的代价之 和最小 ( 这里我们把网络的各个节点当 做代理)。 然而每个代理都有一些诸如存储容 量，单位延迟时间和成本等私有信息.不知道这些信息，机制就无法确j 潮口 些是最优的 路径， 明 a 些不是， 就更谈不上把各数据包的传输路径作到资源最小化的分配。为了 解决 这个问题，一个可行的方法就是给各代理以好处 比如说通过付费的方式)来激励代理 们把他们掌握的信息如实的告知机制。 格罗夫 斯 机制2 1 1 在传统的 机 制设 计中 有着 重要的意 义， 因 为 格罗 夫 斯 机 制是唯一 一 种满足策略无关性质的的 有效 机制。 所谓策略无关指的就是不管其他代理的 策略是什 么， 每个代理的 最优策略就是揭示给系统其真实的偏好。 具体到 在上面提到的 网络数据 包传输博弈的例子，如果机制总是能激励每个代理真实的汇报参数，那么我们称这样一 个网络数据包传输的机制是策略无关的。而有效机制是指机制能从所有可能结果中选出 能使机制总体效用最大的一个结果。 尽管是策略无关的和有效的， 但是格罗夫斯机制从计算可行性的角度来 看却很不理 想。 格罗夫斯机制要求代理们把所有信息 传递给机制， 然后由 机制来统一计算出 最好的 解决方案.这实际上是把分布式问题完全用集中的方法解决。除了隐私和保密性等因素 外，格罗夫斯机制从两个方面看起来是不可行的。首先，要求每个代理计算出在每种可 能结果下她将得到的利益在计算上往往是不可行的;其次，由机制来统一计算最优化的 解决方案在计算上也是非常难的。为了使机制在计算上可行，在保持某些博弈属性同 时，要放松对代理必须把信息直接揭示给机制的要求. i 在计 算机科学中， 人们常把一 个由 多 代理 组成的 组织结构称为系 统. 而 在博弈 论中 t常 称为 一个博 弈或 机制，为了 统一表达， 我 们一律 把这样的 系统称为 机制， 把 机制中的 参与人称之为 代理. 但在组合拍 卖中，我们把代理具体称为投标人 i引言 在计算机科学家看来， 机制设计问 题不仅要考虑问 题的博弈性质方面，同时要考虑 问 题的计算可行性和复杂性。 在有些情况f ， 从博 弈论观点看的 最优解决方案同时也是 计算上最好的。 最明 显的 例子就是占 优策略的实 现。 在这种情况卜 ，不管其他参与者作 出怎样的选择，每个参与者有一个最优策略。这在计算上是非常有利的，因为参与者井 不需要计算当 其他博弈方 作出 某些选择时， 他应该 选择怎 样的策略。 然而，我们并不总 是这样幸运。在绝大多数情形下，参与者都必须对所有可能的分配方案计算自 身的 受 益。而所有可能的分配方案本身就可能是代理方数目的指数。因而，我们经常遇到从博 弈论的描述来看简单，但从计算机科学的角度来看却是计算上不可行的实例.因此，一 个好的 机制在保持博弈属 性的同时，也应当具有较 低的 计算复杂性. 1 . 2相关工作 近年来许多复杂的拍卖和机制在计算机系统上相继实现，从而导致了人们对这些拍卖和 机制的 计算特性的 关注。 这其中 最为引 起计算 机科学工作者关注的恐怕要属组合拍卖问 题了。组合拍卖允许参与拍卖的代理一次性获得多个不同的拍卖品。 组合拍卖问题不仅仅有理论上的意义，在实际中它也有很多应用。在由美国、英国 以及澳大利亚政府举行的对通讯频段的一系列拍卖中，由于很多频段是需要配套销售 的， 这 就要求 应用 组 合拍 卖的 知识来 制定 拍 卖规 则2 5 1 . 组 合拍 卖问 题也在 算法设 计中 有 很 多 应 用12 6 , 4 8 , 3 4 , 4 1 , 2 0 , n is a n 和 r o n e n 3 5 , 3 6 】较早 地 建 立了 机制 设 计、 近 似 算 法 和 有限 理 性的 联 系。 然 而 他们的工作没有考虑到代理的价值函数计算的复杂性问题，而只考虑了 确定机制结果的 赢者 确定问 题。 同 样的， t e n n e n h o lt z 5 0 1 等的 工 作也 仅 局限 于 在 一轮密 封机 制中 怎 样在 赢者确定算法用近似算法解决的基础上取得激励兼容的性 质. n i s a n 玲 川 同 时 也 考虑了 代理的投标语言的 有效 性和 表达简洁性之间如何 折衷的问 题， 并 且 提出了 一 种 o r 语 言的 解决 方 案。 而 近来 l a m u r a 和 s h o h a m 3 1 从 层 次 语 言 的 简洁性的角度出 发，也 提出了 一种用层次树结构来表示偏好的语言。 s h o h a m 和 t e n u e n h o l t z 3 0 】 通 过 对 交 互 式 多 轮 和 单 轮 密 封 拍 卖 的比 较， 对 组 合 拍 卖 的通讯复杂性进行了研究，然而他们的工作也没有考虑代理方的价值偏好关系的计算问 题。 f e ig e n b a u m 1 7 , 3 , 1 5 , 1 6 , 1 8 1 提出 了 一 种 分 布 式 的 机 制 来 解 决 组 波 多 路 传 输问 题， 文中巧妙地用树的 结构来降低拍卖中的通讯复杂性， 但是 文中 刘代理方所需的 计算能 力 没有作更进一步的考虑。 引言 wu r m a n 和 w e ll m a n 沛 8 , 5 3 , 5 2 , 5 7 1 提出了 动态多 轮组 合拍卖 机制， a k b a 。 无独有 偶，d . p a r k e s 也提出了一种分布式动态拍卖机制，i b u n d l e .两者之间的土要区别在于 价格的结构和价格更新的方式不同。a k b a 只有匿名价格，而且a k b a 是以代理方到达 均衡为结束条件的。 其他一些重要s作包括 g u l 和s t a c c h e t t i 2 3 1 ， 特别;pe a u s u b l e 5 , 4 1 . b ik c h a n d a n i 7 1 给 a u s u b l e 的方法提出了原始对偶算法的解释。原始对偶方法最早由 l e o n a r d 2 7 】 和 d e m a n g e 1 1 3 应用于分配问 题。 b ik c h a n d a n i等7 1 以 及b i k c h a n d a n i 和 o s t r o y 合作 18 1 用线 性规 划模型 来 解 释 一 般性的 组合 拍卖问 题中 的 v c g 支 付问 题。 s a n d h o l m哗， 4 3 , 4 6 , 4 9 , 4 7 , 4 4 1 提出了 另外 一 种方 法来处 理 代理方的 有限理 性和 分布式系统中的任务分配等问 题。 总而言之，该领域之所以吸引众多的计算机科学家是因为组合拍卖问 题既需要考 虑问 题 在计算 上的 有效性( 等价于著名 n p 难问 题一 一 包分 配问 题 ( s e t p a c k i n g )， 又要考虑经济上的有效性一即要满足瓦尔拉斯均衡等条件。但是瓦尔拉斯均衡并不 一定存在。 b i k h c h a n d a n i 等19 1 给出了 交换经济中瓦尔拉斯均衡存在的充要条件，并 且 b ik h c h a n d a n i 1 d 健立了 逐 步 实 现瓦 尔 拉 斯 均 衡 的 包 分 配 模 型. 瓦 尔 拉 斯 均 衡 在 经 济 学中有着重 要的意义， 是完全竞争性的 市场中的一 种重要的均衡， 在组合拍卖中 确保瓦 尔拉斯均衡存在性能够使我们算出 来的分配结果有经济学意义上的有效性。 但是以 上两 篇文章忽略掉了问题在计算上的有效性。这样的话，设计出来的拍卖机制在实际上是行 不通的。为此，本文对上述模型进行了改进. 1 . 3本文的工作 考虑到瓦尔拉斯均衡的重要意义，同时瓦尔拉斯均衡又并不一定存在的事实，以 及b i k h c h a n d a n i 9 1 提出 的 瓦尔拉斯 均衡存在的充 要条件的 结论， 本文 作者 考虑如何在 限定拍卖结果必须是瓦尔拉斯均衡的前提下，分析组合拍卖的计算可行性。 本 文针 对组 合拍 卖 提出了 一 个三 层次的 模型: l p i , l p 2 1和l p 3 1 . l p 1 1 实 际 上就 是 组合拍 卖问 题 2 ( 见 3 .3 .1 节) 。l p j + i 是 在协 马 的 基 础上引 入新的 约束条 件 ( j = 1 ,2 )。 这些约 束条 件保 持原问 题的 整数 解不 变， 只去 掉使瓦 尔拉斯均衡不存在的 非整数解。针对这一模型，本文分析了各层次模型对瓦尔拉斯均衡和计算复杂性的影 响，总结了瓦尔拉斯均衡存在性和计算复杂性之间的相互矛盾的关系，得到了瓦尔拉斯 均衡在l p 3 下是存在的结 论。 为了降低灯杂性的同时又确保拍卖结果是瓦尔拉斯均衡的，本文提出了对拍卖中的 2引言 投标人的最优反应集作限制的方法来降低拍卖的复杂性。为了能减少拍卖的复杂度，本 文提出 用分布的动态的机制 迭代机制)来实现组合拍卖问 题，并对迭代机制的正确性 和算法复杂性做了相关的分析。 1 . 4本文结构 第二章引入了传统机制设计，介绍了博弈论、经济学以及机制设计中的一些重要概念， 包括纳什均衡、占优策略均衡、揭示原理和v c g 机制。 第三章开始从计算机科学的角度看待机制设计问题，提出了从计算机科学，尤其是 理论计算机科学来看机制设计和组合拍卖有那些需要考虑的因素。这一章还专门针对组 合拍卖中的瓦尔拉斯均衡的存在性提出了层次模型的解决方案. 第四章对一般性的组合拍卖问 题进行限制， 提出了一种叫作s i n g l e - m i n d e d 的投标 人的概 念， 并 在此基础上分析了 s i n g le - m i n d e d 组合拍卖的计算有效性和计算难解性。 最后提出了 s i n g l e - m i n d e d 组合拍卖的 一种实现方案一一迭代机制。 第二章 古典的机制设计 机制设计是微观经济学和博弈论中的一个子领域，它是一种特殊的不完全信息博弈。该 博弈有一个委托方和若 干个代理，由 委托方来选择机制， 或者说设计一个博弈规则。 委 托方的目 标是使社会福利最大化，也就是所有博弈的参与人的 偏好 ( 可以理解为博弈的 结果给参与人带来的利益) 之和最大化。 但委托方并不知 道各个代理方的实际 偏好. 为 了实现系统目 标，委托方设计博弈规则时就必须要让设计出 来的机制满足参与约束和激 励相容约束条件。 下面这一节将简要介绍博弈论中的一些基本概念和方法，以及这些概念跟机制设计 的联系。 2 . 1博弈论概述 在这一节，我们介绍非合作博弈的一些基本组成要素，并以此作为研究的起点。这一部 分内容可以看作下一章的前奏曲.最近出版的一些可供深入学习博弈论的优秀参考资料 可见奥斯 本与鲁宾 斯坦卜 刘 ， 科莱尔、 温斯顿与 格林!2 s , 富 登 博格与泰 勒尔i s , 梅 耶 森3 2 1 ， 张维 迎ii i 和 谢识予2 1 笼统一点讲，博弈就是对许多人在一个策略相互依存的模型中彼此相互作用这种情 况的正式表述。 策略相互依存表示每个人的获利不仅依赖于她自 己的策略，而且还依赖 于其他人的策略。 而且她采取的最优策略也许要依赖于她所预期的其他代理会采取的行 动。 为详细的描述策略相互作用的情况，我们需要知道跟博弈相关的四件事: .参与人:谁参与了博弈? 2古典的机制设计 规则: 谁在什么时候行动?当 他们行动时， 他们知道什么? 他们能 做什么? 结果: 对于参与人行动的每一个可能的集合， 博弈的结果是什么? 效用 卜 面， 参与人在可能结果 上的偏 好1 ( p r e f e r e n c e ) 是什么? 我先举一个简单的例子来进行说明 例2 . 1英式拍卖:英式拍卖是单个拍卖品的价格上升型的拍卖. 参与 人:一个拍卖人。 ， 和投标人集合万， 投标人记为1 , . . , n ， 其中。 =1万 。 规则: 拍卖品 初始价为s ， 投标人轮番报价p i ， 每个投标人的 报价必须至少比当 前 最高 报价多1 单位价格， 直到没有一个投标人的 报价高于当 前最高的 报价， 栩 。 二 。 结果:报价最高的投标人 i 获得拍卖品。 效用: 报价最高的投标人i 以 报价p i : p - 。 二 支付给拍卖人。 ， 这里假定拍卖品在 i 心目 中的价值是v i , 因而i 的效用就是u i = v i - p . n 。 二 。 从例2 . 1 我们可以 看到， 任一投标人i 的策略s i ( 出不出价?出 价的话，出多少?) 不仅取决于投标者个人对拍卖品的估价的，还取决于其他投标人所采取的行动 ( 即报 价)。 形式化一点来讲就是， 假定ai为 投标人i 采取的 行动， a 为除了i 以 外的 投标 人采 取的 行 动， 那么 投标 人 的 策略 应当 是其 他 投 标人策略的 函 数， 即s i ( a勺 . 投标人为了自身利益最大化所应当采取的策略是:如果投标人现在不是出价最高 者 且当 前最 高价p -二比 该投 标 人的 心 里价位 要来 得 低， 那么 她应该 报价p m a z + 1 这 里1 为单位价格);否则，投标人应选择不报价。 我们还是从例2 . 1 来看， 注意到 任一投标人 的 报价p i 并不一定 等于她对拍卖品的 真实估价v i ，一般来讲报价总是不高于真实估价，所以 有p i 5 v i 。这里估价 是投标人 私有的信息。这些私有信息非常重要，因为正是这些是有信息确定了博弈的结果。在 例2 . 1 中，博弈的结果是由所有投标人的类型确定的。实际上，英式拍卖总是由出价最 高 的 出 价 者 以 次 高 的 估 价 p i 获 得 拍 卖 品 ， 这 里 ， 一 a r g m a xk e n - i叭 ) 。 所 以 英 式 拍 卖 的 结果实际上在拍卖开始之前就己经由最高估价和次高估价确定了。 为了 表示这类私有信息，引入一个新的概念:代理的类型。我们赋予傅个代理i 一 个 类型空间e i ， 代理的类型b i 取自 类型空间e i 。 例如， 例2 . 1 中 任一投标人的 类型空间 不 蔽 r7 f 革 蔽荻# 7 丽 0 万 飞d a 9 r 关 系 ， 有 时 专 门 定 义 一 个 效 用 西 数 u: 。 叶 “ 来 表 示 决 策主休的偏好. z古典的机制设计 为!0 , 州】 ， 这里州 为拍 卖中 价格的 上限。 投 标人的 类型 可以 是 。 到州 之间的 任意整 数。 对于博弈的结果，我们也可以定义相应的结果空间口。考虑到每个代理的偏好 是跟博弈的结果。e 0相关的，比如讲在例2 . 1 中，我们可以把结果描述成n 维向 量 ( 0 , . . . , 1 ， 二 ， ， 0 ) ( 第 位为 1 ) ， 表示第i 个投标人赢得了 拍卖品。 那么每个投 标人的收 益是跟结果相关的。第i 个投标人的收益是:。 二v i 一 p m a z ， 而对于不同于 的投标人 7 来讲，收益为。 。 所以 代理的 偏好的 确是与博弈的结果相关的。我们利用把每一个可 能的结 果 与一 个效 用函 数联系 起来的 效 用函 数- f ( o ) ， 来 描 述 参与 人 的 偏 好。 在 机制中， 代 理的 效 用u i 不仅跟结 果。 有关， 还 跟代理的 类型0 有关 ( 在 例2 .1 中 0 , = v i ) - 所以 代理的 偏好可以 描述成类型和结果的函 数. 我 们定义u i ( o , 幻 为 代理艺 的偏 好( 效 用函 数) ， 给定 两个结果o 1 , 0 2 e q ， 如 果u i ( a l , e i ) u ; 伽， 氏 )那么可以 说类型为o i 的 代理i 相比 较而言更喜欢0 1 一点。 博弈论中有关代理进行选择行动的一个重要概念就是策略: 定 义2 . 1 ( 策 略 ) 策 略是一个完整的 相机行动方案或决策规则，它 规定了: 参与 人 ( 代 理)在轮到她行动时，她将如何行动。 用s i ( b i ) 任 公 来 表 示 类型为b i 的 代理i 的 策 略， 其中# 表示 代理i 的 策 略空 间 。 因为有些时候代理的类型是隐含在上下文中 的， 所以 如果在上下文不引 起歧义的话， 我 们用 来表示代理i 的策略。 代理的策略既可以是纯策略，又可以是混合策略。 混合策略是指代理用一定的概率 来 选择 若干 可 行的 策略。 由。 个 参 与人的 每一 个策略 组 合， =( s 1 , , 8 n ) ， 可 得到 博弈的一 个结 果。 因 此， 对于任意策略组合( 3 1 , , s , ) , 我们可以 推出 每一个参与 人得到的效 用。所以， 我们可 以 用策略以 及与其联系的 效用来直接规定博弈. 定义2 . 2一个博弈由以下 几个部分组成: 有限的 参与人 集合n( ii ( i =司; 每一个参与人i e n规定了 一个非空策略集s i ( 其中 策略r , e s i ): 对每一个参与人i e n , 规定了 一个建 立在 集合s = x j e v s j 上的效 用函数 。 扣 1 , . , s n ) 。 该 效 用函 数 给出了 与 策 略( 3 1 . . . . . . n ) 产生的 结 果 相联系 的 效 用， 正 式地， 我 们把 博 弈写 成勤 =囚， s , u ) ， 这里u=x j f i v u j e 2古典的机制设计 2 . 2解的概念 博弈论中 有许多 解的概念 ( s o l u t i o n c o n c e p t )， 在经济学中应用的 最广泛的解概念就是 纳 什均衡 (3 司 。 假定有 n 个 人参与 博 弈， 给定其 他参与 人策略的 条 件下， 每个 人 选择自 己的最优策略， 所有参与人选择的策略一起构成一个策略组合，这样一种策略组合就称 之为纳什均衡.这种策略组合由 所有参与人的最优策略组成，也就是讲，别人策略给定 的 情况下， 没有任何单个参与人有积极性选择其他策略，从而没有任何 人有积极性打破 这种均衡。 我们用3 =( 3 1 ， 二， ) 来 表示 所有代理的策略组合， ， 一 =( 3 1 ， 二， 3 i - 1 , 3 i + i , ， ) 来 表示除 代 理i 以 外的 策略 组合， 其中。 =万 表 示 代理 的 数目 。 接下 来我 们给出 纳 什 均衡的定义。 定 义2 . 3纳什均衡 1 一个 策略 组合s =( 3 1 , . . . , 3 n ) 构成博 弈cj n=以 s , v 1 的 纳什均 衡， 如果 对每一 个i 万对所有s i c s i ， 有 u i ( s i , s - i ) _ u i ( 9 , s - i ) 为了 加强对纳什均衡的理解，我们引入一个叫最优反应的概念: 定 义2 .4!最 优反应 1 在博弈卯 =n, s , 明 中， 策略s i 是 代理 刘竞争对手策略3 - i 的一个最优反应，如果刘所有成 凡， 有 u i ( s i , ， 一 、 ) u i ( 3 1, s - i ) 引入代理的最优反应这个概念后，我们可以得到对纳什均衡概念的一个更紧凑的表 述。 正式的 说， 我 们称在博 弈9 n=n, s , 阴 中， 代理 的最优 反应几: s - i *s i 是 把集合 r i ( s - i ) = ( 3 i e 又: u i ( s i , 3 - i ) ? u i ( s i , 3 - i ) ，对所 有5 ; 又 指派给每个3 - i 任 s - i 。 有了 这个概念，我们就可以 把纳什均衡的 概念重新表述如 卜 : 策 略 组合( 3 1 , . . . , s rz l 是 博 弈j( n=阿i s , 明的 一个 纳什 均衡， 当 且 仅当 对v i 万， 有 s i e r i ( s - 小 从纳什均衡的更紧凑一点的表述来看，我们知道纳什均衡不仅要求侮一个代理完全 清楚的知道其他代理的偏好和策略，而且彼此理性作为所有代理的共同知识。这里彼此 理性是指每一个代理知道别的代理知道自 己的偏好和策略.所以讲，纳什均衡假定了代 理的策略是刘某个关于竞争对手将如何选择的合理猜想的一个最优反应。然而我们知道 2古典的机制设计 机制设计是不完全信息博弈，而在不完全信息博弈中，这样的假定并不适用。为此，这 里必须提出 一个更强的解概念一一占 优策略均衡。在一个占 优策略均衡中， 每个代理都 会执行相同的使得自身利益最大化的策略。 定 义2 .5( 占 优策略 ) 在博 弈卯 =囚， s , 明中， 代理i 的 一个策 略s i e 又是 她的占 优 策略， 如果 对 所有s ti ， 和 所有。 _ s - i ， 都有 u i ( s i , 8 - i ) ? u s ( 4s - i ) 用普通语言来表述就是， 策略。 ， 是代理 的占 优策略， 如果对于别的代理可能 选 择的任何策略， 它能使代理i 的 效用最大化。 我们用一个例子来解释占 优策略. 例2 .2二级 密封价 格拍卖 v i c k r e y 拍 卖) 在这 个拍卖中 有一个拍 卖品， 而这 个拍 卖品 将 以 次高的 价格卖给出 价最高的 人。 给定投标人 的心里价位v i ( 对应代理的 类型). 投 标 人 的占 优策略 是s i ( v i ) 二 。 。 这 是因 为 投 标人的 效 用函 数为 产!、.、 - v i ( b i , b , v i ) ; 一 d 这里 y指的是所有其他投标人中的最高出价。 如果s i n 否则 当投标人 i 的心里价位 的 最优策略为。 i b ， 而当v i b 时， 的出价s i b 时， 显 然 无论处于哪种情 价格能使她自己 占优策略均衡是一种非常强的解概念，因为它既不要求任意一个代理知道别的代理 的确切类型，也不要求彼此理性是所有代理之间的 一种共同知识. 而且它也并不要求代理相信其他代理都会理性的选择最优的策略。当考虑机制设计 问题时，一般认为社会选择函数 ( s o c i a l c h o i c e f u n c t i o n )的占优策略实现要比 纳什均 衡理想。 另一种解概念就是贝叶斯纳什均衡。在贝叶斯纳什均衡中，每个代理只知道其他代 理类型的概率分布而不清楚其他代理确切的类型.所以博弈中的策略组合是跟类型的概 率分布有关的。类似于纳什均衡，每个代理也是选择使得自己效用最大化的策略，在只 知道对方的类型的概率分布的情况一 f e 定 义2 . 6 贝叶斯纳什均衡卜 一 个策略组合: = ( s r ( ) , . . . , s( - ) 称之为贝叶斯纳什均衡如 果对每个代理i 和i 所有可能的类型b i e o i , u i ( s i ( b t ) , s - i ( ) , e i ) 2 u i ( ; ( b i ) , ， 一 ， ( ) , o s ) ，对所有 。 ; ( 今 笋s i ( 今 2古典的机制设计 在这里4 b ; 表示在类型的 概率分布f ( 的 下的 期望效用。 比 较贝叶斯纳什均衡和纳什均衡，可以发现两者关键的不同在于，在贝叶斯纳什均 衡中， 任意一个代理的 策略都是刘其 他代理类型分布概率的最优反应， 而纳什均衡中， 任意一个代理的策略都是刘其他代理实际的策略的最优反应。 贝叶斯纳什均衡的假设比纳什均衡更加合理，不过从解概念的角度来讲，贝叶斯纳 什均衡要比占优策略纳什均衡要弱。 这三个解概念在动态博弈和静态博弈中都适合。在静态博弈中，所有代理同时做出 行动 ( 比 如说二级密封价格拍卖)。在动态博弈中，代理交替行动， 所以每个代理都可 以通过观察其他代理在之前的行为来了解其他代理的偏好的信息. 下一小节将介绍机制设计，一个理想的机制设计能实现占优策略均衡和解决与此相 关的分布式优化问 题。我们可以根据解概念的强弱对三种解概念排个序， 依次为，占 优 策略r 贝叶斯纳什f 纳什。实际上纳什均衡解在机制设计中几乎可以说是完全无用的除 非博弈各方的偏好是共同的知识。 2 . 3机制设计:一些重要概念 机制设计问 题概括起来讲就是在不完全信息非合作博弈的分布式系统中来解决一个系统 的优化问题。在不完全信息博弈中，每个代理对系统分配方案的偏好都是由一个类型 e ; c e ; 来 确 定 的 。 对 于 这 样的 偏 好 ， 可 以 用 函 数u ; ( o , o i ) 来 表 示 。 机制设计的目 标就是依据代理的真实类型来选择最优分配方案。 这个目 标在经济学和博 弈论中称之为社会选择函数。 定 义2 .7 ( 社 会选择y9 数 ( s o c ial c h o ic e r l n c t i o n ) ) 在给定类型组合b =( e 1 ， 一 ， 0 1 ) 的 情形下， 社会选择函 数f : 0 1 , ， 街*o选择某个结果f ( b ) e o a 实际上，机制设计问题是对游戏规则的确定，比 如讲， 机制设计可以规定那些策略 是合法的 那些是不合法的， 也就是可以限制代理只能采取某些规定允许的策略;机制设 计也可以决定用那一种方法来选择社会分配方案，也就是定义从 夕 到 0的映射，尽管 这种映射是不能任意指派的，因为要考虑到每个代理是自 利的，如果社会选择函数损害 了 任意一个代理的利益，该代理都可以 选择不参加博弈。 定 义2 .8 ( 机制) 一个机制m二( e 1 ， 二， e n , 9 ( -) ) 给每个代理定义了可能的策略空间 e ; 和 一个结果选择规则9 e 1 ， 二， e n *o ，使得9 ( s ) 是 机制实现的针对策略组合 “ 二( 3 1 , , 3 n ) 分 配 方 案 。 2古典的机制设计 所以说， 机制定义了 可行的策略。井且机制规定了 基于代理策略组合的分配规则. 例2 .3还是举单个拍卖品的拍卖的例子。在这个拍卖中， 可行策略就对应于 “ 出价必须 高于 底价” 这一机制规定。 否则的话， 拍卖方 就会亏本， 在自 利的假设下， 交易就不会 成功。 对应的结果 选择函 数规则就是拍卖品只卖给出 价最高的人。 可以 用博弈论 来分析 机制的 结果规则。 给定 机制m和相 应的 结果函 数9 ( ) ， 如 果 机制基于策略计算出来的结果是某种均衡，并且这个均衡的解恰好是社会选择函数选择 的 结果f ( b )那 么 就 称 机制实 现了 社 会选择函 数。 定 义2 . 9 ( 机 制 实 现 ( m e c h a n i s m i m p l e m e n t a t io n ) ) 机制m=( # i , . . . , # n , 9 ( ) ) 实 现社 会选 择函 数f ( 0 ) 如 果 9 ( 3 1 (0 i ) , 一s . (9 ) ) = f (0 ) 对 于 所 有 的但 ; ， 一， 8 ) e 6 1 x x 。 。 ， 这 里 策 略 组 合 (si,.-,4)是由 机制引 导的 博 弈 均衡解。 这里的均衡解没有给出明确的解释， 可以是纳什均衡解，贝叶斯纳什均衡解和占优 均衡解或者其他一些解概念，只要是解概念足够强就可以了。 为了明白 机制设计问 题的难度，让我们先来看一个简单的机制，这个机制的目 标 是实 现某个社会选择函数 f ( b ) . 首先 机制要求每个代理汇 报自 己 的 类型， 然后根据 他 们的 汇 报的 类型 来 计 算 g ( b ) =f ( 0 ) 。 但是 代 理并 没 有 理由 要 汇 报真 实的 类型 给 机制 ， 不 失 一 般 性 ， 假 定 汇 报 的 类 型 为 9 ， 那 么 机 制 实 际 上 实 现 的 9 ( 3 ) 二 f ( 称并 不 是 想 要 实 现 的 f ( b ) 。 在下 一小 节里， 我 们将 要讨论 怎么 解决这 个问 题. 2 .3 . 1社会选择函数的属性 许多机制的特性都是通过机制实现的社会函数的属性来实现的。 所以首先概括一下社会 选择函数的属性。 一个社会选择函数是帕累托最优的如果该选择函数实现了一个分配方案使得没有另 外的分配方案能让在所有代理的效用都不减少的情况下，至少有一个代理的效用会增 h a a 定义2 . 1 0 ( 帕累 托 最 优( p a r e t o o p t i m a l ) ) 社会选