Hi:欢迎来到58硕博论文网     

所有论文科目分类


主页 > 硕博论文 > 若干设施选址博弈问题的机制设计

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

作者2019-03-27 10:21未知
设施选址问题是经典的组合优化问题之一,是指在给定的网络上确定一个或多个设施的位置,为网络上的所有用户服务并使得成本最小化的问题.在优化问题中,所有用户的位置信息都是公开的.随着算法博弈论学科的兴起,单决策者的优化问题演变成多决策者的博弈问题.本文将研究设施选址博弈,其与经典模型不同之处在于,每个用户的位置信息都是私有的.机制设计者首先公布算法(机制),该算法可根据用户的位置求解出设施的位置.用户在了解算法的前提下提供对自己最有利(并不一定真实)的位置信息.在喜好性设施选址博弈问题中,用户期望设施离自己尽可能近;而在排斥性设施选址博弈中,用户则期望设施离自己尽可能远.在博弈问题中,用户的期望量化为用户的效用(费用).机制设计者希望给出的机制能保证用户们愿意提供真实的位置信息,并使得某种社会目标(如所有用户的效用和)达到最优,该目标称为社会效用函数.如何设计高效并且真实可信的机制是机制设计的核心问题.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.综上所述,本文基于实际应用,研究了设施选址机制设计的若干新模型.针对已有研究工作中用户效用函数同构的局限性,本文提出了用户效用为满意度的异构模型;对于用户效用函数为好恶程度不变的情形,本文引进了带排斥因子的分段函数模型;针对已有研究中社会效用函数单一化的问题,我们将平方和社会效用函数引入到排斥性设施选址博弈问题的机制设计中.新模型与真实场景中用户复杂多样的效用更贴切.在研究方法上,本文对所提出的模型给出了真实可信的机制并对所给机制进行了理论分析.
58硕博论文网

最新更新

热门推荐

[硕士论文]企业战略管理视角出发研
本文是 mba论文 ,本论文从企业战略管理的视角出发,依靠文献检索法、调查研究法、对比分析法对案例银行(乌鲁木齐银行)互联网金融竞争环境和因素(外延和内涵)进行了系统而又深入的研究,并综合运用SwOT 分析得出so战略应为乌鲁木齐银行首选的战略,同时给出了-些战略实施的保障措施,以帮助案例银行重新调整竞争模式和发展战略,创新传统的经营模式,以应对新形势下的挑...[全文]
[硕士论文]传统商业银行发展互联网
本文是 mba论文 ,传统商业银行发展互联网金融的主要模式。在互联网金融的强力冲击下,商业银行的金融中介地位逐步弱化,收入来源一再受到冲击,传统的主要收入来源利差收入也难抵颓势。在这样的背景下,传统商业银行唯有积极结合互联网金融并开展相关业务,目前主要模式如下: (一)与互联网企业合作,资源共享 互联网+时代下,跨界合作成为趋势,传统商业银行与...[全文]
[硕士论文]国外金融行业市场进展情
本文是 mba论文 ,随着互联网金融的蓬勃发展,人们分别通过理论研究、市场预测及统计分析等方法对互联网金融及其对传统金融机构的影响,以及在影响之下金融机构采取的战略转型进行了深入研究,并取得了丰硕的成果。下面分别介绍国外相关研究进展情况及发展趋势。 国外研究综述 (一)关于互联网金融对传统金融行业影响的研究 在国外,互联网形式的商业模式和金融业...[全文]
[硕士论文]网络银行金融机构市场主
本文是 mba论文 ,在 20 世纪 90 年代中期,美国出现了一家名为安全第一网络银行(Security First Network Bank, SFNB),正式标志着互联网金融的诞生。随着越来越多的金融科技企业推出高效便捷的金融产品和服务,以网络贷款、网上银行等为代表的金融服务开始在美国金融市场迅速发展,互联网金融企业与传统金融机构开始相互竞争。截至目前,传统金融机构的市场主导地位没有发生...[全文]
[硕士论文]【mpa论文】新媒体视角下
本文是 mpa论文 ,新媒体,从字面意思上理解,就是一种新的媒体形式,是相对于传统媒体而言的。New media是新媒体一词的英文翻译。新媒体概念的提出人是美国的戈尔德马克。从普遍意义上来说,新媒体是继报刊、广播和电视等传统媒体之后发展起来的媒体形态,是通过数字和网络技术,依托互联网平台,以微信、微博、贴吧、论坛等为渠道,向用户传播快捷、广泛的信息、为...[全文]
[硕士论文]地方政府公信力mpa论文研
本文是 mpa论文 ,人无信不立,业无信不兴。同样,国无信必颓,政无信则衰。当前,我国经济和社会发展都取得了重大成就,人们的生活水平也逐步提高,公民参政议政的意识越来越强烈,对政府提出了新的期待。互联网时代,通讯媒体迅速发展,网络信息日益多元化,政府的行政行为都浮现在人们的视线中,一方面加强了对政府工作人员的监督,另一方面信息的多元化网民的...[全文]
关闭窗口 论文咨询