設(shè)施選址問題是經(jīng)典的組合優(yōu)化問題之一,是指在給定的網(wǎng)絡(luò)上確定一個(gè)或多個(gè)設(shè)施的位置,為網(wǎng)絡(luò)上的所有用戶服務(wù)并使得成本最小化的問題.在優(yōu)化問題中,所有用戶的位置信息都是公開的.隨著算法博弈論學(xué)科的興起,單決策者的優(yōu)化問題演變成多決策者的博弈問題.本文將研究設(shè)施選址博弈,其與經(jīng)典模型不同之處在于,每個(gè)用戶的位置信息都是私有的.機(jī)制設(shè)計(jì)者首先公布算法(機(jī)制),該算法可根據(jù)用戶的位置求解出設(shè)施的位置.用戶在了解算法的前提下提供對(duì)自己最有利(并不一定真實(shí))的位置信息.在喜好性設(shè)施選址博弈問題中,用戶期望設(shè)施離自己盡可能近;而在排斥性設(shè)施選址博弈中,用戶則期望設(shè)施離自己盡可能遠(yuǎn).在博弈問題中,用戶的期望量化為用戶的效用(費(fèi)用).機(jī)制設(shè)計(jì)者希望給出的機(jī)制能保證用戶們?cè)敢馓峁┱鎸?shí)的位置信息,并使得某種社會(huì)目標(biāo)(如所有用戶的效用和)達(dá)到最優(yōu),該目標(biāo)稱為社會(huì)效用函數(shù).如何設(shè)計(jì)高效并且真實(shí)可信的機(jī)制是機(jī)制設(shè)計(jì)的核心問題.2009年P(guān)rocaccia和Tennenholtz發(fā)表了第一篇設(shè)施選址博弈的無支付機(jī)制設(shè)計(jì)的文章,引起了學(xué)術(shù)界的廣泛關(guān)注.雖然設(shè)施選址博弈的機(jī)制設(shè)計(jì)近幾年有了不少的研究工作,但目前的成果都集中在較為基礎(chǔ)的模型上,而結(jié)合真實(shí)場(chǎng)景相對(duì)復(fù)雜的效用函數(shù)的研究較少.本文將從用戶效用和社會(huì)效用兩個(gè)方面研究以下幾個(gè)新的設(shè)施選址博弈模型并給出理論分析.已有的研究工作中,用戶的效用一般為用戶到設(shè)施的距離.然而在實(shí)際場(chǎng)景中,由于用戶所處的周圍環(huán)境不同,距離相同時(shí)用戶的效用函數(shù)也不一定相同.我們從相對(duì)滿意的角度出發(fā),以用戶到設(shè)施的距離與其最遠(yuǎn)距離的比例來表示用戶的效用函數(shù),稱之為用戶的滿意度函數(shù).本文分別定義了喜好性和排斥性設(shè)施選址博弈問題的用戶滿意度函數(shù),并且分析了用戶滿意度之和最大化的社會(huì)目標(biāo).對(duì)于喜好性設(shè)施選址問題,我們首先證明中位數(shù)機(jī)制的近似比為3/2,接著給了一個(gè)近似比為5/4的確定機(jī)制,同時(shí)指出該問題的下界至少為5/2-(?);對(duì)于排斥性設(shè)施選址博弈問題,本文證明多數(shù)機(jī)制是2-近似的,這也是任何可信機(jī)制能達(dá)到的最好近似比.在現(xiàn)實(shí)生活中,當(dāng)設(shè)施和用戶的距離足夠近(或者足夠遠(yuǎn))時(shí),用戶對(duì)設(shè)施的好惡程度可能不會(huì)因?yàn)榫嚯x再變近(或再變遠(yuǎn))而發(fā)生改變.針對(duì)排斥性設(shè)施選址博弈問題,我們?cè)O(shè)計(jì)了如下效用函數(shù):給定兩個(gè)距離的閾值d1和d2,當(dāng)用戶和設(shè)施的距離小于d1時(shí),用戶對(duì)設(shè)施是完全排斥的,也就是用戶的效用為0;而當(dāng)該距離超過d2時(shí),用戶對(duì)設(shè)施是完全接受的,也就是用戶的效用為1;在d1和d2之間時(shí),用戶的效用為0和1之間的線性函數(shù).對(duì)于該模型,本文首先討論只有一個(gè)閾值的情形(d1=d2),并設(shè)計(jì)了最優(yōu)的機(jī)制.對(duì)于兩個(gè)閾值的情形,問題則困難得多.當(dāng)?shù)谝粋�(gè)閾值d1≥1/2時(shí),任何真實(shí)可信的確定機(jī)制都是無界的,我們進(jìn)而研究了該情形下的隨機(jī)機(jī)制,其上下界分別為2和4/3.接著,我們給出多數(shù)機(jī)制和d1,d2相關(guān)的近似比,并且證明該機(jī)制大部分情況下是最好的.最后,對(duì)于d2≤1/2的情形,提供了一類確定機(jī)制并給出對(duì)應(yīng)的近似比.在社會(huì)效用函數(shù)方面,我們從實(shí)際經(jīng)濟(jì)應(yīng)用環(huán)境出發(fā),考慮了用戶效用平方和的社會(huì)目標(biāo).本文研究了每個(gè)用戶有一個(gè)位置和多個(gè)位置兩種模型.對(duì)于每個(gè)用戶只有一個(gè)位置、社會(huì)效用函數(shù)為用戶效用平方和的模型,確定機(jī)制的上下界均為5,而隨機(jī)機(jī)制的上下界分別為5/3和1.0428.對(duì)于每個(gè)用戶有多個(gè)位置模型,本文討論了用戶效用和以及用戶效用平方和兩類社會(huì)目標(biāo).對(duì)于第一類社會(huì)效用函數(shù),我們證明隨機(jī)機(jī)制的上下界分別為3/2和10/9;對(duì)于第二類,隨機(jī)機(jī)制的上下界分別為5/3和1.0679.綜上所述,本文基于實(shí)際應(yīng)用,研究了設(shè)施選址機(jī)制設(shè)計(jì)的若干新模型.針對(duì)已有研究工作中用戶效用函數(shù)同構(gòu)的局限性,本文提出了用戶效用為滿意度的異構(gòu)模型;對(duì)于用戶效用函數(shù)為好惡程度不變的情形,本文引進(jìn)了帶排斥因子的分段函數(shù)模型;針對(duì)已有研究中社會(huì)效用函數(shù)單一化的問題,我們將平方和社會(huì)效用函數(shù)引入到排斥性設(shè)施選址博弈問題的機(jī)制設(shè)計(jì)中.新模型與真實(shí)場(chǎng)景中用戶復(fù)雜多樣的效用更貼切.在研究方法上,本文對(duì)所提出的模型給出了真實(shí)可信的機(jī)制并對(duì)所給機(jī)制進(jìn)行了理論分析.
【學(xué)位單位】：浙江大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2018
【中圖分類】：O221.7;O225
【部分圖文】：

算輸出結(jié)果．最后，每個(gè)局中人根據(jù)輸出結(jié)果求得自身的效用．對(duì)于直接機(jī)制，由于局??中人的行為集和類型集相同，因此相當(dāng)于局中Ａ匯報(bào)一個(gè)類型，但這個(gè)類型不一定和??私有的類型相同，我們用＆表示局中人ｉ?ｅ?ｉｖ匯報(bào)的類型．圖１．１分別演示了間接機(jī)??制和直接機(jī)制設(shè)計(jì)問題的流程．??（Ｃｅ＾）?（Ｃｅ＾ｊ?（＾３?局中人私有類型??Ｘ．?Ｘ．??Ｓｉ?：ｒｘ?．．．?ｓｎ－．Ｔ？＾?Ａ？?．局中人策略函數(shù)??Ｊ，?ＪＬ?ｔ＼?．．．?ｉｎ?局中人匯報(bào)的類型??Ｕ?６?＾０?…?局中人的行為??Ｘ，?Ｘ．?＾?＾??Ｎ??分：４?ｘ?…ｘ?人—＞?（９?／?：?Ａ＼?ｘ?？?？?？?ｘ?Ａｎ?—＞?Ｏ?機(jī)制??????ｖ????????－＞??輸出結(jié)果??／???Ｎ?ｆ?＾?Ｎ?ｆ?＾?＼?／＂?＊?＼??Ｕｉ?：?Ｏ?ｘ?Ｔｉ?＾?Ｅ?？?ｕｎ?：?Ｏ?ｘＴｎ?Ｕｉ?：?Ｏ?ｘ?Ｔ＼?Ｕ?…ｕｎ?：?Ｏ?ｘ?Ｔ？?－＞?Ｒ?效用函數(shù)??＠Ｊ…１?＾?＠Ｊ…石?效用值??⑷間接機(jī)制?（ｂ）直接機(jī)制??圖１．１機(jī)制設(shè)計(jì)問題的流程??圖１．１可以很容易看出，間接機(jī)制比直接機(jī)制流程更復(fù)雜．那么，這兩者之間有??什么關(guān)聯(lián)呢？機(jī)制設(shè)計(jì)中著名的顯示原理（Ｒｅｖｅ

數(shù)－由Ａ?Ｓ辦，可知第一個(gè)局中人僅在區(qū)間（１?－?ｅ，１］上有正的效用－由于兩個(gè)局中人??關(guān)于｜對(duì)稱，因此第二個(gè)局中人在區(qū)間［〇ｄ上有正的效用．兩個(gè)局中人的效用函數(shù)??如圖３．３所示．用ｆ表示位置組合ｘ的最優(yōu)設(shè)施位置．從圖３．３很容易得出ｆ為０或??１并且最優(yōu)社會(huì)效用犯（ｙ＊，Ｘ）?＝??令／表示任意的只把０和１作為候選點(diǎn)的防策略操縱性的隨機(jī)機(jī)制．用分布Ｐ??表示機(jī)制／對(duì)位置組合ｘ的解，也即／（ｘ）?＝?Ｒ顯然有抑（尸，Ｘ）?ｇ?ｘ）?＝??并且由于兩個(gè)局中人關(guān)于｜對(duì)稱的，不失一般性，假設(shè)第一個(gè)局中人對(duì)于分布Ｐ的??效用??ｍ?、／抓＜ｙ，ｘ）?ｅ??Ｕｌ｛Ｒ＇Ｘｌ）－￣＾?＝?Ｗ＾ｈＹ??ｕ??１?丨丨?／??（ｙ，?ＸＪ）??／?＼???Ｕ２（ｙ：ｉ２）??／????．／！??■?／?／］???－？?－：?－．１?；－？?ｖ?？－；?－Ｊ．－??＃?＞?Ｖ??０?Ｃ?１?－?ｒｆ－２?＋?ｒｆｌ?１?—?？?１??圖３．３?以及４的效用函數(shù)．橫軸ｙ表示設(shè)施的位置．??接著討論另一個(gè)位置組合Ｘ＇?＝?？?＝?１?—?ｄ２，?．ｔ２?＝?４?＋?ｅ），其中ｅ與位置組合ｘ??中的相同．此時(shí)第一個(gè)局中人到端點(diǎn)〇的距離＜〇，?〇?＜?ｄ１；因此第一個(gè)局中人僅在??區(qū)間（１?－?ｄ２?＋山

么第一個(gè)局中人在［〇，?｜）區(qū)間上，因此第一個(gè)局中人僅在（１?－?１］區(qū)間上有正的??效用．由于兩個(gè)局中人關(guān)于Ｉ對(duì)稱，因此第二個(gè)局中人在［〇，?￥）區(qū)間有正的效用．??兩個(gè)局中人的效用函數(shù)如圖３．４所示．從圖３．４可知位置組合ｘ的最優(yōu)設(shè)施位置在０??或１處并且最優(yōu)的社會(huì)效用為洲（〇，?ｘ）＝抓（１，ｘ）?＝??用／表示任意的防策略操縱性的隨機(jī)機(jī)制．令／⑷＝凡注意任意機(jī)制的解都??不會(huì)超過最優(yōu)社會(huì)效用，于是Ｘ）?ｇ抑（０，?ｘ）．由于兩個(gè)局中人關(guān)于｜對(duì)稱，不失??一般性，假設(shè)??秦??接著討論另一個(gè)位置組合Ｖ?＝（而＝１?－?＾％?＝?ｒｆ２）．很容易看出對(duì)于位??置組合ｘ＇第二個(gè)局中人僅在［０，ｄ２?－由）區(qū)間上有正的效用．效用函數(shù)如圖３．４所??示．用ｆ表示位置組合Ｘ＇的最優(yōu)設(shè)施位置．從圖３．４可以看出ｙ?＝?０，最優(yōu)社會(huì)效用??ｓｕ（ｙ＊，ｘ＇）?＝?１．??ｕ??１?？（??ｗｉ?（ｙ，?ＸＩ?）??＼???ｕ２（ｙ：?ｘ２）??＼???ｗ２（ｗ
【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 嚴(yán)加安;;數(shù)學(xué)的奇妙:我們身邊的概率和博弈問題[J];語數(shù)外學(xué)習(xí)(高中版上旬);2016年09期

2 袁冬冬;;現(xiàn)時(shí)期應(yīng)加強(qiáng)立法博弈問題的研究[J];人大研究;2013年04期

3 邱中華;高潔;朱躍星;;應(yīng)用免疫算法求解博弈問題[J];系統(tǒng)工程學(xué)報(bào);2006年04期

4 吳海民;報(bào)業(yè)競(jìng)爭(zhēng)中的博弈問題[J];青年記者;2005年02期

5 郭世榮;;概率史研究的一部新作:《從博弈問題到方法論學(xué)科》[J];內(nèi)蒙古師范大學(xué)學(xué)報(bào)(自然科學(xué)漢文版);2012年04期

6 林厚從;;博弈問題的策略研究[J];軟件導(dǎo)刊;2010年12期

7 孟坤;;有趣的博弈問題[J];初中數(shù)學(xué)教與學(xué);2006年01期

8 王明珠;;城鎮(zhèn)拆遷的利益博弈問題[J];住宅產(chǎn)業(yè);2010年Z1期

9 馬占欣;李亞;陸玉昌;;用遺傳算法解決博弈問題[J];河南科學(xué);2007年02期

10 賈小勇;袁敏;;彰顯概率文化的亮麗篇章——讀《從博弈問題到方法論學(xué)科》[J];咸陽師范學(xué)院學(xué)報(bào);2012年02期

相關(guān)博士學(xué)位論文 前10條

1 莊翼;部分信息下正倒向隨機(jī)系統(tǒng)的微分博弈問題及金融中的應(yīng)用[D];山東大學(xué);2018年

2 梅麗麗;若干設(shè)施選址博弈問題的機(jī)制設(shè)計(jì)[D];浙江大學(xué);2018年

3 譚德慶;多維博弈及應(yīng)用研究[D];西南交通大學(xué);2004年

4 王昭;具有模糊支付的博弈問題及其應(yīng)用研究[D];北京理工大學(xué);2006年

5 張劍;不確定條件下多周期庫存博弈問題研究[D];北京交通大學(xué);2017年

6 尚宇紅;博弈論前史研究[D];西北大學(xué);2003年

7 魏麒;排序理論中若干問題的理論分析和算法設(shè)計(jì)[D];上海大學(xué);2015年

8 穆蕊;非零和隨機(jī)微分博弈及相關(guān)的高維倒向隨機(jī)微分方程[D];山東大學(xué);2015年

9 方志耕;灰色博弈理論及其經(jīng)濟(jì)應(yīng)用研究[D];南京航空航天大學(xué);2007年

10 孫薇;組織信息安全投資中的博弈問題研究[D];大連理工大學(xué);2008年

相關(guān)碩士學(xué)位論文 前10條

1 盧延杰;幾類博弈問題的直接算法及其應(yīng)用研究[D];福州大學(xué);2014年

2 劉春麗;我國文獻(xiàn)信息資源共享博弈問題研究[D];東北師范大學(xué);2005年

3 姜小華;偷稅與反偷稅，政府與企業(yè)稅收博弈問題研究[D];浙江大學(xué);2002年

4 范國強(qiáng);若干排序博弈問題的協(xié)調(diào)機(jī)制研究[D];中國海洋大學(xué);2014年

5 張芬;基于最優(yōu)控制的微分博弈問題研究[D];云南師范大學(xué);2015年

6 袁冬冬;我國社會(huì)轉(zhuǎn)型期立法博弈問題研究[D];鄭州大學(xué);2012年

7 李靜;時(shí)間一致均值—方差投資組合博弈問題[D];中南大學(xué);2014年

8 任偉;兩臺(tái)同類機(jī)排序覆蓋博弈問題PoA及SPoA研究[D];浙江大學(xué);2010年

9 黃俏玲;零和隨機(jī)微分投資組合博弈問題[D];中南大學(xué);2013年

10 諸栗;易逝品需求不確定的供應(yīng)鏈主從博弈問題[D];天津大學(xué);2007年

本文編號(hào)：2842586