若干組合優(yōu)化對策模型中的算法問題.pdf

1、合作對策考慮的是如何將收益v(N)合理地分配給聯盟N中的成員。根據不同的合理性要求產生了不同的對策解的概念，如核心，核子等等。在這篇論文中，我們主要討論的對策模型是由Kalai和Zemel在1982年首先提出的網鉻流對策，討論的內容包括：網絡流對策的核心穩(wěn)定性和網絡流對策中核子計算的算法問題，主要結果有：·我們先定義了一種特殊的弧，稱之為亞元，亞元滿足的性質是：在網絡中去掉亞元后不會影響網絡的最大流值?；谶@一概念，我們證明了簡單網絡流

2、對策有穩(wěn)定的核心當且僅當網絡中沒有亞元。 ·我們討論了三個與核心穩(wěn)定性密切相關的性質：核心的包容性、對策的精確性和可擴性的等價性，并證明了它們這三個性質與如下條件等價：在簡單網絡中每個(s，t)一截包含一個最小(s，t)一截。(其中s，t分別表示網絡的發(fā)點和收點)·證明了可以在多項式時間內求解簡單網絡流對策的核子。 ·證明了對于一般的網絡流對策，有關核子的計算問題是NP-困難的。 非合作對策理論中，最重要、最核心