Budgeted Facility Location Games with Strategic Facilities

1 Introduction

Facility location games have been extensively studied in algorithmic game theory and approximate mechanism design [Procaccia and Tennenholtz, 2009; Lu et al., 2010; Cheng et al., 2013; Fotakis and Tzamos, 2014]. In a classic setting, the agents can strategically report the private locations to the government. One of the frontier and challenging topics in this area is how to investigate the game with strategic facilities. Archer and Tardos [2001] studied a monetary model: given a set of facilities and a set of customers, all locations are publicly known. The selfish facilities are strategic players in the game, who are required to report their private openingcost. Once receiving the reports, the government needs to select a subset of facilities to open, and can pay some money to the facilities to guarantee the truthful reporting.

In this paper, we study the monetary model [Archer and Tardos, 2001] with a sharp budget constraint: the total payment of a mechanism is upper bounded by a given value B. We say such a truthful mechanism is budget feasible. In many mechanism design problems, the payment may be a large amount to enforce truthfulness. The introduction of budget constraint [Singer, 2010], which applies not to the costs but to the payments the mechanism uses to support truthfulness, reveals a new dimension of difficulty to mechanism design. The requirement of budget feasibility further limits the searching space, especially given the already strong restriction of truthfulness. Designing budget feasible mechanisms even requires us to bound the threshold payment for each player, which, not surprisingly, is tricky to analyze and compute.

∗Corresponding Author

For the motivation, the studied problem models the realistic scenario where the government wants to build some public facilities (e.g., libraries and supermarkets) at a certain number of available locations to serve customers. Each location has a holder, who incurs a private opening-cost when there is a facility to be built. Since the opening-cost may contain many components (e.g., construction cost and renovation cost), the government has no way to access this private information. Moreover, the government has a budget to be assigned to the location holders, aiming at selecting a subset of available locations for building facilities to optimize some system objectives (e.g. the total service cost). This scenario is partially considered in [Chen et al., 2019].

Our goal is to design mechanisms, which satisfy one or more desirable properties, for the facility location game in which each selfish facility is a strategic player and reports her private opening-cost to the government. Usually, a mechanism is required to be truthful, that is, for every facility reporting her true opening-cost is the optimal strategy to maximize her utility. Moreover, the mechanism is expected to have a good performance guarantee (w.r.t. a certain objective function) and satisfies the individual rationality that every facility benefits from participating in the game.

1.1 Our Results

We investigate the facility location game with strategic facilities, where all locations of customers and facilities are publicly known and each facility bids private opening-cost for consideration by the government. Besides, we introduce money into the game and use a budget to limit the ability of the government to select facilities. With respect to a subset of facilities selected by the government, each customer either incurs a connection cost equal to the distance to the nearest opened facility, or obtains a utility equal to a constant minus that distance. The performance of a mechanism is measured by comparing the objective value of the outcome with that of an optimal solution under the budget constraint which upper bounds the total opening-costs of facilities in the solution.

In this paper, we provide upper and lower bounds on the approximation ratios of truthful budget feasible mechanisms under four system objectives.

• For both objectives of minimizing the social cost and maximum cost, we show that no deterministic (randomized universally) truthful budget feasible mechanism can achieve bounded approximation ratio, even if the mechanism is allowed to use an augmented budget.
• For the objective of maximizing the social utility, we prove that both the deterministic and randomized lower bound on the approximation ratio for truthful budget feasible mechanisms are 2. Moreover, we propose a deterministic truthful budget feasible mechanism with approximation ratio 2, matching the lower bound.
• For the objective of maximizing the minimum utility, we show that no deterministic (randomized universally) truthful budget feasible mechanism has a bounded approximation ratio, even if the mechanism is allowed to use any budget less than 2B. Then we present a mechanism w.r.t. budget 2B, achieving an approximation ratio 2, which is the best possible.

Furthermore, we prove lower bounds on the approximation ratio with augmented budget kB for any k > 1.

1.2 RelatedWork

Facility Location Game. Procaccia and Tennenholtz [2009] first study the mechanism design for the facility location game. Lu et al. [2010] improve the mechanisms for twofacility games. Later, the model with strategic customers reporting private information has been widely studied, see, e.g., [Serafino and Ventre, 2015; Babaioff et al., 2016; Yuan et al., 2016; Chen et al., 2018; Fong et al., 2018; Wada et al., 2018; Aziz et al., 2019]. However, few works consider the model with strategic facilities. Archer and Tardos [2001] study the model with publicly known locations and strategic facilities who report private opening-costs; the government pays money to guarantee truthful reporting. The main differences with the model studied in this paper are (i) the payments are not constrained by any budget, and may be arbitrarily large; (ii) the objective is minimizing the sum of service costs and, additionally, the opening-costs.

Single Parameter Problem. A mechanism design problem is called single parameter, if each agent has only one private value. Myerson [1981] gives the first characterization of truthful mechanisms in the reverse-auction. Archer and Tardos [2001] consider a more general setting which defines the cost of each agent as her private value times the amount of load assigned to him. Other related results can be found in [Nisan and Ronen, 2001; Nisan et al., 2007]. Recently, Chen et al. [2019] study the dual-role setting with payment, in which every agent plays a dual role of facility and customer. Each selfish agent is located on a publicly known location, allowing a facility to be opened. Besides, each agent has a private opening-cost and bears a connection cost.

Budget Feasibility. In practise, the authority often has a budget on the payments. We call a mechanism budget feasible if the total payment provided by the mechanism does not exceed a given budget. Singer [2010] initiates the budgetfeasible mechanism design problem, and provides constantapproximate mechanisms for maximizing monotone submodular objective functions. Chen et al.[2011] improve the results. Recently, Khalilabadi et al. [2018] further improve the deterministic approximation ratio to 4.56, which is the best known. Moreover, a lot of works (see,e.g.,[Bei et al., 2012; Amanatidis et al., 2017; Leonardi et al., 2017]) design efficient mechanisms for some special monotone submodular objectives subject to other type of constraints.

2 Preliminaries

Let N = {1, 2, . . . , n} be a set of agents (customers) located on a line segment modeled by an interval [0, 1], where agent i ∈ N is located at point xi, and we refer to x = (xi)ni=1 as the location profile of agents. The government wants to build some facilities to serve the agents. There are m potential facility locations F = {l1, l2, . . . , lm} that can be chosen to build facilities on. We use lj to denote facility location and facility interchangeably, when the context is clear. Each facility lj has an opening-cost cj, which is the cost she incurs if this facility is opened. Let l = (lj)mj=1 and c = (cj)mj=1 be the location profile and opening-cost profile of facilities. The distance function d is Euclidean, i.e., d(xi, lj) := |xi - lj| is the distance between agent i ∈ N and facility lj ∈ F.

In the game, we consider the strategic behaviors of facilities, different from the classic facility location games. All agents' locations and facilities' locations are publicly known, while the opening-cost cj is private information held by facility lj. Facility lj strategically reports her opening-cost as her bid bj , which may not be equal to the true value cj . Upon receiving the bidding profile b = (bj)mj=1 , the government uses a mechanism to select a subset S ⊆ F of facilities to open, and decide a payment pj to each facility lj ∈ F. Call S the winning set and call each selected facility lj ∈ S a winner. Formally, a mechanism M = (f, p) consists of a selection function f : Rm+ → 2F and a payment function p : Rm+ → Rm+ , which map a bidding profile b = (bj )mj=1 to a winning set f (b) = S and a payment profile p(b) = (pj )mj=1 , respectively. We shall denote by (s1, s2, . . . , sm) the indicator vector of S, that is, sj = 1 iff lj ∈ S, and sj = 0 iff lj /∈ S. Let [n] = {1, 2, . . . , n}.

Given a sharp budget constraint B, a mechanism is said to be budget feasible if the total payment paid by the mechanism does not exceed B, i.e., ∑mj=1 pj ≤ B. Each facility lj strategically reports her opening-cost to maximize her gain, defined as pj -sjcj . We require that reporting true cost is a dominant strategy for every bidder. Formally, a mechanism is truthful if for every lj ∈ F with true opening-cost cj and bid c′j , and every set of bids by F\{lj}, we have pj - sjcj ≥ p′j - s′j cj , where (sj, pj) and (s′j , p′j ) are the indicator vectors and payments when the bid is cj and c′j , respectively. A randomized mechanism is universally truthful if it takes a distribution over deterministic truthful mechanisms. As usual, a mechanism is required to be normalized (sj = 0 implies pj = 0), individual rational (pj ≥ sjcj), and with no positive transfers (pj ≥ 0).

We assume that true opening-cost of any facility is no more than the given budget, i.e., cj ≤ B, for all lj ∈ F. This assumption is reasonable because a budget feasible mechanism never selects a facility whose opening-cost is larger than B.

2.1 Characterization of Truthfulness

Our setting is in the single parameter domain, as each agent has one private value. It is well-known that a mechanism is truthful if and only if its allocation rule is monotone and payment to each winner is her threshold bid [Myerson, 1981].

Proposition 1 ([Myerson, 1981]). In single parameter domains a normalized mechanismM= (s, p) is truthful if and only if:

1. f is monotone: ∀i ∈ N, if b′i ≤ bi, then i ∈ f(bi, b-i) implies i ∈ f(b′i , b-i) for every b-i;
2. winners are paid threshold payments: payment to each winning bidder i is inf{bi : i /∈ f(bi, b-i)}.

Hence, we only focus on designing monotone allocations without specifying the payment to each winner explicitly.

2.2 Objectives

Given a winning set S, the cost of each agent i ∈ N is defined as her distance to the nearest opened facility in S, denoted by costi(S) = minlj∈S d(xi, lj), and the utility of i is defined as ui(S) = 1-costi(S). Recall that all facilities and agents are located on the line segment [0, 1]. Therefore, we can guarantee that ui(S) ≥ 0 as long as S ̸= ∅.

In this paper, we consider four system objective functions: social cost, maximum cost, social utility and minimum utility. With respect to a winning set S ⊆ F, the social cost is the total cost of all agents, i.e., SC(S) := ∑i∈N costi(S); the maximum cost is the maximum of all agents' cost, i.e., MC(S) := maxi∈N costi(S); the social utility is the total utility of all agents, i.e., SU(S) := ∑i∈N ui(S); and the minimum utility is the minimum of all agents' utilities, i.e., MU(S) :=mini∈N ui(S).

Our goal is to design truthful budget feasible mechanisms with good performances for the system objectives, that is, minimizing cost objectives and maximizing utility objectives. Denote by I = (x, l, c, B) an instance of our facility location game. Consider a system objective function G : 2F → R+, which may be SC, MC, SU or MU.

For cost objectives, let OPT(I) be the optimal objective value of the linear program on instance I : minS⊂F G(S) subject to ∑lj∈S cj ≤ B, and the approximation ratio of mechanism M with respect to I is γ(M, I) = G(SI) OP T (I) , where SI is the winning set selected byM.

For utility objectives, let OPT(I) be the optimal objective value of the linear program on instance I : maxS⊂F G(S) subject to ∑lj∈S cj ≤ B, and the approximation ratio of mechanismMwith respect to I is γ(M, I) = OPT(I) G(SI) . Then the approximation ratio of M is the worst-case ratio over all possible instances, denoted by γ(M) = supI γ(M, I).

Augmentation. However, for some objectives, the approximation ratio of any budget feasible mechanism may be unbounded, e.g., the cost objectives and minimum utility objective. Therefore, we will consider a budget augmentation framework where we are allowed to exceed the budget B by a certain amount. That is, as performance measure, the optimal objective value will be compared with the value achievable by a mechanism on an instance with augmented budget. Thus, for cost objectives, we define the approximation ratio with augmentation of a mechanismM as γg(M) = supI G(SIg ) OP T (I) , for utility objectives, define the approximation ratio with augmentation as γg(M) = supI OP T (I) G(SIg ) , where g ≥ 1 is the augmentation factor, and SIg is the winning set produced by mechanismMon input instance Ig := (x, l, c, gB).

3 Minimizing Cost Objectives

In this section, we consider the objectives of minimizing the social cost and the maximum cost. It is shown that the approximation ratios of both deterministic truthful budget feasible mechanisms and randomized universally truthful budget feasible mechanisms are unbounded.

Theorem 2. For both objectives of minimizing the social cost and maximum cost, no deterministic truthful budget feasible mechanism has a bounded approximation ratio, even if the mechanism can have a budget kB for any constant k ≥ 1.

Proof. Suppose that there is a deterministic truthful budget feasible mechanismMwith bounded approximation ratio. Let ˜ k = ⌈k⌉. Consider an instance with ˜ k + 1 agents and ˜ k + 1 facilities, where the location profile is x = l = (0, 1/˜ k, . . . , ˜ k/˜ k). For the opening-cost profile (B - ˜ kϵ, ϵ, . . . , ϵ) with sufficiently small ϵ > 0, the optimal solution opens all ˜ k + 1 facilities with a social cost (maximum cost) 0. We claim that Mmust select all ˜ k + 1 facilities, otherwise the approximation ratio is infinite since the social cost (maximum cost) of M is at least 1/˜ k. Similarly, for other ˜ k opening-cost profiles (ϵ,B - ˜ kϵ, ϵ, . . . , ϵ), (ϵ, ϵ,B - ˜ kϵ, . . . , ϵ), . . ., (ϵ, . . . , ϵ,B - ˜ kϵ), all facilities should be selected by M.

Now consider the opening-cost profile (ϵ, . . . , ϵ). The optimal social cost (maximum cost) is 0, and all facilities should be selected by M for a bounded ratio. By Proposition 1, the payment to each facility is the threshold for winning, which is at least B - ˜ kϵ. Hence, the total payment is at least (˜ k + 1)(B - ˜ kϵ) > ˜ kB ≥ kB, which exceeds the budget B (and even the augmented budget kB), a contradiction.

Next we use Yao's min-max principle [1977] to establish a lower bound on the performance of randomized mechanisms.

Theorem 3. For both objectives of minimizing the social cost and minimizing maximum cost, no randomized universally truthful budget feasible mechanism can achieve a bounded approximation ratio, even if the mechanism can have a budget kB for any constant k ≥ 1.

Proof. By Yao's min-max principle, it suffices to construct a distribution of instances, and prove that no deterministic truthful mechanism can achieve a bounded expected approximation ratio against that distribution.

Let ˜ k = ⌈k⌉ and ϵ ∈ (0, 1) be sufficiently small. Define (˜ k + 1)-dimensional vector y = (ϵ, ϵ, . . . , ϵ). Consider a distribution of instances: all instances contain ˜ k + 1 agents and ˜ k + 1 facilities with x = l = (0, 1/˜ k, . . . , ˜ k/˜ k), and the opening-cost profile c = (c1, c2, . . . , c˜k+1 ) is drawn from the following distribution:

For each of the ˜ k + 2 instances, the optimal social cost (maximum cost) is 0, attained by selecting all facilities. Using the same argument as that in the proof of Theorem 2, we claim that for any deterministic truthful mechanism M w.r.t. budget kB achieving a bounded expected approximation ratio, there is at least one instance such that M cannot select all ˜ k + 1 facilities as winners, indicating that the induced social cost (maximum cost) with respect to that instance is at least 1/˜ k. Then the expected ratio of M is at

4 Maximizing the Social Utility

In this section, we consider the objective of maximizing the social utility. We first show that both deterministic and randomized lower bound on the approximation ratio of any truthful budget feasible mechanisms are 2, and then provide a deterministic mechanism with a tight approximation ratio 2.

4.1 Lower Bounds

We give a lower bound of 2 for deterministic mechanisms, by considering a 2-agent and 2-facility instance with x = l = (0, 1), in which the opening-cost profile c is similarly constructed as that in the proof of Proposition 5.2 in [Singer, 2010].

Theorem 4. For the objective of maximizing the social utility, no deterministic truthful budget feasible mechanism can achieve an approximation ratio better than 2.

Motivated by the distribution of instances constructed in the proof of Theorem 4.2 in [Chen et al., 2011], we construct an instance distribution and use Yao's min-max principle to show that the randomized lower bound is also 2.

Theorem 5. For the objective of maximizing the social utility, no randomized universally truthful budget feasible mechanism can achieve an approximation ratio better than 2.

Proof. Consider an instance distribution where all instances contain 2 agents and 2 facilities with x = l = (0, 1). The opening-cost profile c = (c1, c2) is drawn from the following distribution, consisting of two classes:

where L is a large integer, ai > ai+1 for all i ∈ [L- 1], and ϵ ∈ (0, 1) is a sufficiently small constant.

We first show that for any deterministic truthful budget feasible mechanism M with a bounded expected approximation ratio, there is at most one instance such that M selects two facilities as winners. Suppose for contradiction that there are at least two such instances. These must be two instances in class 1, since for any instance in class 2, M cannot select two facilities due to the budget constraint. Denote these two instances as (ai, B-ai) and (aj , B-aj ) with ai > aj . Now consider the instance (ai,B - aj) in class 2, for which M must select at least one facility (assumed w.l.o.g. to be F1 by symmetry), otherwise the approximation ratio is infinite. Then we consider the instance (aj,B - aj), for which both facilities win. The truthfulness guarantees that the payment to facility 1 is at least ai (because the threshold for winning is at least ai), implying that the payment to facility 2 is at most B - ai < B - aj , which violates individual rationality. Therefore, M cannot select two facilities for (aj,B - aj), and there is at most one instance, for which M selects two facilities with a social utility 2.

Next calculate the expected approximation ratio of M. For each instance in class 1, the optimal solution is selecting two facilities with the optimal social utility 2. Thus, the expected approximation ratio ofMis at least 1-ϵ L · 1+ 1-ϵ L · (L-1) · 2 + ϵ · 1 = 2 - 1L - (1 - 1L )ϵ → 2, when L → ∞ and ϵ → 0. Therefore, the randomized lower bound is 2 for the objective of maximizing social utility.

Besides, we have the following lower bounds on approximation ratio with augmentation.

Theorem 6. For the objective of maximizing the social utility, no deterministic truthful (resp. randomized universally truthful) budget feasible mechanism with respect to budget kB can achieve an approximation ratio better than 1 + 1 ⌈k⌉2+⌈k⌉-1 (resp. ⌈k⌉ ⌈k⌉2+⌈k⌉-1 + ⌈k⌉ ⌈k⌉+1 ) for any constant k > 1.

4.2 Budget Feasible Mechanism

In this section, we provide a deterministic truthful budget feasible mechanism with approximation ratio 2, which matches the deterministic and randomized lower bound.

Mechanism 1. Select the single facility that can provide the maximum social utility among ones who bid no more than the budget, breaking ties arbitrarily. That is, select the facility

Pay B to the selected one and 0 to others.

Theorem 7. Mechanism 1 is a truthful, budget feasible and 2-approximate mechanism for maximizing the social utility .

We prove Theorem 7 in three aspects: truthfulness, budget feasibility and approximation ratio.

Truthfulness and Budget Feasibility

Mechanism 1 is clearly normalized, individual rational and has no positive transfer. For truthfulness, by Proposition 1 it suffices to show the selection function is monotone and the payment to each winner is her threshold bid. The monotonicity is straightforward. Let l∗ j be the facility maximizing social utility. If l∗ j bids at most B, she will always win, otherwise, she will not be selected. Hence, her threshold bid for winning is B, equal to the payment. The truthfulness is guaranteed. Mechanism 1 is budget feasible since it selects only one facility and pays exactly B.

Approximation Ratio

We first make some assumptions for simplicity. Given any instance I = (x, l, c, B), w.l.o.g., assume that 0 ≤ x1 ≤ . . . ≤ xn ≤ 1 and 0 ≤ l1 ≤ . . . ≤ lm ≤ 1. When n is even, let xn1 and xn2 be the left and right median location of agents. When n is odd, let xn1 = xn2 be the median location of agents. Define function g(y) := ∑ni=1 |xi - y| over [0, 1], where g(y) is convex because it is the sum of convex functions |xi - y|. Then we have the following observation.

Observation 8. g(y) decreases in [0, xn1 ), reaches its minimum throughout [xn1 , xn2 ], and increases in (xn2 , 1].

The following lemma says that the winner facility is either between the medians or the nearest facility to the medians.

Lemma 9. Let l∗ j be the single facility selected by Mechanism 1. If there exists a facility located in [xn1 , xn2 ], then l∗ j ∈ [xn1 , xn2 ], otherwise, it must have l∗ j = arg min lj≤xn1 d(xn1 , lj )

Proof. Mechanism 1 selects the facility l∗ j such that l∗ j = argmaxlj∈F SU(lj) = argminlj∈F ∑ni=1 |lj - xi| = argminlj∈F g(li). That is, it selects a facility to minimize g. By Observation 8, if there is a facility located in [xn1 , xn2 ], then l∗ j ∈ [xn1 , xn2 ]. Otherwise, the winner is the nearest facility to the median either from the left, or from the right.

Now we calculate the approximation ratio of Mechanism 1. The basic idea is to divide all possible instances into three classes with respect to the relative positions of agents and facilities, and identify a worst-case instance I ′ = (x′ , l′ , c,B) for each class, such that any instance I within this class cannot have a larger approximation ratio than that of I ′ . Therefore, it suffices to prove γ(M, I) ≤ γ(M, I ′ ) ≤ 2.

Case 1. There exists at least one facility lj located in (xn1 , xn2 ). In this case, n is even, and Mechanism 1 will select an arbitrary single facility located in (xn1 , xn2 ). Let l∗ j ∈ (xn1 , xn2 ) be the winner, and define an instance I ′ as

Then d(x′i , l∗ j ) ≥ d(xi, l∗ j ) for any i ∈ N. For instance I ′ , the social utility induced by any single facility l′j is n/2, and the optimal social utility is n. Thus the ratio under I ′ is γ(M, I ′ ) = n n/2 = 2. Then we have

where li∗ ∈ F is the nearest facility to agent i ∈ N.

Case 2. All facilities are located on one side of themedians, i.e., either lj ≤ xn1 for any lj ∈ F, or lj ≥ xn2 for any lj ∈ F. Here we only consider the subcase that lj ≥ xn2 for any lj ∈ F, and the other subcase is symmetric. By Lemma 9, Mechanism 1 selects facility l1 as the winner. Let q =

max{i ∈ N|xi ≤ l1} be the nearest agent to facility l1 on its left, and define an instance I ′ as:

Then d(x′i , l1) ≥ d(xi, l1) for any i ∈ N. For instance I ′ , Mechanism 1 also selects facility l1 as the winner. Let a = d(0, l1), then the induced social utility w.r.t. I ′ is n - aq - (1-a)(n-q), and the optimal social utility is n-aq. Thus

Case 3. There is no facility located in (xn1 , xn2 ), while there are some facilities located on the left of xn1 and some facilities located on the right of xn2 . Let lj0 = argminlj≤xn1 d(xn1 , lj) be the nearest facility to xn1 on its left, and lj0+1 = argminlj≥xn2 d(xn2 , lj) be the nearest facility to xn2 on its right. Denote a = d(0, lj0 ), b = d(lj0 , lj0+1), c = d(lj0+1, 1), and let Q = lj0 +lj0+1 2 be the midpoint of [lj0 , lj0+1]. Then define an instance I ′ as:

Then d(x′i , lj0 ) ≥ d(xi, lj0 ), d(x′i , lj0+1) ≥ d(xi, lj0+1), and

Considering two subcases Q ∈ [xn1 , xn2 ] and Q /∈ [xn1 , xn2 ], it yields that γ(M, I ′ ) ≤ 2. Omitted proof can be found in a full version.

From the discussion of the above three cases, we complete the proof of the approximation ratio 2. We remark that the main difficulty of this proof is how to identify the worst-case instance for each class.

5 Maximizing the MinimumUtility

In this section, for maximizing the minimum utility of agents, we show the approximation ratios of any deterministic and randomized budget feasible mechanisms are unbounded. Then, in the budget augmentation framework, we propose a deterministic truthful mechanismw.r.t. budget 2B.

5.1 Lower Bounds

A simple observation shows that no deterministic truthful or randomized universally truthful budget feasible mechanism has bounded approximation ratios. In addition, we prove a stronger negative result as follows.

Theorem 10. For the objective of maximizing the minimum utility, no deterministic truthful budget feasible mechanism has a bounded approximation ratio, even if the mechanism M can have a budget 2B - ϵ for sufficiently small ϵ > 0.

Proof. SupposeMis a deterministic truthful budget feasible mechanism with a bounded approximation ratio w.r.t. budget 2B - ϵ. Consider an instance I with 2 agents and 2 facilities, where x = (0, 1), l = (ϵ, 1-ϵ), and the opening-cost profile is c = (B - ϵ/3, B - ϵ/3). Then Mmust open at least one facility, say facility 1, otherwise the approximation ratio is unbounded.

Consider another opening-cost profile (ϵ/3, B - ϵ/3). By monotonicity and the threshold of winning, facility 1 is selected with payment at least B - ϵ/3. Then the payment to facility 2 is at most B - 2ϵ/3 < B - ϵ/3, so that facility 2 cannot be selected by individual rationality. Therefore, M can only open one facility with the minimum utility ϵ, while the optimal solution opens the two facilities with the optimal minimum utility 1 - ϵ. Then the approximation ratio is 1-ϵ ϵ , approaching infinity when ϵ tends to 0, a contradiction.

Theorem 11. For the objective of maximizing the minimum utility, no randomized universally truthful budget feasible mechanism can achieve a bounded approximation ratio, even if mechanism M has budget 2B - ϵ for sufficiently small ϵ > 0.

Proof. Construct a distribution of instances where all instances contain 2 agents and 2 facilities with x = (0, 1) and l = (ϵ, 1 - ϵ). The opening-cost profile c is drawn from the following distribution: (B- ϵ3 , ϵ) and (ϵ, B- ϵ3 ) happen with probability 1-ϵ 2 , and (ϵ, ϵ) happens with probability ϵ.

By Yao's principle, it suffices to prove that any deterministic truthful budget feasible mechanism cannot have a bounded expected approximation ratio w.r.t. budget 2B - ϵ, over the above distribution. Suppose that there exists such a mechanismMwith a bounded expected ratio. Using the similar argument as that in Theorem 10, we claim that there is at most one instance between (B - ϵ3 , ϵ) and (ϵ, B - ϵ3 ) such that M can select both facilities as winners. That is, there is at least one instance, for whichMcan select at most one facility with a minimum utility at most ϵ, while the optimal solution under any instance is selecting both facilities with the optimal minimum utility 1 - ϵ. Thus, the expected ratio of M is at least 1-ϵ 2 · 1-ϵ ϵ + 1-ϵ 2 ·1+ϵ·1 approaching infinitywhen ϵ → 0.

Furthermore, we can have more general results on the lower bound of approximation ratio with augmentation.

Theorem 12. For the objective of maximizing the minimum utility, no deterministic truthful (randomized universally truthful) budget feasible mechanism with respect to budget kB achieves approximation ratio better than 1 + 1 ⌈k⌉-1 (1+ 1 ⌈k⌉2-1 ) for any constant k ≥ 2.

5.2 Mechanismwith Augmented Budget

We have shown that the deterministic lower bound w.r.t. budget 2B is 2. Next we provide a deterministic mechanism with approximation ratio 2, matching this bound.

Mechanism 2. Let lj1 = argminlj∈F d(x1, lj) be the nearest facility to the leftmost agent 1, and lj2 = argminlj∈F d(xn, lj) be the nearest facility to the rightmost agent n, breaking ties arbitrarily. Then,

• (i) If lj1 ̸= lj2 and bj1 , bj2 ≤ B, select the winning set S = {lj1 , lj2 }, and the payment to each winner is B.
• (ii) If lj1 = lj2 and bj1 , bj2 ≤ B, select the single facility lj1 , and the payment to lj1 is B.

The truthfulness and budget feasibility are straightforward. For the performance, when lj1 = lj2 , the nearest facility for every agent is lj1 , i.e., an optimal solution is selecting lj1 , and Mechanism 2 achieves the optimal minimum utility. When lj1 ̸= lj2 , define δ1 = d(lj1 , lj2 )/2, δ2 = d(x1, lj1 ), δ3 = d(xn, lj2 ). Then the minimum utility w.r.t. S is at least 1 - max{δ1, δ2, δ3}, and the optimal minimum utility is at most 1 -max{δ2, δ3}. Then we have the following result.

Theorem 13. Mechanism 2 (denoted byM2) is truthful and budget feasible with respect to budget 2B, and the approximation ratio with augmentation is γ2(M2) = 2.

6 Conclusion

This paper studies the budgeted facility location game with strategic facilities, who are required to report their private opening-costs for building a facility on their locations. Four system objectives are considered: social cost, maximum cost, social utility, and minimum utility. On the negative side, we prove lower bounds on the approximation ratios of truthful budget feasible mechanisms for all four objectives. On the positive side, we provide two mechanisms with good performances: For the utilitarian objective of maximizing the total utility of all agents, we present a 2-approximate mechanism, which says that, by simply building one single facility with the smallest total distance to all customers, the government can induce a social utility no less than half of the optimum. For the egalitarian objective of maximizing the minimum utility of customers, we give a 2-approximate mechanism w.r.t. budget 2B, which says that, by building two facilities at the locations closest to the leftmost and the rightmost customer, the government can make the minimum utility of customers no less than half of the optimum, if it can double the budget.

For further directions, other system objectives can be taken into consideration, e.g., the least squares objective studied in [Feldman and Wilf, 2013]. It is also interesting to explore the facility location game with both strategic customers and facilities, in which each customer reports private location, and each facility reports private opening-cost. The goal is to open some facilities to minimize the total service cost.

Acknowledgments

Minming Li is also from City University of Hong Kong Shenzhen Research Institute, Shenzhen, P. R. China. The work described in this paper was supported by a grant from Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CityU 11205619) and was partially sponsored by Project 11771365 supported by NSFC.