<p>Square-City: <span class="math-container">$[0,1]×[0,1]$</span></p>
<p>The objective is to establish a public facility at a specific location <span class="math-container">$(x, y)$</span>, such as a library within the region <span class="math-container">$[0, 1] × [0, 1]$</span>. This facility will be accessible to three individuals residing at the following locations:
<span class="math-container">$l_1 =(x_1,y_1),l_2 =(x_2,y_2),l_3=(x_3,y_3)$</span>
respectively.
Utility function of <span class="math-container">$i\in\{1,2,3\}$</span> is
<span class="math-container">$u_i:[0,1]^2\rightarrow\mathbb{R}$</span> defined as
<span class="math-container">$u_i(x,y)=-|x-x_i|-|y-y_i|$</span></p>
<p>Pareto optimal Location for the library is defined as that location such that no other location is strictly better than it for all users.</p>
<p>Set of Pareto optimal Locations for the following three situations is a rectangle/square:
<a href="https://i.sstatic.net/65UkALiB.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/65UkALiB.png" alt="enter image description here" /></a></p>
<p>Conjecture: In a plane <span class="math-container">$\mathbb{R}^2$</span>, with the taxi-cab metric, and <span class="math-container">$n$</span> individuals located at <span class="math-container">$(x_1,y_1), \ldots, (x_n,y_n)$</span>, set of Pareto optimal locations for the library consists of all the locations that lie inside the rectangle formed by end points <span class="math-container">$(x_\min, y_\min), (x_\min, y_\max), (x_\max, y_\max),(x_\max, y_\min)$</span> where <span class="math-container">$x_\max=\max_{i}x_i, x_\min=\min_{i}x_i, y_\max=\max_{i}y_i, y_\min=\min_{i}y_i$</span>.</p>

CC BY-SA 4.0
2024-12-30T11:30:30.833Z
2024-12-30T11:36:42.450Z
2024-12-30T11:36:42.450Z
Amit
<p>In the <strong>facility location problem</strong>, the government wants to construct a useful facility (e.g. a school, a bus-station), and has to decide where exactly to locate it. There are <span class="math-container">$n$</span> potential users of the facility; each user <span class="math-container">$i$</span> has a known location <span class="math-container">$x_i$</span> (a point in some multi-dimensional space). The cost of each user is the distance between its location and the facility location, where 'distance' can be measured using different metrics.</p>
<p>Clearly, each location chosen for the facility can be good for some users (thoes who live nearby) and bad for others (those who live far away). Therefore, it makes sense to first find the set of all <strong>Pareto-efficient</strong> locations - those locations such that no other location is strictly better for all users (nearer to all users' locations).</p>
<p>In <a href="https://math.stackexchange.com/a/5010174/29780">this answer</a> it is proved that, when distance is measured by the Euclidean metric, the set of all efficient allocations is exactly the convex hull of the points <span class="math-container">$x_i$</span>.</p>
<p>Is there a reference that studies such problems in a more general way, and has a characterization of efficient points for a larger class of metrics?</p>

CC BY-SA 4.0
2024-12-17T21:32:08.343Z
The tools from spatial voting theory might be useful; they address questions that seem to be very similar. The book "Positive Political Theory I" by Austen-Smith and Banks is a good introduction to the topic. It's been a while that I looked at the topic, though.
Michael Greinecker
CC BY-SA 4.0
2024-12-18T04:44:38.457Z
I have tried to solve this problem earlier this year for taxi-cab metric in two-dimensional space, but could only solve it for the case of three users. Please see pages 27-29 of the following document: https://piazza.com/redirect/s3?bucket=uploads&prefix=paste%2Fi5t4zjz64oq3sl%2F25c99e0ffecc71285e0970995390e53a92ba34736804d8cc45be0ea1c29b64f7%2FEcon-postcards.pdf
Amit
CC BY-SA 4.0
2024-12-18T06:13:40.213Z
The definition of Pareto efficiency I have used here is as follows: A location is said to be Pareto efficient if there is no other location such that we can make one user better off without making the others' worse off.
Amit
CC BY-SA 4.0
2024-12-19T01:45:08.283Z
@Amit yes, your definition is the standard one. The definition I used is usually called "weak Pareto efficiency". Both are interesting; I used weak Pareto efficiency because it is simpler.
Erel Segal-Halevi
<reference-request><pareto-efficiency>
Facility location: what is the set of Pareto-efficient outcomes?
Erel Segal-Halevi
# Facility location: what is the set of Pareto-efficient outcomes?

(Asked by: username_0 on 2024-12-17)

In the **facility location problem**, the government wants to construct a useful facility (e.g. a school, a bus-station), and has to decide where exactly to locate it. There are $n$ potential users of the facility; each user $i$ has a known location $x\_i$ (a point in some multi-dimensional space). The cost of each user is the distance between its location and the facility location, where 'distance' can be measured using different metrics.

Clearly, each location chosen for the facility can be good for some users (thoes who live nearby) and bad for others (those who live far away). Therefore, it makes sense to first find the set of all **Pareto-efficient** locations - those locations such that no other location is strictly better for all users (nearer to all users' locations).

In [this answer](https://math.stackexchange.com/a/5010174/29780) it is proved that, when distance is measured by the Euclidean metric, the set of all efficient allocations is exactly the convex hull of the points $x\_i$.

Is there a reference that studies such problems in a more general way, and has a characterization of efficient points for a larger class of metrics?

**Tags:** reference-request, pareto-efficiency

> **Comments:**
> **username_1**: The tools from spatial voting theory might be useful; they address questions that seem to be very similar. The book "Positive Political Theory I" by Austen-Smith and Banks is a good introduction to the topic. It's been a while that I looked at the topic, though.  
> **username_2**: I have tried to solve this problem earlier this year for taxi-cab metric in two-dimensional space, but could only solve it for the case of three users. Please see pages 27-29 of the following document: https://piazza.com/redirect/s3?bucket=uploads&prefix=paste%2Fi5t4zjz64oq3sl%2F25c99e0ffecc71285e0970995390e53a92ba34736804d8cc45be0ea1c29b64f7%2FEcon-postcards.pdf  
> **username_2**: The definition of Pareto efficiency I have used here is as follows: A location is said to be Pareto efficient if there is no other location such that we can make one user better off without making the others' worse off.  
> **username_0**: @username_2 yes, your definition is the standard one. The definition I used is usually called "weak Pareto efficiency". Both are interesting; I used weak Pareto efficiency because it is simpler.  

---

## 1 answers

### Answer by username_2 on 2024-12-30. Score: 0

Square-City: $[0,1]×[0,1]$

The objective is to establish a public facility at a specific location $(x, y)$, such as a library within the region $[0, 1] × [0, 1]$. This facility will be accessible to three individuals residing at the following locations:
$l\_1 =(x\_1,y\_1),l\_2 =(x\_2,y\_2),l\_3=(x\_3,y\_3)$
respectively.
Utility function of $i\in\{1,2,3\}$ is
$u\_i:[0,1]^2\rightarrow\mathbb{R}$ defined as
$u\_i(x,y)=-|x-x\_i|-|y-y\_i|$

Pareto optimal Location for the library is defined as that location such that no other location is strictly better than it for all users.

Set of Pareto optimal Locations for the following three situations is a rectangle/square:
[![enter image description here](https://i.sstatic.net/65UkALiB.png)](https://i.sstatic.net/65UkALiB.png)

Conjecture: In a plane $\mathbb{R}^2$, with the taxi-cab metric, and $n$ individuals located at $(x\_1,y\_1), \ldots, (x\_n,y\_n)$, set of Pareto optimal locations for the library consists of all the locations that lie inside the rectangle formed by end points $(x\_\min, y\_\min), (x\_\min, y\_\max), (x\_\max, y\_\max),(x\_\max, y\_\min)$ where $x\_\max=\max\_{i}x\_i, x\_\min=\min\_{i}x\_i, y\_\max=\max\_{i}y\_i, y\_\min=\min\_{i}y\_i$.


---

