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