具有图结构和联盟结构的Banzhaf值及应用_单而芳.pdf

第 卷 第 期运筹与 管理，年 月 收稿日期：基金项目：国家自然科学基金资助项目（）；浙江省社科联研究课题（）作者简介：单而芳（），通讯作者，男，河北石家庄人，教授，博士生导师，研究方向：图论及其应用，图上合作对策；刘贺宇（），女，河北石家庄人，硕士研究生，研究方向：图上合作对策，供应链管理；吕文蓉（），女，山东济南人，硕士研究生，研究方向：图上合作对策，供应链管理；史纪磊（），男，山东临沂人，博士研究生，研究方向：图上合作对策。具有图结构和联盟结构的 值及应用单而芳，刘贺宇，吕文蓉，史纪磊（上海大学 管理学院，上海）摘 要：值是经典可转移效用合作对策中一个著名的分配规则，可以用来评估参与者在对策中的不同作用。本文将 值推广到具有联盟结构和图结构的 对策中，首先提出并定义了具有联盟结构和图结构的 值（简称 值），证明了 值满足公平性、平衡贡献性和分割分支总贡献性，并给出了该值的两种公理性刻画。其次，讨论了 值在跨国天然气管道案例中的应用，并和其他分配规则进行了比较分析。关键词：对策；图；通讯情境；联盟结构；值中图分类号：；文章标识码：文章编号：（）：，（，）：，（），：；引言可转移效用合作对策（），简称 对策，描述的是参与者间通过形成合作联盟，产生一定的联盟效用。该模型假设任何有限参与者间都可能形成合作联盟（），即任何联盟都是可行的。针对 对策，以每个参与者为分析对象，对参与者合作产生的联盟效用提出了一种分配规则，即 值。对策中另一个著名分配规则是由 提出的 值，该值起源于投票对策，后被逐 步 拓 展 到 对 策 中。值和 值都是通过参与者的边际贡献来度量的，可以看作参与者对所有联盟产生的边际贡献的期望值。不过，它们对于每个联盟边际贡献的权重定义是不同的。具体地，在 值中，规定每个参与者加入任何相同规模联盟的可能性是相同的，而在 值中，规定参与者加入任何联盟的可能性都是相同的。对于总效用的分配，值的计算方式比 值更为简单。实际中，并非所有参与者间均能进行有效合作。为描述该合作约束，引入图（）的概念，将 对策和图结构结合，提出了具有图结构的 对策，简称图对策（）。图中的节点（）代表参与者，图中的边（）代表参与者之间存在的某种合作关系，且假设只有在有边或路（）连通的情况下，参与者间才能形成合作联盟。在 此 基 础 上，定 义 图 限 制 对 策（）上的 值作为图对策中的一种分配规则，即著名的 值。同样使用图结构描述参与者间的合作约束。对 值进行了研究，提出了图限制对策中的 值，简称为 图值（）。之后，和 给 出 了 图值的四种公理性刻画。第一种是使用独立性（）、二合并性（）和公平性（）；第二种是利用分支总贡献性（）和公平性（）；第三种和第四种由平衡贡献性（）代替公平性得到。其他以图结构描述合作约束的研究可参见。不同于 用图结构描述参与者间的合作约束，使用联盟结构描述合作约束，分析优先联盟（）对效用分配造成的影响，提出了具有联盟结构的 对策（），并定义了具有联盟结构的 值（简称 值）作为该对策上的一种分配规则。考虑对称性，和提出了具有联盟结构的 值的另一种修正形式，即对称联盟 值（）。类 似 的，定义了联盟结构 对策上的分割限制对策，提出并刻画了该结构下的一种新的分配方案，即 值。值和 值所定义的联盟结构的不同点在于前者的优先联盟中的部分参与者可以和其他完整的优先联盟进行合作，而后者则假定只有完整的优先联盟间才能进行完全合作。合作的复杂性使得合作往往受两种甚至多种形式的约束。等考虑了具有联盟结构和图结构双重限制的 对策，将 值和对称联盟 值推广到了该模型中。而 等则将 值和 值推广到具有联盟结构和图结构的 对策（）上，提出了图分 割 值（）和 分 割图 值（），即具有图结构的 值和具有联盟结构的 值，并进行了公理性刻画。这两个值都是 值的推广，而 值在该形式下的推广尚未有学者进行研究。本文旨在将 值推广到具有联盟结构和图结构的 对策上，提出并刻画一种新的具有联盟结构和图结构的 值。本文结构安排如下：第二节给出本文需要的基本定义和符号。第三节给出具有联盟结构和图结构的 值的定义，并进行公理性刻画。第四节以天然气管道案例进行分析，将具有联盟结构和图结构 的 值与其他值进行比较分析。最后对本文所做工作进行总结并给出注记。预备知识 对策可转移效用合作对策，简称 对策，是由二元组（，）组成。其中 表示有限参与者（）集，表示特征函数（），它是定义在 上的一个映射，并规定（）。对 中任意一个非空子集，（）表示联盟中成员进行合作所产生的效用，用 表示联盟 的基数。（，）是（，）的子对策，且对任意的，有（）（）。为了简便，我们将（，）简记为（，），相应的也将 简记为。支付向量（）（，）是指分配给每个参与者 的支付为。对策的一个分配规则（）或者值是一个函数，指分配给任意（，）的一个支付向量（，）。对于对策（，）和任意的，值（，）是 对策上最著名的一个分配规则，其定义为：（，）！（）！（）（）对策中，另一个分配规则是 值，其定义如下：（，）（）（）（）图和通讯情境图（）由有限点集 和无向边集，组成，用二元组（，）表示，其中 称为 上的完全图。在参与者集合 固定时，我们将（，）简记为。记所有的图（，）的集合为。为简便起见，文中将，简记为。如果对任意 ，都有 ，则称点集（，）为 中的一条路。如果 和运 筹 与 管 理 年第 卷 间存在一条路或者 ，则称 和 在 中是连通的。如果图 中任意两点间均是连通的，则称图 是连通的。对于任意的，图（，（）称为 在 上的子图，其中（），。对于任意的，如果 中任意两点在（）上均是连通的，则称 在 上是连通的。一个极大的连通子集 称为 上的一个分支。将（，（）和（，）中所有分支的集合分别记为 和 。用（，）表示由（，）去掉边 后形成的图，用 表示 中所有与 相关的无向边的集合，记 ，表示去掉所有与 相关的无向边后形成的子图。通讯情境（），又称为图对策（），由三元组（，）组成，其中（，）是 对策，（，）是图。对任意（，）和，图值（，）被定义为图限制对策下的 值，即：（，）（，），其中 表示图限制对策（，）的特征函数。定义为：对任意 ，（）（）。具有联盟结构的 对策联盟结构由有限点集和联盟结构或分割 ，组成，记为（，）。其中，联盟结构 满足：（）；（）对任意的，；（）对任意的，有 。记 上所有联盟结构的集合为（）。特别地，把 或 ，称为平凡联盟。对于给定的 ，（），记 ，将每一个（），称为 的一个优先联盟。具有联盟结构的 对策是一个三元组（，），其中（，）表示 对策，（，）表示联盟结构。记所 有 具 有 联 盟 结 构 的 对 策 集 合 为（）。对任意的（，）（），且 ，将（，）对应的商对策（）定义为（，），其中 是参与者集，且对任意的，有（）（）。与上述联盟结构定义不同，认为联盟内部的参与者能够相互合作，但与联盟外部参与者进行合作时必须取得该联盟内所有参与者的同意。因此，给定一个联盟结构（），任意联盟 中的参与者能够相互合作获得收益（）；当，且，优先联盟 与中所有参与者均同意合作时，可获得收益（）；而当 与 合作时，仅能获得收益（）（）。即，对任意的 ，且，定义 ，。对任意的（，）（），由 联 盟 结 构 导 出 的 分 割 限 制 对 策（）（，）的特征函数定义为：对任意的 ，（）（）。具有联盟结构和图结构的 值及其公理化刻画 具有联盟结构和图结构的 值具有联盟结构和图结构的 对策由四元组（，）组成，其中（，）代表 对策，（，）代表图，而（，）代表联盟结构。记所有具有联盟结构和图结构的 对策（，）的集合为。对任意的（，），等将分割图限制对策（，（）的特征函数定义为：对任意的（）（）（）（）（）在上述理论基础上，本文将 值拓展到具有联盟结构和图结构的 对策中，定义一种新的具有联盟结构和图结构的 值，简称为 值。定义（值）对于任意的（，），值（，）可定义如下：对任意的（，）（，）（，（）（）显然，当 为平凡联盟，也即 或 ，时，值就是 图值。进一步，当 为平凡联盟并且图是完全图时，值就是 值。因此，值是 图值和 值的一类自然推广。值的公理化刻画本节将给出 值的公理性刻画。为方便刻画，我们首先介绍一些性质。分割分支总贡献性（，简记为）。对任意（，），若分配规则 满足（，）（）（）（）（），则称 具有分割分支总贡献性。分割分支总贡献性是指：分支的总效用等于该分支内每个参与者限制在该分支子对策上的效应第 期 单而芳，等：具有图结构和联盟结构的 值及应用之和。公平性（，简记为）。对任意（，），及任意的，若分配规则 满足（，）（，）（，）（，），则称 具有公平性。公平性是指：与一条无向边关联的两个参与者，当去掉这条无向边时，对这两个参与者支付造成的影响是相同的。引理 对 任 意 的（，），值（，）满足。证明 由定义 及 图值满足 易得：（，）（，）（，）（，）（，）（，）（，）（，）所以（，）满足公平性，引理得证。平衡贡献性（，简记为）。对任意（，）及，若分配规则 满足（，）（，）（，）（，），则称 具有平衡贡献性。平衡贡献性是指：和 为联盟 中的两个参与者，参与者 选择孤立自己对参与者 支付的影响与参与者 选择孤立自己对参与者 支付的影响是相等的。引理 对 任 意 的（，），值（，）满足平衡贡献性（）。证明 由定义 及 图值满足 易得：（，）（，）（，）（，）（，）（，）所以（，）满足平衡贡献性，引理得证。定理 对任意的（，），值（，）可由公平性（）和分割分支总贡献性（）所唯一确定。证明 存在性。对于任意（，），根据引理 可知，值（，）满足公平性。而由 图值满足分支总贡献性易证 值满足。唯一性。假设存在另一个满足 和 的分配规则，我们需证明 。当 时，即 为空图。此时，每个节点 都是一个分支，由 可得：（，）（）（，）。现假设对任意的（，），当 时，有（，）（，）。下证 （）时，对任意的 ，都有（，）（，）。对任意的，使得（），由归纳假设和 可得：（，）（，）（，）（，）（，）（，）（，）（，）即，（，）（，）（，）（，）。根据分支内参与者间的传递性可知，存在一个实数，使得对任意 ，有（，）（，）。进一步结合 可得：（，）（，）（，）（，）因为，所以 ，即（，）（，）。综上所述，对任意的，均有（，）（，），定理得证。引理 对 任 意 的（，），值（，）满足平衡贡献性（）必定满足公平性（）。证明 对于对策（，）及任意的，由 图值满足 可知：（，）（，）（，）（，）（）对任意的，及对策（，），由图值满足 可知：（，）（，（），）（，）（，（），）（）容易验证（）及（）成立。进一步，式（）可化简为 （，）（，）（，）（，）（）将式（）和式（）相减可得 （，）（，）（，）（，）所以（，）满足 必定满足，引理得证。结合引理、引理 和定理 可得关于 值的新刻画。定理 对任意的（，），值（，）可由平衡贡献性（）和分割分支总贡献性（）所唯一确定。运 筹 与 管 理 年第 卷 应用举例天然气管道运输问题跨国运输问题一般均可抽象为具有联盟结构和图结构的 对策，其中每个国家代表一种联盟结构，天然气运输管道代表图结构。本节将引入一个跨国天然气管道运输案例，分析 值的合理性和优势。图 跨国天然气管道运输模型示意图 考虑由五个地区构成的天然气跨国运输模型。，是地区集合，其中地区 坐落在 国，地区 坐落在 国，地区 坐落在 国，地区 和地区 属于同一个国家，记为 国。地区 是天然气的主要出口区，通过现有的天然气管道将天然气运送给其他各区。而地区 是天然气自给自足区，产生的天然气仅供给本区使用，且不需要进口。将国家抽象为联盟结构，天然气管道抽象为图结构，可将上述模型抽象为如图 所示的结构。其中边集 ，联盟分割为 ，根据上述假设可知，地区 自身即可产生收益，不需与其他地区合作。地区 自身可以产生收益，也可通过与其他地区合作获得更大的收益。而其他地区均需包含天然气的出口区 时才会产生收益。现只考虑每个地区在运输过程中产生的效用，据此，我们定义如下特征函