Strategy Proof Mechanisms for Facility Location with Capacity Limits

The facility location problem is a classic problem in social choice that has attracted attention from researchers in several fields including AI, Operations Research, and Game Theory (e.g. (Drezner and Hamacher 2002; Lu et al. 2010; Fotakis and Tzamos 2010; Escoffier et al. 2011; Procaccia and Tennenholtz 2013; Serafino and Ventre 2015; Feigenbaum and Sethuraman 2015; Golowich, Narasimhan, and Parkes 2018; Jagtenberg and Mason 2020)). Our goal here is to design mechanisms to locate one or more facilities fairly and optimally to serve a set of agents. The locations of the agents are privately known to the agents themselves. We therefore wish to identify strategy proof mechanisms that are likely to elicit the true locations of the agents and minimize the total or maximum distance of the agents from the facilities serving them. Facility location problems model many real world problems including locating schools, hospitals, warehouses, and libraries. In many of these problems, facilities have capacity limits (Brimberg et al. 2001; Aziz et al. 2019, 2020). A school has only places for a certain number of students, a warehouse can only serve a given number of shops, a hospital has only a limited number of beds, etc. Our contribution is to demonstrate that such capacity constraints can make it harder to design strategy proof mechanisms, but paradoxically can increase the welfare of the solutions that we are guaranteed to return.

As in much previous work on mechanism design for facility location (e.g. (Procaccia and Tennenholtz 2013)), we consider the one-dimensional setting. This models a number of real world problems such as locating wastewater plants along a river, or warehouses along a highway. There are also various non-geographical settings that can be viewed as one-dimensional facility location problems (e.g. choosing the temperature for a classroom, or selecting a committee to represent people with different political views). In addition, there are settings where we can use the one-dimensional problem to solve more complex problems (e.g. decomposing the 2-d rectilinear problem into a pair of 1-d problems). Finally, the one-dimensional problem is the starting point to consider more complex metrics (e.g., trees and networks) and provides bounds on solutions for these more complex settings (e.g. lower bounds for the 1-d problem provide lower bounds for the 2-d problem).

We have $n$ agents located on the real line, and wish to locate $m$ facilities on the real line to serve all the agents. Each agent $i$ is at location $x_{i}$. We suppose agents are ordered so that $x_{1}\leq\ldots\leq x_{n}$. In the uncapacitated setting, an agent is served by the nearest facility, and a solution is a location $y_{j}$ for each facility $j$. In the capacitated setting, the $j$th facility can serve up to $c_{j}$ agents. We assume that $\sum_{j=1}^{m}c_{j}\geq n$ so that every agent can be served. One special setting we consider is when there is no spare capacity (i.e. $\sum_{j=1}^{m}c_{j}=n$). Another special setting we consider is when facilities are identical (i.e. $c_{i}=c_{j}$ for all $i<j)$. A solution in the capacitated setting is both a location $y_{j}$ for each facility $j$, and an assignment of agents to facilities such that the capacity limit $c_{j}$ for each facility is not exceeded. Let $a_{i}\in[1,m]$ denote the facility serving agent $i$, and $N_{j}$ denote the set of agents assigned to facility $j$, i.e., $N_{j}=\{i|a_{i}=j\}$. Then the capacity constraints in the capacitated setting ensure $|N_{j}|\leq c_{j}$ for all $j\in[1,m]$. We consider an utilitarian objective of the total distance, $\sum_{i=1}^{n}|x_{i}-y_{a_{i}}|$ and an egalitarian objective of the maximum distance, $\mbox{\rm max}_{i=1}^{n}|x_{i}-y_{a_{i}}|$. Our goal is to minimize one of these two welfare objectives.

We consider a number of mechanisms for the uncapacitated facility location problem. With parameters $p_{1}$ to $p_{m}$ with $0\leq p_{1}\leq\ldots\leq p_{m}\leq 1$, the Percentile mechanism locates facility $j$ at $x_{1+\lfloor p_{j}(n-1)\rfloor}$ for $j\in[1,m]$. For example, the Leftmost  mechanism has $m=1$ and $p_{1}=0$, while the Median mechanism has $m=1$ and $p_{1}=\frac{1}{2}$. The EndPoint mechanism which locates facilities at the left and rightmost agents has $m=2$, $p_{1}=0$ and $p_{2}=1$. The $j$Left$k$Right mechanism locates $j$ facilities at the leftmost $j$ distinct locations of the agents, and $k$ facilities at the rightmost $k$ distinct locations. If agents declare less than $j+k$ distinct locations, the mechanism puts multiple facilities at a location. The EndPoint mechanism is the $j$Left$k$Right mechanism with $j=k=1$, the TwoLeftPeaks mechanism has $j=2$ and $k=0$, the TwoRightPeaks mechanism has $j=0$ and $k=2$, the ThreeLeftPeaks mechanism has $j=3$ and $k=0$, and the ThreeRightPeaks mechanism has $j=0$ and $k=3$.

We also consider a number of mechanisms for the capacitated problem. For two capacitated facilities, the InnerPoint mechanism locates one facility at $x_{c_{1}}$ serving the leftmost $c_{1}$ agents, and the other facility at $x_{1+c_{1}}$ serving the remaining agents. The ExtendedEndPoint mechanism is an extension of the EndPoint mechanism to deal with capacity limits that retains strategy proofness. It was first proposed in (Aziz et al. 2020). It can deal with facilities of different capacity, as well as with spare capacity. It is defined formally as follows.

Let $f_{1}$ and $f_{2}$ be the output locations of the two facilities. Define $X_{1}=\{i|x_{i}-x_{1}\leq\frac{1}{2}(x_{n}-x_{1})\}$ and $X_{2}=\{i|x_{n}-x_{i}<\frac{1}{2}(x_{n}-x_{1})\}$. If $|X_{1}|\geq|X_{2}|$, execute one of the following three cases.

Case 1.

If $|X_{1}|\leq c_{1}$ and $|X_{2}|\leq c_{2}$, $f_{1}=x_{1}$ and $f_{2}=x_{n}$. Agents in $X_{1}$ are allocated to $f_{1}$ and the others are allocated to $f_{2}$ as in the EndPoint mechanism.

Case 2.

If $|X_{1}|>c_{1}$ and $|X_{2}|\leq c_{2}$, $f_{1}=2x_{c_{1}+1}-x_{n}$ and $f_{2}=x_{n}$. Agents $\{1,\cdots,c_{1}\}$ are allocated to $f_{1}$ and the others are allocated to $f_{2}$.

Case 3.

If $|X_{1}|\leq c_{1}$ and $|X_{2}|>c_{2}$, $f_{1}=x_{1}$ and $f_{2}=2x_{n-c_{2}}-x_{1}$. Agents in $\{1,\cdots,n-c_{2}\}$ are allocated to $f_{1}$ and the others are allocated to $f_{2}$.

If $|X_{1}|<|X_{2}|$, switch the roles of the two facilities in above cases and execute one of them.

We extend the Percentile and $j$Left$k$Right mechanisms to the capacitated setting by allocating agents left to right to facilities ordered left to right up by their capacity.

We consider three desirable properties of mechanisms for facility location problems: anonymity, Pareto optimality and strategy proofness. Anonymity is a fundamental fairness property that requires all agents to be treated alike. Pareto optimality is one of the most fundamental normative properties in economics. It demands that we cannot improve the solution so one agent is better off without other agents being worse off. Finally, strategy proofness is a fundamental game theoretic property that ensures agents have no incentive to act strategically and try to manipulate the mechanisms.

More fomally, a mechanism is anonymous iff permuting the agents does not change the solution. For instance, the Median mechanism is anonymous. A mechanism is Pareto optimal iff it returns solutions that are always Pareto optimal. A solution is Pareto optimal iff there is no other solution in which one agent travels a strictly shorter distance to the facility serving them, and all other agents travel no greater distance. For example, the Median mechanism is Pareto optimal. A mechanism is strategy proof iff no agent can mis-report and reduce their distance to travel to the facility serving them. For example, the Median mechanism is strategy proof.

Finally, we wil consider strategy proof mechanisms that may not return the optimal solution. In particular, we will consider how well a mechanism approximates the optimal possible welfare. A mechanism achieves an approximation ratio $\rho$ of the total (maximum) distance iff the total (maximum) distance in any solution it returns is at most $\rho$ times the optimal. In this case, we say that the mechanism $\rho$-approximates the optimal total (maximum) distance. For example, the Leftmost mechanism 2-approximates the optimal maximum distance (Theorem 2.1 in (Procaccia and Tennenholtz 2013)).

We begin by summarizing some existing results about strategy proof mechanisms for the uncapacitated facility location problem, and by filling in a few small gaps in the literature. This summary of uncapacitated results will serve as a baseline to compare against when we add capacity constraints.

Since we suppose facilities have enough capacity to serve all agents, the first non-trivial capacitated case to consider is two facilities. Capacity constraints can make strategy proofness harder to achieve even in this simplest of settings. For instance, the EndPoint mechanism stops being strategy proof when we add capacity limits. In fact, the only Percentile mechanism that remains strategy proof with the addition of capacity constraints is the InnerPoint mechanism (Theorem 9 of (Aziz et al. 2020)).

Supposing we have two identical facilities with no spare capacity, we now prove that the InnerPoint mechanism is in fact the only mechanism that is anonymous, Pareto optimal and strategy proof. We contrast this strong characterization result with the uncapacitated problem where there are multiple mechanisms for locating two uncapacitated facilities that are anonymous, Pareto optimal and strategy proof (e.g. the TwoLeftPeaks or EndPoint mechanisms).

In the base case, $k=1$. There are two subcases. In the first subcase, we have just two agents and two facilities of capacity 1. The unique Pareto optimal solution locates a facility at the location of each agent. A mechanism that does this is a strategy proof and anonymous. This is also the solution return by the InnerPoint  mechanism. In the second subcase, we have three agents, a facility of capacity 1 on the left and a facility of capacity 2 on the right. Suppose the three agents are at $x_{1}\leq x_{2}\leq x_{3}$. The Pareto optimal solution set puts the smaller facility at $x_{1}$ serving the leftmost agent and the larger facility somewhere in the interval $[x_{2},x_{3}]$ serving the other two agents. Now move the agent at $x_{3}$ to $x_{2}$. The unique Pareto optimal solution puts the smaller facility at $x_{1}$ serving the leftmost agent and the larger facility at $x_{2}$ serving the two agents there. We next move the rightmost agent from $x_{2}$ back towards its original position at $x_{3}$. Let $x$ be the distance of the rightmost agent from $x_{2}$ so that $x$ varies from 0 to $x_{3}-x_{2}$, and $f(x)$ be the distance of the rightmost agent from the facility serving them. It is not hard to show that since the mechanism is strategy proof, $f(x)$ must be a continuous function of $x$. Any discontinuity would give the rightmost agent an opportunity to mis-report their location strategically and travel less distance. The location of the rightmost facility therefore tracks continuously to the right, staying within the interval $[x_{2},x_{2}+x]$ to ensure Pareto optimality. There are four scenarios for where the mechanism locates the rightmost facility as we vary $x$: (a) the larger facility remains at $x_{2}$ as with the InnerPoint mechanism, (b) the larger facility remains at $x_{2}+x$, (c) the larger facility tracks $x_{2}+x$ until some $x^{\prime}$ with $x_{2}+x^{\prime}<x_{3}$ after which the location of the larger facility remains static or (d) the larger facility at some point tracks behind and is strictly between $x_{2}$ and $x_{2}+x$. Note that the larger facility cannot track in front of $x_{2}+x$ as this would not be Pareto optimal. In case (b), consider $x_{1}=\frac{1}{5}$, $x_{2}=\frac{2}{5}$, $x_{3}=1$ and $x=\frac{3}{5}$. Then the middle agent at $x_{2}$ can profitably misreport their location as $0$. The leftmost facility will then be located at 0 serving the middle agent. The distance the middle agent travels to be served thereby decreases from $\frac{3}{5}$ to $\frac{2}{5}$ violating the assumption that the mechanism is strategy proof. In case (c), suppose $x_{1}=\frac{x}{2}$, $x_{2}=x$ then the agent at $x_{2}$ can profitably misreport their location as $\frac{x}{2}$, contradicting the assumption that the mechanism is strategy proof. In case (d), the larger facility tracks strictly behind $x_{2}+x$. By continuity arguments, we can identify two values, $x=a$ and $x=b$ with $a<b$ such that when the rightmost agent is at $x_{2}+b$, the rightmost facility is located at $x_{2}+a$, and when the rightmost agent is at $x_{2}+a$, the rightmost facility is located at $x_{2}+c$ where $c<a$. Then if agents are at $x_{1}$, $x_{2}$ and $x_{2}+a$, the rightmost agent at $x_{2}+a$ can profitably misreport their location as $x_{2}+b$. This violates the assumption that the mechanism is strategy proof. Therefore the only case that does not lead to a contradiction is case (a). That is, the mechanism acts like the InnerPoint mechanism.

In the step case, we suppose that the only anonymous, Pareto optimal and strategy proof mechanism for $2k$ agents and two facilities of capacity $k$, or for $2k+1$ agents and a facility of capacity $k$ on the left and a facility of capacity $k+1$ on the right is the InnerPoint mechanism. We need to prove two subcases: the first subcase of $2k+2$ agents and two facilities of capacity $k+1$, and the second subcase of $2k+3$ agents and a facility of capacity $k+1$ on the left and a facility of capacity $k+2$ on the right. We consider the first subcase. Suppose the $2k+2$ agents are at $x_{1}\leq x_{2}\leq\ldots\leq x_{2k}\leq x_{2k+1}\leq x_{2k+2}$. We move the leftmost agent at $x_{1}$ to 0 and suppose it is fixed and served by the leftmost facility. We now have a facility location problem with $2k+1$ agents, and a facility of capacity $k$ on left and $k+1$ on the right. By the induction hypothesis, the only anonymous, Pareto optimal and strategy proof mechanism is the InnerPoint mechanism that locates one facility at $x_{k+1}$ serving agents located in the interval $[x_{2},x_{k+1}]$, and the other facility at $x_{k+2}$ serving the remaining agents. We next move the leftmost agent from 0 back to $x_{1}$. By similar continuity arguments used in the base case, the leftmost facility must remain at $x_{k+1}$. Continuity arguments also prevent the rightmost facility moving away from $x_{k+2}$ or for agents switching facility when $x_{k+2}>x_{k+1}$ as such a switch changes the distances traveled. If $x_{k+2}=x_{k+1}$ we don’t care which facility serves which agent as the two facilities are co-located and switching is irrelevant. Hence, with the leftmost agent back at $x_{1}$, the solution is that returned by the InnerPoint mechanism.

This leaves the final subcase of $2k+3$ agents and a facility of capacity $k+1$ on the left and a facility of capacity $k+2$ on the right. Suppose the agents are at $x_{1}\leq x_{2}\leq\ldots\leq x_{2k}\leq x_{2k+1}\leq x_{2k+2}\leq x_{2k+3}$. We move the rightmost agent at $x_{2k+3}$ to 1 and suppose it is fixed and served by the rightmost facility. We now have a facility location problem with $2k+2$ agents, and two facilities of capacity $k+1$. By the previous case, the only anonymous, Pareto optimal and strategy proof mechanism for such a setting is the InnerPoint mechanism that locates one facility at $x_{k+1}$ serving agents located in the interval $[x_{1},x_{k+1}]$, and the other facility at $x_{k+2}$ serving the remaining agents. We next move the rightmost agent from 1 back to $x_{2k+3}$. By similar continuity arguments, the rightmost facility must remain at $x_{k+2}$. Continuity arguments also prevent the leftmost facility moving away from $x_{k+1}$ or for agents to switch facility when $x_{k+2}>x_{k+1}$ and such a switch changes the distances traveled. Hence, with the rightmost agent back at $x_{2k+3}$, the solution is that returned by the InnerPoint mechanism. $\diamond$

It follows immediately that the InnerPoint mechanism is the unique Percentile mechanism that is Pareto optimal. We next consider dropping in turn one of anonymity, Pareto optimality and strategy proofness. If we drop anonymity, then there are multiple other mechanisms besides the InnerPoint mechanism that are Pareto optimal and strategy proof but not anonymous. For example, the CapSD mechanism is a modified serial dictator mechanism for locating capacitated facilities that is Pareto optimal and strategy proof but not anonymous.

If we drop Pareto optimality, there are multiple mechanisms besides the InnerPoint mechanism that are anonymous and strategy proof but not Pareto optimal (e.g. any Percentile  mechanism with $p_{1}=p_{2}$). And if we drop strategy proofness, there are multiple mechanisms besides the InnerPoint mechanism that are anonymous and Pareto optimal but not strategy proof (e.g. the EndPoint and TwoRightPeaks mechanisms). Hence, anonymity, Pareto optimality and strategy proofness are the minimal combination of axioms characterizing the InnerPoint mechanism.

If we increase the number of facilities, strategy proofness and Pareto optimality become harder to achieve simultaneously. In fact, even in the restricted setting of just three capacitated facilities of equal size but no spare capacity, no mechanism can be simultaneously anonymous, Pareto optimal and strategy proof. We again contrast this with the uncapacitated problem where there are multiple mechanisms for locating three uncapacitated facilities that are anonymous, Pareto optimal and strategy proof (e.g. the ThreeLeftPeaks and ThreeRightPeaks mechanisms). The following strong impossibility theorem demonstrates that capacity limits make it impossible to achieve anonymity, Pareto optimality and strategy proofness with three or more facilities.

Suppose now the agents at 0 are fixed, but the other four agents are allowed to vary. Then we effectively have a two facility, four agent mechanism acting on the agents at 10, 11 and two at 20 which locates the two rightmost facilities, while the leftmost facility remains at 0. By Theorem 4, the only anonymous, Pareto optimal and strategy proof mechanism for locating two facilities is the InnerPoint mechanism. This locates the two rightmost facilities at 11 and 20. Suppose now that the agents at 20 are fixed, but the other four agents are allowed to vary. Then we again effectively have a two facility, four agent mechanism acting on agents at 10, 11 and two at 0 which locates the two leftmost facilities, while the rightmost facility remains at 20. By Theorem 4, this must be the InnerPoint mechanism which locates the two leftmost facilities at 0 and 10. This is a contradiction as the middle facility cannot simultaneously by at position 10 and 11. Therefore our assumption that there is an anonymous, Pareto optimal and strategy proof mechanism for three capacitated facilities must be incorrect. $\diamond$

It follows immediately that no Percentile mechanism for locating three or more capacitated facilities is Pareto optimal. If we drop anonymity, there are multiple mechanisms that are Pareto optimal and strategy proof (e.g. any CapaSD mechanism). Similarly, if we drop Pareto optimality, there are multiple mechanisms that are anonymous and strategy proof (e.g. any Percentile  mechanism with $p_{1}=p_{2}=p_{3}$). And if we drop strategy proofness, there are multiple mechanisms that are anonymous and Pareto optimal (e.g. ThreeLeftPeaks, and ThreeRightPeaks mechanisms). Hence, anonymity, Pareto optimality and strategy proofness are a minimal combination of incompatible axioms for locating three or more capacitated facilities.

We next consider the impact of capacity constraints on the ability of strategy proof mechanisms to approximate the optimal solution. With no spare capacity, we can give a tight lower bound on the approximation ratio for the total distance. No deterministic and strategy proof mechanism can do better than this bound.

With two identical facilities of capacity $k$ and no spare capacity, the InnerPoint mechanism has an approximation ratio for the total cost of at most $k-1$ (Theorem 5 in (Aziz et al. 2020)). Hence, the InnerPoint mechanism is optimal. No other deterministic and strategy proof mechanism can have a better approximation ratio. We contrast this with the uncapacitated setting where the lower bound for any deterministic and strategy proof mechanism is $n-2$ which is nearly twice as big (Corollary 3.2 in (Fotakis and Tzamos 2013)). Counter-intuitively adding capacity constraints improves the guarantee on the approximation of the optimal solution.

We also prove a tight lower bound on the approximation ratio for the maximum distance. No deterministic and strategy proof mechanism can do better than this bound. Interestingly, this is the same lower bound as in the uncapacitated setting.

As the InnerPoint mechanism achieves an approximation ratio of at most 2 (Aziz et al. 2020), it is optimal. No deterministic and strategy proof mechanism is guaranteed to return better quality solutions. It is perhaps surprising that, with two capacitated facilities, we can approximate the maximum distance so well. For the more relaxed problem of approximating the maximum distance with a single uncapacitated facility, the best possible deterministic and strategy proof mechanism already has an approximation ratio of 2. Despite complicating the problem with an additional facility, and with capacity limits, we can still do just as well.

So far, we have supposed that there is no spare capacity in the problem. We now relax this assumption. We observe that this can make Pareto optimality and strategy proofness harder to achieve simultaneously even with just two facilities.

Note that if the spare capacity is sufficiently large then there are mechanisms that are anonymous, Pareto optimal and strategy proof. For example, when the spare capacity is $m(c-1)$, we have only $m$ agents for the $m$ facilities. We can then simply locate a facility at each agent. Another edge case is three agents and two facilities of capacity 2. Consider the mechanism that locates one facility at the leftmost agent, the other at the rightmost agent, and allocates the middle agent to whichever facility is nearest. This mechanism is anonymous, Pareto optimal and strategy proof

Note also that if we drop anonymity, there are multiple mechanisms that are Pareto optimal and strategy proof despite the presecne of spare capacity (e.g. any CapSD mechanism). Similarly, if we drop Pareto optimality, there are multiple mechanisms that are anonymous and strategy proof despite the presence of spare capacity (e.g. any Percentile  mechanism with $p_{1}=p_{2}=p_{3}$). And if we drop strategy proofness, there are multiple mechanisms that are anonymous and Pareto optimal despite the presence of spare capacity (e.g. TwoLeftPeaks, and TwoRightPeaks mechanisms). Hence, anonymity, Pareto optimality and strategy proofness are a minimal combination of incompatible axioms in the presence of spare capacity.

Counter-intuitively, when we introduce spare capacity, the lower bound on approximating the optimal total distance increases. More capacity means we may have a less good approximation of the optimal solution. More precisely, increasing the spare capacity increases the lower bound on the optimal total distance linearly from $\frac{n}{2}-1$ to $n-2$. Eventually and unsurprisingly it matches the lower bound of $n-2$ seen in the uncapacitated setting (Corollary 3.2 in (Fotakis and Tzamos 2013)). Note that we cannot directly apply lower bounds from the uncapacitated setting to our capacitated problem as the space of mechanisms in the capacitated setting is imposing and thus different to that in the uncapacitated setting (Fotakis and Tzamos 2010). In the capacitated setting, we force an agent to be served by a particular facility (an “imposing” mechanism) while in the uncapacitated setting agents can visit whichever facility is nearest their true location.

For two facilities of capacity $n-1$ or greater, the EndPoint mechanism (which locates a facility at the leftmost and rightmost locations serving whichever agents are nearest) achieves this lower bound and so is optimal. No other deterministic and strategy proof mechanism can have a better approximation ratio for the total distance. We see therefore that increasing the spare capacity turns the problem inside out – the optimal mechanism goes from the InnerPoint mechanism that locates facilities on the inside around the median agents when there is no spare capacity to the EndPoint mechanism that locates facilities at the end points of the reported locations when there is a large amount of spare capacity. It follows immediately that the ExtendedEndPoint mechanism, which has an approximation ratio for the total distance of $\frac{3n}{2}$ (Theorem 11 in (Aziz et al. 2020)), is asymptotically optimal. It is an interesting open question to close the gap between $n-k-1$ and $\frac{3n}{2}$.

For the maximum distance, we can easily adjust the proof of Theorem 7 to show that, even with spare capacity, the approximation ratio for the maximum distance is again at least 2. It immediately follows that the ExtendedEndPoint mechanism, which achieves an approximation ratio of $4$ (Theorem 12 in (Aziz et al. 2020)), is asymptotically optimal. It is also an interesting open question to close the gap between $2$ and $4$.

So far, we have supposed that all facilities have the same capacity. What happens if facilities can have different capacity to each other? We will show that unsurprisingly this can make it harder to achieve Pareto optimality and strategy proofness simultaneously. For instance, with two facilities of different capacities, there is no anonymous, Pareto optimal and strategy proof mechanism.

An edge case is when we have two facilities and one has just capacity for a single agent. More generally, suppose we have $m+1$ agents, one facility of capacity $m$ and the other of capacity 1 where $m>1$. Consider the mechanism that locates the largest facility at the leftmost agent, and the other at the rightmost agent when the $m$th agent from the left is nearer the leftmost agent, and otherwise locates the largest facility at the rightmost agent and the other facility at the leftmost agent. Agents are allocated to the nearest facility. This mechanism is anonymous, strategy proof and Pareto optimal.

Note also that if we drop anonymity, there are multiple mechanisms that are Pareto optimal and strategy proof despite the presence of facilities of unequal capacity (e.g. any CapSD mechanism). Similarly, if we drop Pareto optimality, there are multiple mechanisms that are anonymous and strategy proof despite the presence of facilities of unequal capacity (e.g. any Percentile  mechanism with $p_{1}=p_{2}=p_{3}$). And if we drop strategy proofness, there are multiple mechanisms that are anonymous and Pareto optimal despite the presecne of facilities of unequal capacity (e.g. TwoLeftPeaks, and TwoRightPeaks mechanisms). Hence, anonymity, Pareto optimality and strategy proofness are a minimal combination of incompatible axioms when facilities can have different capacity.

As might be expected, the more equal the capacity of the different facilities, the better the guarantee on the approximability of the optimal solution.

It again immediately follows from this result that the ExtendedEndPoint mechanism, which achieves an approximation ratio of $\frac{3n}{2}$ (Theorem 11 in (Aziz et al. 2020)) with facilities of different capacities, is asymptotically optimal. It is an interesting open problem to close the gap between the upper and lower bounds.

For the maximum distance, we can easily adjust the proof of Theorem 7 to show that, even with facilities of different capacities, the approximation ratio for the maximum distance is at least 2. It follows that the ExtendedEndPoint mechanism, which achieves an approximation ratio of $4$ (Theorem 12 in (Aziz et al. 2020)), is asymptotically optimal. It is again an interesting open problem to close the gap between the upper and lower bounds.

We have studied the impact of capacity constraints on mechanisms for facility location considering three important axiomatic properties: anonymity which is a fundamental fairness property, Pareto optimality which is a fundamental efficiency property, and strategy proofness which is a fundamental property about incentives to report sincerely. As a baseline, we began by surveying what is known about strategy proof mechanisms without capacity limits. For example, we identified those mechanisms for locating one or two uncapacitated facilities with bounded (in fact optimal) approximation ratios for the total and maximum distance. In addition, we filled a small gap in the literature by proving that, with three or more uncapacitated facilities, the only deterministic, anonymous and strategy proof mechanism with a bounded approximation ratio for the maximum distance is the EndPoint mechanism.

Our main contribution, however, is in the design of strategy proof mechanism for locating facilites with capacity limits on the number of agents that can be served. We provided a comprehensive characterization of the anonymous, Pareto optimal and strategy proof mechanisms for locating capacitated facilities. We also identified tight bounds on how well such mechanisms can approximate the optimal total or maximum distance. In general, and as might be expected, capacity constraints make it more difficult to design strategy proof mechanisms for facility locations. However, a little unexpectedly, capacity constraints can result in better guarantees on the quality of the approximate solutions returned.

There are many directions for future work. For example, randomization is a useful tool to enable mechanisms to ensure desirable axiomatic properties like anonymity and strategy proofness. It would therefore be interesting to extend our analysis from purely deterministic to randomized mechanisms for capacitated facility location. As a second example, many problems are not one dimensional. Can we extend these results to trees, networks, and two-dimensional rectilinear or Euclidean metrics? As a third example, there is a dual class of obnoxious facility location problems where agents wish to be as far as possible from the facility such as a rubbish dump, nuclear power station, or prison. There are also mixed facility location problems where some agents wish to be close to the facility and others far away such as a playground or cell phone tower. It would be interesting to consider the impact of capacity constraints on such problems.