若干设施选址博弈问题的机制设计

发布时间：2020-10-16 02:05

　　 设施选址问题是经典的组合优化问题之一,是指在给定的网络上确定一个或多个设施的位置,为网络上的所有用户服务并使得成本最小化的问题.在优化问题中,所有用户的位置信息都是公开的.随着算法博弈论学科的兴起,单决策者的优化问题演变成多决策者的博弈问题.本文将研究设施选址博弈,其与经典模型不同之处在于,每个用户的位置信息都是私有的.机制设计者首先公布算法(机制),该算法可根据用户的位置求解出设施的位置.用户在了解算法的前提下提供对自己最有利(并不一定真实)的位置信息.在喜好性设施选址博弈问题中,用户期望设施离自己尽可能近;而在排斥性设施选址博弈中,用户则期望设施离自己尽可能远.在博弈问题中,用户的期望量化为用户的效用(费用).机制设计者希望给出的机制能保证用户们愿意提供真实的位置信息,并使得某种社会目标(如所有用户的效用和)达到最优,该目标称为社会效用函数.如何设计高效并且真实可信的机制是机制设计的核心问题.2009年Procaccia和Tennenholtz发表了第一篇设施选址博弈的无支付机制设计的文章,引起了学术界的广泛关注.虽然设施选址博弈的机制设计近几年有了不少的研究工作,但目前的成果都集中在较为基础的模型上,而结合真实场景相对复杂的效用函数的研究较少.本文将从用户效用和社会效用两个方面研究以下几个新的设施选址博弈模型并给出理论分析.已有的研究工作中,用户的效用一般为用户到设施的距离.然而在实际场景中,由于用户所处的周围环境不同,距离相同时用户的效用函数也不一定相同.我们从相对满意的角度出发,以用户到设施的距离与其最远距离的比例来表示用户的效用函数,称之为用户的满意度函数.本文分别定义了喜好性和排斥性设施选址博弈问题的用户满意度函数,并且分析了用户满意度之和最大化的社会目标.对于喜好性设施选址问题,我们首先证明中位数机制的近似比为3/2,接着给了一个近似比为5/4的确定机制,同时指出该问题的下界至少为5/2-(?);对于排斥性设施选址博弈问题,本文证明多数机制是2-近似的,这也是任何可信机制能达到的最好近似比.在现实生活中,当设施和用户的距离足够近(或者足够远)时,用户对设施的好恶程度可能不会因为距离再变近(或再变远)而发生改变.针对排斥性设施选址博弈问题,我们设计了如下效用函数:给定两个距离的阈值d1和d2,当用户和设施的距离小于d1时,用户对设施是完全排斥的,也就是用户的效用为0;而当该距离超过d2时,用户对设施是完全接受的,也就是用户的效用为1;在d1和d2之间时,用户的效用为0和1之间的线性函数.对于该模型,本文首先讨论只有一个阈值的情形(d1=d2),并设计了最优的机制.对于两个阈值的情形,问题则困难得多.当第一个阈值d1≥1/2时,任何真实可信的确定机制都是无界的,我们进而研究了该情形下的随机机制,其上下界分别为2和4/3.接着,我们给出多数机制和d1,d2相关的近似比,并且证明该机制大部分情况下是最好的.最后,对于d2≤1/2的情形,提供了一类确定机制并给出对应的近似比.在社会效用函数方面,我们从实际经济应用环境出发,考虑了用户效用平方和的社会目标.本文研究了每个用户有一个位置和多个位置两种模型.对于每个用户只有一个位置、社会效用函数为用户效用平方和的模型,确定机制的上下界均为5,而随机机制的上下界分别为5/3和1.0428.对于每个用户有多个位置模型,本文讨论了用户效用和以及用户效用平方和两类社会目标.对于第一类社会效用函数,我们证明随机机制的上下界分别为3/2和10/9;对于第二类,随机机制的上下界分别为5/3和1.0679.综上所述,本文基于实际应用,研究了设施选址机制设计的若干新模型.针对已有研究工作中用户效用函数同构的局限性,本文提出了用户效用为满意度的异构模型;对于用户效用函数为好恶程度不变的情形,本文引进了带排斥因子的分段函数模型;针对已有研究中社会效用函数单一化的问题,我们将平方和社会效用函数引入到排斥性设施选址博弈问题的机制设计中.新模型与真实场景中用户复杂多样的效用更贴切.在研究方法上,本文对所提出的模型给出了真实可信的机制并对所给机制进行了理论分析.
【学位单位】：浙江大学
【学位级别】：博士
【学位年份】：2018
【中图分类】：O221.7;O225
【部分图文】：

算输出结果．最后，每个局中人根据输出结果求得自身的效用．对于直接机制，由于局??中人的行为集和类型集相同，因此相当于局中Ａ汇报一个类型，但这个类型不一定和??私有的类型相同，我们用＆表示局中人ｉ?ｅ?ｉｖ汇报的类型．图１．１分别演示了间接机??制和直接机制设计问题的流程．??（Ｃｅ＾）?（Ｃｅ＾ｊ?（＾３?局中人私有类型??Ｘ．?Ｘ．??Ｓｉ?：ｒｘ?．．．?ｓｎ－．Ｔ？＾?Ａ？?．局中人策略函数??Ｊ，?ＪＬ?ｔ＼?．．．?ｉｎ?局中人汇报的类型??Ｕ?６?＾０?…?局中人的行为??Ｘ，?Ｘ．?＾?＾??Ｎ??分：４?ｘ?…ｘ?人—＞?（９?／?：?Ａ＼?ｘ?？?？?？?ｘ?Ａｎ?—＞?Ｏ?机制??????ｖ????????－＞??输出结果??／???Ｎ?ｆ?＾?Ｎ?ｆ?＾?＼?／＂?＊?＼??Ｕｉ?：?Ｏ?ｘ?Ｔｉ?＾?Ｅ?？?ｕｎ?：?Ｏ?ｘＴｎ?Ｕｉ?：?Ｏ?ｘ?Ｔ＼?Ｕ?…ｕｎ?：?Ｏ?ｘ?Ｔ？?－＞?Ｒ?效用函数??＠Ｊ…１?＾?＠Ｊ…石?效用值??⑷间接机制?（ｂ）直接机制??图１．１机制设计问题的流程??图１．１可以很容易看出，间接机制比直接机制流程更复杂．那么，这两者之间有??什么关联呢？机制设计中著名的显示原理（Ｒｅｖｅ

数－由Ａ?Ｓ办，可知第一个局中人仅在区间（１?－?ｅ，１］上有正的效用－由于两个局中人??关于｜对称，因此第二个局中人在区间［〇ｄ上有正的效用．两个局中人的效用函数??如图３．３所示．用ｆ表示位置组合ｘ的最优设施位置．从图３．３很容易得出ｆ为０或??１并且最优社会效用犯（ｙ＊，Ｘ）?＝??令／表示任意的只把０和１作为候选点的防策略操纵性的随机机制．用分布Ｐ??表示机制／对位置组合ｘ的解，也即／（ｘ）?＝?Ｒ显然有抑（尸，Ｘ）?ｇ?ｘ）?＝??并且由于两个局中人关于｜对称的，不失一般性，假设第一个局中人对于分布Ｐ的??效用??ｍ?、／抓＜ｙ，ｘ）?ｅ??Ｕｌ｛Ｒ＇Ｘｌ）－￣＾?＝?Ｗ＾ｈＹ??ｕ??１?丨丨?／??（ｙ，?ＸＪ）??／?＼???Ｕ２（ｙ：ｉ２）??／????．／！??■?／?／］???－？?－：?－．１?；－？?ｖ?？－；?－Ｊ．－??＃?＞?Ｖ??０?Ｃ?１?－?ｒｆ－２?＋?ｒｆｌ?１?—?？?１??图３．３?以及４的效用函数．横轴ｙ表示设施的位置．??接着讨论另一个位置组合Ｘ＇?＝?？?＝?１?—?ｄ２，?．ｔ２?＝?４?＋?ｅ），其中ｅ与位置组合ｘ??中的相同．此时第一个局中人到端点〇的距离＜〇，?〇?＜?ｄ１；因此第一个局中人仅在??区间（１?－?ｄ２?＋山

么第一个局中人在［〇，?｜）区间上，因此第一个局中人仅在（１?－?１］区间上有正的??效用．由于两个局中人关于Ｉ对称，因此第二个局中人在［〇，?￥）区间有正的效用．??两个局中人的效用函数如图３．４所示．从图３．４可知位置组合ｘ的最优设施位置在０??或１处并且最优的社会效用为洲（〇，?ｘ）＝抓（１，ｘ）?＝??用／表示任意的防策略操纵性的随机机制．令／⑷＝凡注意任意机制的解都??不会超过最优社会效用，于是Ｘ）?ｇ抑（０，?ｘ）．由于两个局中人关于｜对称，不失??一般性，假设??秦??接着讨论另一个位置组合Ｖ?＝（而＝１?－?＾％?＝?ｒｆ２）．很容易看出对于位??置组合ｘ＇第二个局中人仅在［０，ｄ２?－由）区间上有正的效用．效用函数如图３．４所??示．用ｆ表示位置组合Ｘ＇的最优设施位置．从图３．４可以看出ｙ?＝?０，最优社会效用??ｓｕ（ｙ＊，ｘ＇）?＝?１．??ｕ??１?？（??ｗｉ?（ｙ，?ＸＩ?）??＼???ｕ２（ｙ：?ｘ２）??＼???ｗ２（ｗ
【相似文献】

相关期刊论文 前10条

1 严加安;;数学的奇妙:我们身边的概率和博弈问题[J];语数外学习(高中版上旬);2016年09期

2 袁冬冬;;现时期应加强立法博弈问题的研究[J];人大研究;2013年04期

3 邱中华;高洁;朱跃星;;应用免疫算法求解博弈问题[J];系统工程学报;2006年04期

4 吴海民;报业竞争中的博弈问题[J];青年记者;2005年02期

5 郭世荣;;概率史研究的一部新作:《从博弈问题到方法论学科》[J];内蒙古师范大学学报(自然科学汉文版);2012年04期

6 林厚从;;博弈问题的策略研究[J];软件导刊;2010年12期

7 孟坤;;有趣的博弈问题[J];初中数学教与学;2006年01期

8 王明珠;;城镇拆迁的利益博弈问题[J];住宅产业;2010年Z1期

9 马占欣;李亚;陆玉昌;;用遗传算法解决博弈问题[J];河南科学;2007年02期

10 贾小勇;袁敏;;彰显概率文化的亮丽篇章——读《从博弈问题到方法论学科》[J];咸阳师范学院学报;2012年02期

相关博士学位论文 前10条

1 庄翼;部分信息下正倒向随机系统的微分博弈问题及金融中的应用[D];山东大学;2018年

2 梅丽丽;若干设施选址博弈问题的机制设计[D];浙江大学;2018年

3 谭德庆;多维博弈及应用研究[D];西南交通大学;2004年

4 王昭;具有模糊支付的博弈问题及其应用研究[D];北京理工大学;2006年

5 张剑;不确定条件下多周期库存博弈问题研究[D];北京交通大学;2017年

6 尚宇红;博弈论前史研究[D];西北大学;2003年

7 魏麒;排序理论中若干问题的理论分析和算法设计[D];上海大学;2015年

8 穆蕊;非零和随机微分博弈及相关的高维倒向随机微分方程[D];山东大学;2015年

9 方志耕;灰色博弈理论及其经济应用研究[D];南京航空航天大学;2007年

10 孙薇;组织信息安全投资中的博弈问题研究[D];大连理工大学;2008年

相关硕士学位论文 前10条

1 卢延杰;几类博弈问题的直接算法及其应用研究[D];福州大学;2014年

2 刘春丽;我国文献信息资源共享博弈问题研究[D];东北师范大学;2005年

3 姜小华;偷税与反偷税，政府与企业税收博弈问题研究[D];浙江大学;2002年

4 范国强;若干排序博弈问题的协调机制研究[D];中国海洋大学;2014年

5 张芬;基于最优控制的微分博弈问题研究[D];云南师范大学;2015年

6 袁冬冬;我国社会转型期立法博弈问题研究[D];郑州大学;2012年

7 李静;时间一致均值—方差投资组合博弈问题[D];中南大学;2014年

8 任伟;两台同类机排序覆盖博弈问题PoA及SPoA研究[D];浙江大学;2010年

9 黄俏玲;零和随机微分投资组合博弈问题[D];中南大学;2013年

10 诸栗;易逝品需求不确定的供应链主从博弈问题[D];天津大学;2007年

本文编号：2842586