Group Strategy-proof Mechanisms for Shuttle Facility Games
Yuhei Fukui, Aleksandar Shurbevski, Hiroshi Nagamochi · Journal of Information Processing · 2020
We study the game-theoretical structure of a scenario where a decision maker has to determine locations of stations in a transportation system.We introduce a new model on facility games, called the "shuttle facility game."A facility F is defined to be an interval with two stations over a transportation line.Then, the decision maker wishes to design a mechanism that given as input a set of intervals reported by each player, where I i represents the commuting route of player i, determines a location for F. The profit of a facility location is defined based on the "convenience" to each player, such as the distance to the facility.A player i may try to manipulate the output of the mechanism by strategically misreporting I i to get a higher profit.We formulate two shuttle facility games: the fixed-length and the flexible-length shuttle facility game; and prove that each admits a group strategy-proof mechanism.We prove that the social profit is also maximized by a location of F determined by our group strategy-proof mechanism, that is, a decision maker can find a location of F so that the social profit is maximized and group strategy-proofness is attained at the same time.