# facilitys_perspective_to_fair_facility_location_problems__77bc15e5.pdf

Facility s Perspective to Fair Facility Location Problems

Chenhao Wang,1 Xiaoying Wu,2,3 Minming Li,4 Hau Chan1

1 University of Nebraska-Lincoln 2 AMSS, Chinese Academy of Sciences 3 University of Chinese Academy of Sciences 4 City University of Hong Kong chenhwang4-c@my.cityu.edu.hk, xywu@amss.ac.cn, minming.li@cityu.edu.hk, hchan3@unl.edu

We study the problem faced by a decision maker who wants to locate a set of facilities on a real line and allocate agents/items to the facilities. The items have given locations on the line, and can only be assigned to one of their closest facilities. The facilities are controlled by managers, who have additive utility over the items. An optimal solution that maximizes the (utilitarian or egalitarian) social welfare of the facilities may present a very unbalanced allocation of the items to the facilities and hence be perceived as unfair. In this paper, we are interested in fair allocation among facility managers and consider the well-studied proportionality and envy-freeness fairness notions and their relaxations. We assess the availability, existence, approximability, and the quality (price of fairness) of fair solutions, where the quality measures the system efﬁciency loss under a fair allocation compared to the one that maximizes the social welfare. further, we show that one can ﬁnd a Pareto-optimal solution in polynomial time.

1 Introduction Facility location problems and their variants (Stollsteimer 1963; Manne 1964; Shmoys, Tardos, and Aardal 1997; Jain and Vazirani 2001) have been actively (and most commonly) studied in the economics, operations research, and computer science communities since the mid 20th century due to its applicability in modeling and solving various realistic optimization and resource allocation problems (e.g., transportations and clustering). In the standard facility location problem, we are given a set of m facilities such as libraries, parks, and schools, a set of locations (e.g., bounded interval of [0,1]), and a set of n agents locating within the set of locations. The typical goal, from the agent s perspective, is to locate the facilities within a set of locations to minimize the total or maximal distance/cost of the agents to their closest facilities. Despite the numerous research work of facility location problems in the mechanism design and algorithmic settings (see e.g., (Procaccia and Tennenholtz 2013; Lu et al. 2010; Fotakis and Tzamos 2014; Cheng and Zhou 2015)), limited work has explored the facility location problems from the

Copyright 2021, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

facility s perspective where each facility has a (cardinal, satisfaction) utility function/preference over the possible subsets of agents the facility can serve the larger value it is for a subset, the more preferable the subset is to the facility. It is not hard to see that each facility, e.g., managed by certain personnel, can form a utility preference over the agents. For example, a recreation facility management of a recreation center has an underlying preference with regards to serving various groups of citizens. A principal or an organization of a public school has a preference over the types of students (see e.g., (Abdulkadiro glu 2005; Ehlers et al. 2014) in school choice) that can be admitted to the school. An optimal solution that maximizes the (utilitarian or egalitarian) social welfare of the facilities may present a very unbalanced allocation of the items to the facilities and hence be perceived as unfair, while fair allocations may induce a bad social welfare. Motivated by this, in this work, we consider the facilities utility preferences over the agents and initiate the study of fair facility location problems from the facility s perspective. More speciﬁcally, we aim to locate facilities within a set of locations to serve a set of population such that each facility s partition of agents (i.e., induced by the agents selecting the closest facilities) is fair under the facility s utility function. We address such a key problem of locating facilities under fundamental fairness notations to achieve (approximately) fairness. Our Results and Organization. We study the fair facility location problem where there is a set of m facilities with additive valuations over n agents or items in a bounded interval of [0,1]. We consider the well-studied proportionality (Prop) and envy-freeness (EF) fairness and their (additive) relaxations for our setting. Given the fairness concepts, we study the existence and guarantees of (approximately) fair contiguous valid allocations, which admit a location proﬁle of facilities such that the allocation satisﬁes the closest assignment rule. We note that our problem is related to the fair division problems with contiguous bundles (FDC) (Bouveret et al. 2017; Bil o et al. 2018; Suksompong 2019) in which the goal is to fairly allocate indivisible items to players/facilities such that each bundle forms a contiguous block; but we additionally require the closest assignment. In Section 3, we ﬁrst prove that the problem of deter-

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

mining the existence of a Prop allocation is NP-complete, using a similar reduction in (Bouveret et al. 2017) for the FDC. We show that for any instance, there exists a valid n+m 1

2m umax-Prop allocation where umax is highest value of any facility for any item. On the other hand, the existence of a valid ( n

12 umax ϵ)-Prop allocation is not guaranteed for any ϵ > 0, even if there are m = 3 facilities. In Section 4, we prove that the problem of determining the existence of an EF allocation is NP-complete. For any instance, there exists a valid ( 3

5)umax-EF allocation. The existence of a valid ( n

4 umax ϵ)-EF allocation is not guaranteed for any ϵ > 0, even if there are m = 3 facilities. When there are exactly two facilities, one can ﬁnd a valid umax-EF allocation. In Section 5, we study the best and worst price of fairness for both utilitarian and egalitarian social welfare, which is the ratio of the maximum possible social welfare over that of a (best or worst) fair allocation. While the best price of fairness is well-studied for fair division problems, we are the ﬁrst to study the worst price of fairness. We show that they have signiﬁcant difference for the egalitarian price of proportionality. Table 1 summarizes our results on the price of fairness, where UB and LB indicate the worst and best price of fairness, respectively. In Section 6, we propose an algorithm that returns a Pareto-optimal valid allocation in polynomial time, and analyze its efﬁciency on both types of social welfare. Comparison with FDC. In both settings, determining the existence of a Prop (and EF) allocation is NP-complete. Table 2 summarizes the results on additive fairness relaxations, and shows that both fairness concepts are much more difﬁcult to approximate in our problem. Surprisingly, the closest assignment constraint does not change the best price of fairness (LB in Table 1), which is the same as (Suksompong 2019) for FDC. We give all omitted proofs in Supplementary Material.

Price Utilitarian Egalitarian

Prop. UB: [m 1 + 1

m, m] UB: m LB: m 1 + 1

2 + 1 o(1)] UB: [ m

2 , m] LB: [ m

2 + 1 o(1)] LB: m

Table 1: Our results on the price of fairness.

Fairness Our setting FDC

Prop. UB: m+n 1

2m umax UB : m 1

m umax LB: n

12 umax LB : m 1

EF UB: ( 3n

5) umax UB : 2umax LB: n

Table 2: Additive-approximate fairness guarantees for our setting and FDC. The latter can be found in (Suksompong 2019), indicated by .

Related Work. Our work is grounded on a string of fruitful research in fair division and facility location problems. It is related to the Hotelling-Downs model (Hotelling 1929; Downs 1957), where some players (facilities) strategically locate themselves at a point along a line so as to attract the greatest number of clients; the client is attracted by the closest player. Our model differs from theirs in that the facilities have utility functions, i.e., different agents have different values to the facilities. Fair division with contiguous bundles. In FDC, the goal is to fairly allocate indivisible items that are located on a line to a group of players such that the allocation is required to be contiguous. The main difference to our problem is that, we need additionally to locate the facilities and allocate items to their closest players/facilities on the line. Such a variation takes into account the decisions of agents/items and introduces new challenges into fair division. More formally, the n items form a connected graph and are to be allocated to m players. In a contiguous allocation, the bundle of each player must form a contiguous block of items, inducing a connected subgraph. Each player has a value for each item. When the graph is a line, under the additive fairness relaxation, Suksompong (2019) shows that there is a contiguous m 1

m umax-Prop allocation, and a contiguous 2umax-EF allocation where umax is the highest value of any player for any item. Bouveret et al. (2017) prove that the problem of determining the existence of a contiguous Prop/EF allocation for an instance is NP-complete. Bei et al. (2019) study the price of connectivity. Price of Fairness. The price of fairness quantiﬁes the loss of social welfare that is necessary if we impose a fairness constraint on the allocation, initially studied by Caragiannis et al. (2012) for both allocating divisible and indivisible items. Later, Aumann and Dombb (2015) focus on contiguous allocations of divisible items and consider both utilitarian and egalitarian welfare, where utilitarian welfare refers to the sum of agents utilities and egalitarian welfare refers to their minimum. Suksompong (2019) completes the picture by providing tight or almost tight bounds on the price of fairness for contiguous allocations of indivisible items. Facility location games. In the algorithmic mechanism design settings of facility location games (Procaccia and Tennenholtz 2013; Chen et al. 2019), the locations of the agents are private. The planner s goal is to elicit (true) locations from the agents and locate the facilities to optimize the desirable objectives. In many of such facility location problems, fairness is usually studied from the agents perspective. For example, Cai et al. (2016) introduced a fairness criterion, called minimax-envy, to 1-facility location games and proposed strategy-proof mechanisms. Chen et al. (2020) study the minimax-envy for 2-facility location games. Liu et al. (2020) study the envy ratio for k-facility location games, which is a fairness concept derived from fair division (Lipton et al. 2004), and deﬁned as the maximum over the ratios between any two agents utilities. In this paper, however, we are interested in the fairness of facilities, and to our best knowledge, no previous work considers fairness from the facility s perspective.

2 Preliminaries

Let N = {1, . . . , n} be the set of agents/items. The items are located in a line segment, represented by the interval [0, 1]. We want to locate m 2 facilities F = {F1, F2 . . . , Fm} in the interval [0, 1] and allocate n items to the m facilities such that each item is assigned to the closest facility. An allocation A = (A1, . . . , Am) is a partition of all items into bundles for the facilities so that facility Fi receives bundle Ai. An allocation A is contiguous, if each bundle forms a contiguous block of items. An allocation A is valid, if there exists a location proﬁle of the facilities such that the locations of facilities are pairwise distinct and each item is assigned to a facility who has the smallest distance to the item. Since the facility locations must be different, a valid allocation implies that the bundle of every facility induces a contiguous block, and thus it is contiguous. Each facility Fi F has some nonnegative value ui(j) for item j N. Assume w.l.o.g. that for every item j, there is some facility Fi with positive value, i.e., ui(j) > 0. For each facility Fi, deﬁne ui,max := maxj N ui(j) to be the highest value of Fi for an item. Let umax := max Fi F ui,max be the highest value of any facility for an item. We assume that utilities are additive, which means ui(N ) = P j N ui(j) for any facility Fi and any subset of items N N. In terms of social welfare, the utilitarian welfare of A is the total utility P Fi F ui(Ai) of all facilities, and the egalitarian welfare is the minimum utility min Fi F ui(Ai) among the facilities. We are interested in ﬁnding valid allocations that are fair for the facilities, which implicitly induce a location proﬁle of facilities. We mainly study the following two fairness concepts and their (additive) relaxations.

Deﬁnition 2.1 (Proportional (Prop)). An allocation A = (A1, . . . , Am) is proportional if ui(Ai) ui(N)

m for all Fi F. For ϵ 0, the allocation is ϵ-proportional if ui(Ai) ui(N)

m ϵ for all Fi F.

Deﬁnition 2.2 (Envy-Free (EF)). An allocation A = (A1, . . . , Am) is envy-free if ui(Ai) ui(Aj) for all Fi, Fj F. For ϵ 0, the allocation is ϵ-envy-free if ui(Ai) ui(Aj) ϵ for all Fi, Fj F.

From these deﬁnitions, it is not hard to see that EF implies Prop, and ϵ-EF implies ϵ-Prop. We know that a valid allocation is contiguous but not vice versa. For example, consider a 3-facility instance with 4 items located at (0, 0.1, 0.9, 1), and a contiguous allocation ({1}, {2, 3}, {4}). There is no feasible location proﬁle of facilities such that each item is assigned to the closest facility, and thus it is not valid. In particular, when there are two facilities, any contiguous allocation is also valid, because we can locate one facility at the right endpoint of the left bundle, and locate the other at the left endpoint of the right bundle, such that every item is assigned to the closest facility.

Observation 2.3. When m = 2, every contiguous allocation is valid.

We assume that the items have pairwise distinct locations. If the items can be located at the same point, there is a very

bad instance of 2 facilities, where n 1 items are located at 0 and one item is located at 1. Note that the facility locations are different. Then any valid allocation cannot be fair, because it must assign the items at 0 to one facility, and the remaining item to the other. This is unacceptably unbalanced. Therefore, we only consider the case with pairwise distinct locations of items.

As a preliminary result, we present a key proposition that is important for ﬁnding ϵProp and ϵ-EF valid allocations in Sections 3 and 4.

Proposition 2.4. Given a contiguous allocation A = (A1, . . . , Am), we can have a valid allocation A = (A 1, . . . , A m) which obtains at least half utility for each facility from A, that is, ui(A i) 1

2 ui(Ai) for every Fi F.

Proof. Let A = (A1, . . . , Am) be a contiguous allocation. Let ai and bi be the leftmost and rightmost items allocated to facility Fi F. Denote by yi = ai+bi

2 the midpoint of Fi s bundle. Now we construct a location proﬁle x = (x1, . . . , xm) of facilities. In view of each facility Fi, if the total utility for the items located in interval [ai, yi] is greater than that for the items located in [yi, bi], then locate facility Fi at xi = ai, otherwise xi = bi. Based on the facilities location proﬁle x = (x1, . . . , xm), we obtain an allocation A = (A 1, . . . , A m) by assigning each item to the closest facility, breaking ties arbitrarily. By deﬁnition, allocation A is contiguous and valid. By the above construction of location proﬁle x and the closest assignment, if xi = ai (resp. xi = bi), then all items in the interval [ai, yi] (resp. [yi, bi]) are assigned to Fi. Therefore, we have ui(A i) 1

2 ui(Ai), establishing the theorem.

To end this section, we show that, given a contiguous allocation A = (A1, . . . , Am), there is an efﬁcient algorithm that determines whether it is valid. This enables us to focus on valid allocations, as the corresponding location proﬁle of facilities can be computed efﬁciently. We assume each bundle Ai is non-empty here, otherwise we can remove facility Fi from the allocation, and do not locate it. Let ai and bi be the left and right endpoints of Ai. (Recall that items have distinct locations.) Renaming if necessary, assume bi 1 < ai bi < ai+1, for i = 2, . . . , m 1. Let xi be a variable indicating the location of facility Fi. We need to check the existence of a facilities location proﬁle (x1, . . . , xm) so that the locations are pairwise distinct and items are assigned to their closest facilities. We can do that by solving the following program, whose feasible solution corresponds to such a location proﬁle and whose feasible region is non-empty if and only if A is valid.

max 0 s.t. |xi ai| |ai xi 1| for i = 2, . . . , m |bi xi| |xi+1 bi| for i = 1, . . . , m 1 0 xi 1. for i = 1, . . . , m

The ﬁrst 2m 2 constraints characterize closest assignment. Through simple manipulation of the absolute value expression, this problem can be solved via linear programming.

3 Proportionality In this section, we consider Prop allocations. Inspired by Theorem 3.1 of (Bouveret et al. 2017), which states that determining whether an FDC instance admits a Prop allocation is NP-complete, we adapt their reduction by adding distance terms and locating facilities to obtain the NP-hardness result in Theorem 3.1. Then, we present possibility and impossibility results for the existence of ϵ-Prop valid allocations.

Theorem 3.1. The problem of determining the existence of a proportional valid allocation is NP-complete.

Proof. We reduce from EXACT-3-COVER (X3C), which is an NP-complete problem (Garey and Johnson 1979). An instance of X3C is given by I = (X, T ), where X = {x1, . . . , x3s} is a set of elements, and T = {T1, . . . , Tr} is a family of 3-element subset of X. The answer is yes if and only if X can be exactly covered by s sets from T , i.e., each element in X is covered by exactly one of the s sets. This problem remains NP-complete if the frequency fx = |{T T : x T}| of each x X is at most 3. Consider an instance I = (X, T ) of X3C, where fx 3 for each x X, and the elements of T are denoted by x1 T , x2 T , x3 T for each T T . We construct an instance of our problem as follows. There are three items v1 T , v2 T , v3 T for each set T T , a set of s items B = {b1, . . . , bs} and a dummy item w. Let ϵ > 0 be a sufﬁciently small number. The order of these n = 3r + s + 1 items in the line segment [0,1] is

v1 T1 < v2 T1 < v3 T1 < v1 T2 < < v3 Tr < b1 < < bs < w.

For each Ti T , the lengths of both intervals (v1 Ti, v2 Ti) and (v2 Ti, v3 Ti) are ϵ. For i = 1, . . . , r 1, the lengths of both intervals (v3 Ti, v1 Ti+1) and (v3 Tr, b1) are 3ϵ. For j = 1, . . . , s 1, the lengths of intervals (bj, bj+1) and (bs, w) are ϵ. Deﬁne a T-set to be VT = {v1 T , v2 T , v3 T } for each T T . There are a total of m = 3s + r + 1 facilities: one facility FT for each T T , one facility Fx for each x X and one dummy facility Fd. The values are deﬁned as:

1/(3m) if v VT 1/m if v B (m s 1)/m if v = w 0 otherwise

( 1/m if v VT and x T 1 3fx/m if v = w 0 otherwise

ud(v) = 1 if v = w 0 otherwise

Then each facility has a utility of 1 over the set of all items, and in any Prop allocation he should have a utility of at least 1/m. It is easy to see that, an allocation is Prop, if and only if facility Fd receives the dummy item w, each facility Fx receives an item in VT such that x T, and each facility FT receives the set VT or an item from B. Suppose that there is a valid Prop allocation. As |B| = s, the number of T-facilities who is assigned to a T-set must

be r s. So the number of T-sets available for x-facilities is s, which constitutes a cover for X. Suppose that I admits an exact cover T T of size s. Let µ be a perfect matching between T and B. Deﬁne a location proﬁle of facilities and the allocation as follows:

for each T T , facility FT is located at the position of item µ(T) B, and receives item µ(T); for each T / T , facility FT is located at the position of item v2 T , and receives the T-set VT ; each facility Fx is located at the position of item vk T such that x = xk T and T T , and receives item vk T ; facility Fd is located at the position of item w, and receives item w.

It is easy to verify that each facility receives a contiguous piece of value at least 1/m, and each item is assigned to the closest facility. Thus, the allocation is Prop and valid.

ϵ-Proportionality Suksompong (2019) shows that there always exists a contiguous allocation A such that ui(Ai) 1

m ui(N) m 1

m ui,max. By Proposition 2.4, we can obtain a valid allocation with a loss of at most half utility for each facility, by locating each facility in the left (or right) endpoint of his bundle in A if he prefers the left (or right) half of his bundle, and then allocating the items subject to the closest assignment.

Theorem 3.2. Given any instance, there exists a valid allocation (N1, . . . , Nm) such that for every facility Fi,

m ui(N) n + m 1

In particular, there exists a valid n+m 1

2m umax-proportional allocation.

Proof. By Theorem 1 of (Suksompong 2019), there is a contiguous m 1

m umax-proportional allocation A = (A1, . . . , Am) such that ui(Ai) 1

m ui(N) m 1

m ui,max. By Proposition 2.4, it can induce a valid allocation A = (A 1, . . . , A m) such that, for every facility Fi F,

ui(A i) ui(Ai)

2m (m 1)ui,max

m (n ui,max

Next, we give a non-existence result for ϵ-Prop valid allocations.

Theorem 3.3. The existence of a valid ( n

12 umax δ)- proportional allocation is not guaranteed for any δ > 0, even if there are m = 3 facilities.

Proof. Suppose that there are n = 2k (k > 1) items with unit value of 1 (implying umax = 1) to be assigned to m = 3 facilities. The leftmost k items are located in [0, 0.1], and the rightmost k items are located in [0.9, 1]. Then a ( n

12 umax δ)-proportional allocation guarantees that each facility receives a utility at least n

2 + δ. If such an allocation is valid, it admits a location proﬁle of facilities so that each item is allocated to his closest facility. Renaming if necessary, assume F1 is the leftmost facility and F3 is the rightmost one. Assume w.l.o.g. that F1 and F2 are located in [0, 0.5]. Then they cannot receive the items located in [0.9, 1], because facility F3 is always closer to them. It indicates that F1 and F2 can only be allocated the leftmost k items, and one of them has a utility at most k

2, giving a contradiction.

4 Envy-Freeness In this section, we consider EF valid allocations. Using a similar reduction as in Theorem 3.1, we have the following hardness result on EF. Then we present possibility and impossibility results for the existence of ϵ-EF valid allocations.

Theorem 4.1. The problem of determining the existence of an envy-free valid allocation is NP-complete.

ϵ-Envy-Freeness For m = 2 facilities, one can ﬁnd a contiguous umax-EF allocation (Suksompong 2019). It follows by Proposition 2.4 that a valid umax-EF allocation also exists.

Theorem 4.2. Given any instance with two facilities, there exists a valid allocation such that facility i has envy at most ui,max towards the other. In particular, there exists a valid umax-envy-free allocation.

Proof. Arranging the items in an order from left to right, we add one item to a block (initiated as an empty set) at each time, until some facility i (say F1) values this block at least ui(N)/2 ui,max/2. Then we allocate this block (denoted by A1) to F1, and the leftover (denoted by A2) to F2. Clearly facility F1 values F2 s block A2 at most u1(N)/2+u1,max/2. It implies u1(A1) u1(A2) u1,max, and F1 has envy at most u1,max towards F2. Similarly, F2 values F1 s block A1 less than u2(N)/2 u2,max/2 + u2,max = u2(N)/2+u2,max/2, because the last item added in A1 has a value at most u2,max to F2. Then he values his own block A2 more than u2(N)/2 u2,max/2, which implies u2(A2) > u2(A1) u2,max, and F2 has envy at most u2,max towards F1.

For general number of facilities, Suksompong (2019) shows that there exists a contiguous allocation such that facility Fi has envy less than 2ui,max towards any other. We can also modify it to construct a valid allocation, incurring a loss of the utility.

Theorem 4.3. Given any instance, there exists a valid ( 3

5n+ 8 5)umax-envy-free allocation.

Proof. Suppose that A = (A1, . . . , Am) is a contiguous allocation given in (Suksompong 2019). We construct a

valid allocation A = (A 1, . . . , A m) as in Proposition 2.4, where ui(A i) ui(Ai)/2 holds for every facility Fi F. Note that A is 2ui,max-envy-free (Suksompong 2019). So the inequality ui(Ai) ui(Aj) 2ui,max holds for any j = i. Let Ak be the bundle which satisﬁes ui(Ak) = max Aj A ui(Aj). By the construction rule of allocation A , the bundle A j is a subset of the union of Aj and Aj s one neighbor bundle in A, which implies that ui(A j) ui(Ak) + ui(Aj). We obtain that for any j = i,

4(ui(Ak) + ui(Aj) 4ui,max)

4ui(A j) umax.

Since ui(A j) + ui(A i) numax, it gives that

4ui(A j) umax

8)ui(A j) umax

8ui(A i) umax.

It immediately follows that ui(A i) ui(A j) ( 3

5n + 8 5)umax, establishing the proof.

Using the example constructed in the proof of Theorem 3.3, we have the following lower bound. Theorem 4.4. For any δ > 0, the existence of a valid ( n

4 umax δ)-envy-free allocation is not guaranteed, even if there are m = 3 facilities. The bounds in Theorems 4.3 and 4.4 are asymptotically tight when m = 3.

5 Price of Fairness The price of fairness measures the efﬁciency loss of allocations due to fairness constraints. In this section, we study the best and worst prices, which compare the solution maximizing the social welfare and the best/worst fair solution. We assume the normalization ui(N) = 1 for all i = 1, . . . , m when considering the price of fairness notions. Given an instance (along with a set of allocations considered), its best utilitarian price of proportionality is deﬁned as the ratio of the utilitarian welfare of the optimal valid allocation over that of the best Prop valid allocation. Formally, given instance I, if it admits a valid Prop allocation, its best utilitarian price of proportionality is

P u pr(I) :=

P Fj F uj(A ) P Fj F uj(A pr),

where A is an optimal valid allocation, and A pr is an optimal Prop valid allocation. If a Prop valid allocation does not exist, then the price is not deﬁned for that instance. The egalitarian price is deﬁned analogously. Given instance I, if it admits a valid Prop allocation, its best egalitarian price of proportionality is

P e pr(I) := min Fj F uj(A )

min Fj F uj(A pr).

The (overall) best utilitarian (resp., egalitarian) price of proportionality is then the supremum over all instances: P u pr = sup I P u pr(I) (resp., P e pr = sup I P e pr(I)). The price of envy-freeness P u ef and P e ef are deﬁned analogously. Suksompong (2019) studies the best price of fairness for the FDC problem. His results are applicable to our problem, because we can deﬁne suitable distances of items in the constructed instances such that each contiguous allocation considered is valid. Theorem 5.1. For valid allocations of indivisible items, P u pr = m 1 + 1

m, and P e pr = 1. Theorem 5.2. For valid allocations of indivisible items, P u ef m

2 + 1 o(1) , and P e ef = m

Proof sketch. The upper bound of P u ef can be derived by using the proof of Theorem 2.1 in (Aumann and Dombb 2015), which establishes the same upper bound for the connected cake cutting problem, by linear programming. The lower bound of P u ef can be derived as in the proof of Theorem 8 in (Suksompong 2019), which considers best price for the FDC problem. The bounds of P e ef comes from Theorem 11 in (Suksompong 2019).

While the best price of fairness is well-studied in fair division problems, we are the ﬁrst to study the worst price of fairness: given instance I,

P u pr(I) = sup A Apr

Fj F uj(A )

Fj F uj(A) , P e pr(I) = sup A Apr

min Fj F uj(A )

min Fj F uj(A) ,

where Apr is the set of Prop valid allocations. Similarly, the overall price of proportionality is P u pr = sup I P u pr(I) and P e pr = sup I P e pr(I). The worst price of envy-freeness P u ef and P e ef are deﬁned analogously. We show that the worst price has a signiﬁcant difference with the best price only for the egalitarian price of proportionality. Theorem 5.3. For valid allocations of indivisible items, m 1 + 1

m P u pr m.

Proof. Consider an arbitrary instance. In any Prop valid allocation, since the utility of each facility is at least 1 m, the utilitarian welfare is at least 1. In an optimal valid allocation, the utility of each facility is no more than 1, so the utilitarian welfare is at most m. Thus we have that P u pr m. Since P u pr P u pr = m 1 + 1

m, we obtain the lower bound.

Theorem 5.4. For valid allocations of indivisible items, P e pr = m.

Proof. Upper bound. Consider an arbitrary instance. A Prop valid allocation ensures that every facility has utility at least 1 m, while the optimal egalitarian welfare is no more than 1. Thus the worst egalitarian price is no more than m. Lower bound. Suppose that there are m facilities and n = m2 items. The value of facility Fi is ui(j) = 1 m for j = (i 1)m + 1, . . . , im and ui(j) = 0 otherwise. For i = 1, 2, . . . , m, items (i 1)m + 1 are located at i 1

m + 1 2m, and items (i 1)m + 2, (i 1)m + 3, . . . , im are located in ( i 1

m + 1 2m, i

m). Consider a valid allocation A where facility

Fi is located at i 1

m + 1 2m. The items (i 1)m + 1, . . . , im are assigned to facility Fi which implies that Fi has a utility 1, and the egalitarian welfare is 1. Consider another valid allocation A where facility Fi is located at i 1

m , and let F1 receive item 1, Fi receive items (i 2)m + 2, (i 2)m + 3, . . . , (i 1)m, (i 1)m + 1 for i = 2, . . . , m 1, and Fm receive items (m 2)m+2, (m 2)m+3, . . . , (m 1)m, (m 1)m+1, (m 1)m+2, . . . , m. Since each facility has a utility at least 1 m, this allocation is Prop. As the utility of facility F1 is 1 m, the egalitarian welfare is 1

m. Thus we have that P e pr 1 1/m = m.

Theorem 5.5. For valid allocations of indivisible items, m

2 < P u ef m

2 + 1 o(1), and m

2 P e ef m.

6 Pareto-Optimality In this section, we study the Pareto-optimality of valid allocations. Given an allocation A, an allocation A is a Paretoimprovenment of A if ui(A i) ui(Ai) for all Fi F and uj(A j) > uj(Aj) for some Fj F. A valid allocation is Pareto-optimal if no valid allocation is its Paretoimprovement. Denote set {1, . . . , k} by [k]. We assume the normalization ui(N) = 1 for i [m].

Theorem 6.1. Given any instance, a Pareto-optimal valid allocation can be found in polynomial time.

Proof. Let min(V ) be the leftmost item in bundle V . Let Si N be the minimum contiguous bundle containing all items to which Fi has positive utility, that is, Fi beneﬁts from the leftmost and rightmost items in Si, and ui(N\Si) = 0. We show that Algorithm 1 ﬁnds a Pareto-optimal valid allocation. We consider unallocated items from left to right, and give a facility (say Fi), who has positive utility to the current item, the intersection between Si and unallocated items, if this allocation is valid1. This process ends when all items are assigned or the allocation is no longer valid. If there are remaining items unallocated, we assign them to the last facility who receives a non-empty bundle. The returned allocation is valid, because the process always maintains the validity when adding a new bundle to the allocation. The time complexity of Algorithm 1 mainly comes from checking the validity of an allocation in Line 10, which can be done by solving LP (1), and thus is polynomial. It remains to show the Pareto-optimality of the returned allocation A = (A1, . . . , Am). Assume bundles A1, . . . , Ak are non-empty, and Ak+1, . . . , Am are empty. Suppose there is a valid allocation A = (A 1, . . . , A m) which is a Paretoimprovement of A. Note that items in N\A1 have 0 value to F1, and u1(A 1) = u1(A1) = u1(N). Because A1 is the minimum contiguous bundle such that facility F1 receives the full utility, it must be A1 A 1. Since A2 is the minimum contiguous bundle such that F2 receives the maximum possible utility u2(N\A1) = u2(A2), we have A1 = A 1 (otherwise the leftmost item in A2 belongs to A 1, and u2(A 2) < u2(A2)). Similarly, it must be A2 A 2 and

1If partial allocation (A1, . . . , Ai 1, {j}) is valid for facilities F1, . . . , Fi, then (A1, . . . , Ai 1, Ai = Si\ i 1 k=1 Ak) is also valid.

Algorithm 1 Pareto-optimal valid allocation

Require: The number m of facilities, and location proﬁle x of items N satisfying x1 xn. Ensure: A valid allocation of items. 1: Initialize Ai = for i [m]. 2: Let Si N be the minimum contiguous bundle containing all items to which Fi has positive utility. 3: Let Pj = {Fi F|ui(j) > 0} be the set of facilities that have positive utility to item j N. Pj = . 4: Assume F1 P1 (renaming if necessary). A1 S1. 5: for i = 2, . . . , m do 6: if N = i 1 k=1Ak then 7: break 8: end if 9: Let j = min(N\ i 1 k=1Ak) be the leftmost one among the unallocated items. 10: Assume Fi Pj (renaming if necessary). Check if (A1, . . . , Ai 1, {j}) is valid for facilities F1, . . . , Fi. 11: if not valid then 12: Ai 1 Ai 1 N\ i 1 k=1 Ak. 13: return allocation A = (A1, . . . , Am). 14: else 15: Ai Si\ i 1 k=1 Ak. 16: end if 17: end for 18: return allocation A = (A1, . . . , Am).

u2(A 2) = u2(A2) by A1 = A 1. Since A3 is the minimum contiguous bundle such that F3 receives u3(N\ i=1,2Ai) = u3(A3), we have A2 = A 2. Repeating this analysis, we have Ai = A i for i [k 1], and Ak A k. If k = m, all facilities receive a non-empty bundle in A, and it must be A = A . So we consider the case when k < m. Suppose Fl (l > k) improves in A , and A l is non-empty. Let j = min(N\ i 1 k=1Ak), and Fi Pj. Note from Line 10 of Algorithm 1 that the partial allocation (A1, . . . , Ak, {j}) is not valid for facilities F1, . . . , Fk, Fi. The only possible reason is that any potential location for Fi that is closest for item j would attract some item in Ak. Then it is easy to see that the partial allocation (A 1, . . . , A k, A l) is not valid for facilities F1, . . . , Fk, Fl, because any potential location for Fl that is closest for items in A l would attract some item in A k. Thus A is not valid, a contradiction.

Once a valid allocation is given, one can ﬁnd the corresponding location proﬁle of facilities easily by solving LP (1). Our solution is not (approximately) fair, as it may assign nothing to a facility. We also remark that, while Igarashi and Peters (2019) show that a Pareto-optimal contiguous allocation on a path can be found efﬁciently, their algorithm is not applicable here due to the closest assignment constraint. For the utilitarian welfare, every optimal allocation must be Pareto-optimal. For the egalitarian welfare, there exists an optimal valid allocation (which lexicographically maximizes the facilities utility, from the smallest to the largest) is Pareto-optimal. Thus the (best) price of Pareto-optimality equals 1 for both types of social welfare. However, it is dif-

ﬁcult to calculate a valid allocation maximizing social welfare, and the solution found by Algorithm 1 may incur a large loss of social welfare. Theorem 6.2. The utilitarian welfare induced by Algorithm 1 is at least 1

m fraction of the optimal utilitarian welfare. For the worst instance, the ratio of the utilitarian (or egalitarian) welfare of the optimal valid solution over that of the outcome of Algorithm 1 approaches m (or inﬁnity).

Proof. In an allocation given by Algorithm 1, the utility of the ﬁrst facility equals 1, implying that the utilitarian welfare is no less than 1. Note that the utilitarian welfare is no more than m in the optimal allocation. Thus, the ﬁrst claim holds. Consider m facilities and n = m + 1 items. The utilities of facilities are deﬁned as folllows: u1(1) = 1 ϵ, u1(2) = = u1(m) = 0, u1(m + 1) = ϵ; uj(j) = 1, uj(i) = 0 for j = 2, . . . m and i = j. In the optimal allocation, facility Fi serves item i for i = 1, . . . , m 1, and Fm serves two items m and m + 1. The utilitarian welfare equals m ϵ, and the egalitarian welfare equals 1 ϵ. But in the Paretooptimal allocation given by Algorithm 1, facility F1 obtains all items, implying that the utilitarian welfare equals 1 and the egalitarian welfare equals 0, completing the proof.

7 Conclusions This paper is devoted to the problem of fairly locating the facilities and assigning the agents/items to the facilities. We consider the fairness concepts of proportionality and envyfreeness, and their additive relaxations. Compared with the results for the well-studied fair division problem with contiguous bundles, an approximate fair allocation in our problem is much harder to obtain and to guarantee the existence, while the price of fairness is almost the same. A Paretooptimal valid allocation can be found efﬁciently, though it does not satisfy the fairness criteria. This problem contributes to the class of facility location problems by ﬁrst considering the fairness of facilities, while previous works only consider the fairness of agents (items). On the other hand, it adds a new dimension to the typical fair division problems, that all items/agents must be assigned to their closest individuals/facilities. It takes into account the preference of items, and the allocations are non-imposing in the sense that the items can freely select the facilities. There are a lot of future directions for this problem. First, we only consider the additive approximate fairness. What about the multiplicative approximate fairness, or envyfreeness up to one good (EF1) (Bil o et al. 2018)? Second, other fairness concepts (e.g., maximin share (Garg and Taki 2020)) and other social welfare (e.g., Nash welfare (Mc Glaughlin and Garg 2020)), along with their prices, can be studied. Further, when the items and facilities are allowed to locate on a more general space such as a tree or a cycle, there are more possibilities to explore. Acknowledgements Minming Li is also from City University of Hong Kong Shenzhen Research Institute, Shenzhen, P. R. China. The work was partially sponsored by Project 11771365 supported by NSFC.

References Abdulkadiro glu, A. 2005. College admissions with afﬁrmative action. International Journal of Game Theory 33(4): 535 549. Aumann, Y.; and Dombb, Y. 2015. The efﬁciency of fair division with connected pieces. ACM Transactions on Economics and Computation (TEAC) 3(4): 1 16. Bei, X.; Igarashi, A.; Lu, X.; and Suksompong, W. 2019. The price of connectivity in fair division. ar Xiv ar Xiv: 1908.05433. Bil o, V.; Caragiannis, I.; Flammini, M.; Igarashi, A.; Monaco, G.; Peters, D.; Vinci, C.; and Zwicker, W. S. 2018. Almost envy-free allocations with connected bundles. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS), volume 124, 14:1 14:21. Bouveret, S.; Cechl arov a, K.; Elkind, E.; Igarashi, A.; and Peters, D. 2017. Fair division of a graph. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 135 141. Cai, Q.; Filos-Ratsikas, A.; and Tang, P. 2016. Facility location with minimax envy. In Proceedings of the 25th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 137 143. Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; and Kyropoulou, M. 2012. The efﬁciency of fair division. Theory of Computing Systems 50(4): 589 610. Chen, X.; Fang, Q.; Liu, W.; and Ding, Y. 2020. Strategyproof mechanisms for 2-Facility location games with minimax envy. In International Conference on Algorithmic Applications in Management, 260 272. Springer. Chen, X.; Li, M.; Wang, C.; Wang, C.; and Zhao, Y. 2019. Truthful mechanisms for location games of dual-role facilities. In Proceedings of the 18th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 1470 1478. Cheng, Y.; and Zhou, S. 2015. A survey on approximation mechanism design without money for facility games. In Advances in Global Optimization, 117 128. Springer. Downs, A. 1957. An Economic Theory of Democracy. Harper and Row 28. Ehlers, L.; Hafalir, I. E.; Yenmez, M. B.; and Yildirim, M. A. 2014. School choice with controlled choice constraints: Hard bounds versus soft bounds. Journal of Economic Theory 153: 648 683. Fotakis, D.; and Tzamos, C. 2014. On the power of deterministic mechanisms for facility location games. ACM Transactions on Economics and Computation (TEAC) 2(4): 1 37. Garey, M. R.; and Johnson, D. S. 1979. Computers and intractability, volume 174. Freeman San Francisco. Garg, J.; and Taki, S. 2020. An improved approximation algorithm for maximin shares. In Proceedings of the 21st ACM Conference on Economics and Computation (ACMEC), 379 380.

Hotelling, H. 1929. Stability in Competition. The Economic Journal 39(153): 41 57. Igarashi, A.; and Peters, D. 2019. Pareto-optimal allocation of indivisible goods with connectivity constraints. In Proceedings of the 33rd AAAI Conference on Artiﬁcial Intelligence (AAAI), volume 33, 2045 2052. Jain, K.; and Vazirani, V. V. 2001. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM 48(2): 274 296. Lipton, R. J.; Markakis, E.; Mossel, E.; and Saberi, A. 2004. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (ACM-EC), 125 131. Liu, W.; Ding, Y.; Chen, X.; Fang, Q.; and Nong, Q. 2020. Multiple facility location games with envy ratio. In International Conference on Algorithmic Applications in Management, 248 259. Springer. Lu, P.; Sun, X.; Wang, Y.; and Zhu, Z. A. 2010. Asymptotically optimal strategy-proof mechanisms for two-facility games. In Proceedings of the 11th ACM Conference on Electronic Commerce (ACM-EC), 315 324. Manne, A. S. 1964. Plant location under economies-ofscale decentralization and computation. Management Science 11(2): 213 235. Mc Glaughlin, P.; and Garg, J. 2020. Improving nash social welfare approximations. Journal of Artiﬁcial Intelligence Research 68: 225 245. Procaccia, A. D.; and Tennenholtz, M. 2013. Approximate mechanism design without money. ACM Transactions on Economics and Computation (TEAC) 1(4): 1 26.

Shmoys, D. B.; Tardos, E.; and Aardal, K. 1997. Approximation algorithms for facility location problems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), 265 274. Stollsteimer, J. F. 1963. A working model for plant numbers and locations. Journal of Farm Economics 45(3): 631 645. Suksompong, W. 2019. Fairly allocating contiguous blocks of indivisible items. Discrete Applied Mathematics 260: 227 236.