路上的半厌恶型设施选址博弈的机制设计

姜秀秀，姜 永，刘龙城，朱李岑

(1.厦门大学数学科学学院，福建 厦门 361005；2.福建农林大学计算机与信息学院，福建 福州 350002)

算法机制设计，最早起源于Nisan等[1]为解决任务排序和资源分配等优化问题所做的研究. 在这些问题中，输入的最初信息来源于每个参与者报告的私人信息，而每个参与者可能是自私的，即他们可能会为了获得更多的利益而谎报私人信息，最终导致输出的结果与最优结果相差甚远. 一个机制就是一个可以输出结果的函数.给定参与者的报告信息，目标是设计一个机制，不仅迫使所有参与者讲真话，而且使目标函数最优.

本文讨论一种新的设施选址博弈，称之为半厌恶型设施选址博弈. 一个典型的例子是：政府计划在一个城市新建一个高铁站服务于全市居民. 对于即将建立的高铁站，一部分人因要经常乘坐高铁出行而希望高铁站离自己所在居住地越近越好，另一部分人极少乘坐高铁出门而希望高铁站离自己所在居住地越远越好，以免高铁站给他们的日常生活带来不利的影响. 所有居民向政府报告他们的居住地址和对高铁站的偏好(喜欢或讨厌)，以便政府确定建立高铁站的最优位置. 喜欢高铁站的居民的效用为：城市的直径减去居住地与高铁站的距离. 讨厌高铁站的居民的效用为：居住地与高铁站的距离. 半厌恶的社会福利被定义为所有居民的效用总和. 因此，政府的目标是使半厌恶的社会福利最……