本文關(guān)鍵詞：基于多樣性約束的匹配模型與算法，由筆耕文化傳播整理發(fā)布。

【摘要】：1962年David Gale和Lloyd Shapley提出了穩(wěn)定匹配的概念,以此為基礎(chǔ)的理論及應(yīng)用獲得了2012年的諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。該模型涉及應(yīng)用數(shù)學(xué)、經(jīng)濟(jì)學(xué)和計(jì)算機(jī)科學(xué),在市場(chǎng)機(jī)制設(shè)計(jì)和工程實(shí)踐中有很多重要的應(yīng)用。在多元化的今天,很多實(shí)際的匹配問題需要結(jié)果中更多考慮多樣性要求。因?yàn)楸尘暗牟町愋酝沟眠@樣的群體更活躍、更有創(chuàng)造力也更穩(wěn)健。本文研究基于多樣性約束的單邊偏好列表的匹配問題。多樣性的描述中包含大量的互補(bǔ)性,這給經(jīng)典的穩(wěn)定匹配算法帶來(lái)了本質(zhì)性的困難。本文通過(guò)對(duì)參與者分類并控制每一個(gè)子類的上下限來(lái)間接地描述多樣性�？紤]到單邊偏好列表,我們分別提出松弛優(yōu)化方法和動(dòng)態(tài)清倉(cāng)價(jià)格機(jī)制來(lái)解決該問題。在松弛優(yōu)化方法中,我們?cè)跐M足子類上下限約束的前提下,把最大化偏好得分的總和作為優(yōu)化目標(biāo)。我們證明了在子類不交的情況下,松弛后的優(yōu)化問題仍然可以得到整數(shù)最優(yōu)解。為了進(jìn)一步平衡公平性和多樣性,我們?cè)趦?yōu)化目標(biāo)中加入多樣性的懲罰項(xiàng),通過(guò)調(diào)整懲罰系數(shù)來(lái)把握兩者之間的平衡。結(jié)合升價(jià)拍賣和降價(jià)拍賣,我們提出了兩階段的動(dòng)態(tài)清倉(cāng)價(jià)格機(jī)制。在第一階段我們對(duì)供不應(yīng)求的商品進(jìn)行升價(jià)拍賣,以滿足上限約束;在第二階段,我們對(duì)還有剩余的商品進(jìn)行降價(jià)拍賣,以滿足下限約束。最終得到滿足上下限約束的清倉(cāng)價(jià)格和穩(wěn)定匹配。類似于松弛優(yōu)化方法中公平性和多樣性的平衡,我們的動(dòng)態(tài)機(jī)制在滿足上下限約束之后,啟發(fā)式地嘗試優(yōu)化多樣性度量,進(jìn)一步平衡公平性和多樣性。付費(fèi)搜索是商業(yè)搜索引擎主要的贏利方式,其本質(zhì)上就是一個(gè)匹配的優(yōu)化問題,這個(gè)領(lǐng)域的研究也稱為計(jì)算廣告。本文給出匹配模型和算法在計(jì)算廣告中的應(yīng)用,并進(jìn)行了數(shù)值實(shí)驗(yàn)。
【關(guān)鍵詞】：穩(wěn)定匹配 清倉(cāng)價(jià)格 動(dòng)態(tài)機(jī)制 NP完全問題 計(jì)算廣告
【學(xué)位授予單位】：清華大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP301.6
【目錄】：

• 摘要3-4
• abstract4-8
• 第1章 引言8-35
• 1.1 穩(wěn)定匹配的模型與算法9-22
• 1.1.1 延遲接受算法10-12
• 1.1.2 Top Trading Circle算法12-14
• 1.1.3 市場(chǎng)機(jī)制下的匹配算法14-21
• 1.1.4 四種算法的聯(lián)系21-22
• 1.2 穩(wěn)定匹配的擴(kuò)展及變型22-30
• 1.2.1 偏好列表的擴(kuò)展22-24
• 1.2.2 一對(duì)多的擴(kuò)展24-29
• 1.2.3 高維匹配問題29-30
• 1.3 研究?jī)?nèi)容30-35
• 1.3.1 問題的描述、思路及解決方案30-33
• 1.3.2 各章內(nèi)容簡(jiǎn)介33
• 1.3.3 主要貢獻(xiàn)33-35
• 第2章 容量下限與多樣性約束35-45
• 2.1 容量下限約束35-36
• 2.2 多樣性約束36-39
• 2.3 多樣性約束的分類刻畫39-41
• 2.4 相關(guān)工作41-45
• 第3章 松弛優(yōu)化方法45-61
• 3.1 多樣性作為上下限約束45-54
• 3.1.1 數(shù)學(xué)表達(dá)45-46
• 3.1.2 松弛后的解46-51
• 3.1.3 對(duì)偶問題51-54
• 3.2 多樣性和公平的平衡54-61
• 3.2.1 二次規(guī)劃56-58
• 3.2.2 一些其他選擇58-61
• 第4章 動(dòng)態(tài)清倉(cāng)價(jià)格機(jī)制61-75
• 4.1 動(dòng)態(tài)清倉(cāng)價(jià)格機(jī)制研究現(xiàn)狀61-63
• 4.2 上下限約束的動(dòng)態(tài)機(jī)制算法63-68
• 4.3 子類約束的動(dòng)態(tài)機(jī)制算法（SCDM）68-69
• 4.4 考慮平衡的子類約束動(dòng)態(tài)機(jī)制算法（SCDMB）69-72
• 4.5 討論72-75
• 第5章 計(jì)算廣告75-80
• 5.1 付費(fèi)搜索系統(tǒng)75-76
• 5.2 廣義二價(jià)競(jìng)拍76-77
• 5.3 廣告選擇77-80
• 第6章 總結(jié)與展望80-82
• 6.1 總結(jié)80-81
• 6.2 展望81-82
• 參考文獻(xiàn)82-88
• 致謝88-90
• 個(gè)人簡(jiǎn)歷、在學(xué)期間發(fā)表的學(xué)術(shù)論文與研究成果90

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前2條

1 季曉慧;張健;;一種求解混合約束問題的快速完備算法[J];計(jì)算機(jī)研究與發(fā)展;2006年03期

2 ;[J];;年期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前1條

1 沈杰;王艷;張芳明;;市場(chǎng)經(jīng)濟(jì)條件下誠(chéng)信理論和我國(guó)的政策[A];國(guó)有經(jīng)濟(jì)論叢(2012)——深入推進(jìn)國(guó)有經(jīng)濟(jì)戰(zhàn)略性調(diào)整[C];2012年

中國(guó)重要報(bào)紙全文數(shù)據(jù)庫(kù) 前6條

1 本報(bào)特約評(píng)論員;化要素約束壓力為轉(zhuǎn)型發(fā)展動(dòng)力[N];中國(guó)城鄉(xiāng)金融報(bào);2013年

2 唐人;“約束”與“速度”不能再打架[N];中國(guó)國(guó)土資源報(bào);2006年

3 陶金節(jié);從四個(gè)方面約束政府權(quán)力[N];民主與法制時(shí)報(bào);2013年

4 楊成超;民主社會(huì)的危機(jī)與非選舉約束[N];中國(guó)圖書商報(bào);2004年

5 牛潤(rùn)霞;無(wú)差異法則是醫(yī)治自主創(chuàng)新缺乏的良藥[N];學(xué)習(xí)時(shí)報(bào);2012年

6 夏興園 趙明嵐;提高資源配置使用效率[N];吉林日?qǐng)?bào);2005年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前3條

1 崔卿;基于多樣性約束的匹配模型與算法[D];清華大學(xué);2015年

2 閆鄒先;我國(guó)上市公司最優(yōu)激勵(lì)約束結(jié)構(gòu)研究[D];山東大學(xué);2008年

3 楊丹妮;政府籌資方式選擇與約束:一項(xiàng)思想史考察及對(duì)中國(guó)財(cái)政體制改革的意義[D];浙江大學(xué);2015年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前4條

1 王恒進(jìn);國(guó)有企業(yè)高層管理人員的約束與激勵(lì)問題研究[D];蘇州大學(xué);2003年

2 黃志鵬;中國(guó)企業(yè)對(duì)歐盟直接投資研究[D];福州大學(xué);2005年

3 宋其勤;帶二維裝箱約束的團(tuán)隊(duì)定向問題的研究[D];重慶交通大學(xué);2014年

4 柯丹;國(guó)有商業(yè)銀行激勵(lì)與約束問題研究[D];廣西大學(xué);2004年

  本文關(guān)鍵詞：基于多樣性約束的匹配模型與算法，，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：381120