基于抽象論辯理論的穩(wěn)定匹配問題研究.pdf

1、穩(wěn)定匹配問題（簡稱為SM）一直是數(shù)學(xué)、運(yùn)籌學(xué)、經(jīng)濟(jì)學(xué)和社會學(xué)等領(lǐng)域研究的熱點(diǎn)問題。穩(wěn)定匹配問題通常以矩陣形式出現(xiàn)，因此多以組合數(shù)學(xué)的方法進(jìn)行計(jì)算，比較依賴數(shù)組的順序特性，適合求解性別優(yōu)先的單個穩(wěn)定匹配結(jié)果。圖論也是求解穩(wěn)定匹配較常用的理論之一，主要從穩(wěn)定匹配問題的結(jié)構(gòu)著手，通過求解符合某些特點(diǎn)的二分圖來計(jì)算穩(wěn)定匹配結(jié)果。無論是從組合數(shù)學(xué)的角度還是從圖論的角度，對穩(wěn)定匹配問題的研究都缺少系統(tǒng)的形式化刻畫，并且求解過程高度抽象。傳統(tǒng)的研究無

2、法高效地判斷單個配對的狀態(tài)，因?yàn)橐粋€配對必須在某個穩(wěn)定匹配中才是穩(wěn)定配對，因此我們必須計(jì)算出完整的穩(wěn)定匹配才能判斷單個配對的狀態(tài)。此外，穩(wěn)定匹配問題具有非單調(diào)性，而已有的研究著重分析新加入的對象以及原有對象所獲得的匹配更好或者更差，不能很好地處理穩(wěn)定匹配問題的動態(tài)計(jì)算問題。
　　論辯理論可以很好地解決上述問題。穩(wěn)定匹配問題是一個在沖突的信息中進(jìn)行選擇——評估——再選擇——再評估的過程，可以用抽象論辯框架對其進(jìn)行刻畫。與組合數(shù)學(xué)和圖

3、論的方法相比，基于論辯的分析更貼合我們的日常推理過程。我們將每一個配對抽象為論證，將對象間互相的偏好度抽象為論證間的二元攻擊關(guān)系，因此計(jì)算穩(wěn)定匹配時(shí)可以從任何一個論證入手，而不必依賴原有的順序特征。抽象論辯框架有各種語義，而我們可以選擇穩(wěn)定語義和優(yōu)先語義現(xiàn)有的算法對不同的穩(wěn)定匹配問題進(jìn)行求解，如基于回答集編程的方法（ASP），基于加標(biāo)的方法（MC），基于強(qiáng)連通分量的方法（SCC）和基于絕對被駁斥論證的方法（MSR）。論辯語義可以計(jì)算出所

4、有穩(wěn)定匹配結(jié)果，并且所求得的結(jié)果是無性別差異的（當(dāng)然，對于穩(wěn)定婚姻問題，男士最優(yōu)和女士最優(yōu)的結(jié)果也在所有的穩(wěn)定匹配中）。我們可以通過提高論辯語義計(jì)算效率來提高穩(wěn)定匹配的計(jì)算效率，例如，將整個論辯框架劃分為多個更小的SCC，分別計(jì)算每個SCC，然后合并各個部分的語義;或者將絕對被駁斥論證——被基外延攻擊的論證從計(jì)算過程中刪除。我們可以用論辯爭議樹來判斷單個配對是否穩(wěn)定，是否屬于所有穩(wěn)定匹配。當(dāng)穩(wěn)定匹配問題發(fā)生變化時(shí)，例如增加匹配對象、改變

5、偏好列表、刪除配對，通過論辯框架可以對匹配結(jié)果的數(shù)量改變和內(nèi)容變化進(jìn)行分析，并且用論辯語義的動態(tài)計(jì)算對穩(wěn)定匹配問題進(jìn)行比較高效的重新求解。
　　我們首先介紹抽象論辯理論，然后用抽象論辯框架對穩(wěn)定婚姻和穩(wěn)定室友問題進(jìn)行了刻畫:包括帶完整全序偏好列表的經(jīng)典穩(wěn)定婚姻問題sm和經(jīng)典穩(wěn)定室友問題sr，帶完整非全序偏好列表（又稱偏序列表或無差別列表）的穩(wěn)定婚姻問題smt和穩(wěn)定室友問題srt，帶全序不完整偏好列表的穩(wěn)定婚姻問題smi和穩(wěn)定室友問

6、題sri，帶非全序不完整偏好列表的穩(wěn)定婚姻問題smti和穩(wěn)定室友問題srti。對穩(wěn)定匹配問題進(jìn)行論辯形式化后，我們用論辯語義證明的方法來判斷單個配對的狀態(tài);然后用穩(wěn)定語義來求解sm、smt、smi、smti問題，用優(yōu)先語義求解sr、srt、sri、srti問題。最后在靜態(tài)求解的基礎(chǔ)上根據(jù)論辯動態(tài)性的研究對穩(wěn)定匹配問題的動態(tài)性進(jìn)行分析，主要介紹基于劃分的動態(tài)計(jì)算方法和基于論證狀態(tài)的計(jì)算方法。
　　通過分析，我們證明穩(wěn)定語義和優(yōu)先語義

7、的求解結(jié)果就是我們所要求取的相應(yīng)的穩(wěn)定匹配結(jié)果，并且如果穩(wěn)定匹配結(jié)果存在，我們總是能用相應(yīng)的論辯語義進(jìn)行求解。對于某個配對，如果該配對相應(yīng)的論證沒有被輕信證成（在某個語義下），則該論證不屬于任何外延，該配對也不屬于任何穩(wěn)定匹配。穩(wěn)定匹配問題的論辯框架有其自身的特點(diǎn)——每個論證都與其他論證有直接或間接的關(guān)系，使得我們無法很好地劃分SCC，并且使用基于加標(biāo)的方法也會延長判斷的過程，因此，我們用基于擴(kuò)展的MSR方法:從每一個論證出發(fā)，嘗試將其