Strategyproof Mechanisms for Group-Fair Facility Location Problems

1 Introduction

In the classical facility location problems (FLPs) from the mechanism design perspective [Procaccia and Tennenholtz, 2009], we have a set N of agents, and each agent i has a privately known location xi ∈ R on the real line. The typical goal is to design a strategyproof mechanism that elicits true location information from the agents and locates a facility (e.g., a public library, park, or representative) y ∈ R on the real line to (approximately) minimize a given cost objective that measures agents' distances to the facility. Subsequent works have explored settings with more than one facility (e.g., [Procaccia and Tennenholtz, 2009; Lu et al., 2010; Fotakis and Tzamos, 2014; Serafino and Ventre, 2015; Chen et al., 2020; Zou and Li, 2015]) and various models/objectives (e.g., [Sui et al., 2013; Sui and Boutilier, 2015; Filos-Ratsikas et al., 2017; Cai et al., 2016; Feldman and Wilf, 2013; Mei et al., 2016; Aziz et al., 2020b; Aziz et al., 2020a]). See [Chan et al., 2021] for a survey.

Motivated by the importance of ensuring group fairness and equality among groups of agents in our society, we consider the group-fair FLPs where the set N of n agents is partitioned into m groups, G1, ...,Gm, based on criteria (e.g., gender, race, or age) and aim to design strategyproof mechanisms to locate the facility to serve groups of agents to ensure some desired forms of group fairness and the truthfulness of agents. Potential applications include determining the best location of a public facility (e.g., park or library) to serve a subset of agents as to provide fair access to different groups (e.g., based on race, gender, and age) and determining the best candidate or ideal point to select in an election within an organization as to ensure fair representative for groups of agents.

Our Key Challenges and Contribution. It is easy to see that any facility location (e.g., either at a fixed point or at an agent's location) can be unfair for different groups of agents under some FLP instances. Therefore, in order to understand the degree of unfairness suffered by each group of agents, we use group-fair objectives to mathematically quantify and compare the unfairness (or inequality) of each group (e.g., based on group costs) given the location of the facility. Given the group-fair cost objectives, we aim to design strategyproof mechanisms to locate a facility that ensures the costs of groups are fair and can (approximately) minimize the overall unfairness of all groups. As a result, our key challenges are (1) defining appropriate group-fair objectives and (2) designing strategyproof mechanisms to (approximately) optimize a given group-fair objective.

As our starting point, we consider group-fair cost objectives introduced by well-established domain experts [Marsh and Schilling, 1994] in the optimization literature of FLPs dated back in the 1990s. As we showed (in Theorem 1), it is impossible to design any reasonable strategyproof mechanisms with a bounded approximation for many of these objectives. Despite the negative result, we identify other wellmotivated group-fair cost objectives and introduce novel objectives that capture intergroup and intragroup fairness (IIF) for agents that are within each group, in which the design of strategypoof mechanisms with constant approximation ratios is possible. Using simple existing mechanisms and new mechanisms designed by us, our results (through rigorous non-trivial arguments) demonstrate the possibility of achieving approximately group-fair outcomes for these objectives.

Our results are summarized in Table 1. More specifically:

• For the group-fair objective that aims to minimize the maximum total group cost (mtgc), we show that the classical mechanisms (i.e., Median Deterministic Mechanism (MDM), Leftmost Deterministic Mechanism (LDM), and Randomized Mechanism (RM)) proposed by [Procaccia and Tennenholtz, 2009] have parameterized approximation ratios. In contrast, the mechanism we proposed, Majority Group Deterministic Mechanism (MGDM), that leverages group information and puts the facility at the median of the largest group, obtains an improved approximation ratio of 3. We also provide a lower bound of 2 for this objective. We show that putting the facility at the median of any group with a smaller size will result in a larger approximation ratio.
• For the objective of minimizing the maximum average group cost (magc), we provide the upper bounds for all of the considered mechanisms and the lower bounds for the objective. The Narrow Randomized Mechanism (NRM), which leverages randomization and group information, modifies the range used by RM for placing facilities to achieve a better approximation ratio.
• We introduce a new notion of intergroup and intragroup fairness (IIF) that considers group-fairness among the groups and within groups. We consider two objectives based on the IIF concept: IIF1, IIF2, where the first considers these two fairness measures as two separate indicators, while the second considers these two fairness measures as one combined indicator for each group. For both objectives, we establish upper bounds of 4 by using the kth-Location Deterministic Mechanism (kLDM), which puts the facility at the kth (leftmost) agent location, and the matching lower bounds of 4.

Due to the space limit, most of the proofs are in the full version of the paper (https://arxiv.org/abs/2107.05175).

Related Work. We will elaborate below the most related works of facility location problems (FLPs) to ours that consider some forms of individual fairness and envy (i.e., a special case of group fairness). From the optimization perspective, early works (see e.g., [McAllister, 1976; Marsh and Schilling, 1994; Mulligan, 1991]) in FLPs have examined objectives that quantify various inequity notions. For instance,

[Marsh and Schilling, 1994] considers a group-fairness objective (i.e., the Center objective in [Marsh and Schilling, 1994]) that is equivalent to our mtgc group-fair objective and similar to our magc group-fair objective. These works do not consider FLPs from the mechanism design perspective.

Although previous works have not considered the general notion of group fairness explicitly (e.g, |Gj | > 1 for some j), a few works have considered some form of individual fairness (i.e., the maximum cost objective when m = n) and envy in general. The seminal work of approximate mechanism design without money in FLPs [Procaccia and Tennenholtz, 2009] considers the design of strategyproof mechanisms that approximately minimize certain cost objectives such as total cost or maximum cost. An individual fair objective that is considered in [Procaccia and Tennenholtz, 2009] is that of the maximum cost objective, which aims to minimize the maximum cost of the agent farthest from the facility (i.e., m = n). For the maximum cost objective, [Procaccia and Tennenholtz, 2009] establish tight upper and lower bounds of 2 for deterministic mechanisms and 1.5 for randomized mechanisms. However, applying these mechanisms to some of our objectives directly, such as the mtgc and randomized part in the magc, would yield worse approximation ratios. There are also envy notions such as minimax envy [Cai et al., 2016; Chen et al., 2020], which aims to minimize the (normalized) maximum difference between any two agents' costs, and envy ratio [Liu et al., 2020; Ding et al., 2020], which aims to minimize the maximum over the ratios between any two agents' utilities. Other works and variations on facility location problems can be found in a recent survey [Chan et al., 2021].

2 Preliminary

In this section, we define group-fair facility location problems and consider several group-fair social objectives. We then show that some of these objectives have unbounded approximation ratios.

2.1 Group-Fair Facility Location Problems

Let N = {1, 2, ..., n} be a set of agents on the real line and G = {G1,G2, ...,Gm} be the set of (disjoint) groups of the agents. Each agent i ∈ N has the profile ri = (xi, gi) where xi ∈ R is the location of agent i and gi ∈ {1, ...,m} is the group membership of agent i. Each agent knows the mechanism and then reports her location, which may be different from her true location. We use |Gj| to denote the number of the agents in group Gj . Without loss of generality, we assume that x1 ≤ x2 ≤ ... ≤ xn. A profile r = {r1, r2, .., rn} is a collection of the location and group information. A deterministic mechanism is a function f which maps profile r to a facility location y ∈ R. A randomized mechanism is a function f, which maps profile r to a facility location Y , where Y is a set of probability distributions over R. Let d(a, b) = |a - b| be the distance between two points a, b ∈ R. Naturally, given a deterministic (or randomized) mechanism f and the profile r, the cost of agent i ∈ N is defined as c(r, xi) = d(f(r), xi) (or the expected distance EY ∼f(r)[d(Y, xi)]).

Our goal is to design mechanisms that enforce truthfulness while (approximately) optimizing an objective function.

Definition 1. A mechanism f is strategyproof (SP) if and only if an agent can never benefit by reporting a false location, regardless of the strategies of the other agents. More formally, for any profile r = {r1, ..., rn}, for any i ∈ N and for any x′i ∈ R, let r′i = (x′i , gi). We have c(f(r), xi) ≤ c(f(r′i , r-i), xi) where r-i is the profile of all agents except agent i.

Notice that when f is randomized, Definition 1 implies SP in expectation.

In the following, we discuss several group-fair cost objectives that model some form of inequity. We invoke the legal notions of disparate treatment [Barocas and Selbst, 2016; Zimmer, 1996] and disparate impact [Barocas and Selbst, 2016; Rutherglen, 1987], the optimization version of FLPs [McAllister, 1976; Marsh and Schilling, 1994; Mulligan, 1991], and recent studies in optimization problems [Tsang et al., 2019; Celis et al., 2018] to derive and motivate the following group-fair objectives.

Group-fair Cost Objectives. We consider defining the group cost from two main perspectives. One is the total group cost, which is the sum of the costs of all the group members. Through the objective, we hope to measure the inequality of each group in terms of its group cost to the facility. Hence, our first group-fair cost objective is to minimize the maximum total group cost (mtgc) to ensure that each group as a whole is not too far from the facility. More specifically, given a true profile r and a facility location y,

Our second group-fair cost objective is to minimize the maximum average group cost (magc). Therefore, we have

and we hope to ensure that each group, on average, is not too far from the facility. We measure the performance of a mechanism f by comparing the objective that f achieves and the objective achieved by the optimal solution. If there exists a number α such that for any profile r, the output from f is within α times the objective achieved by the optimal solution, then we say the approximation ratio of f is α.

2.2 Alternative Group-Fair Social Objectives

In addition to the objectives defined earlier, we can also consider the following natural objectives for group-fair facility location problems:

where hj is a function that can be (i) ∑i∈Gj c(y, xi), (ii) ∑i∈Gj c(y,xi) |Gj | or (iii) maxi∈Gj c(y, xi), which implies that each of (a) and (b) has three different group-fair objectives. In general, both (a) and (b) capture the difference between groups in terms of difference and ratio, respectively, under the desirable hi. For objectives under type (a), it can be seen as a group envy extended from individual envy works [Cai et al., 2016; Chen et al., 2020], and type (a) with function (i) is exactly measure (7) in [Marsh and Schilling, 1994]. For objectives under type (b), it can be seen as a group envy ratio extended from previous individual envy ratio studies [Liu et al., 2020; Ding et al., 2020].

Surprisingly, we show that any deterministic strategyproof mechanism for those objectives have unbounded approximation ratios.

Theorem1. Any deterministic strategyproof mechanismdoes not have a finite approximation ratio for minimizing the three different objectives (i), (ii), and (iii) under (a).

Theorem2. Any deterministic strategyproof mechanismdoes not have a finite approximation ratio for minimizing the three different objectives (i), (ii), and (iii) under (b).

Notice that [Marsh and Schilling, 1994] consider 20 groupfair objectives in total. However, using a similar technique as in the proof of Theorem 1, we can show that any deterministic strategyproof mechanism does not have a finite approximation ratio for all of the objectives mentioned in [Marsh and Schilling, 1994] except measure (1), which is the mtgc in our paper (we will explore this objective in Section 3.1). The main reason is that for the other objectives in [Marsh and Schilling, 1994] containing the form such as one group cost minus the other group cost (e.g., objective type (a) with function (i) we mentioned earlier), we can easily construct profiles similar to those in the proof of Theorem 1 where the optimal value is 0.

3 MechanismDesign for Group-Fair Objectives

In this section, we consider two group fair objectives, the maximum total group cost (mtgc) and the maximum average group cost (magc). First, we consider three classical strategyproof mechanisms proposed by [Procaccia and Tennenholtz, 2009], which are independent of group information.

Median Deterministic Mechanism (MDM). Given x1 ≤ x2 ≤ x3... ≤ xn, put the facility at y = x⌈ n2 ⌉.

Leftmost Deterministic Mechanism (LDM). Given x1 ≤ x2 ≤ x3... ≤ xn, put the facility at y = x1.

Randomized Mechanism (RM). Given x1 ≤ x2 ≤ x3... ≤ xn, put the facility at x1 with probability 1/4, xn with probability 1/4, x1+xn 2 with probability 1/2.

Because none of the three mechanisms above leverages group information, their strategyproofness still holds in our model. However, for some group-fair objectives, they might perform poorly. Thus, we propose the following deterministic and randomized mechanisms, which depend on group information, in which case strategyproofness is no longer obvious.

Majority Group Deterministic Mechanism (MGDM). Let g ∈ arg max1≤j≤m |Gj |, put facility y at the median of group Gg (break ties by choosing the smallest index).

Proposition 1. MGDM is strategyproof.

Our goal is to consider a facility's location that strikes a balance between unfairness across all of the groups while accounting for potential misreporting. While MGDM might focus on a group of the agents when locating a facility, it implicitly considers the unfairness induced by other groups of the agents given their preferences in our later approximation analyses. Without such a consideration, the mechanisms can perform badly and induce prohibitively high costs or unfairness for groups. Notice that we can alternatively consider other deterministic mechanisms such as choosing the median of all group median agents or choosing the median of another group, but they cannot guarantee strategyproofness or achieve better approximation ratios (i.e., counterexamples are given in the in the full version of the paper, https://arxiv.org/abs/2107.05175) for both objectives.

Narrow Randomized Mechanism (NRM). Let M be a set of median agents of all groups (choose the left one if there are two median agents in the group) and let ml = argmini∈M{xi} and mr = argmaxi∈M{xi}, put the facility at xml with probability 1/4, xmr with probability 1/4, and xml+xmr 2 with probability 1/2.

Proposition 2. NRM is strategyproof.

When designing the NRM, we observe that for any profile, the optimal solutions of both group-fair objectives are in [xml, xmr] since all group total (average) costs increase from xml to the left and from xmr to the right. Then putting the facility outside the interval we mentioned above with a certain probability will only hurt the mechanism's performance. Therefore, it would be better to design a randomized mechanism which only puts the facility in [xml, xmr]. Based on this fact, we use the same probabilities as RM to guarantee the strategyproofness, but use xml and xmr instead of x1 and xnto achieve better performance.

In the following subsections, we show the approximation ratios of these mechanisms and provide lower bounds for minimizing the two group-fair objectives.

3.1 MaximumTotal Group Cost

In this subsection, we focus on minimizing the maximum total group cost, Table 2 summaries the results.

We first provide upper bounds for the considered deterministic mechanisms discussed earlier. It turns out that existing mechanisms, MDM and LDM, do not perform well for the mtgc objective.

Proposition 3. MDM has an approximation ratio of Ω(m) for minimizing the mtgc.

Proposition 4. LDM has an approximation ratio of Ω(n) for minimizing the mtgc.

Next, we show that our mechanism, MGDM, that leverages group information has a good constant approximation ratio.

Theorem 3. MGDM has an approximation ratio of 3 for minimizing the mtgc.

Proof. Given any profile r, let y be the output of MGDM, y∗ be the optimal location and without loss of generality we assume that y < y∗ and mtgc(y, r) is achieved by Gg′ . Then from

By a simple transformation, we further have

Moreover, mtgc(y∗ , r) is at least 12 |Gg|(y∗ -y) because there are at least |Gg| 2 agents on the left side of y. Then we have the approximation ratio

In fact, the following example shows that the bound given in Theorem 3 is tight.

Example 1. Consider the case (see Figure 1) with one agent in group G1 at 0, one agent in group G1 at 2/3, and two agents in group G2 at 1. MGDM puts the facility at 0 achieving the mtgc of 2, but location 2/3 can achieve the optimal mtgc value 2/3. Hence, the approximation ratio of MGDM for the mtgc is at least 3.

To complement our upper bound results, we provide a lower bound for this objective.

Theorem 4. Any deterministic strategyproof mechanism has an approximation ratio of at least 2 for minimizing the mtgc.

Next, we investigate whether the considered randomized mechanisms can help to improve the approximation ratios. Unfortunately, these mechanisms do not performwell for this objective. For completeness, we provide a lower bound for any strategyproof randomized mechanisms.

Proposition 5. RMand NRMhave an approximation ratio of Ω(n) for minimizing the mtgc.

Theorem 5. There does not exist any strategyproof randomized mechanism with an approximation ratio less than 3/2 for minimizing the mtgc.

3.2 MaximumAverage Group Cost

In this subsection, we focus on minimizing the maximum average group cost, Table 3 summaries the results.

We first provide upper bounds for the considered deterministic mechanisms. Surprisingly, both MDM and MGDM give an approximation ratio of 3.

Theorem 6. MDM has an approximation ratio of 3 for minimizing the magc.

For LDM, we can reuse the proof of Proposition 4 since all agents are in the same group in the proof, minimizing the mtgc is equivalent to minimizing the magc.

Corollary 1. LDM has an approximation ratio of Ω(n) for minimizing the magc.

For MGDM, we can also use a similar argument as in the proof of Theorem 3 to show that MGDM can achieve an upper bound of 3 since for any profile r, there are at least half of the members who are in the largest group and on the left-hand side of the output of MGDM.

Corollary 2. MGDM has an approximation ratio of 3 for minimizing the magc.

Next, we investigate the lower bound. We can reuse the proof of Theorem 4 to show the same lower bound since there is only one agent in each group in the proof, minimizing the maximum average group cost is equivalent to minimizing the maximum total group cost.

Corollary 3. Any deterministic strategyproof mechanism has an approximation ratio of at least 2 for minimizing the magc.

We now investigate whether the considered randomized mechanisms can help to improve the approximation ratios. While the existing randomized mechanism does not, our mechanism, NRM, improves the approximation ratio to 2.

Proposition 6. RM has an approximation ratio of Ω(n) for minimizing the magc.

Theorem 7. NRM has an approximation ratio of 2 for minimizing the magc.

The following example shows that the bounds given in Theorem 6 and Theorem 7 are tight.

Example 2. Consider the case (see Figure 2) where k agents in group G1 are at 0, k - 1 agents in group G1 are at 2 3 , and one agent in group G2 is at 1. MDM puts the facility at 0 achieving the magc of 1, NRM puts the facility at 0 with probability 1/4, 1/2 with probability 1/2, 1 with probability 1/4, achieving the magc of 2/3, but the optimal solution puts the facility at 2/3 achieving the magc of 1/3.

Next, we provide a lower bound to complement our upper bound results. Note that we can reuse the argument as in the proof of Theorem 5, since each group has only one agent in the proof, minimizing the maximum cost is equivalent to minimizing the magc.

Corollary 4. There does not exist any strategyproof randomized mechanism with an approximation ratio less than 3/2 for minimizing the magc.

4 Intergroup and Intragroup Fairness

In this section, we investigate Intergroup and Intragroup Fairness (IIF), which not only captures fairness between groups but also fairness within groups. IIF is an important characteristic to be considered in the social science domain when studying fairness in group dynamics (see e.g., [Haslam et al., 2014]).

To facilitate our discussion, given group g, profile r and facility location y, let avgc(r, g, y) be the average cost of agents in g, maxc(r, g, y) be the maximum cost among agents in g, and minc(r, g, y) be the minimum cost among agents in g. We define below new group-fair IIF social objectives which measure both intergroup and intragroup fairness:

Using maxc(r, Gj , y) - minc(r, Gj , y) to measure intragroup fairness is well justified since this is the max-envy considered for one group in [Cai et al., 2016]. For IIF1, the intergroup fairness and the intragroup fairness are two separate indicators and they can be achieved by different groups, while for IIF2, we combine these two as one indicator of each group.

The reason we do not use the total group cost in this combined measure is that when the group size is large, the total cost is large but the maximum cost minus minimum cost is just the cost of one agent. Then the total cost will play a major role and intragroup fairness will be diluted, which goes against the purpose of the combined fairness measure. Moreover, since both the values of the average group cost and the max-envy are in [0, 1], we combine them directly without normalization.

Given the objectives, our goal is to minimize IIF1 or IIF2.

kth-Location Deterministic Mechanism (k-LDM). Given x1 ≤ x2 ≤ x3... ≤ xn, put the facility at y = xk (k = 1, 2, ..., n).

k-LDM can be seen as a class of mechanisms and LDM is one of them (k = 1). It is well known that putting the facility at the k-th agent's location is strategyproof. Thus we focus on the approximation ratios.

Theorem 8. For any 1 ≤ k ≤ n, k-LDM has an approximation ratio of 4 for minimizing IIF1 and IIF2.

Proof. First, we focus on IIF1. Let y∗ be the optimal location and we assume that y < y∗ without loss of generality. Then we prove that the approximation ratio

As Figure 3 shows, given any profile r and for each group j, we move all the agents to y∗ - maxc(r,Gj, y∗ ) if they are on the left of y, and to y∗ +maxc(r,Gj, y∗ ) if they are on the right of y. Then we will obtain a new profile r′ with the approximation ratio ρ′ . If we prove these movements do not make the optimal solution increase and do not make the mechanism solution decrease, namely ρ ≤ ρ′ , and further show that ρ′ ≤ 4, then we can obtain the approximation ratio of 4.

After the movements, maxc(r′ ,Gj, y∗ ) - minc(r′ ,Gj, y∗ ) = 0 and avgc(r′ ,Gj, y∗ ) = maxc(r,Gj, y∗ ) for all group Gj. Without loss of generality, suppose that maxj{avgc(r′ ,Gj, y∗ )} is achieved by group Gp. Then we have

which implies the optimal solution does not increase after the movements since maxc(r′ , Gj , y∗ )-minc(r′ , Gj , y∗ ) =

0. Moreover, because y is an agent location and there exists at least one agent on the left of or at y, we have maxc(r′ , p, y∗ ) ≥ y∗ - y.

For the mechanism solution, neither of maxj{avgc(r,Gj, y)} and maxj {maxc(r,Gj, y)} decreases if r changes to r′ since no agent moves closer to y.

Therefore, the approximation ratio ρ′ is at most

For IIF2, we can use a similar argument as IIF1 since it only focuses on group p and all inequalities are also valid under this objective.

Next, we provide lower bounds for the IIF objectives.

Theorem 9. Any deterministic strategyproof mechanism has an approximation ratio of at least 4 for minimizing IIF1 and IIF2.

It is interesting to see that when one only considers intragroup fairness, only the additive approximation is possible. When we combine it with intergroup fairness, a tight multiplicative approximation can be obtained for IIF1 and IIF2.

5 Conclusion

We study the problem of designing strategyproof mechanisms in group-fair facility location problems (FLPs), where agents are in different groups, under several well-motivated groupfair objectives. We first show that not all group-fair objectives admit a bounded approximation ratio. Then we give the complete results of three classical mechanisms and two new mechanisms for minimizing two group-fair objectives, and we show that it is possible to design strategyproof mechanisms with constant approximation ratios that leverage group information. We also introduce Intergroup and Intragroup Fairness (IIF), which takes both fairness between groups and within each group into consideration. We study two natural IIF objectives and provide a mechanism that achieves a tight approximation ratio for both objectives.

Naturally, there are many potential future directions for the group-fair FLPs in mechanism design. For the group-fair FLPs under the considered group-fair objectives, an immediate direction is to tighten the gaps between the lower and upper bounds of our results. Moreover, one can consider alternative group-fair objectives that are appropriate for specific application domains.