Nash Welfare and Facility Location
This work addresses fairness-efficiency trade-offs in resource allocation for agents on a line, representing an incremental advance in mechanism design for facility location.
The paper tackles the facility location problem on a line by applying the Nash welfare objective to balance fairness and efficiency, resulting in a polynomial-time approximation algorithm and a strategy-proof mechanism with a bounded approximation ratio.
We consider the problem of locating a facility to serve a set of agents located along a line. The Nash welfare objective function, defined as the product of the agents' utilities, is known to provide a compromise between fairness and efficiency in resource allocation problems. We apply this welfare notion to the facility location problem, converting individual costs to utilities and analyzing the facility placement that maximizes the Nash welfare. We give a polynomial-time approximation algorithm to compute this facility location, and prove results suggesting that it achieves a good balance of fairness and efficiency. Finally, we take a mechanism design perspective and propose a strategy-proof mechanism with a bounded approximation ratio for Nash welfare.