１４４　传感器与微系统（Ｔｒａｎｓｄｕｃｅｒ　ａｎｄ　Ｍｉｃｒｏｓｙｓｔｅｍ　Ｔｅｃｈｎｏｌｏｇｉｅｓ）　２０１１年第３０卷第１Ｏ期　

自动机制设计中一种改进的混沌蚁群算法　

陈旭，蔚承建，吉　军，罗　杰　

（南京工业大学电子与信息工程学院，江苏南京２１０００９）　

摘要：针对自动机制设计计算复杂度会随具体问题规模的增大而呈指数增长等问题，提出了一种改进　的混沌蚁群算法。在机制设计基础上，依据激励兼容和个人理性约束，分析了自动机制设计中的占优策略　机制模型和贝叶斯一纳什均衡机制模型，并将改进的算法用于实现这２种机制模型。结果表明：该算法在　公共货物配置问题上取得了较好的效果。　关键词：机制设计；混沌蚁群算法；占优策略；纳什均衡；货物配置　中图分类号：ＴＰ３０１．６　文献标识码：Ａ　文章编号：１０００－９７８７（２０１１）１０－０１４４－０４　

▲　‘　１　’　・－　・　ｌ　－・’　●　Ａｎ　ｉｍＤｒｏｖｅｎ　ＣｈａｏｔｉＣ　ａｎｔ　ＳＷａｒｍ　ａｌ￣ｏｒｉｔｎｍ　ｉｎ　

ａｕｔＯｍａｔｅｃＩ　ｍｅｃ１１ａｎｌＳｍ　ｄｅｓｉｔ￣ｎ　－　』　１　’　●　ｌ　●　

ＣＨＥＮ　Ｘｕ，ＷＥＩ　Ｃｈｅｎｇ－ｊｉａｎ，ＪＩ　Ｊｕｎ，ＬＵＯ　Ｊｉｅ　（ＳｃｈｏｏＩ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃｓ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎａｎｊｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｎａｎｊｉｎｇ　２１０００９，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇ　ａｔ　ｔｈｅ　ｐｒｏｂｌｅｍｓ　ｏｆ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｔｙ’Ｓ　ｅｘｐｏｎｅｎｔｉａｌ　ｇｒｏｗｔｈ　ｗｉｔｈ　ｔｈｅ　ｓｉｚｅ’ｓ　ｉｎｃｒｅｍｅｎｔ　ｏｆ　ｔｈｅ　ｓｐｅｃｉｆｉｃ　ｐｒｏｂｌｅｍｓ　ｉｎ　ａｕｔｏｍａｔｅｄ　ｍｅｃｈａｎｉｓｍ　ｄｅｓｉｇｎ，ａｎ　ｉｍｐｒｏｖｅｄ　ｃｈａｏｔｉｃ　ａｎｔ　ＳＷａｌ３Ｔｌ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｐｒｅｓｅｎｔｅｄ．　Ｂａｓｅｄ　ｏｎ　ｍｅｃｈａｎｉｓｍ　ｄｅｓｉｇｎ，ａｃｃｏｒｄｉｎｇ　ｔｏ　ｃｏｎｓｔｒａｉｎｔｓ　ｏｆ　ｉｎｃｅｎｔｉｖｅ　ｃｏｍｐａｔｉｂｉｌｉｔｙ　ａｎｄ　ｉｎｄｉｖｉｄｕａｌ　ｒａｔｉｏｎａｌｉｔｙ，ｍｏｄｅｌｓ　ａｒｅ　ａｎａｌｙｚｅｄ　ｆｏｒ　ｔｈｅ　ｄｏｍｉｎａｎｔ　ｓｔｒａｔｅｇｙ　ｍｅｃｈａｎｉｓｍ　ａｎｄ　Ｂａｙｅｓｉａｎ—Ｎａｓｈ　ｅｑｕｉｌｉｂｒｉｕｍ　ｍｅｃｈａｎｉｓｍ　ｉｎ　ａｕｔｏｍａｔｅｄ　ｍｅｃｈａｎｉｓｍ　ｄｅｓｉｇｎ，ａｎｄ　ｂｏｔｈ　ｏｆ　ｔｈｅ　ｍｅｃｈａｎｉｓｍ　ｍｏｄｅｌｓ　ａｙｅ　ａｃｈｉｅｖｅｄ　ｕｓｉｎｇ　ｔｈｅ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ．Ｉｔ　ｉｓ　ｄｅｍｏｎｓｔｒａｔｅｄ　ｔｈａｔ　ｔｈｅ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｈａｓ　ａｃｈｉｅｖｅｄ　ｇｏｏｄ　ｅｆｆｅｃｔ　ｏｎ　ｐｕｂｌｉｃ　ｇｏｏｄｓ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｐｒｏｂｌｅｍｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｍｅｃｈａｎｉｓｍ　ｄｅｓｉｇｎ；ｃｈａｏｔｉｃ　ａｎｔ　ｓｗａｒｍ　ａｌｇｏｒｉｔｈｍ；ｄｏｍｉｎａｎｔ　ｓｔｒａｔｅｇｙ；Ｎａｓｈ　ｅｑｕｉｌｉｂｒｉｕｍ；ｇｏｏｄｓ　ｄｉｓｔｉｌ—　ｂｌｌ　ｏｎ　

０引　言　机制设计属于博弈论和微观经济学的一个分支领域，　它研究的是在多个代理为了自身利益而不报告真实信息的　

情况下，设计出一种规则对各代理的偏好进行整合，以求达　

到某种最优的结果。机制设计有时也被叫做博弈论的反问　

题。博弈论是指某个个体或者组织在某种确定规则的前提　下，根据所掌握的信息进行策略选择并加以实施，从而各自　

取得相应结果或收益的过程；机制设计则是根据某种结果　

去设计规则。然而，机制设计却是一个复杂的问题…，因　

为代理可能为了自己的利益报告不真实的信息。对于确定　

性的机制，机制设计问题也是一个ＮＰ完全问题，例如：在　

占优策略下的机制实施和贝叶斯一纳什实施。　

２０世纪７Ｏ年代，美国经济学家Ｈｕｒｗｉｃｚ　Ｌ提出了机制　设计理论　Ｊ，他把机制定义为一种信息交换系统，参与者　

在这种体制中相互发送信息或发送到信息中心。这种理论　

收稿日期：２０１１　１—１１　基金项目：南京市留学基金资助项目（ＺＢＷ３０２００１）　框架最初用于解决服务和公共货物的分配等问题。Ｈｕｒ—　

ｗｉｃｚ　Ｌ在研究初期主要是集中在机制设计过程的计算成本　

和信息等方面，没有考虑激励问题。Ｍａｒｓｈａｋ和Ｒａｄｎｅｒ　

后来提出的团队理论在一定程度上补充了这方面的不足。　

随着网络技术的快速发展，机制设计的理论得到了很大的　发展，同时其应用也更加广泛。以色列耶路撒冷希伯来大　

学的Ｎｉｓａｎ　Ｎ和Ｒｏｎｅｎ　Ａ基于机制设计的理论首先提出了　

算法机制设计的基本框架技术和一系列关于近似机制问题　

的定理　，并把这种算法机制应用于算法问题、负载平衡，　特别是最短路径问题。斯坦福大学的Ｓａｍｕｅｌ　Ｉ　等针对以　

ｆ　没有考虑信息不确定的情况，提出了基于算法和博弈论　

方法的随机机制设计，对这种机制的实施给出了正式的证　

明。进一步美国杜克大学的Ｇｉｕｓｅｐｐｅ　Ｌ等人讨论了带有奈　

特不确定性的机制设计问题　，研究了机制设计中激励兼　

容的２个方面（最大激励兼容和最优激励兼容），得出在一　第１Ｏ期　陈旭，等：自动机制设计中一种改进的混沌蚁群算法　１４５　

般的公平信任条件下，最优激励兼容和事后激励兼容等价。　

传统的机制设计是通过手工完成的，机制设计者根据　

经验假设某个具体问题存在一个满意的规则，然后试图证　

明这种机制的存在性。但手工设计机制通常都较为繁琐，　

也加重了设计者的负担。Ｃｏｎｉｔｚｅｒ和Ｓａｎｄｈｏｌｍ　Ｔ提出了自　

动机制设计　（ａｕｔｏｍａｔｅｄ　ｍｅｃｈａｎｉｓｍ　ｄｅｓｉｇｎ，ＡＭＤ）的方法，　

利用这种方法计算机自动地为具体的问题实例产生机制，　

并且应用范围不局限于以往手工机制设计可以完成的问题　

类型。此外，对于代理个数一定的情况下，文献［６］把机制　

设计问题转化为线性规划加以解决。但是，线性规划的复　

杂度是随代理个数的增加而呈指数的增长，不利于求解较　

大规模的机制设计问题。根据混沌蚁群算法　能够处理较　

为困难和较大规模的优化问题及具有较好的全局搜索能力　

的特性，本文在其基础上改进了混沌蚁群算法，并将其应用　

于公共货物配置问题，取得了较好的效果。　

１自动机制设计　

１．１　自动机制设计的一般形式　针对传统的手工机制设计，Ｃｏｎｉｔｚｅｒ和Ｓａｎｄｈｏｌｍ　Ｔ提出　

了自动机制设计，为某种特定的场景和目的而自动设计出　

机制　，其基本内容包括以下几个部分：１）一个关于结果的　

有限集合０，０＝｛Ｏ　－．，Ｏ　｝。２）针对具体的问题而设计机　

制的代理数集合Ａ。３）对于每一个代理。，又包含３个方　

面：ａ．代理类型的有限集合　，Ｔ＝｛ｔ　一，ｔ　｝；ｂ．对每一个　

，ａ　Ａ，存在一个概率分布　。（类型相互关联时，对于　

ＴＩ　Ｘ　Ｘ…Ｘ　，存在一个联合分布　）；ｃ．代理的效用值　

函数Ｕ。：　ＸＯ—　。４）一个机制设计者期望能最大化的目　

标函数ｚ。　

１．２机制类型及其计算问题　自动机制设计是针对具体的问题设计机制，而不是针　

对一类问题，本文根据公共货物配置问题进行一些形式的　

调整。假设问题类型是独立分布，则参与者类型的概率分　

布定义为：Ｐ：　｛０，１｝，其中，∑Ｐ（ｔ）＝１，设计者的目标　

函数定义为ｚ：　ＸＯ—Ｒ，参与者的均衡效用函数为　：Ｔ　Ｘ　

Ｄ一尺；其中，ｍ为参与者数，　，ｋ≤ｍ。在自动机制设计　

过程中，有２种可能性：贝叶斯一纳什激励兼容（Ｂａｙｅｓ　Ｎａｓｈ　

ｉｎｃｅｎｔｉｖｅ　ｃｏｍｐａｔｉｂｉｌｉｔｙ，ＢＮＩＣ）和占优策略激励兼容（ｄｏｍｉ—　

ｎａｎｔ　ｓｔｒａｔｅｇｙ　ｉｎｃｅｎｔｉｖｅ　ｃｏｍｐａｔｉｂｉｌｉｔｙ，ＤＳＩＣ）。在ＢＮＩＣ情况　下，每个参与者报告他的真实类型以最大化其期望收益，而　

在ＤＳＩＣ情况下，报告真实信息可以达到占优策略均衡。有　

关定义如下　Ｊ：　

定义１：一个机制　属于贝叶斯一纳什激励兼容，如果　

对于每个０∈Ａ，且ｔ。∈Ｔ，有不等式Ｅ…［∑‰（ｔ。，０）］　Ｍ（ｔ　…ｏ）］≥Ｅ…［∑　（ｆ。，ｏ）　（　，ｆ…０）］Ｙｔ　。∈Ｔ　

成立；一个机制　属于占优策略激励兼容，如果对于每个　

。∈Ａ，￡　∈　，有不等式∑Ｉｔａ（　。，。）Ｍ（ｔ　，￡一。，０）≥　

∑　（　，ｏ）　（　。，ｆ一。，０）Ｖ　。∈　，￡一。∈　成立。此外，　

设计者在进行机制设计时，除了需要考虑激励兼容约束，还　需考虑个人理性（ｉｎｄｉｖｉｄｕａｌ　ｒａｔｉｏｎａｌｉｔｙ，ＩＲ），个人理性可以　

分为先验个人理性（ＣＸ　ｉｎｔｅｒｉｍ　ｉｎｄｉｖｉｄｕａｌ　ｒａｔｉｏｎａｌｉｔｙ，ＥＩＩＲ）和　

事后个人理性（ｅｘ　ｐｏｓｔ　ｉｎｄｉｖｉｄｕａｌ　ｒａｔｉｏｎａｌｉｔｙ，ＥＰＩＲ）。基于前　

者，参与者可以在联合类型分布情形下获得其期望收益，而　

后者可以保证实现任何参与者的机制类型。　定义２：一个机制　带有先验个人理性（ＥＩＩＲ），如果对　

于每个ｎ∈Ａ且ｔ。∈　，有不等式Ｅ…［∑Ｕａ（　。，。）Ｍ（ｔ。，　

ｔ一。，０）］ｔ＞０成立。一个机制　带有事后个人理性（ＥＰＩＲ），　如果对于每个ａ　Ｅ　Ａ，ｔ。∈Ｔ，且ｔ一。∈　～，有不等式　

∑　（ｆ　）　（　一ｔ　，ｏ）≥０成立。　

１．３　自动机制设计的２种数学模型　由以上的定义，依据ＢＮＩＣ和ＥＩＩＲ进行的机制设计命　

名为贝叶斯一纳什机制设计（Ｂａｙｅｓ　Ｎａｓｈ　ｍｅｃｈａｎｉｓｍ　ｄｅｓｉｇｎ，　ＢＮＭＤ），运用ＤＳＩＣ和ＥＰＩＲ的机制设计命名为占优策略机　制设计（ｄｏｍｉｎａｎｔ　ｓｔｒａｔｅｇｙ　ｍｅｃｈａｎｉｓｍ　ｄｅｓｉｇｎ，ＤＳＭＤ）。　贝叶斯一纳什机制设计数学模型如下　

（ｆ，０　ｃ，０）Ｐ（ｃ）ｊ　（　）　

ｓ．ｔ．ＩＲ：∑∑ｕ（ｔ　）　（　…。）Ｐ（　一　）≥０，Ｖ。∈　

Ａ，ｔ。∈Ｔ，　

Ｉｃ：∑∑“（￡。，。）［　（￡　…。）一Ｍ（ｔ　…ｏ）］　０Ｅ【　ｔ一Ⅱ　Ｐ（ｔ一　）≥Ｏ，Ｖａ∈Ａ，ｔ。∈Ｔ，ｔ　∈Ｔ，　

∑Ｍ（ｔ，ｏ）＝ｌ　Ｖｔ；Ｍ（ｔ，ｏ）ｉ＞０　Ｖｔ∈　，０∈Ｏ．　

其中，最后一个约束条件保证了产生的机制是基于类　

型向量的一种结果集的有效分布。占优策略机制设计的数　

学模型为　

ｚ（ｆ，ｏ）　（ｆ，０）Ｐ（ｔ），　（２）　

ｓ．Ｉ．ｔ　ＩＲ：∑“（　。，ｏ）　（ｆ　，ｔ…０）≥０ＶａｅＡ，ｔ一。∈　

，ｔ　∈Ｔ，　

Ｉｃ：∑“（￡　，。）［Ｍ（￡。，ｔ…。）一Ｍ（ｔ’　，ｔ…。）］＞１０，　

Ｖａ∈Ａ，ｔ一。∈Ｔｍ一　，ｔ　，ｔ　。∈Ｔ，　

∑Ｍ（ｔ，。）＝１　Ｙｔ∈　，Ｍ（ｔ，。）≥Ｖ　∈　，。∈０．　

由上面的模型可知是带有许多约束的线性规划，如果　

参与者的数目一定，可以求解。但是如果规模很大，

线性规