指派问题的纳什均衡解

《指派问题的纳什均衡解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２２卷第４期运筹与管理Ｖｏｌ．２２，Ｎｏ．４２０１３年８月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＡｕｇ．２０１３指派问题的纳什均衡解徐屹嵩，王应明（福州大学公共管理学院，福建福州３５０１０８）摘要：为弥补传统指派问题解不符合个体理性的不足，提出指派问题的纳什均衡解，并证明有限指派问题有且仅有纯纳什均衡解。相比传统的指派问题解，纯纳什均衡符合Ｐａｒｅｔｏ最优，是个体理性视角下的最优解。在此基础上，给出一个综合考虑个体理性与集体理性的求解方法。关键词：指派问题；纳什均衡；个体理性中图分类号：Ｃ９３４文章

2、标识码：Ａ文章编号：１００７-３２２１（２０１３）０４-０１０１-０５TheNashEquilibriumintheAssignmentProblemＸＵＹｉ-ｓｏｎｇ，ＷＡＮＧＹｉｎｇ-ｍｉｎｇ（SchoolofPublicAdministration，FuzhouUniversity，Fuzhou３５０１０８，China）Abstract：Ｃｏｎｓｉｄｅｒｉｎｇｔｈｅａｓｓｉｇｎｅｄｐｅｒｓｏｎｓ’ｉｎｄｉｖｉｄｕａｌｒａｔｉｏｎａｌｉｔｙ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄｔｈｅａｍｅｔｈｏｄｔｏｓｏｌｖｅｔｈｅａｓｓｉｇｎｍｅｎｔ

3、ｐｒｏｂｌｅｍｗｉｔｈｇａｍｅｔｈｅｏｒｙ，ａｎｄｐｒｏｖｅｔｈｅｅｘｉｓｔｅｎｃｅｏｆｔｈｅｐｕｒｅｓｔｒａｔｅｇｙｎａｓｈｅｑｕｉｌｉｂｒｉｕｍ．Ｃｏｍｐａｒｅｗｉｔｈｔｈｅａｓｓｉｇｎｍｅｎｔｒｅｓｕｌｔ，ｔｈｅＰｕｒｅＳｔｒａｔｅｇｙＮａｓｈＥｑｕｉｌｉｂｒｉｕｍｃｏｒｒｅｓｐｏｎｄＰａｒｅｔｏＯｐｔｉｍｕｍ．Ａｎｄｉｔｉｓｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｉｎｉｎｄｉｖｉｄｕａｌｒａｔｉｏｎａｌｅｎｖｉｒｏｎｍｅｎｔ．Ａｂｏｖｅａｌｌ，ｗｅｐｒｏｐｏｓｅｄａｃｏｍｐｌｅｘｍｅｔｈｏｄｃｏｎｓｉｄｅｒｉｎｇｉｎｄｉｖｉｄｕａｌｒ

4、ａｔｉｏｎａｌｉｔｙａｎｄｇｒｏｕｐｒａｔｉｏｎａｌｉｔｙｓｉｍｕｌｔａｎｅｏｕｓｌｙ．Keywords：ｔｈｅａｓｓｉｇｎｍｅｎｔｐｒｏｂｌｅｍ；ｔｈｅｎａｓｈｅｑｕｉｌｉｂｒｉｕｍ；ｉｎｄｉｖｉｄｕａｌｒａｔｉｏｎａｌｉｔｙ０引言在日常生活中，某单位需要完成n项任务，恰好有n个人可承担这些任务。由于每个人的专长不同，各人完成任务的效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需总时间最小）的问题，称为指派问题或分派问题。但在实际中，被指派人往往是理性的，即每个人都想承担自己效率最大的任务，为组织创造最

5、大的效用，并获得最多的收入。在这种情况下，常常出现n个人中存在２人或多人争抢同一任务的情况。对于这种情况，传统指派问题均以整体效率最大化为目标化解冲突。然而，从博弈论的角度看，这种冲突化解方法不符合个体理性。事实上，指派问题是一个被指派人追求效率最大化的完全信息静态博弈过程。因此，本文从博弈论的角度研究指派问题，即在被指派人是理性的且理性是被指派人的共同知识的情况下，求解每个参与人的最优选择。从另一个角度来理解，假设指派问题是一个被指派人选择任务的博弈，所有被指派人事先达成一项协议，规定每个人的选择。那么，在没有外在约束力的情况下，当事人

6、是否会自觉遵守这个协议？如果当事人会自觉遵守这个协议，那么这个协议构成一个纳什均衡：给定别人遵守协议的情况下，没有人有积极性偏离协议中规定的自己的选［１］择。为了寻找这种协议，提出一个求解指派问题纳什均衡的简化方法，并证明了不存在冲突的指派问题的最优解一定为纯纳什均衡解，存在冲突的指派问题的纳什均衡解小于等于指派问题的最优解，且有限收稿日期：２０１２-０５-１７基金项目：国家杰出青年科学基金：决策理论与方法（７０９２５００４）作者简介：徐屹嵩，男，博士研究生，主要研究方向：运筹学、博弈论；王应明，男，教授，工学博士，国家杰出青年科学基金获

7、得者，福建省闽江学者特聘教授，博士生导师。研究领域：决策理论与方法，数据包络分析（ＤＥＡ），规则库和人工神经网络。１０２运筹与管理２０１３年第２２卷指派问题有且仅有纯纳什均衡解。［２］目前，国内外对指派问题与博弈论的交叉研究主要集中于指派博弈，Ｓｈａｐｌｅｙ和Ｓｈｕｂｉｋ最早引入了［３］带转移支付的双边市场模型的指派博弈，并研究其核心的一些性质；Ｑｕｉｎｔ指出了指派博弈的核心满足［４］一种特殊的拓扑类；Ｓｏｌｙｍｏｓｉ和Ｒａｇｈａｖａｎ提出了指派博弈的稳定集，并对稳定集的性质进行论述；Ｅｓ-［５］ｔｅｒ证明指派博弈的核心非空且只有一个卖家

8、时，核心元素满足一种偏序关系。指派博弈讨论的是多边的合作和选择关系，其研究的主题是使用指派方法解决博弈问题。相似的研究还有博弈论与匹配问题的［６］［７］交叉研究，Ｌａｚｚａｒｉｎｉ等、Ｓｃｈｍ