关键词: 无支付机制设计, 防策略性, 选址博弈, 算法博弈论

Abstract:

Facility location game is one of important research areas in the forefront of algorithmic game theory. Different with the traditional facility problem, there are $n$ selfish agents in game and the addresses where they are located are private information. The game designer tries to design a mechanism, which outputs the locations of facilities according to the reported addresses of agents. One of the most important objectives in the study of facility location game is to design approximation strategy-proof or group strategy-proof mechanisms without money in order to enforce all agents to choose strategies faithfully and to achieve the overall equlibria. Mechanism design without money for the facility location game is an interdisciplinary project with topics in the common part of combinatorial optimization and theoretical computer science, which has important applications in a few practical areas such as management science, information science, social economics, etc. This survey aims at listing the recent results on the approximation mechanism design without money for facility location games from different perspectives of agent preferences, facility types, metric spaces and social objectives, and summarizes some problems which have not been solved for readers.

Key words: mechanism design without money, strategy-proof facility location game, algorithmic game theory