设施选址中的高效可信的激励机制设计研究

As one of the most representative problems in mechanism design without money, facility location games have been extensively studied in recent years. Originating from the facility location problem, which is a classic optimization problem, the facility location game introduces the selfish behavior of participating agents. The government will collect necessary information from agents before deciding the location of the facilities and has an objective function to optimize. Agents on the other hand can misreport their information if doing so will improve their utilities. Therefore the optimization objective sometimes needs to be sacrificed to guarantee the truthful report from the agents. Current study on facility location games usually consider the homogeneous setting where the utility functions of agents are the same or the facilities are the same. Furthermore, agents do not affect each other in the classic setting. However, in the real scenario, heterogeneity among users and among facilities are quite common and agents may also be affected by each other (called externality by economic terminology). In this project, we propose to study how to design truthful mechanisms when heterogeneity and externality exist. To be more specific, we will study dual preference (some agents like the facility and some agents dislike it), opposite facility (agents like one facility and dislike the other), optional preference (different agents like different set of facilities) and fractional preference (different agents have different fondness level for various facilities, which is proposed for the first time). We will also study how the existence of externality affects the mechanism design for facility location games. We will design truthful mechanisms for the above extensions with provable approximation guarantee for various objectives and experiments will be used to verify the effectiveness and also help to find the lower bounds for different models.

公共设施选址问题是社会公共决策中常见的问题，既需要尽量减少成本，又需要提高公众参与决策积极性以提高公共设施配置效率。作为博弈理论中无支付激励机制设计的典型问题，公共设施选址中的激励机制设计在近几年成为研究的热点。但是由于不能引入支付函数，高效可信的公共设施选址激励机制设计面临很大的挑战。现有的公共设施选址激励机制大多没有考虑实际应用场景下复杂的用户效用函数，比如用户之间效用函数独立性、不一致性等所引起的异质性，用户之间效用函数彼此互相影响所产生的外部性。为此，本项目拟结合实际环境中复杂的用户效用函数特点对设施选址激励机制设计进行深入的研究：研究多重喜好，互斥喜好，喜好可选，比例喜好等异质性用户效用函数情况下的多设施选址激励机制；研究考虑用户效用函数具有外部性情况下的多设施选址激励机制；研究用户效用函数具有异质性和外部性情况下的多设施选址激励机制。在此基础上实验验证所设计机制的有效性。

公共设施选址问题是社会公共决策中常见的问题，既需要尽量减少成本，又需要提高公众参与决策积极性以提高公共设施配置效率。作为博弈理论中无支付激励机制设计的典型问题，公共设施选址中的激励机制设计在近几年成为研究的热点。但是由于不能引入支付函数，高效可信的公共设施选址激励机制设计面临很大的挑战。现有的公共设计选址激励机制大多没有考虑实际应用场景下复杂的用户效用函数，比如用户之间效用函数独立性、不一致性等所引起的异质性，用户之间效用函数受彼此互相影响所产生的外部性。为此，本项目结合实际环境中复杂的用户效用函数特点对设施选址激励机制设计进行深入的研究：研究考虑互斥喜好，喜好可选，比例喜好等异质性用户效用函数情况下的多设施选址激励机制，通过严格的数学推导，证明设计的机制所达到的性能可以在最优解的若干倍之内，并且同时证明可近似的下界，即没有一个激励机制的性能可以在所有的可能输入上达到最优解的若干倍之内；我们也研究了考虑用户效用函数具有外部性情况下的多设施选址激励机制，找到了特定外部性系数条件下激励机制必须满足的条件以及他们可以多接近最优解；最后，我们也探索了当用户效用函数同时具有异质性和外部性情况下的多设施选址激励机制，得到了一些初步结果。在此基础上我们也用实验验证了所设计机制的有效性。