基于机制设计理论的一些最优化问题的研究

1、基于机制设计理论的一些最优化问题的研究 瘩微太学硕士学位论支题 目基孟扭剑遮盐望诠的些量盐丝闼题鳗噩.窀.:士研究方 向让墓扭敛鱼周.、姓名、届别樊晓垂 .呈壁。二五 四年 月摘要摘要机制设计是微观经济学和博弈论的子领域,考虑如何很好地执行系统范围问题的解。计算机科学种研究与计算机互相联系的协议和算法有关。这样一个算法的设计者通常做出某个隐含的假设,即所参与的计算机将充当接受指令的角色?也许这些指令是除去错误或恶意的指令。随着网络的出现,这个假设不再认为是理所当然的。网络上的计算机属于不同的人或组织,并且将执行最利于它们主人的工作。我们不能仅仅期望网络上的每一台计算机一定会执行设计好的协议算法

2、。而此时,更加合情理的是,期望每一台计算机将试图为主人的利益而运行。作为这样的参与者即操纵算法的代理,算法设计者应事先确保代理的利益通过真实报告是最大的。本文引用了机制设计的概念,提出了研究这样算法的框架。在这个模型中,算法解与参与者的支付有关。支付应选择那些激励所有参与者真实报告的支付。首先,本文介绍了机制设计基本的概念和基本性质;然后,本文又将机制设计的标准工具机制应用到解决最短路问题和最小支撑树问题。最后,本文讨论了任务分配问题。我们提出几个定理,包括近似机制,下界和随机机制。关键词:机制设计;机制;最短路;最小支撑树;任务分配弭穗 工 垃。锄 . ?时血.啪 州?,廿 。腩 .曲 .雌

3、协 姆 删. 行印 . 州, 疵; . 疳如, .舯.,恤 硎血 如.也 也嫡弘硝.,叩 .,印也 啪血订., , 印 .:印;迁; ;符号约定符号约定结果结果集, 代理的类型代理的类型集代理的效用社会选择函数机制代理的策略集结果函数“几;西 策略代理的支付配置配置集、一 代理的估值代理的支付函数代理的外部效用,“砥 图权独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获瞰夫啤或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献

4、均已在论文中作了明确的说明并表示谢意。签字日期:;。时年岁月,。日学位论文作者签名:裂晚杳学位论文版权使用授权书本学位论文作者完全解童缸夫竽有关保留、使用学位论文的规定,有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和借阅。本人授权复蝴可以将学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密的学位论文在解密后适用本授权书学位论文作者签名:硬吃奇 导师签名 翻舞辛袁签字日期:;一一年士月口日签字日期:酊 年月日学位论文作者毕业去向工作单位:电话:通讯地址:邮编:第一章绪论第一章绪论.引言机制设计是微观经济学和博弈论的分

5、支领域,研究的是对涉及多个自利代理的问题,其中每个代理都有对偏好的个人信息,如何执行一个好的系统范围内的解。在机制设计问题中,对于输入的具体信息,系统范围的目标就是求解的一个具体的最优化问题。考虑这样一个例子,网络路径问题,系统范围的目标是如何分配资源以使得所有代理的延迟时间总和最小,但是每个代理只提供关于私人信息的参数如信息量的大小和延误损失单位值。机制设计中典型的方法是提供激励例如适合的支付以改善代理的真实显示,从而能计算出实际问题的最优锯。机制不仅在经典机制设计中具有十分重要的地位,而且在可计算的机制设计中也十分重要。确实,机制在我的论文里也占据举足轻重的位置。我们可以利用机制解决许多最

6、优化问题,比如组合配置问题等。机制主要研究了从离散结果中选择使所有代理总估值最大的一个结果的优化问题。机制是具有许多的好的性质,比如它是防策略操作的,即无论其他代理的策略和偏好是什么,偏好的真实显示的结果总是占优策略真实显示都是最优的。近几年来,机制设计已经发现了许多重要的应用领域,如电子市场的设计,分布任务分配问题,组合资源配置问题等等。.机制设计理论简介机制设计是微观经济学和博弈论的分支领域。对一个出售商品的卖者,给定众多的可供使用的出售商品方式,如果他的目的是最大的赢利,即得到一个最高的卖价,他应该选择何种方式出售自己的商品昵这就是机制设计问题。机制设计是一种特殊的不完全信息博弈。当卖者

7、在选择出售商品的方式时,他事实上是在选择或设计一个博弈规则。除了上面的商品拍卖外,机制设计的例子还有垄断企业定价,政府税收政策的制定,政府对垄断企业的规置,茎三型堡兰里丝堕二些墨垡些塑壁竺竺塞公共产品的供给,雇主对雇员的职位安排,保险公司的收费和赔偿政策,等等。在所有这些例子中,有一个“委托人”和一个或多个“代理人”:委托人的支付函数是公开的,称为共同知识,代理人的支付函数只有代理人自己知道,委托人和其他代理人不知道。比如说,在一级密封价格拍卖中,卖者不知道买者对被拍卖品的评价;在双方叫价拍卖中,拍卖人不知道买者的评价,也不知道卖者的供给成本;在垄断企业定价中,垄断企业不知道消费者愿意付出的最

8、高价格;在征税中,政府不知道纳税人的能力。委托人当然可以直接要求代理人报告自己的类型,但代理人不可能会说实话,除非委托人能提供给代理人足够的激励货币的或非货币的。因为提供激励是有成本的,因此,委托人面临着成本与收益的平衡问题。委托人是在选择一个机制,而不是使用一个给定的机制,这是机制设计的一个基本特征。正是从这个意义上,我们说委托人在设计一个博弈规则包括代理人的行动空间。比如说,在垄断定价中,垄断企业设计一个价格表,依赖于其购买数量,规定消费者如何支付的价格。委托人设计机制的目的是最大化自己的期望效用函数。但他这样做时,必须面临两个约束。第个约束是,如果要一个理性的代理人有兴趣接收委托人设计的

9、机制即参与博弈的话,代理人在该机制下得到的期望效用必须不小于他在不接受这个机制时得到的最大期望效用。这个约束被称为个人理性约束或参与约束 。代理人在博弈之外能得到的最大期望效用称为代理人的保留效用:因为代理人参与博弈时他就失去了博弈之外的机会,因而保留效用又称为机会成本。在设计机制时委托人要考虑的第二个约束是,假设委托人不知道代理人类型的情况下,在所设计的机制下,代理人必须积极地选择委托人希望他选择的行动。显然,只有当代理人选择委托人所希望的行动时,所得到的期望效用不小于他选择其他行动时所得到的期望效用时,代理人才积极地选择委托人所希望的行动。这个约束被称为激廨相容约束 。满足参与约束的机制称

10、为可行机制;满足激励相容约束的机制称为可实旌机制 。如果一个机制满足参与约束和激励相容约束,我们说这个机制是可行的可实施机制。委托人的问题是筮二兰堕笙如何选择一个可行的可实施机制来最大化他的期望效用。典型的机制设计可分为三个阶段的不完全信息博弈。在第一阶段,委托人设计一个“机制”。这里,机制是一个博弈规则,根据这个规则,代理人发出信息如买者报价,实现了信息决定配置结果如谁得到被拍卖品,支付什么价格。在第二阶段,代理人同时选择接受或不接受委托人设计的机制。如果代理人选择不接受,他得到外部的保留效用。在第三阶段,接受机制的代理人根据机制的规则进行博弈。在第一阶段,对应于不同的情况,机制设计一般要涉

11、及到几个不同的解概念的定义,如纳什均衡概念适用于静态博弈,而不适用于完全信息的动态博弈分析一样,贝叶斯均衡概念是一个较弱的概念。然而,根据梅耶森,的显示原理,为了获得最大的期望效用,委托人只须考虑“直接机制”肌:在第二阶段,所有代理人都接受所设计的机制;在第三阶段,所有代理人同时如实地报告自己的类型这里,“直接”指的是代理人的策略空间等同于类型空间。这一点意味着,委托人可以通过代理人直接的静态贝叶斯博弈来获得最大的期望效用。.机制设计理论的发展机制设计理论开始于上世纪年代关于市场社会主义经济机制的可行性的大论战。所以说,它的历史可以追溯到上世纪大约年代至年代,经济学家就开始研究机制设计的理论了

12、。在经济学中,利用机制设计理论,经济学家能系统地比较各种经济制度的优劣,研究不同的经济制度是如何影响人们的相互行为和资源配置的结果。经济机制理论的优点是可以把所有的经济机制集中在一起进行研究。它研究的对象大到对整个经济制度的一般均衡设计,小到对某个经济活动的激励机制设计。这个理论的基本框架是由美国经济学家利奥?赫维兹 首先严格地给出的。它可用来研究和探讨各种经济问题,特别是在不完全信息情况下探讨和设计各种激励机制,以实施所要达到的社会或某个既定目标。随着计算机技术的发展,互联网逐渐进入了寻常百姓的生活。上世纪苎王型型丝盐墨堡塑二些星垡些囹矍塑里垄年代,电子商务开始蓬勃发展起来。于是,一批计算机

13、科学的学者和数学家开始介入机制设计的研究中,他们的目的是想利用机制设计的理论帮助解决电子商务中的一些算法设计问题。早期的讨论集中在显示机制,每个代理对委托人报告他所知道的选择。后来,发现针对公共物品分配的规则和针对私有物品分配的规则都不是防策略操纵的,即所有代理报告真实信息是不对称的。对于准线性公共物品环境,和设计了防策略操纵的显示机制。但是,除了真实均衡,防策略操纵显示机制的结果有可能是不想要的非真实均衡,这种非真实均衡只要通过在更一般的信息空间中讨论就可被去除。在一般信息空间的机制设计的研究是由、和开始的。.机制设计的研究现状虽然机制设计理论的是一个正在发展的研究理论,但是他的进展速度还是

14、很快的。下面我们简单介绍一下机制设计理论研究的现状,这些研究主要集中在国外的计算机系中。以色列希伯来大学的和,在一定程度上,已经将近似算法、有限理性代理和机制设计联系起来了。他们研究以下几个方面:将近似赢家决定算法和近似机制联系起来;用近似赢家决定算法改善激励相容性;“可行占优”概念,即描述一个拍卖,给定可能策略的一个子集,真实显示在这个拍卖中是最优的。在他们的研究中缺少代理估值和偏好显示的考虑,因为他们将讨论的重点放在了赢家决定和策略行为上了。类似地,.】也研究了一个逼近赢家决定算法所需的性质。】还考虑了出价语言的表示和有效性之间的关系,并提出了具有性质容易组合的语言。最近。和“】也考虑了拍

15、卖中简明出价语言的重要性。美国斯坦佛大学的和研究了拍卖机制的信息流通的复杂性,比较了重复拍卖和单次密封拍卖。瑚】和提出了对于重复组合拍卖砧出的设计【,】。和之间的主塑二兰丝笙要区别是价格和价格更新的结构。其他重要的研究还有和埘】,和【,】。能够在一些问题中获得支付。由最近的分析,提出了方法的.解释。.方法最初是为了解决分配问题而提出的。【】和也讨论了在一般问题中计算支付的线性规划模型。美国卡耐基梅隆大学的】已经提出许多方法处理分布系统中有限理性和对策理论上所涉及的内容。最近,和】又已经研究了均衡中商议模型。机制设计的一些应用机制设计不仅理论性强,而且也有十分广泛的应用,可以说,机制设计理论很好

16、地将理论和实际应用结合起来。下面我们来看一下它的一些应用。令动态资源配胃。带宽分配问题就是一个动态资源配置问题。夺课程登记。每个学生想要登记一组课程,但不能有时间冲突。夺航空着陆和起飞安排【】。有限的航道需要提供给飞机起飞和降落,如何安捐起飞时间和降落时间呢这也需要机制设计理论的帮助。夺频段分配问题。要求获得一个有效的新频段的配置。夺协作计划【】。考虑一个机器人系统,它希望完成一组任务,且目标是在一个低的总值下完成任务。夺供应链调和、矿】。考虑分配零件到竞争的制造商的问题。每个制造商需要零件组合的供应。.选题背景计算机科学主要是研究有关计算机相互连接的协议和算法。通常个算法的设计者隐含地有这种

17、假设,即所有连接的计算机将充分地接受指令?除了基十制制砹计埋论的一些最优化瑚般的斜咒错误或恶意的指令。随着互联网的出现,这个假设不再认为是理所当然的。互联网上的计算机属于不同的人或组织,并且都执行最利于它们所有者的工作。所以,我们不能只是期望网络上的每一台计算机一定会执行设计好的协议算法,一个更合理的期望是每一台计算机将尽量为拥有者的利益而运行。因此,这样一种算法或协议必须为这种行为而设计。例如:负载平衡。网络上所有计算机的资源是巨大的。我们希望这些资源能在所有在线的处理器中,最佳地被分配。可以想象,把密集的工作自动地转移到服务器中,自动地由计算机的空闲磁盘空间完成这项工作。数据,光纤,甚至外

18、置设备都能在网络中最佳地被分配。显然,这是一个困难的最优化问题。网络上,同类型的分配需要知道一个额外的问题:资源属于不同的人群,而这些人不允许其他人自由地使用它们。这样,算法需要提供一些激励,让所有者参与进来。信息传送。当一台计算机希望传送信息到另一台时,数据通常通过不同的路由器而传送。路由器读取每一个数据包中的地址然后决定如何传送。到目前为止,这个任务已经能够被自愿地完成了。然而,当大量的数据进行通讯时例如,视频数据,则需要在不同的服务质量的协议下保留带宽,路由器的利他行为可能就不再保持了。如果是这样,我们将必须特别设计考虑到路由器自利的协议。.论文的研究内容及安排在这篇论文里,我们提出一个

19、正式的模型来研究优化算法。这种算法假设所有参与者部按照自己的利益而工作。我们采用一种方法,使用来自博弈论和微经济学中的概念,特别是利用了机制设计的领域中一些概念。我们假设每个参与者都有一个定义好的效用函数,这个效用函数表示了算法可能输出的偏好。假设参与者为了自己的利益能合理且充分地利用其有用的东西,则称这样理性、自私的参与者为代理。我们所考虑的解决方法包含算法成分和激励代理第一苹绪论的支付成分。这样的解决方法称为一个机制。我们提出一个正式的模型来研究最优化问题。这个模型是基于机制设计领域的。这个模型里的问题,除了输出的详细情况外,还有代理效用的描述;除了算法产生想要的输出外,机制还产生了激励参

20、与代理的支付。我们观察到,机制设计的已知技术,提供了几个基本最优化问题的解决方法。特别地,我们提出了对于最短路问题和最小连接问题的解决。在这两个问题中,每条边可以属于不同的代理。我们利用机制设计理论来研究一个重要的最优化问题?任务分配问题。内容如下:.设计一个疗一近似的机制,这里是代理的数目。证明近似率的下界为,且近似率能够由任何机制获得。这个界限对于两个代理的情况是紧的,但对于更多代理的情况,则会留下一个空隙。.设计一个随机机制,这个随机机制打破了确定性的下界。基于机制设计理论的一些最优化问题的研究第二章机制设计理论机制设计问题是将一个最优系统解实施到一个分散的最优化问题中,即一些具有私人信

21、息的自利代理的问题。而代理类型的概念,只,它决定了在不同结果上的偏好,即“,只是对于结果,具有类型只的代理的效用。机制设计里系统目标定义为社会选择函数,它选择了给定代理类型的最优结果。定义社会选择函数社会选择函数厂:。?,给定类型臼佾,?,目,选择结果厂。换句话,给定代理类型占,?,研,我们想要选择结果厂。机制设计问题是实施“博弈规则”。例如,定义用于选择基于代理策略的可能策略和方法,以实施社会选择的解,不管代理是否自利。定义?机制机制蹦。.,?定义了每个代理可获得的策略集,和结果规则:。?.,斗,使得对于策略数组,?,是由的机制实施的结果。简而言之,机制定义了可获得的策略如在最小的询问价上报

22、价,和基于代理策略选择的最终结果如价格递增到仅有一个代理报价时,然后物品以报价卖给了代理。而博弈论则用于分析机制的结果。给定具有结果函数的机制,如果用代理的均衡策略计算出的结果是社会选择函数关于所有可能代理偏好的解,那么,我们说机制实旄社会选择函数厂。定义?机制实施如果对于所有的?.,岛,?,第二章机制设计理论积?,:,厂,那么我们说机制,.,实旌社会选择函数厂,这里策略组合:?。;是由诱导的博弈的均衡解。为了理解机制设计问题为什么是困难的,我们考虑一个非常简单的机制。假设系统范围的目标是实旌社会选择函数/。机制询问代理以报告类型,然后简单地实旋对应于报告的社会选择函数的解,即给定报告的类型痧

23、:慨,.,谚,结果规则等同于社会选择函数,修厂舻。但是,代理没有理由报告其真实的类型在贝叶斯纳什均衡中,给定关于其它代理类型的分布信息,并假设其它代理也紧跟期望效用最大化的策略,每个代理将选择宣布类型臼。,使期望效用最大,并解得:学警%,%柳,缸。铂。这个被宣布的类型莎不需要等于代理的真实类型。机制设计问题是设计一种机制?可能的代理策略集和结果规则?在尽可能强的解概念中,以实施一个具有理想性质的社会选择函数。.社会选择函数的性质机制的许多性质是按照社会选择函数陈述的。一开始,本文将概括地叙述许多社会选择函数的理想性质。社会选择函数是帕累托最优或者帕累托有效,如果在均衡点所有的参与者的效用总和达

24、到最大。定义.帕累托晟优社会选择函数,是帕累托最优的,如果对于每一个厂,所有类型。.,研,有虬,只“。,只 可“,。,“, 基于机制设计理论的一些最优化司题的研究换句话说,如果一种机制具有占优策略均衡和社会盈余的话,这种机制就被称为是帕累托最优的。即在均衡点所有参与者的效用的总和达到最大化。更形象的说,如果其中一个代理要得到最大的效用,那么其他代理的效用一定要减少,这就构成了帕累托最优。拍卖理论和机制设计中,一个非常共同的假设是代理为风险中立的,并有准线性效用函数。定义.准线性偏好具有类型目,的代理的准线性效用函数,具有形式:峨,只。,只一这里结果定义了来自离散选择集的选择,和由代理所支付的。

25、具有准线性偏好的代理类型定义了估值函数,即每个选择的值。在一个配置问题里,可选集表示配置,平移量表示拍卖者的支付。准线性偏好直接通过代理经旁支付转移效用。例如。单物品拍卖中,结果定义了配置,即代理得到物品和每个代理的支付。假设代理有值,那么对于一个结果所分配的效用是“,一?,代理关于这个结果有正效用,只要。保持风险中立性,因为期望效用最大化的代理将支付和一个物品的期望值一样多。例如,在代理以概率万且估值接受此物品的情况中,代理将愿意为这个项目支付石。用准线性代理偏好,我们能将社会选择函数的结果分解为一个选择和由每个代理所做出的支付,:厂?,在具有准线性代理偏好的机制中,结果规则,分解为一个选择

26、规则七,即从给定策略组合的选择集中做出一个选择,和个支付规则,第二二章机制设计理论即对于代理,基于策略组,选择一个支付。定义.准线性机制一个准线性机制睚,.,毛?,定义为:每个代理可获得的策略集。;一个选择规则:。.,一,使得七是实施策略组置,?,的选择;对于每个代理,转移规则。: .,寸,计算由代理所做的支付,。由一个机制实施的社会选择函数的性质现在可以被分开陈述为选择和支付。一个社会选择函数是有效的,如果:定义.配置有效社会选择函数厂是配置有效的,如果对于所有偏好护,?,研,慨,有,;只。,拉一般将这个定义陈述为配置有效的,因为选择集通常定义一件物品到代理的配置。有效配置使所有代理上的总值

27、最大。一个社会选择函数是预算平衡的,如果:定义.预算平衡社会选择函数,是预算平衡的,如果对于所有的偏好目积,.,舅,有。换句话说,没有净利转移出系统或者转移出系统。综合起来,配置有效和预算平衡隐含了帕累托最优性。一个社会选择函数是弱预算平衡的,如果:基十机制设计理论的一些最优化问题的研究定义.弱预算平衡社会选择函数厂是弱预算平衡的,如果对于所有偏好口慨?.,岛,有换句话说,能够有个从代理到机制做出的净利支付,但没有从机制到代理的净利支付。.机制的性质最终,我们能定义机制理想的性质。在描述机制性质时,必须陈述解概念,如贝叶斯纳什均衡,占优均衡等等;代理偏好的范围,如准线性,单调性等等。定义十分自

28、然地紧跟实施概念见定义.和社会选择函数性质。如果机制以性质尸实施社会选择函数,则机制有性质。例如,考虑帕累托最优机制的定义:定义.帕累托最优机制如果机制实施柏累托最优社会选择函数厂则机制是帕累托最优的。技术上,这是事后帕累托最优,即对于特定的代理类型,结果是帕累托最优的。帕累托最优的弱形式是事前的,即对于代理偏好上的一个分布,结果是期望的帕累托最优。相似地,机制是有效的,如果它选择使得总值最大:定义.“有效机制如果机制实施一个配置有效的社会选择函数,机制是有效的。对应定义紧跟预算平衡和弱预算平衡。在预算平衡情况中,区别事前预算平衡和事后预算平衡是很重要的。第二章机制设计理论定义.事前预算平衡如

29、果对于代理偏好上的一个分布,在期望中均衡净利转移到机制是平衡的,则机制是事前预算平衡的。定义.事后预算平衡机制是事后预算平衡的,如果对于所有代理偏好,均衡净利转移到机制是非负的。机制另一个重要性质是个体理性,有时称之为“自愿参与”约束,即允许代理不受强迫地去参与机制,而且能够决定是否参与。本质上,个体理性约束期望效用的水平,这个效用是一个代理从参与中接收到的。设玩表示当代理类型是只时,它从机制外获得的期望效用。个体理性的最自然的定义是过渡时期个体理性,即一个代理的期望效用至少是它期望的外部效用,而这个代理知道自己偏好且仅有关于其它代理偏好的分布信息。定义.个体理性机制是过渡时期个体理性的,如果

30、对于所有偏好只,它实施社会选择函数,有“,咿,矿。玩这里给定关于其它代理偏好目一。的分布信息,虬驴,晓,是代理在结果上的期望效用,瓦是不参与机制时获得的期望效用。换句话说,如果给定对于其它代理偏好的先验信任,参与的代理总接收和没有参与时一样多的期望效用,那么机制是个体理性的。在代理能退出的机制中,旦代理知道结果,事后个体理性更适合,即从参与中获得的代理期望效用必须至少是最佳外部效用。在代理必须选择参与的机制中,甚至是在代理知道自己偏好之前,则事前个体理性是适合的,即机制中的代理期望效用必须至少是没参与时的期望效用。最后一个重要的机制设计性质是激励相容性,是为直接显示机制定义的。激励相容性和直接

31、显示机制的概念在机制设计中非常重要,在下一节中集中讨论。基于机制设汁理论的一些最优化问题的研究.显示原理,激励相容和直接显示显示原理陈述:在十分弱的条件下,任何一个机制能被转化为激励相容的直接显示机制,使得它实施同样的社会选择函数。这被证明是一个强有力的理论工具,产生机制设计重要的可能和不可能结论。在直接显示机制中,代理所获得的唯一行为是将其偏好直接报告给机制。激励相容机制是直接显示机制。在这个机制中,代理报告关于均衡中其偏好的真实信息。激励相容性抓住设计机制的本质以克服代理的自利性?在激励相容机制中,代理将选择真实地报告私人信息。例如。对于单一物品配置问题而言,二价密封报价拍卖是激励相容的实

32、际上是防策略操纵的直接显示机制。计算上,显示原理必须谨慎看待。直接显示机制常常对于代理来说代价太高,因为他们十分需要信息揭示。一个重复机制有时能够与一个直接机制实施同样的结果,但它却仅需要较少的信息揭示和代理计算。显示原理限制了我们所能做的,但不解释如何构建一个机制以获得一个特别的性质集。.激励相容和防策略操纵在直接显示机制中,代理可获得的唯一行为是提交关于其偏好的声明。定义.直接显示机制直接显示机制。?,约束了策略集,并有结果规则:。?,规则选择了基于报告偏好舀幢?.,舀,的结果。换句话说,在直接显示机制中,代理的策略是报告类型谚,基于实际偏好只。揭示真实的策略是基于所有可能的偏好,报告关于

33、偏好的真实信息。第二章机制设计理论定义.真实显示如果只,有,只,则策略。是真实显示。在激励相容机制中,均衡策略组驴。,?,使每个代理报告其真实的偏好给机制。首先,我们定义贝叶斯纳什激励相容:定义.贝叶斯纳什激励相容如果真实显示在由机制所诱导的博弈中是贝叶斯纳什均衡,那么直接显示机制是贝叶斯纳什激励相容的,。换句话,在激励相容机制中,均衡中每个代理使期望效用最大化的策略是报告其真实偏好。机制是防策略操纵的或者说占优策略激励相容的,如果真实显示是占优策略均衡:定义.防策略操纵如果真实显示是占优策略均衡,直接显示机制是防策略操纵的,。防策略操纵是博弈理论上和计算上非常有用的性质。占优策略实施是关于代

34、理非常鲁棒的假设,如代理的信息和理性。计算上,不管其它代理的偏好和策略,代理就能够计算最优策略。在直接显示机制中,结果函数侈之间存在一个简单的等式,机制选择基于报告类型百的一个结果和机制所实旖的社会选择函数厂佃。命题.激励相容实施激励相容直接显示机制实施社会选择函数/,这里是机制的结果规则。换句话,在激励相容机制中,结果规则正好是由机制实施的社会选择函数。在.节中,我们将介绍机制,它对于具有准线性偏好的代理,是防策略操纵的有效机制,即给定报告的类型舀,选择规则七活,计算有效的配置,且代理的占优策略是真实显示。基于机制设计理论的一些最优化问题的研究.显示原理显示原理说,在十分弱的条件下,任何一个

35、机制能转化为等价的激励相容直接显示机制,它实施同样的社会选择函数。显示原理对于机制设计中“什么是可能的,什么是不可能”的理论分析,是一个重要的工具。显示原理首先以占优策略均衡阐述。显示原理的一个解释是激励相容的。这不是说真实显示容易获得,但简单地说,如果间接显示和非真实机制解决了分布最优化问题,那么我们也期望直接显示真实的实旌。对于占优策略实施的显示原理来说,用占优策略实旌的任何社会选择函数在防策略操纵的机制中也是可实施的。定理.占有策略显不原理假设存在一个机制直接或者其它,以占优策略实施的社会选择函数,.,那么,.以占优策略真实实施,即在防策略操纵的机制中可真实实施的。证明:如果。.,以占优

36、策略实施,那么由占优策略实施定义,存在策略组?,”,使得臼,和只,有:厂,且“,钆,只甜,.,%,只;,。和一,用二缸,代替一,伶代替;,则乒。和以,。,有%:,旺。只%。,:。仅,最终,由于对于所有的口,有,则参。和以。,有坼厂,以。只%,矿,只这恰是在直接显示机制中以占优策略真实实旌时,厂所需满足的条件。防策第二章机制设计理论略操纵机制中结果规则:鼠.已,仅等于社会选择函数,.。显示原理直观上得到的知识如下。假设它可能模拟非直接机制的整个系统?代理的报价策略和结果规则?给定关于每个代理的偏好的完全且完美信息。现在,如果给定关于代理偏好的信息,声明“模拟者”将忠实地实施一个代理的最优策略是可

37、能的,那么一个代理将其偏好真实地报告给新机制是最优的策略。这个占优策略显示原理是十分引人注意的。特别地,它暗含了要区别哪些社会选择函数是以占优策略实施的,我们仅需要区别那些函数厂。对于这些函数,在直接显示机制中,真实显示是一个占优策略且有结果规则?厂.。同样,显示原理能用贝叶斯纳什均衡陈述。定理.贝叶斯纳什显示原理假设存在机制直接或者其它,它以贝叶斯纳什均衡实施社会选择函数/,那么厂?在贝叶斯纳什激励相容直接显示机制中是真实地实施。换句话说,如果目标是以贝叶斯纳什均衡实旌特定的社会选择函数,只要考虑激励相容直接显示机制即可。证明与占优策略显示原理的证明十分近似。贝叶斯纳什实施的显示原理的一个问

38、题是代理类型上的分布对于直接显示机制是公共知识。. ?机制在早期开创性的论文中,和,提出了?机制族,对于代理有准线性偏好的问题,它们经常简单地被称为机制。机制是配置有效的且是防策略操纵的直接显示机制。在特别的情况中,存在一种机制,它也是个体理性的并满足弱预算平苎兰型堡盐堡丝塑二些墨垡些塑堡堕竺窒衡,使得机制不需要外面的补助金去操纵。例如,组合拍卖中使用?机制。事实上,机制的族特征是,在直接显示机制中,既配置有效又防策略操纵的唯一机制。.功利主义函数机制应用于机制设计最大化问题,这里的目标函数是所有代理值的总和,可能的输出集被限定为有限的。定义.功利主义的一个最大化机制设计问题被称为功利主义的,

39、如果其目标函数满足,目。,。定义?族我们说,一个直接的显示机制,口属于族,如果.。口一。:。谚,。.。,口如伊,这里趣是旦,的一个任意函数。定理.机制是真实的。这样,机制本质上提供了解决任意功利主义问题的方法。机制是功利主义问题的唯一真实实施。相似地,机制的加权版本也会被实施。定义.加权功利主义的最大机制设计问题被称为加权功利主义的,如果存在实数届,?,届,使得问题的目标函数满足,口。屈?舅,。定义?加权族我们说,一个直接显示机制埘。护,属于加权族,如果第二章机制设计理论.口。,口,臼去,盆巳嘭,。妒墨金,这罩穗是馥,的一个任意函数。定理.加权机制是真实的。证明:设反,?,为代理的最后报价,瞑

40、,?,幺表示其真实类型。假设真实报告不是一个占优策略,则存在,口,.,使得,。以,十只心,。以,。以,只心,。以,以,则一只,。叱,包去萎,。叱,只,。叱爿去丢只弋一一两边同乘肛,得蔷只州以矧荟侈,。以“”与的定义相矛盾。口定理.机制唯一性对于所有直接显示机制中,具有准线性偏好和般价值函数的代理而言,机制是唯一配置有效和防策略操纵的机制。显示原理延展其唯一性到一般机制。给定前提是重复机制常常比密封报价机制有更好的计算性质,那么这个唯一性暗示了集中焦点在重复机制上,因为:任何一个重复机制必须实施一个结果,重复机制按占优策略实施获得配置有效。.机制考虑可能选择集,代理有准线性效用函数,使得基于机制

41、设计理论的一些最优化问题的研究%,只,.,舅。这里七,谚是对于可选项七代理的值, 是代理向机制做出的支付。而类型只.是表达代理价值函数的一种简便的方式。在直接显不机制中,对于准线性偏好,我们按照选择规则七:。?,一和支付规则:。?,孵,写出结果规则。在机制中,代理报告类型谚疋,它可能不是真实类型。假设报告的类型舀怜,.,谚,则在机制中,选择规则计算出:五唆,仁,乒选择七。是使所有代理上总报告值最大的选择。机制中的支付规则被定义为:啊幢,一,矽这里向,:一。斗婀是每个代理除了代理的报告类型上的任意一个函数。对于,?的选择是自由的,这就产生了机制“族”的描述。.分析机制是有效的和防策略操纵的:定理

42、.机制对于具有准线性偏好的代理,机制是配置有效的和防策略操纵的。证明:我们证明机制是防策略操纵的,使得真实显示对于每个代理而言是占优策略,配置有效紧随防策略操纵之后,因为选择规则七计算了有效的配置。代理从策略只得到的效用是:虬修。忙侈只一第一二章机制设计理论:。仁谚,如。嘭一砖幢.忽略最后一项,因为囊幢,是与代理所报类型无关的独立项,我们证明真实显示矿只解出:搿卜盼蚺善,金。刚搿卜咖黔钏这里:女陋,矿,是机制选择的结果。代理宣布类型谚的唯一影响是在上,并且代理通过宣布谚只,能使最大,因为机制计算伶,矿,是为了明确地解出:麟,忙,仁,乒真实显示是代理的占优策略,无论其它代理报告的类型矿,是什么。

43、支付,一。,仁,的影响是“使客观的主观化”,即通过代理所报告的偏好,来影响其它代理的选择。这调整了代理的激励与有效配景的系统目标一致,代理想要机制选择最佳系统解,只要给定其它代理的报告和自己的真实偏好即可。支付规则中第一项,磙,能用于获得预算平衡和个体理性。简单地综合起机制中每个代理所做的支付且同样地在代理之间划分是不可能的,因为总支付依赖结果,和每个代理的报告类型。这将破坏机制的防策略操纵十牛。基于机制设计理论的一些角优化问题的研究第三章机制研究两个基本最优化问题.最短路问题.简介最短路问题是优化领域一个最基本的问题。事实上,在优化领域内,很多问题均需要最短路方面的计算,抑或采用部分最短路问

44、题内提出的概念。随着大规模网络模型的发展,经济领域中的物流规划研究发展,如车辆调度或因特网络规划等,更加大了对效率高的最短路模型的需求。如何有效的减少运费以取得最大的效益,使得本领域内的研究具有非常大的现实意义。值得强调的是,最短路问题的重要性己经日渐走出它在优化问题中所扮演的地位和角色。最短路问题的设计与分析也渐成为运筹学领域和计算机领域合作的基石之一。尤其是数据结构的发展和计算机编程技术的进步,已经逐渐使得最短路领域设计更新式大规模的模型成为可能。.定义和名词解释定义.设图,对的每一条边如。,相应地有一个数,。,简记作,。称为边卜,的权。连同在它边上的权称为赋权图。为了说明清楚起见,在赋权

45、图中,一条边的权也说成是它的长。给定一个顶点,称为始点及顶点,称为终点。所谓最短路问题就是在。,道路集合也中,寻求长为最小的路,这样的路称为从。到,的最短路。从,到,的最短路的长记作【,.。.传统算法下面叙述的算法是由得克斯特拉.于年提出的,它第三章机制研究两个基本最优化问题不仅求出从。到。的最短路径,最后所得到的实际上是从.到各顶点的最短路径。先给赋权图的每一个顶点丑一个数称为标号?临时标号简称丁标号或者固定标号简称标号。标号表示从始点到这一点的最短道路长的上界;标号则是从始点到这一点的最短路径长。每一步把某个点的丁标号改变为标号。这样,一旦终点得到户标号,算法停止。若寻求从始点到每一点的最

46、短路径,则最多经一步算法停止是的顶点数。算法的步骤:给始点。标上尸标号。,给其他各点标上标号,?,。在所有丁标号中取最小者,譬如说是。,。,则把点。的标号改为尸标号。重新计算具有丁标号的其他各点的标号:选点的标号【,与。,中较小者作为,的新的标号。一般地,设小,具有标号,小,具有哳号。令卿扣,为点的标号,于是咋。把巧中点,的标号修改为,。乞重复上述步骤,直到%,这时是从。到。的最短路径长。.基于机制的算法上面叙述的是传统的算法,算法的正确性是显然的。下面我们从一个新的角度给出最小路径的算法。问题描述:假设有一个定向图模拟的通讯网络,其中有两个特殊的节点和基于机制设计理论的一些最优化问题的研究。

47、图的每个边是一个代理。每个代理有私人的信息包,它是代理沿此边传递的一个单一信息,目标是为了找到从到的最短路径。机制可能的输出集是从到的所有路径,目标函数是路径的总值。如果边口不是所选路径的部分,则代理的值是,反之,其值是一眈。我们假设是双连通图。真实实施:下面的机制保证每个代理以占优策略,报告其真实类型只给机制。当所有的代理都诚实地报告其值时,最短路径就被选择了。通过一个简单的最短路径计算,即可获得输出值。如果不在最短路径中,则代理给出的支付见是:反之,见吒?一叱。,。?是不包含的最短路径的长度;如旧是当的值假定为时,最短路径的长度。注意:.最短路径确实是总值的最小化值。.给定的机制是一个机制

48、:钆:。相当于啊晓。,。相当于。哆,。目.最小支撑树问题.简介假设在某地区内要修建一个连接若干个城镇的公路系统。已知城:和之问直通公路的造价为。,试设计一个造价最低的建造方案。这类问题很多,如某城市内供气系统的设计,供水系统的设计,供电系统以及通讯系统的设计等等。我们把这类问题称为最小支撑树问题。.定义和名词解释构作加权简单图,其中城镇,被视为的顶点薯,营。若,则认为城和城之间不可能修筑公路第三章机制研究两个基本最优化问题。,。于是这样一个最小连接问题转化为在,印中找出一棵权和最小的支撑树。这样的支撑树称为最小树。最小树存在的一个必要条件是为连通图。反之,连通图中最小树是存在的。枚举的所有支撑

49、树,然后比较它们的权和,找出最小树。用这种方法来找出的最小树无疑是可以的。但一般说来,当顶点数很大时,列出支撑树的数目本身就是一件十分困难的事。因此有必要寻找求晟小树的有效方法。.传统算法目前有许多算法可用来求加权连通简单图,脚的最小树,其中最为著名的是算法和算法。下面就介绍一下算法。算法的步骤:任取矿,。,。,%缸。,死且七。对。或一,若曲。上,则用一,替代,。选取哌使,:瓦一,。设咯淑。,“圪使吼,。令圪圪一,扛。,瓦瓦一。印。若七一,则转:若一,则停止。算法的执行过程是最小树的增长过程。.基于加权机制的算法使用机制,许多算法设计问题都能够被解决。下面我们就来看看加权机制是如何设计最小支撑

50、树问题的算法的。问题描述:假设要建造一个连接若干城镇的铁路网络。己知城镇和,之间直通线路的造价为。,试设计一个总造价最小的铁路网络。构作加权简单图基十机制设计理论的一些最优化问题的研究,功,其中城镇被视为的顶点,一。若口。,则认为城和城,之间不可能修筑公路,脚。, ,。于是这样一个最小连接问题转化为在,国中找出一棵权和最小的支撑树。图的每条边是一个代理。每个代理有私人的信息晓,它是代理沿此边传递的一个单一信息值,目标是为了找到从一到,权和最小的路径。机制可能的输出集是从,到所有路径,目标函数是路径权和。如果边不是所选路径的部分,则代理的值是;反之,其值为一眈。真实实施:下面的机制保证每个代理以占优策略,报告其真实类型给机制。当所有的代理都诚实地报告其值时,最小连接路径就被选择了。通过一个简单的权和计算,即可获得输出值。如果不在最小连接路径中,则代理给出的支付晓是:反之,见%?一%。,国础。是不包含的最小连接路径的权和:%。是当的值假定为时,最小连接的权和。注意:.最小支撑树确实是权和的最小化值。.给定的机制是一个机制:盘稚:。相当于扛