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

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

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

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

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

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

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

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

4 吳海民;報業(yè)競爭中的博弈問題[J];青年記者;2005年02期

5 郭世榮;;概率史研究的一部新作:《從博弈問題到方法論學(xué)科》[J];內(nèi)蒙古師范大學(xué)學(xué)報(自然科學(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é)報;2012年02期

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

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

2 梅麗麗;若干設(shè)施選址博弈問題的機制設(shè)計[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è)計[D];上海大學(xué);2015年

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

9 方志耕;灰色博弈理論及其經(jīng)濟應(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 范國強;若干排序博弈問題的協(xié)調(diào)機制研究[D];中國海洋大學(xué);2014年

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

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

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

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

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

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

本文編號：2842586