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

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

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