Hi:欢迎来到中国论文网     

所有论文科目分类


中国论文网 > 硕博论文 > 若干设施选址博弈问题的机制设计

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

作者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.综上所述,本文基于实际应用,研究了设施选址机制设计的若干新模型.针对已有研究工作中用户效用函数同构的局限性,本文提出了用户效用为满意度的异构模型;对于用户效用函数为好恶程度不变的情形,本文引进了带排斥因子的分段函数模型;针对已有研究中社会效用函数单一化的问题,我们将平方和社会效用函数引入到排斥性设施选址博弈问题的机制设计中.新模型与真实场景中用户复杂多样的效用更贴切.在研究方法上,本文对所提出的模型给出了真实可信的机制并对所给机制进行了理论分析.

最新更新

热门推荐

[硕士论文]MPACC硕士论文重复率要求是
MPACC硕士论文 重复率要求是多少及方法?每个学校对自己的论文重复率要求可能会有所不同,但是大致也不会超过哪个范围,本篇文章就为大家介绍一下MPACC硕士论文重复率要求是多少?大家可以大致的参考一下,具体情况还请参考自己学院的详细要求哦。 MPACC硕士论文重复率要求 一般而言,大部分院校针对硕士研究生研究生论文重复率都规定在20%以内,当然,也有部分院校规定...[全文]
[硕士论文]MPACC硕士论文答辩详细流程
论文答辩都有一套详细的流程要走,具体哪个步骤做什么,都会有详细的要求介绍,下面我们就为大家详细介绍一下MPACC硕士论文答辩的详细步骤,具体哪一步做什么,都给大家粗略的介绍一下。 一、 MPACC硕士论文 答辩的详细步骤 二、自我介绍想必关于自我介绍大家都知道, 而在论文答辩的过程中, 自我介绍的时候,需要举止大方、态度从容、面带微笑,礼貌得体的介绍自己...[全文]
[硕士论文]教育硕士毕业论文开题报
教育硕士研究生开题报告可能很容易忽视,可能内心想着就是那几个方面,不需要一直提,其实有很多细节你可能不知道,现在58 博学论文 网小编主要包括以下几个方面: (一)教育硕士论文名称 论文名称就是课题的名字 第一,名称要准确、规范。准确就是论文的名称要把论文研究的问题是什么,研究的对象是什么交待清楚,论文的名称一定要和研究的内容相一致,不能太大...[全文]
[硕士论文]企业管理研究生论文创新
企业发展过程中的重要途径和方式就是企业管理,结合市场发展以及企业的实际情况进行调整才是企业管理的重要需求。传统的管理方式已经无法满足企业发展的需求,因此电力企业创新管理体系构建十分必要,利用现有的资源,实现科学发展,制定企业发展的具体目标,适应环境的变化,尤其是要让企业内部实现紧密配合,提高企业的经济效益,满足更多的社会需求,管理创新可以促进企业...[全文]
[硕士论文]硕士研究生开题报告选题
很多 管理论文 的硕士研究生开题报告中,会对自己的学科领域在报告中最后做一个综合说明。述更多的并不是叙述,而是评述与述评,即要有作者自己的独特见解。要注重分析研究,善于发现问题,突出选题在当前研究中的位置、优势及突破点;要摒弃偏见,不引用与导师及本人观点相悖的观点是一个明显的错误。 1、开题报告毕业论文题目题目是硕士毕业论文中心思想的高度...[全文]
[硕士论文]硕士研究生开题报告怎么
硕士研究生开题报告 格式与开题报告技巧开题报告是研究生毕业论文工作的重要环节,是指为阐述、审核和确定毕业论文题目而做的专题书面报告,它是研究生实施毕业论文课题研究的前瞻性计划和依据,是监督和保证论文质量的重要措施,同时也是训练研究生科研能力与学术作品能力的有效的实践活动。《中国青年报》报道:复旦大学新闻学院2002级研究生所做毕业论文开题报告...[全文]
关闭窗口 论文咨询