Strategyproof Approximation of the Minimax on Networks 2: No Strategyproof Randomized Mechanism Beats 2 - o(1) on TreesResearch Paper
A public facility (a fire station, a hospital, a server) is to be placed on a road network, and the people it serves report their own locations. When the planner wants to minimise the distance to the farthest user (the minimax or egalitarian objective, in the sense of Rawls), each user has an incentive to misreport so as to pull the facility towards…