自动机制设计的社会认知优化方法

《自动机制设计的社会认知优化方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第27卷计算机应用Vo.l272007年6月ComputerApplicationsJune2007文章编号:1001-9081(2007)S1-0070-03自动机制设计的社会认知优化方法苏俊霞,蔚承建(南京工业大学信息科学与工程学院,江苏南京210009)(sujunxia1982@163.com)摘要:机制设计用来解决理性代理的偏好汇集问题以达到某种目标。自动机制设计把机制设计作为优化问题,目前使用线性规划来解决,但是随着理性代理数目的增长,优化问题的复杂度呈指数增长。使用社会认知优化方法实现自动机制设计,对离婚案和公共物品配置

2、问题都获得了较好的结果。关键词:机制设计;自动机制设计;社会认知优化中图分类号:TP301.6文献标识码:A[3]结果的机制和随机性结果的机制,具体形式定义如下:0引言定义2不包含支付的确定性机制是一个结果选择函数博弈论是数学和经济学相结合的一个分支,研究理性代O:(1@(2@,@(N→O,理的决策行为以及这种决策的均衡问题。机制设计是博弈论不包含支付的随机性机制是一个具有概率结果选择函数的反问题,它在已知某些结果的情况下,寻找选择规则以激励p:(1@(2@,@(N→p(O),其中p(O)是结果O的一个概理性代理报告真实类型,达到某种

3、最优结果,类型的取值一般率分布集。称为偏好。历史上,机制设计是由社会选择理论而来的,解决包含支付的确定性机制含有一个结果选择函数O:(1@投票系统、征税政策和公共物品的分配等问题。以色列希伯(2@,@(N→O,并且对于每个代理i,都有一个支付函数来大学的Nisan和Ronenk首先提出算法机制设计的框架,并Pi:(1@(2@,@(N→R,其中P(H1,H2,,,HN)给出了代理且把这种机制应用于计算机科学中的一些基本问题的理性情i的报告类型是H1,H2,,,HN时的支付。况,包括最短路径问题、最小生成树问题和不相关车床的时序包含支付的

4、随机性机制含有一个具有概率结果选择函数安排问题等等[1]。耶鲁大学、哈佛大学、卡耐基梅隆大学和p:(1@(2@,@(N→p(O),并且对于每个代理i,都有一个麻省理工学院的一些学者对机制设计做了进一步的研究。其支付函数Pi:(1@(2@,@(N→R。中,卡耐基梅隆大学的Conitzer和Sandholm提出了自动机制自动设计机制时,设计者应考虑两种约束:理性设计的方法,并且研究了其计算的复杂性[2,3]。(individualrationality,IR)约束和激励兼容(incentivecompatibility,IC)约束。理性(

5、IR)约束是指代理参与博弈比自动机制设计方法把机制设计作为优化问题并且通过线不参与能获得更多的利益,激励兼容(IC)约束是指代理报告性规划来解决。但线性规划的复杂度是随理性代理的个数呈真实类型比报告错误能获得更多的利益。指数增长的,因此这种方法只适用于少数理性代理,而实际问IR约束根据代理参与机制所知其余代理的类型情况分题中约束个数可能成千上万。社会认知优化方法是一种集群为先验性约束和后验性约束。先验性指代理仅知道自己的类智能方法,适合于大规模约束问题的处理,并且在许多应用领[4,5]型而不知道其余代理类型的参与情形。后验性指代理不仅

6、知域获得了成功的结果。因此,本文提出使用社会认知优道自己的类型而且知道其余代理类型的参与情形。化来实现AMD,简单有效地解决了文献[3]中的机制设计问一个机制称为实现了占优策略,如果一个代理真实报告题,并且取得了比文献[3]中更好的结果。其类型的结果总是最优的,即使它已经知道其余代理的类型。1自动机制设计一个机制称为实现了贝叶斯纳什均衡,如果一个代理不知道任何其他代理的类型并且其他代理都真实报告其类型,[3]一个机制设计问题的基本定义如下:该代理真实报告其类型的结果总是最优的。定义1在一个机制设计中,我们假定:1)一个可行结果定义3给

7、定一个自动机制设计的设置,一个理性(IR)的有限集O;2)一个含有N个代理的有限集;3)一个代理集概念(先验或者后验),一个解的概念(占优策略或者贝叶斯合I,包括下面四个属性:①每个代理i有一个类型集合(i,所纳什均衡)。机制设计产生的结果可能有支付,可能是随机有代理的类型集合为(,对于每个代理iII,都有一个类型Hi的。最后,我们给定一个目标函数G,判断是否存在一个具I(i,并且

8、I

9、=N,(=(1@(2@,@(N;②对于(i,有体类型的机制同时满足理性约束和解的概念。一个概率分布Ci(在类型相互关联的情况下,对于(1@(2@2社会

10、认知优化,@(N,有一个联合分布C);③对于每一个类型Hi和每一个结果o(oIO),都有一个效用函数ui(o;Hi);4)一个目标函基于社会认知理论提出的社会认知优化算法,已经得到数G,机制设计者期望目标函数值能够最大。