Nash Welfare in the Facility Location Problem

1 Introduction

The facility location problem is a classic problem in operations research, computational social choice and mechanism design. In many variations of the problem, we are tasked with placing a single facility on a line to serve a set of agents, who each incur a cost proportional to their distance from the facility. This problem has many applications, such as a government computing the optimal location to place a library, school or warehouse on a street for the nearby citizens [Miyagawa, 2001]. Apart from the intuitive geographical applications, the facility location problem can also be used in voting with single-peaked preferences to elect a representative. An agent's location on the line could indicate their position on the political spectrum, and the facility placement would indicate the policies of the representative that optimally reflects the agents' political leanings [Feldman et al., 2016]. By extending the problem to graphs, we can also find the optimal router placement on a network [Gao, 2012].

In operations research, an optimization approach is often taken with the objective of minimizing transport costs. Typically, a linear programming problem is formulated with constraints respective to the specifics of the problem, and an algorithm is proposed to compute the problem. Examples of such variations are capacity-constrained facilities [Wu et al., 2006] or stochastic facility location models when there is uncertainty surrounding agent locations [Snyder, 2006]. Many of the optimization problems in this field are NP-Hard, so there has been a significant amount of work on approximation algorithms [Shmoys et al., 1997; Charikar and Guha, 2005;

Chudak and Williamson, 1999]. We remark that the proposed solutions in this field are focussed on maximizing efficiency, and may therefore result in a facility placement that seems unfair to some agents, either due to their relatively high incurred cost, or due to the presence of agent strategic behaviour.

In scenarios where an agent's location is their own private information, agent strategic behaviour becomes an issue, as they may lie about their location to unfairly improve the facility location placement relative to their true location. A significant portion of the facility location problem research in computational social choice and mechanism design involves designing strategy-proof mechanisms, in which it is optimal for each agent to report their true locations. This research was initiated by Moulin [1980], who found that placing the facility at the median agent minimizes total cost and is strategyproof. The idea was then popularized by Procaccia and Tennenholtz [2013], who analysed the use of strategy-proof mechanisms to minimize the utilitarian objective of total cost and the egalitarian objective of maximum cost. Specifically, they examined the worst case approximation ratio between the objective value resulting from a strategy-proof facility placement and from the optimal facility placement. While most of the literature considers fairness and efficiency objectives separately, there is little mention of how a facility could be placed to strike a balance between the two objectives.

The Nash welfare, defined as the product of agent utilities, is a well-researched objective function first formulated by Nash and applied to the bargaining problem in Nash [1950]. It is known to provide a reasonable balance between fairness and efficiency in several social choice applications. When fairly allocating indivisible goods, the allocation maximizing Nash welfare has been proven to be envy-free up to one good and Pareto optimal [Caragiannis et al., 2016]. The authors have also successfully implemented the Nash solution in the popular fair division site Spliddit. In a variation of the participatory budgeting model, the optimal Nash solution is ex-ante efficient and satisfies strong fairness guarantees [Aziz et al., 2019]. The solution maximizing the Nash welfare has also been applied to the ambulance placement variant of the facility location model, in which an agent's utility is defined as the time it has access to an ambulance [Jagtenberg and Mason, 2020]. While the authors use a practical, experimental approach, we aim to find theoretical results in our work.

To convert costs to utilities, Moulin [2003] restricts the interval to [0, 1] and defines an agent's utility as 1 - cost. He also describes placing the facility such that the Nash welfare is maximized, but mentions that "this optimum is neither easy to compute nor to interpret". In our research, we expand on Moulin's idea, taking the classic facility location setting, defining agent utilities as 1 - cost and analyse the facility placement that maximizes Nash welfare. Specifically, we question whether the optimal Nash solution also maintains a reasonable fairness-efficiency balance in the facility location setting, and investigate the computational and structural properties. We also take a mechanism design approach and prove bounds on the approximation of the Nash welfare by a strategy-proof mechanism.

2 Contribution

Our current working paper details many results pertaining to the aforementioned points. While the optimal Nash solution is NP-Hard to compute in many other contexts, we show that the facility location maximizing Nash welfare can be approximated up to a specified additive error in polynomial time. We also show that the facility may be optimally located at a position not described by a rational number, even when all agents are located at positions with rational descriptions. It is hence unnecessary to compute the exact solution and an approximation algorithm suffices. By proving approximation ratio bounds on the utilitarian objective of total utility and the egalitarian objective of minimum utility, we show that the Nash solution strikes a balance between fairness and efficiency in this setting. We reinforce this result by proving that the solution meets certain fairness properties. When considering the context where agent locations are private information, our results are somewhat negative. The optimal Nash solution is not strategy-proof, so we may wish to find a strategy-proof mechanism that approximates the optimal Nash welfare. However, we find that no strategy-proof mechanism can approximate the optimal Nash welfare up to a constant factor, suggesting that the Nash welfare may not be an effective objective function in such a setting.

3 FutureWork

There are many extensions of this research. Our current primary focus is to analyse agent strategic behaviour when the facility is placed such that the Nash welfare is maximized. Specifically, we will look at Nash equilibria and weaker notions of strategy-proofness. Following [Procaccia and Tennenholtz, 2013], we could also extend the setting to 2 facilities, and/or consider randomized mechanisms. Finally, we could extend the problem to 2 dimensions with both Manhattan and Euclidean metrics, as in [Walsh, 2020].