论文部分内容阅读
为了使得合作博弈的研究更加贴合实际,博弈中联盟的结构一直被学者们所关注。图上博弈以图为媒介来描述参与者之间的交流局面,在经典博弈之外被广泛应用。在这些图博弈中,假定参与者通过直接或间接的链接,形成联盟,获得固定的收益,并在一定的法则下进行利益分配。但这其中未从考虑到连通的结构,也就是说,无论连通的结构如何,联系的路径是直接的还是间接的,其收益是特征函数的同一值,分配结果也一样。然而,现实中,参与者之间不同的联系结构,在大的系统中,其收益或损失往往是不同的,特征函数的定义也有可能失真。在联盟及其结构形成的过程中,合作的收益以及成果或成本的分摊是关键。本文的研究围绕特征函数和相应的分配法则及其联盟结构对其的影响展开。从一个具体的图上博弈模型切入,并对分配法则进行完善。更进一步,则是把着眼点放在改进合作博弈中的特征函数,考虑联盟结构对合作博弈的收益及其分配的影响,研究新的特征函数下的分配法则,使之满足相关性质,以达到公平、合理。与此同时,从另外的角度给出合作博弈的一个不依赖于特征函数的分配法则,称之为Page-Shapley值。本文所做的主要研究工作如下:首先,以日常生活中常见的团购活动为对象,建立其图上合作(支付)博弈模型。以两位参与者之间是否可以相互代领包裹作为他们之间是否有边相连的标志而构造一个交流图。在一般成本函数下,本文证明了此博弈存在无穷多个解,使得任何消费者团体都不愿意脱离大联盟而单独行动,并且保证购买量大的消费者一定可以支付(严格)较小的单价。此前的购物模型,都是以总价来衡量分配方案,而本文则以单价为标准,一般认为,用单价衡量支付标准更接近顾客的关注点,优化了分配法则。其次,引入了描述图的局部结构的函数,将Myerson定义的图上博弈推广为局部结构下的图上博弈,给出了新的Myerson值的特征刻画。同时,给出带局部结构的边博弈和位置值的定义,并且对位置值进行了特征刻画,就是说,位置值是唯一由分支有效性和边平衡贡献性所确定的分配法则。这里的创新在于:在图博弈的定义中,连通集合都可以取得最大效益,而本文则是假定只要局部的涉及到参与者之间的联络结构是相同的,那么此局部结构对联盟整体收益的影响也是相同的。在此基础上定义了具有局部结构的Myerson值,给出了该Myerson值的特征刻画。本文也把局部结构的思想推广到位置值。思路是:位置值来自于边博弈,而边博弈源于点博弈。那么利用一定的规则,将点与点之间的联络结构作为“中介”来确定边集的赋值。用这样的边的值计算位置值,考虑了不同的结构对边博弈位置值的影响。同时得到了类似Slikker对位置值的性质的特征刻画。最后,本文从另一方面来考虑目前研究的分配法则。在上述两点中,所讨论的分配都直接或间接的使用了Myerson图上博弈的定义,该博弈中的特征函数是原来的特征函数的衍生物,有人为的规定,如每一个连通集合都是可行的联盟,且取得完全博弈下的效益。尽管所引入的刻画连通集合结构的局部函数就是试图弥补这样规定中的不合理之处,但也不能保证特征函数会完全真实的反映合作博弈的效益。为此本文提出一个新的分配法则,首先以(不受限制下)经典博弈的Shapley值作为个人能力的标志。用类似于Google搜索网页排序的PageRank的算法作为参与者在交流局面中的地位。定义Page-Shapley值,使得参与者所得与Shapley值和PageRank都成正比。然后给出一个系数,使得该分配法则满足分支有效性,从而构造出一个新的分配法则。