- Tuesday 9 July 2019
- Professor Toby Walsh; Scientia Professor of Artificial Intelligence; UNSW Sydney
The facility location problem looks to find the optimal place to locate a facility (e.g. school or warehouse) to minimise the distance that agents (e.g. students or shops) are from the facility serving them. I study such problems in one dimension where each facility can serve only a limited number of agents, and consider both the optimisation and mechanism design perspectives. The addition of capacities, which have not been considered much in previous work, makes the facility location problem harder to solve. I show, for instance, that a number of mechanisms lose either 'strategyproofness' or a bound on the solution quality. I identify instead some new mechanisms that are 'strategyproof' and achieve good approximation guarantees.