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

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

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

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

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

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

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

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