残缺区间合作博弈及其在农地污染治理中的应用

针对联盟收益值部分未知的区间合作博弈,定义了残缺区间合作博弈的相关概念。基于合作博弈的超可加性,建立了联盟区间收益值的一致性验证模型。通过构造正、负理想分配及其与收益分配向量之间的偏差,给出了残缺区间合作博弈的区间Ideal-Shapley值求解模型,分析了区间Ideal-Shapley值的合理性与存在性。利用上述模型求解农地污染联合治理的节约成本分摊策略,验证了区间Ideal-Shapley值求解模型的有效性。     

基于区间与模糊Shapley值的合作收益分配策略

将经典Shapley值三条公理进行拓广,提出具有模糊支付合作对策的Shapley值公理体系。研究一种特殊的模糊支付合作对策,即具有区间支付的合作对策,并且给出了该区间Shapley值形式。根据模糊数和区间数的对应关系,提出模糊支付合作对策的Shapley值,指出该模糊Shapley值是区间支付模糊合作对策的自然模糊延拓。结果表明:对于任意给定置信水平α,若α=1,则模糊Shapley值对应经典合作对策的Shapley值,否则对应具有区间支付合作对策的区间Shapley值。通过模糊数的排序,给出了最优的分配策略。由于对具有模糊支付的合作对策进行比较系统的研究,从而为如何求解局中人参与联盟程度模糊化、支付函数模糊化的合作对策,奠定了一定的基础。     

Acyclic edge colorings of planar graphs and seriesparallel graphs

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1. This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation of Shandong Province (Grant No. Y2008A20).     

基于图对策的收益分配

基于具有交流结构的合作对策,即图对策,对平均树解拓展形式的特征进行刻画,提出此解满足可加性公理。进一步地,分析了对于无圈图对策此解是分支有效的。并且当连通分支中两个局中人相关联的边删掉后,此连通分支的收益变化情况可用平均树解表示。这一性质是Shapley值和Myerson值所不具有的。最后,我们给出了模糊联盟图对策中模糊平均树解的可加性和分支有效性。     

图博弈的过程比例解

本文对具有图结构合作博弈（图博弈）进行了研究,采用比例原则和过程化分配方法,定义了比例分配过程,并对其性质进行了分析。随后,针对比例分配过程的超有效情况,运用等比例妥协的方式给出满足有效性的过程比例解,并研究了稳定性。最后,将比例分配过程与过程比例解应用到破产问题中,得到图博弈过程比例解与破产问题比例规则等价的结论。     

系列平行图的边面染色

一个平面图G的边面色数xef(G)是指对G的边和面进行染色所用最少的颜色数目,并同时使得相邻或相关联的两个元素间染不同颜色.若G是一个系列平行图,也就是不含K_4的剖分作为子图的平面图,则有Xef(G)≤max{7,△(G) 1};同时如果G还是2-连通的且△(G)>6,则有Xef(G)=△.     

Minimum convex piecewise linear cost tension problem on quasi-<Emphasis Type="Italic">k</Emphasis> series-parallel graphs

Some hypermedia synchronization issues request the resolution of the minimum convex piecewise linear cost tension problem (CPLCT problem) on directed graphs that are close to two-terminal series-parallel graphs (TTSP-graphs), the so-called quasi-k series-parallel graphs (k-QSP graphs). An aggregation algorithm has already been introduced for the CPLCT problem on TTSP-graphs. We propose here a reconstruction method, based on the aggregation and the well-known out-of-kilter techniques, to solve the problem on k-QSP graphs. One of the main steps being to decompose a graph into TTSP-subgraphs, methods based on the recognition of TTSP-graphs are thoroughly discussed.Received: October 2003, Revised: July 2004, MSC classification: 90C35, 05C85     

Partitioning series-parallel multigraphs into ν *-excluding edge covers

We prove that, for any given vertex ν* in a series-parallel graph G, its edge set can be partitioned into κ = min{κ′(G) + 1, δ(G)} subsets such that each subset covers all the vertices of G possibly except for ν*, where δ(G) is the minimum degree of G and κ′(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for actually finding such a partition by our proof.     

Partitioning series-parallel multigraphs into υ*-excluding edge covers

We prove that, for any given vertex υ* in a series-parallel graph G, its edge set can be partitioned into k = min{κ'(G) + 1,δ(G)} subsets such that each subset covers all the vertices of G possibly except for υ*, where δ(G) is the minimum degree of G and κ'(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for actually finding such a partition by our proof.     

The Entire Coloring of Series-Parallel Graphs

The entire chromatic number X_(vef)(G) of a plane graph G is the minimal number of colors needed for coloring vertices, edges and faces of G such that no two adjacent or incident elements are of the same color. Let G be a series-parallel plane graph, that is, a plane graph which contains no subgraphs homeomorphic to K_(4-) It is proved in this paper that X_(vef)(G)≤max{8, △(G) 2} and X_(vef)(G)=△ 1 if G is 2-connected and △(G)≥6.     

A note on a core catcher of a cooperative game

In Driessen (1986) it is shown that for games satisfying a certain condition the core of the game is included in the convex hull of the set of certain marginal worth vectors of the game, while it is conjectured that the inclusion holds without any condition on the game. In this note it is proved that the inclusion holds for all games.

---

Zusammenfassung In Driessen (1986) wurde für Spiele, die eine gewisse Bedingung erfüllen, gezeigt, da\ der Kern des Spieles in der konvexen Hülle von gewissen Vektoren der Marginalwerte liegt. Es wurde vermutet, da\ diese Inklusion ohne weitere Bedingung an das Spiel gilt. In dieser Note wird nun gezeigt, da\ die Inklusion für alle Spiele gilt.

     

Partitioning series-parallel multigraphs intoν*-excluding edge covers

We prove that, for any given vertexν* in a series-parallel graph G, its edge set can be partitioned into k= min{k′(G) 1,δ(G)} subsets such that each subset covers all the vertices of G possibly except forν*, whereδ(G) is the minimum degree of G and k′(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for actually finding such a partition by our proof.     

灾后运输网络中的最短路修复合作博弈

在最短路修复合作博弈中,当灾后运输网络规模较大时,最优成本分摊问题难以直接求解。基于拉格朗日松弛理论,提出了一种最短路修复合作博弈成本分摊算法。该算法将最短路修复合作博弈分解为两个具有特殊结构的子博弈,进而利用两个子博弈的结构特性,可以{高效地}求解出二者的最优成本分摊,将这两个成本分摊相加,可以获得原博弈的一个近乎最优的稳定成本分摊。结果部分既包含运输网络的随机仿真,也包含玉树地震灾区的现实模拟,无论数据来源于仿真还是现实,该算法都能在短时间内为最短路修复合作博弈提供稳定的成本分摊方案。     

系列平行图上带时间约束的Steiner最小树问题

对一类特殊系列平行图上带有时间约束的Steiner最小树问题,证明了其复杂性为NPC,并给出了一个完全多项式时间近似方案.     

合作博弈视角下城市道路交通拥堵收费研究

城市道路交通设施作为准公用物品,其外部效应必然导致交通拥堵的发生,实施拥堵收费的目的则是使交通拥堵产生的外部成本内部化,确保城市道路资源得到高效配置,应用经济杠杆来调节交通需求,以缓解交通拥堵.本文应用合作博弈相关理论对城市道路拥堵网络问题进行了分析,从同一时刻各个路段的通勤者数目这一角度定义拥堵成本,重点证明了拥堵成本为凸函数的城市道路拥堵网络博弈存在非空的核,拥堵成本为凹函数的城市道路交通网络博弈虽不存在非空的核,但总是存在最优的树网络,最后,结合上述结论对城市道路拥堵收费进行讨论,从理论上对拥堵收费的合理性进行了说明,并提出了进一步研究的方向.     

On computational complexity of membership test in flow games and linear production games

Let Γ≡(N,v) be a cooperative game with the player set N and characteristic function v: 2^N→R. An imputation of the game is in the core if no subset of players could gain advantage by splitting from the grand coalition of all players. It is well known that, for the flow game (and equivalently, for the linear production game), the core is always non-empty and a solution in the core can be found in polynomial time. In this paper, we show that, given an imputation x, it is NP-complete to decide x is not a member of the core, for the flow game. And because of the specific reduction we constructed, the result also holds for the linear production game. Received: October 2000/Final version: March 2002     

基于参与主体异质性条件下囚徒困境合作演化博弈模型研究

利用演化博弈理论,对参与主体异质性条件下的囚徒困境模型进行了探讨,求出了满足不同条件下的演化稳定策略,并对种群中个体异质性对演化稳定策略的影响进行了分析,得出种群中选择相同策略的个体异质性差异越大,参与个体选择合作行为作为演化稳定策略的可能性就越大.极端地,当个体的异质性趋向于无穷大时,合作成为唯一的演化稳定占优策略,为现实大多数合作系统中能保持长期的一种合作稳定状态提供了合理地解释.