若干組合合作對策模型的核心穩(wěn)定性.pdf

1、合作對策考慮的中心問題是如何將聯(lián)盟的整體收益(費用)公平合理地分配給聯(lián)盟中的每個成員。不同的合理性要求產(chǎn)生了不同的對策解的概念，如核心，穩(wěn)定集等。對具有穩(wěn)定核心的對策進(jìn)行刻畫是合作對策理論中最著名的困難問題之一。本論文討論的對策模型是建立在最優(yōu)填裝與覆蓋問題(packing andcovefing problem)基礎(chǔ)上的組合合作對策。組合合作對策模型的特點是：其特征函數(shù)值由相應(yīng)的組合優(yōu)化問題所確定，并且模型中組合優(yōu)化問題的結(jié)構(gòu)性質(zhì)與對

2、策解之間有密切關(guān)系?；诰€性規(guī)劃對偶理論，多面體理論和圖論中相關(guān)結(jié)果，本文主要研究了匹配對策、頂點覆蓋對策核心穩(wěn)定性的刻畫及相關(guān)的算法問題。主要結(jié)果有： ●核心穩(wěn)定性的充要條件及其相應(yīng)判定問題的多項式時間算法：匹配對策有穩(wěn)定核心當(dāng)且僅當(dāng)其基礎(chǔ)二部圖具有完美匹配；頂點覆蓋對策有穩(wěn)定核心當(dāng)且僅當(dāng)其基礎(chǔ)圖中任_邊都屬于一個最大匹配。 ●三個與核心穩(wěn)定性密切相關(guān)的性質(zhì)(核心的包容性、對策的精確性和可擴(kuò)性)的等價條件及其相應(yīng)判定問