Strategic Facility Location with Limited Liars
Yue Gruszecki 0009-0002-8037-5998, Elliot Anshelevich 0000-0001-9757-6839 · 2026
Read Strategic Facility Location with Limited Liars by Yue Gruszecki 0009-0002-8037-5998, Elliot Anshelevich 0000-0001-9757-6839 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-16829.txt.
Introduction
Gruszecki and Anshelevich examine Nash equilibria in strategic facility location games with clients in an arbitrary metric space. Some clients are always truthful while k strategic clients lie about their location when it benefits them. A Nash equilibrium always exists with price of stability very close to 1, and all equilibria sit within n plus 2k over n minus 2k of optimum. Strong equilibrium may not exist generally, but always exists for line metrics with cost at most n plus k over n minus k times optimum.
Catalog record
| CREATOR | Yue Gruszecki 0009-0002-8037-5998, Elliot Anshelevich 0000-0001-9757-6839 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77045 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.16829
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Strategic Facility Location with Limited Liars Yue Gruszecki 0009-0002-8037-5998, Elliot Anshelevich 0000-0001-9757-6839 Abstract We study Nash equilibria in strategic facility location games where clients are located in an arbitrary metric space. Specifically, there are n n clients, and the goal is to choose a facility from a set of given locations, so that the total distance from the clients to the facility is as small as possible. While some of the clients are always truthful, k k of them are strategic, and will lie about their location if it benefits them. We quantify how the fraction of strategic clients affects the existence and quality of Nash equilibrium and strong equilibrium solutions, and note that even for relatively large k k , the properties of these solutions can be much better than the results of fully strategyproof mechanisms. For Nash equilibrium, we show that it always exists, and the price of stability is very close to 1. More importantly, we prove that all Nash equilibria are within a factor of at most n + 2 k n − 2 k \frac{n+2k}{n-2k} from the optimum solution, and that this price of anarchy bound is almost tight. While strong equilibrium may not exist for this setting, we prove that it always exists for line metrics, and its cost is at most n + k n − k \frac{n+k}{n-k} times that of optimum. Keywords: Facility Location, Nash Equilibrium, Price of Anarchy, Price of Stability 1 Introduction Strategic facility location problems have been studied under many settings, see Related Work and [ 10 ] for a survey. We consider the case where clients and facilities are located in some arbitrary metric space, and there is a finite set of possible locations to build a facility. The goal is to choose one facility location to minimize the total distance from all clients to the chosen facility (known as the minisum objective). This applies to scenarios such as building a new post office or hospital in a community, or spatial voting settings where the clients are voters and the facilities are candidates, with voters wanting a candidate which is close to them ideologically. Note that if we know the exact locations of the clients, such problems can be solved easily. Strategic facility location, however, considers the case where clients act strategically: the exact locations of the clients are private, while we know only the reported locations of the clients that may not be their true locations. With strategic clients, most existing work studied strategyproof mechanisms, i.e., mechanisms where no client has an incentive to report anything other than their true location. Under the strategic facility location or voting settings, most existing work assumes that all clients can lie about their true locations. This is not always true, however. First, we may know the true locations of many or most of the clients via other means (e.g., their addresses on record), and thus detect when such clients are mis-reporting. Second, even when all clients are able to lie without being detected, it is likely that a large fraction still may not act strategically even if they can benefit from doing so. For example, as shown in [ 15 ] , sophisticated voting in Congress is rare. In a laboratory setting, 61.8% of the voters voted for their true preference regardless of the proposed voting rule [ 8 ] . In addition, in matching settings, as shown in [ 17 ] , there will be a fixed constant fraction of players who will always play truthfully in the Boston mechanism. This means that even for mechanisms that are not strategyproof, the number of strategic players may be limited, and there will be a set of players that will always act truthfully. Because of this, in our work we assume that only k out of the n clients are strategic, while the other n-k always tell the truth about their locations. This is either because we know their true locations from a different source, because they are inherently truthful people, or because they do not follow any complex and sophisticated strategies, and telling the truth is the simplest and easiest strategy. Moreover, we note that strategyproof mechanisms for this setting have some limitations, such as that they result in bad approximation bounds. We define the approximation ratio of a mechanism as the worst-case ratio of the outcome produced by the mechanism to the cost of the optimal solution (in other words, this is a way to evaluate the quality of the outcome of the mechanism as compared with the quality of the optimal solution). When the set of possible facility locations is finite, the approximation ratio for any deterministic strategyproof mechanism is at least \Omega(n) , where n is the number of clients (see results in [ 19 ] and discussion in [ 1 ] ). This holds for general metric spaces, and even for circle networks, where the clients are located on a simple cycle. 1 1 1 Note that results are much better for strategyproof mechanisms if facilities can be placed anywhere in the space, instead of only at a finite set of locations. For example, as shown in [ 14 ] , there exist 3-approximation deterministic strategyproof mechanisms when clients are located in \mathbb{R}^{d} and the distance corresponds to most L_{p} norms. In addition, on a tree network, one can obtain the optimal solution using a deterministic strategyproof mechanism [ 19 ] . This bound is significantly worse than the best possible approximation ratio of 3 that strategyproof mechanisms can achieve in one-dimensional space [ 12 ] . Thus, despite their obvious benefits, strategyproof mechanisms may not be desirable for metric spaces beyond 1-D. In our work, we instead relax the constraint of strategyproofness and study Nash equilibrium and strong equilibrium for non-strategyproof mechanisms. In addition, as discussed above, using the fact that not every client would act strategically, we analyze the stable solutions with the assumption that only k of the clients act strategically. This can also be seen as another relaxation of stategyproofness. As a result, we show that Nash equilibrium always exists and the quality of the equilibria is close to the optimal solution, even for a relatively large fraction (e.g., 20-40%) of strategic clients, whereas the approximation ratio is \Omega(n) for strategyproof mechanisms. We present the detailed results below. Figure 1: Plots of the approximation ratio w.r.t. k/n under the worst case NE (for general metrics) or SNE (for line metrics). The solid line shows the upper bound for POA w.r.t. k/n while the dashed line shows the upper bound for SPOA w.r.t. k/n . 1.1 Our Contributions We analyze the natural mechanism that, given the clients’ reported locations, simply chooses the solution minimizing the (perceived) sum of distances from the clients to the chosen facility. Despite its simplicity, we show that this mechanism has nice properties, and in fact no other reasonable deterministic mechanism can achieve better price of anarchy bounds. We first show that there always exists a (pure) Nash equilibrium (NE) for a general metric space with an arbitrary finite set of given facility locations. We then analyze the quality of such equilibria: the approximation ratio of the