--- title: "Strategy Proof Mechanisms for Facility Location with Capacity Limits" authors: - "Toby Walsh" doi: "10.24963/ijcai.2022/75" url: "https://ijcai.org/proceedings/2022/75" pdf: "https://ijcai.org/proceedings/2022/0075.pdf" venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence" year: 2022 pages: "527-533" track: "Main Track" keywords: - "Agent-based and Multi-agent Systems: Computational Social Choice" - "Agent-based and Multi-agent Systems: Mechanism Design" --- # Strategy Proof Mechanisms for Facility Location with Capacity Limits Toby Walsh *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 527-533. DOI: [10.24963/ijcai.2022/75](https://doi.org/10.24963/ijcai.2022/75) ## Abstract An important feature of many real world facility location problems are capacity limits on the number of agents served by each facility. We provide a comprehensive picture of strategy proof mechanisms for facility location problems with capacity constraints that are anonymous and Pareto optimal. First, we prove a strong characterization theorem. For locating two identical facilities with capacity limits and no spare capacity, the INNERPOINT mechanism is the unique strategy proof mechanism that is both anonymous and Pareto optimal. Second, when there is spare capacity, we identify a more general class of strategy proof mechanisms that interpolates smoothly between INNERPOINT and ENDPOINT which are anonymous and Pareto optimal. Third, with two facilities of different capacities, we prove a strong impossibility theorem that no mechanism can be both anonymous and Pareto optimal except when the capacities differ by just a single agent. Fourth, with three or more facilities we prove a second impossibility theorem that no mechanism can be both anonymous and Pareto optimal even when facilities have equal capacity. Our characterization and impossibility results are all minimal as multiple mechanisms exist if we drop one property. ## Full text ## 1 Introduction In facility location, we decide where to locate one or more facilities to serve a set of agents. This models geographical problems such as locating schools, mobile phone masts and sewage plants, and non-geographical problems such as deciding the budget for a communal purchase, or selecting the "best" products in a multi-dimensional parameter space. As in previous work (e.g. [Fotakis and Tzamos, 2010; Procaccia and Tennenholtz, 2013; Serafino and Ventre, 2015; Sui and Boutilier, 2015; Golowich et al., 2018; Mei et al., 2016; Procaccia et al., 2018; Aziz et al., 2021]), our goal is to design mechanisms to locate the facilities fairly and efficiently. The locations of the agents is private information. We therefore wish to identify strategy proof mechanisms where agents have no incentive to mis-report their location, which optimize or, at least, approximate an objective such as the total or maximum distance of agents from the facilities. For example, when buying a communal coffee machine, can we design a mechanism for fairly deciding the cost so that agents have no incentive to mis-report their preferred spend? ∗ Supported by ARC Laureate project FL200100204. In many real world problems, facilities have capacity limits. 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, each committee member can only represent a small number of constituents, a maximum number of people can use the purchased coffee machine etc. Previous work on mechanisms for facility location problems have largely ignored such capacity constraints. There are two notable exceptions. Aziz et al. [2019] consider such capacity constraints but, unlike here, consider a setting where there may be more agents than the total capacity of facilities. We consider a setting first considered by Aziz et al. [2020] in which the total capacity permits every agent to be served. We extend this work by characterizing those strategy proof mechanisms for facility location with capacity limits which are anonymous and Pareto optimal. See Tables 1 and 2 for a summary of our results. ## 2 Formal Background As in much previous work on mechanism design for facility location (e.g. [Procaccia and Tennenholtz, 2013]), we consider the one-dimensional setting where agents are located along a line. This models a number of real world problems such as locating wastewater plants along a river, warehouses along a highway, or bus stops along a road. There are also various non-geographical settings that can be viewed as onedimensional facility location problems (e.g. deciding the budget for a communal coffee machine, selecting 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 two-dimensional rectilinear problem into a pair of one-dimensional problems). Finally, the one-dimensional problem is the starting point to consider more complex metrics (e.g., trees, networks or twodimensional Euclidean space) and provides insights into these more complex settings. For example, our proof that no strategy proof mechanism exists for the one-dimensional problem with facilities of different capacity that is both anonymous and Pareto optimal can be easily extended to show that no such mechanism exists for such facility location problems in two-dimensional Euclidean space - we simply need to consider agents restricted to an one-dimensional line. Table 1: Summary of known and new results proved here about existence of strategy proof mechanisms for facility location with and without capacity limits that are anonymous and Pareto optimal. | | no capacity limits | equal capacity, no spare capacity | equal capacity, spare capacity | unit capacity difference | non-unit difference | |----------------|-----------------------------|-------------------------------------|----------------------------------|----------------------------|-----------------------| | 2 facilities | ENDPOINT, 2LEFTPEAK, . . . | INNERPOINT | INNERGAP | INNERCHOICE | impossible | | 3 facilities | 3LEFTPEAK, 3RIGHTPEAK,. . . | impossible | impossible | impossible | impossible | | > 3 facilities | 4LEFTPEAK, 5RIGHTPEAK,. . . | impossible | impossible | impossible | impossible | Table 2: Summary of results about existence of mechanisms for facility location problems with capacity limits satisfying either all or two of anonymity (Anon), Pareto optimality (PO) and strategy proofness (SP) in the setting of facilities of equal capacity and no spare capacity. | | Anon, PO, SP | ¬Anon, PO, SP | Anon, ¬PO, SP | Anon, PO, ¬SP | |---------------------------|-----------------------|-------------------------------------|-----------------------------------------------|-------------------------------------------| | 2 facilities 3 facilities | INNERPOINT impossible | SD⋆ family, . . . SD⋆ family, . . . | FIXED, MIDPOINT, . . . FIXED, MIDPOINT, . . . | ENDPOINT⋆ , 2LEFTPEAK⋆ , . . . impossible | | > 3 facilities | impossible | SD⋆ family, . . . | FIXED, MIDPOINT, . . . | impossible | We have n agents located on the interval [0, 1] and wish to locate m facilities in this interval to serve all the agents. Each agent i is at location xi. We suppose agents are ordered so that x1 ≤ . . . ≤ xn. The jth facility can serve up to cj agents. We assume that ∑mj=1 cj ≥ n so that every agent can be served. One special setting we consider is when there is no spare capacity (i.e. ∑mj=1 cj = n). Another special setting we consider is when facilities are identical (i.e. ci = cj for all i < j). A solution is both a location yj for each facility j, and an allocation of agent i to facility ai such that the capacity limit cj for each facility is not exceeded. Note that, unlike the more traditional uncapacitated problem, an agent may not be served by the nearest facility. This is an important difference that, as we shall see, drastically changes the space of possible strategy proof mechanisms. Let Nj denote the set of agents allocated to facility j, i.e., Nj = {i|ai = j}. Then the capacity constraints ensure |Nj| ≤ cj for all j ∈ [1,m]. ## 3 CapacitatedMechanisms We consider deterministic mechanisms for locating capacitated facilities. We focus on two families of mechanisms with good normative properties. The two families have previously been proposed for uncapacitated facility location. For example, PERCENTILE mechanisms without capacity limits are defined in [Sui et al., 2013]. We generalize such mechanisms to deal with capacity limits. Both families of mechanisms order facilities left to right in increasing capacity, and allocate agents left to right to the nearest facility with spare capacity, tie-breaking to the leftmost facility. PERCENTILE: With parameters p1 to pm with 0 ≤ p1 ≤ . . . ≤ pm ≤ 1, a member of this family of mechanisms locates facility j at x1+⌊pj(n-1)⌋ for j ∈ [1,m]. The ENDPOINT mechanism has m = 2, p1 = 0 and p2 = 1, and locates facilities at the left and rightmost agents, x1 and xn. The INNERPOINT mechanism has m = 2, p1 = c1-1 n-1 and p2 = c1 n-1 , and locates one facility at xc1 serving the leftmost c1 agents, and the other at x1+c1 serving the remaining agents. The FIXED mechanism has pi = pj for 1 ≤ i < j ≤ m and locates every facility at the same agent. jLEFTkRIGHT: a member of this family of mechanisms locates j facilities at the leftmost j distinct locations of the agents, and k facilities at the rightmost k distinct locations. If agents declare insufficient distinct locations, multiple facilities are located at the rightmost. The ENDPOINT mechanism is the jLEFTkRIGHT mechanism with j = k = 1, the 2LEFTPEAK mechanism has j = 2 and k = 0, the 2RIGHTPEAK mechanism has j = 0 and k = 2, the 3LEFTPEAK mechanism has j = 3 and k = 0, etc. We also consider the MIDPOINT mechanism which locates all facilities at 1/2. We focus on three desirable properties of mechanisms for facility location problems with capacity limits: anonymity, Pareto optimality and strategy proofness. We extend the usual definitions of these properties to take account of the fact that facilities have capacity limits and agents are allocated to particular facilities. This impacts on what it means to be anonymous, Pareto optimal or strategy proof. Definition. We say that a mechanism for facility location problems with capacity limits is: Anonymous: iff for any location of agents xi, given any permutation of agents σ, when each agent i reports xσ(i) rather than xi resulting in facilities located at y′j and an allocation of agents to facility a′i , then y′a′i = yaσ(i) for every agent i. Pareto optimal: iff for any location of agents xi, there is no other location of facilities y′j and allocation of agents to facility a′i such that |y′a′i -xi| ≤ |yai -xi| for all agents i, and |y′a′k -xk| < |yak -xk| for one agent k. Strategy proof: iff for any location of agents xi, no agent k can report a new location giving a location of facilities y′j and allocation of agents to facilities a′i such that - xk| < |yak - xk|. 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 ensures that we cannot improve the solution so one agent is nearer the facility serving them without other agents being further away. Finally, strategy proofness is a fundamental game theoretic property. It guarantees that no agent can misreport their location, and reduce their distance to the facility serving them. ## 4 Uncapacitated Problem We begin by summarizing existing results about strategy proof mechanisms for the uncapacitated problem. This will serve as a baseline to compare against when we consider capacity constraints on the facilities. Without capacity limits, agents can always be served by their nearest facility. With any number of facilities, every PERCENTILE mechanism is anonymous and strategy proof (Theorem 1 in [Sui et al., 2013]). Similarly, with any number of facilities m, any jLEFTkRIGHT mechanism with j + k = m is strategy proof and anonymous. Pareto optimality is more difficult to achieve than anonymity, especially as the number of facilities increases. With a single facility, any PERCENTILE mechanism is Pareto optimal and strategy proof. With two facilities, the only PERCENTILE mechanism that is Pareto optimal and strategy proof is the ENDPOINT mechanism. With three or more facilities, no PERCENTILE mechanism is Pareto optimal. On the other hand, with any number of facilities m (m ≥ 1), every jLEFTkRIGHT mechanism with j + k = m is Pareto optimal in addition to being anonymous and strategy proof. ## 5 Two Capacitated Facilities Since we suppose facilities have enough capacity to serve all agents, the first non-trivial case to consider is two identical facilities with equal capacity limits and no spare capacity. Capacity constraints can make axiomatic properties harder to achieve even in this simplest setting. With two facilities and no capacity limits, the only PERCENTILE mechanism that is strategy proof and Pareto optimal is the ENDPOINT mechanism. However, the ENDPOINT mechanism stops being strategy proof when we add capacity limits. For example, if agents are at 0, 1/8, 1/4 and 1, and we have two facilities, each with capacity for two agents, the agent at 1/4 can profit by mis-reporting their location as 0. They are then allocated to the leftmost facility at 0 rather than the rightmost facility at 1, and this is closer to their true location at 3/4. In fact, to keep strategy proofness when we add capacity limits, we must locate the two facilities not at the two extreme endpoints, but at the two innermost points. It follows from Theorem 7 in [Aziz et al., 2020], the only PERCENTILE mechanism that is strategy proof and Pareto optimal with two identical facilities is the INNERPOINT mechanism. We now prove a strong characterization result: the INNERPOINT mechanism is in fact the only strategy proof mechanism that is anonymous and Pareto optimal when we have two identical facilities and no spare capacity. We contrast this strong characterization result with the uncapacitated problem where there are multiple strategy proof mechanisms for locating two uncapacitated facilities that are anonymous and Pareto optimal (e.g. in the uncapacitated setting, strategy proof mechanisms that are anonymous and Pareto optimal include 2LEFTPEAK, 2RIGHTPEAK and ENDPOINT). Theorem 1. With 2k agents and two facilities of capacity k, a strategy proof mechanism is anonymous and Pareto optimal iff it is the INNERPOINT mechanism. Proof: It is easy to see that the INNERPOINT mechanism is anonymous, Pareto optimal and strategy proof. Therefore it remains to show that if a strategy proof mechanism is anonymous and Pareto optimal then it is the INNERPOINT mechanism. We actually prove a stronger statement: if a strategy proof mechanism is anonymous and Pareto optimal for 2k agents and two facilities of capacity k, or for 2k + 1 agents and a facility of capacity k and another of capacity k + 1 in a given fixed order left to right then that mechanism must be the INNERPOINT mechanism. The proof uses induction on k, the capacity of the facilities. To be able to complete the induction step, we extend the definition of facility location problem to include optionally one special agent at one of the two extreme locations, 0 or 1. The location of this special agent is fixed and it is allocated respectively to the leftmost or rightmost facility. As we will argue, this fixed agent can be factored out of consideration given that agents are allocated to particular facilities. We can simply consider mechanisms for one fewer agent provided we reduce the capacity limit of the facility to which this special agent is allocated. Base case: k = 1. There are three 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 returned 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 x1 ≤ x2 ≤ x3. The Pareto optimal solution puts the smaller facility at x1 serving the leftmost agent and the larger facility somewhere in the interval [x2, x3] serving the other two agents. Now move the agent at x3 to x2. The unique Pareto optimal solution puts the smaller facility at x1 serving the leftmost agent and the larger facility at x2 serving the two agents there. We next move the rightmost agent from x2 back towards its original position at x3. Let x be the distance of the rightmost agent from x2 so that x varies from 0 to x3 - x2, 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 [x2, x2 + 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 x2 as with the INNERPOINT mechanism, (b) the larger facility remains at x2 + x, (c) the larger facility tracks x2 + x until some x′ with x2 + x′ < x3 after which the location of the larger facility remains static or (d) the larger facility at some point tracks behind and is strictly between x2 and x2 +x. Note that the larger facility cannot track to right of x2 + x as this would not be Pareto optimal. In case (b), consider x1 = 1/5, x2 = 2/5, x3 = 1 and x = 3/5. Then the middle agent at x2 can profitably mis-report 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 3/5 to 2/5 violating the assumption that the mechanism is strategy proof. In case (c), suppose x1 = x2 , x2 = x then the agent at x2 can profitably mis-report their location as x2 , contradicting the assumption that the mechanism is strategy proof. In case (d), the larger facility tracks strictly behind x2+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 x2 + b, the rightmost facility is located at x2 + a, and when the rightmost agent is at x2+a, the rightmost facility is located at x2+c where c < a. Then if agents are at x1, x2 and x2 +a, the rightmost agent at x2 +a can profitably mis-report their location as x2 +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. This completes the proof of the second subcase. In the third subcase, we have three agents, a facility of capacity 2 on the left and a facility of capacity 1 on the right. This is symmetric to the second subcase. This completes the proof of the third subcase, and of the base case as a whole. Step case: we suppose that the only strategy proof mechanism that is anonymous and Pareto optimal for 2k agents and two facilities of capacity k, or for 2k + 1 agents and facilities of capacity k and k + 1 in some fixed order is the INNERPOINT mechanism. We need to prove three subcases. We consider the first subcase with 2k + 2 agents and two facilities of capacity k + 1. Suppose the 2k + 2 agents are at x1 ≤ x2 ≤ . . . ≤ x2k ≤ x2k+1 ≤ x2k+2. We move the leftmost agent at x1 to 0 and suppose it is fixed and served by the leftmost facility. Because the agent at 0 is fixed and allocated to the leftmost facility, this agent does not change the image sets for the other agents. We therefore have a facility location problem with the remaining 2k + 1 agents, and a facility of capacity k on left and k + 1 on the right. By the induction hypothesis, the only strategy proof mechanism that is anonymous and Pareto optimal is the INNERPOINT mechanism that locates one facility at xk+1 serving agents located in the interval [x2, xk+1], and the other facility at xk+2 serving the remaining agents. We next move the leftmost agent from 0 back to x1. By similar continuity arguments used in the base case, the leftmost facility must remain at xk+1. By a symmetric argument moving the rightmost agent at x2k+2 to 1 and then back to its original position, the rightmost facility must remain at xk+2. Pareto efficiency prevents other agents from being served by a different facility when xk+2 > xk+1 as such a switch changes the distances traveled. If xk+2 = xk+1 we don't care which facility serves which agent as the two facilities are co-located and switching is irrelevant. Hence, the solution is that returned by the INNERPOINT mechanism. This leaves 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. Suppose the agents are at x1 ≤ x2 ≤ . . . ≤ x2k ≤ x2k+1 ≤ x2k+2 ≤ x2k+3. We move the rightmost agent at x2k+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 strategy proof mechanism for such a setting that is anonymous and Pareto optimal is the INNERPOINT mechanism that locates one facility at xk+1 serving agents located in the interval [x1, xk+1], and the other facility at xk+2 serving the remaining agents. We next move the rightmost agent from 1 back to x2k+3. By similar continuity arguments, the rightmost facility must remain at xk+2. Similar arguments also prevent the leftmost facility moving away from xk+1 or for agents to switch facilities. Hence, with the rightmost agent back at x2k+3, the solution is that returned by the INNERPOINT mechanism. This leaves the third subcase of 2k+3 agents and a facility of capacity k + 2 on the left and a facility of capacity k + 1 on the right. This is symmetric to the second subcase. This completes the proof of the induction step, and of the proof as a whole. ⋄ We next prove that this characterization result is minimal by dropping in turn anonymity, Pareto optimality and strategy proofness. There are multiple strategy proof mechanisms that are Pareto optimal but not anonymous. For example, the following family of serial dictator mechanisms modified to take account of capacity limits are strategy proof and Pareto optimal, but not anonymous. SD⋆ mechanism: Given a permutation σ of agents, we locate the first facility at xσ(1). Let j = min{i | xσ(i) ̸= xσ(1)}∪{k+1} where k is the capacity of each facility. We locate the second facility at xσ(j). We then allocate agents to facilities in permutation order. Each is allocated to the nearest facility with remaining capacity. If an agent is equidistant from both facilities and both facilities have spare capacity, we skip allocating this agent till the next and final phase. In this phase, we allocate the equidistant agents, again in permutation order, and again respecting the remaining capacities of the facilities, tiebreaking with the leftmost facility where ties remain. This serial dictatorship mechanism can be extended to three or more facilities, respecting capacity constraints yet ensuring Pareto optimality. We also consider dropping Pareto optimality and strategy proofness. There are multiple strategy proof mechanisms for locating two capacitated facilities that are anonymous but not Pareto optimal (e.g. any FIXED mechanism, or the MIDPOINT mechanism). Finally, there are multiple mechanisms that are anonymous and Pareto optimal but not strategy proof. Due to capacity limits, neither the ENDPOINT mechanism nor the 2LEFTPEAK mechanism are strategy proof. However, while both mechanisms are Pareto optimal, neither is anonymous when we impose capacity limits. For the ENDPOINT mechanism, consider facilities of capacity 2 and one agent at 0, two at 14 and one at 1. For the 2LEFTPEAK mechanism, consider facilities of capacity 2 and one agent at 0, one at 14 and two at 1. However, it is possible to modify both mechanisms to make them anonymous. ENDPOINT⋆ mechanism: Given two facilities of capacity k, if k + 1 or more agents are at a single location, then we locate both facilities at this location. If k agents are at the same location and this is not an endpoint, then we locate a facility at this location, and the other facility at the left endpoint. Otherwise we locate one facility at each endpoint. 2LEFTPEAK⋆ mechanism: Given two facilities of capacity k, if k + 1 or more agents are at a single location, then we locate both facilities at this location. If k agents are at the same location and this is not one of the two leftmost distinct locations, then we locate a facility at this location, and the other facility at the left endpoint. Otherwise we locate one facility at each of the two leftmost distinct locations. Both the ENDPOINT⋆ and 2LEFTPEAK⋆ mechanisms are anonymous and Pareto optimal, but not strategy proof. In conclusion, anonymity, Pareto optimality and strategy proofness are the minimal combination of these axioms characterizing the INNERPOINT mechanism. ## 6 Spare Capacity So far, we have supposed that there is no spare capacity in the problem. We now relax this assumption. We will identify a new class of strategy proof mechanisms that smoothly interpolates between the ENDPOINT and INNERPOINT mechanisms which are anonymous and Pareto optimal in the presence of spare capacity. INNERGAP family of mechanisms: For a facility location problem with two facilities of capacity k and j units of spare capacity where 0 ≤ j < k (i.e. 2k - j agents in total), the INNERGAPj mechanism is an instance of PERCENTILE with parameters p1 = k-j-1 2k-j-1 and p2 = k 2k-j-1 which locates facilities at xk-j and xk+1. We give a few examples. INNERGAP0 is the INNERPOINT mechanism, locating facilities at xk and xk+1 and allocating the leftmost k agents to the facility at xk and the rightmost k agents to the facility at xk+1. INNERGAP1 locates facilities at xk-1 and xk+1, and allocates the agent at xk to whichever facility is nearest. Note that capacity limits permit xk to be allocated to either facility as the leftmost facility serves the k-1 agents at x1 to xk-1, while the rightmost facility serves the k-1 agents at xk+1 to x2k-1 leaving one unit of spare capacity in either facility to serve the agent at xk. INNERGAP2 locates facilities at xk-2 and xk+1, and allocates the agents at xk-1 and xk to whichever facility is nearest. Again capacity limits permit xk-1 and xk to be allocated to either facility as the leftmost facility serves the k - 2 agents at x1 to xk-2, while the rightmost facility serves the k - 2 agents at xk+1 to x2k-2 leaving two units of spare capacity in either facility to serve agents at xk-1 and xk. Finally INNERGAPk-1 is the ENDPOINT mechanism, locating facilities at x1 and xk+1 which are the two endpoints of the k+1 agents, and allocates every agent to the nearest endpoint. Theorem 2. With two facilities, each of capacity k and j units of spare capacity for j ≥ 0, the following strategy proof mechanisms are anonymous and Pareto optimal: 1. case j = 0: the INNERPOINT mechanism; 2. case 0 ≥ j ≥ k -1: the INNERGAPj mechanism; 3. case j ≥ k -1: the ENDPOINT mechanism. When there is lots of spare capacity, there are in fact multiple strategy proof mechanisms that are anonymous and Pareto optimal. For example, in the third case with k - 1 or more units of spare capacity, both the ENDPOINT and the 2LEFTPEAK mechanisms are anonymous, Pareto optimal and strategy proof. On the other hand, with no spare capacity, there is an unique strategy proof mechanism that is anonymous and Pareto optimal. Spare capacity thus makes it easier for strategy proof mechanisms to be anonymous and Pareto optimal. ## 7 Unequal Capacity So far, we have supposed that all facilities have the same capacity. What happens if facilities have unequal capacities? You might think this would be similar to the previous setting with spare capacity. Suppose we have a facility location problem with spare capacity such as five agents and two facilities with equal capacity for three agents. Then any solution inevitably allocates two agents to one facility, and three agents to the other. It therefore resembles a facility location problem with unequal capacities. Despite this similarity between spare and unequal capacity, anonymity and Pareto optimality are more difficult to achieve with facilities of unequal capacity than with facilities of equal capacity but when there is spare capacity. In particular, with two facilities of different capacities, we prove an impossibility result that no mechanism can be both anonymous and Pareto optimal except in one special case. In this case, where the capacities of the two facilities differ by just a single agent, we propose a new strategy proof mechanism that is both anonymous and Pareto optimal. INNERCHOICE mechanism: For a facility location problem with two facilities of capacity k and k + 1 agents, if xk+1 - xk < xk+2 - xk+1 then this mechanism locates the facility of capacity k + 1 at xk and the other at xk+2. Otherwise it locates the facilities at the same locations but in the opposite order. In either case, agents are allocated left to right to facilities up to their capacity limit. Theorem 3. With two facilities of capacity k and k + d, no mechanism is both anonymous and Pareto optimal when d > 1. For d = 1, the INNERCHOICE mechanism is anonymous, Pareto optimal and strategy proof. Proof: Consider d > 1. Suppose k + 1 agents are at 0, and k+d-1 at 1. There are two cases. In the first case, one agent at 0 is served by the facility of capacity k at some location x. By anonymity, all k + 1 agents at 0 are served by facilities at x. Therefore both facilities are at x. If x < 1 this is not Pareto optimal as locating the facility of capacity k +d at x, serving k + 1 agents at 0 and d - 1 agents at 1, and the other facility at 1 dominates. If x = 1 this is also not Pareto optimal as locating the facility of capacity k at 0 serving k agents at 0, and the other facility at 1 dominates. This completes the first case. In the second case, no agent at 0 is served by the facility of capacity k. Therefore the facility of capacity k serves only agents at 1. Suppose the facility of capacity k is at y. By anonymity, all k +d-1 agents at 0 are served by facilities at y. Therefore both facilities are at y. By a similar argument to the first case, this is not Pareto optimal. ⋄ We can show that this impossibility result is minimal. If we drop one of anonymity or Pareto optimality, we can even add back strategy proofness. There are multiple strategy proof mechanisms for locating two facilities of unequal capacity that are Pareto optimal but not anonymous (e.g. the SD⋆ mechanism modified to take account of the unequal capacities). Similarly, there are multiple strategy proof mechanisms for locating two facilities of unequal capacity that are anonymous but not Pareto optimal (e.g. any FIXED mechanism, or the MIDPOINT mechanism). This impossibility is in contrast to the uncapacitated problem where there are multiple strategy proof mechanisms for locating two facilities without capacity limits that are both anonymous and Pareto optimal (e.g. the 2LEFTPEAK and ENDPOINT mechanisms). ## 8 Three or More Capacitated Facilities If we increase the number of facilities then anonymity and Pareto optimality become harder to achieve simultaneously. Indeed, even with facilities that have equal capacity, no mechanism for locating three or more capacitated facilities can be both anonymous and Pareto optimal. Theorem 4. With three or more capacitated facilities with greater than unit capacity, no mechanism is both anonymous and Pareto optimal. Proof: Suppose we have m facilities with capacity k where m > 2 and k > 1. Consider ⌈ 3k 2 ⌉ agents at 0, ⌊ 3k 2 ⌋ agents at 12 , and the remaining (m- 3)k agents at 1. Note that when m = 3, agents are just at 0 and 12 . To ensure anonymity and Pareto optimality, (m-3) facilities are at 1 serving the agents at 1. Again when m = 3, there are no agents or facilities at 1. We turn our focus to the other 3k agents at 0 and 12 , as well as the 3 facilities which serve them. Capacity constraints require two facilities to serve the agents at 0. Anonymity requires both these facilities to be at the same location. Capacity constraints also require two facilities to serve the agents at 12 . Anonymity again requires both these facilities to be at the same location. Hence, all three facilities must be at the same location. But this is not Pareto optimal. Any Pareto optimal solution has one facility at 0, one facility at 12 , and the third facility somewhere in [0, 12 ]. ⋄ This impossibility result is also minimal. If we drop one of anonymity or Pareto optimality, we can again add back strategy proofness. For example, there are multiple strategy proof mechanisms for locating three or more capacitated facilities that are Pareto optimal but not anonymous (e.g. any SD⋆ mechanism). Similarly, there are multiple strategy proof mechanisms that are anonymous but not Pareto optimal (e.g. any FIXED mechanism). This impossibility is again in contrast to the uncapacitated problem where there are multiple strategy proof mechanisms for locating three facilities without capacity limits that are both anonymous and Pareto optimal (e.g. the 3LEFTPEAK and 3RIGHTPEAK mechanisms). ## 9 Conclusions We have studied the impact of capacity constraints on mechanisms for facility location satisfying three important axioms: 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. Our four key results provide a comprehensive understanding of the strategy proof mechanisms for locating capacitated facilities which are anonymous and Pareto optimal. First, we proved a strong characterization theorem: the INNERPOINT mechanism is the unique strategy proof mechanism for locating two identical facilities with no spare capacity that is both anonymous and Pareto optimal. Second, if there is spare capacity, we identified a more general class of strategy proof mechanisms that interpolates smoothly between the INNERPOINT and ENDPOINT mechanisms that are anonymous and Pareto optimal. Third, with facilities of different capacities, we proved an impossibility theorem that no mechanism can be both anonymous and Pareto optimal except when the difference in capacity limits is just a single agent. Fourth, with three or more facilities, we proved a second impossibility result that no mechanism can be both anonymous and Pareto optimal, even when facilities have equal capacity. In all our characterization and impossibility results, if we drop one of the axioms (anonymity, Pareto optimality or strategy proofness as appropriate), multiple mechanisms exist satisfying the remaining axioms. Hence, these results are minimal. 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 have a richer underlying metric. Can we extend these results to trees, or networks? 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 (e.g. [Ibara and Nagamochi, 2012; Cheng et al., 2013]). 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 (e.g. [Zou and Li, 2015; Feigenbaum and Sethuraman, 2015]). ## References 1. [Aziz et al., 2019] Haris Aziz, Hau Chan, Barton Lee, and David C. Parkes. The capacity constrained facility loca- tion problem. In Ioannis Caragiannis, Vahab S. Mirrokni, and Evdokia Nikolova, editors, 15th International Confer- ence on Web and Internet Economics, WINE 2019, volume 11920 of Lecture Notes in Computer Science, page 336. Springer, 2019. 2. [Aziz et al., 2020] Haris Aziz, Hau Chan, Barton Lee, Bo Li, and Toby Walsh. Facility location problem with capacity constraints: Algorithmic and mechanism design perspec- tives. In Vincent Conitzer and Fei Sha, editors, Proceed- ings of the Thirty-Fourth AAAI Conference on Artificial In- telligence. AAAI Press, 2020. 3. [Aziz et al., 2021] Haris Aziz, Alexander Lam, Barton Lee, and Toby Walsh. Strategyproof and proportionally fair fa- cility location. CoRR, abs/2111.01566, 2021. 4. [Cheng et al., 2013] Yukun Cheng, Wei Yu, and Guochuan Zhang. Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theoretical Com- puter Science, 497:154 -163, 2013. Combinatorial Algo- rithms and Applications. 5. [Feigenbaum and Sethuraman, 2015] Itai Feigenbaum and Jay Sethuraman. Strategyproof mechanisms for one- dimensional hybrid and obnoxious facility location mod- els. In AAAI Workshop on Incentive and Trust in E- Communities. AAAI Press, 2015. 6. [Fotakis and Tzamos, 2010] Dimitris Fotakis and Christos Tzamos. Winner-imposing strategyproof mechanisms for multiple facility location games. In Internet and Network Economics, pages 234-245, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. 7. [Golowich et al., 2018] Noah Golowich, Harikrishna Narasimhan, and David Parkes. Deep learning for multi-facility location mechanism design. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pages 261-267. International Joint Conferences on Artificial Intelligence Organization, 7 2018. 8. [Ibara and Nagamochi, 2012] Ken Ibara and Hiroshi Nag- amochi. Characterizing mechanisms in obnoxious facil- ity game. In 6th International Conference on Combinato- rial Optimization and Applications, volume 7402 of Lec- ture Notes in Computer Science, pages 301-311. Springer, 2012. 9. [Mei et al., 2016] Lili Mei, Minming Li, Deshi Ye, and Guochuan Zhang. Strategy-proof mechanism design for facility location games: Revisited (extended abstract). In Catholijn M. Jonker, Stacy Marsella, John Thangarajah, and Karl Tuyls, editors, Proceedings of the 2016 Inter- national Conference on Autonomous Agents & Multiagent Systems, Singapore, May 9-13, 2016, pages 1463-1464. ACM, 2016. 10. [Procaccia and Tennenholtz, 2013] Ariel Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. ACM Trans. Econ. Comput., 1(4):18:1- 18:26, December 2013. 11. [Procaccia et al., 2018] Ariel Procaccia, David Wajc, and Hanrui Zhang. Approximation-variance tradeoffs in fa- cility location games. In Sheila A. McIlraith and Kil- ian Q. Weinberger, editors, Proceedings of the Thirty- Second AAAI Conference on Artificial Intelligence, pages 1185-1192. AAAI, 2018. 12. [Serafino and Ventre, 2015] Paolo Serafino and Carmine Ventre. Truthful mechanisms without money for non- utilitarian heterogeneous facility location. In Proceed- ings of Twenty-Ninth AAAI Conference on Artificial Intel- ligence, pages 1029-1035. AAAI Press, 2015. 13. [Sui and Boutilier, 2015] Xin Sui and Craig Boutilier. Ap- proximately strategy-proof mechanisms for (constrained) facility location. In Gerhard Weiss, Pinar Yolum, Rafael H. Bordini, and Edith Elkind, editors, Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, May 4-8, 2015, pages 605-613. ACM, 2015. 14. [Sui et al., 2013] Xin Sui, Craig Boutilier, and Tuomas Sandholm. Analysis and optimization of multi- dimensional percentile mechanisms. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI '13, page 367-374. AAAI Press, 2013. 15. [Zou and Li, 2015] Shaokun Zou and Minming Li. Facility location games with dual preference. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pages 615-623. International Foun- dation for Autonomous Agents and Multiagent Systems, 2015.