# budgeted_facility_location_games_with_strategic_facilities__b8cc036c.pdf

Budgeted Facility Location Games with Strategic Facilities

Minming Li1 , Chenhao Wang1,2,3 and Mengqi Zhang2,3

1Department of Computer Science, City University of Hong Kong 2Academy of Mathematics and Systems Science, Chinese Academy of Sciences 3School of Mathematical Sciences, University of Chinese Academy of Sciences minming.li@cityu.edu.hk, chenhwang4-c@my.cityu.edu.hk, mqzhang@amss.ac.cn

This paper studies the facility location games with payments, where facilities are strategic players. In the game, customers and facilities are located at publicly known locations on a line segment. Each selﬁsh facility has an opening-cost as her private information, and she may strategically report it. Upon receiving the reports, the government uses a mechanism to select some facilities to open and pay to them. The cost/utility of each customer depends on the distance to the nearest opened facility. Under a given budget B, which constrains the total payment, we derive upper and lower bounds on the approximation ratios of truthful budget feasible mechanisms for four utilitarian and egalitarian objectives, and study the case when augmented budget is allowed.

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 selﬁsh 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

Corresponding Author

the payments the mechanism uses to support truthfulness, reveals a new dimension of difﬁculty 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. 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 selﬁsh 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 satisﬁes the individual rationality that every facility beneﬁts 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

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

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 k B for any k > 1.

1.2 Related Work Facility Location Game. Procaccia and Tennenholtz [2009] ﬁrst 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., [Seraﬁno 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 ﬁrst characterization of truthful mechanisms in the reverse-auction. Archer and Tardos [2001] consider a more general setting which deﬁnes 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 selﬁsh 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 efﬁcient 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)n i=1 as the location proﬁle 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)m j=1 and c = (cj)m j=1 be the location proﬁle and opening-cost proﬁle 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 proﬁle b = (bj)m j=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 proﬁle b = (bj)m j=1 to a winning set f(b) = S and a payment proﬁle p(b) = (pj)m j=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., Pm j=1 pj B. Each facility lj strategically reports her opening-cost to maximize her gain, deﬁned 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 jcj, 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 as-

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

sumption 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 mechanism M = (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 deﬁned 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 deﬁned 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) := P 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) := P 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 : min S F G(S) subject to P 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 by M. For utility objectives, let OPT(I) be the optimal objective value of the linear program on instance I : max S F G(S) subject to P

lj S cj B, and the approximation ratio of

mechanism M with respect to I is γ(M, I) = OP T (I)

G(SI) . Then the approximation ratio of M is the worst-case ratio over all possible instances, denoted by γ(M) = sup I γ(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 deﬁne the approximation ratio with augmentation of a mechanism M as γg(M) = sup I G(SIg ) OP T (I), for utility objectives, deﬁne the approximation ratio with augmentation as γg(M) = sup I OP T (I)

G(SIg ) , where g 1 is the augmentation factor, and SIg is the winning set produced by mechanism M on input instance Ig := (x, l, c, g B).

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 k B for any constant k 1.

Proof. Suppose that there is a deterministic truthful budget feasible mechanism M with bounded approximation ratio. Let k = k . Consider an instance with k + 1 agents and k + 1 facilities, where the location proﬁle is x = l = (0, 1/ k, . . . , k/ k). For the opening-cost proﬁle (B kϵ, ϵ, . . . , ϵ) with sufﬁciently small ϵ > 0, the optimal solution opens all k + 1 facilities with a social cost (maximum cost) 0. We claim that M must select all k + 1 facilities, otherwise the approximation ratio is inﬁnite since the social cost (maximum cost) of M is at least 1/ k. Similarly, for other k opening-cost proﬁles (ϵ, B kϵ, ϵ, . . . , ϵ), (ϵ, ϵ, B kϵ, . . . , ϵ), . . ., (ϵ, . . . , ϵ, B kϵ), all facilities should be selected by M. Now consider the opening-cost proﬁle (ϵ, . . . , ϵ). 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ϵ) > k B k B, which exceeds the budget B (and even the augmented budget k B), 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 k B for any constant k 1.

Proof. By Yao s min-max principle, it sufﬁces 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 sufﬁciently small. Deﬁne ( k + 1)-dimensional vector y = (ϵ, ϵ, . . . , ϵ). Consider a

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

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 proﬁle c = (c1, c2, . . . , c k+1) is drawn from the following distribution:

1. c = (B kϵ, y i) with probability 1 ϵ

k+1, for all i

[ k + 1]; 2. c = (ϵ, . . . , ϵ) with probability ϵ.

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 k B 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 least 1 ϵ

k+1 1 + ϵ 1 , a contradiction.

4 Maximizing the Social Utility In this section, we consider the objective of maximizing the social utility. We ﬁrst 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 proﬁle 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 proﬁle c = (c1, c2) is drawn from the following distribution, consisting of two classes: 1. c = (ai, B ai) with probability 1 ϵ

L , for all i [L]

2. c = (ai, B aj) with probability 2ϵ L(L 1), for all 1 i < j L where L is a large integer, ai > ai+1 for all i [L 1], and ϵ (0, 1) is a sufﬁciently small constant. We ﬁrst 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 inﬁnite. 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 of M is at least 1 ϵ

L (L 1) 2 + ϵ 1 = 2 1

L)ϵ 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 k B 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 arg max lj F:bj B SU({lj}).

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 sufﬁces 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.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

Approximation Ratio We ﬁrst 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. Deﬁne function g(y) := Pn i=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)

or l j = arg min lj xn2 d(xn2, lj).

Proof. Mechanism 1 selects the facility l j such that l j = arg maxlj F SU(lj) = arg minlj F Pn i=1 |lj xi| = arg minlj 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 sufﬁces 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 deﬁne an instance I as

x i = 0, 1 i n1 1, n2 i n , l j =

0, j = 1 lj, 2 j m 1 1, j = m .

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

γ(M, I) = n Pn i=1 d(xi, li ) n Pn i=1 d(xi, l j) n n Pn i=1 d(x i, l j)

= γ(M, I ) = 2,

where li F is the nearest facility to agent i N. Case 2. All facilities are located on one side of the medians, 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 deﬁne an instance I as:

x i = 0, 1 i q 1, q + 1 i n , l j = lj, 1 j m 1 1, j = m .

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

γ(M, I) = n Pn i=1 d(xi, li ) n Pn i=1 d(xi, l1) n Pq i=1 d(xi, l1) n Pn i=1 d(xi, l1)

n Pq i=1 d(x i, l1) n Pn i=1 d(x i, l1) = γ(M, I )

= n aq n aq (1 a)(n q) 1 + n n2

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 = arg minlj xn1 d(xn1, lj) be the nearest facility to xn1 on its left, and lj0+1 = arg minlj 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 deﬁne an instance I as:

0, xj < lj0 xi, lj0 i lj0+1 1, xj > lj0+1 , l j =

0, j = 1 lj, 2 j m 1 1, j = m .

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

γ(M, I ) = n P lj0 xi lj0+1 d(xi, li )

n min{Pn i=1 d(x i, lj0), Pn i=1 d(x i, lj0+1)}

n Pn i=1 d(xi, li ) n min{Pn i=1 d(xi, lj0), Pn i=1 d(xi, lj0+1)} = γ(M, I),

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 difﬁculty of this proof is how to identify the worst-case instance for each class.

5 Maximizing the Minimum Utility 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 mechanism w.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.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

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 sufﬁciently small ϵ > 0.

Proof. Suppose M is 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 proﬁle is c = (B ϵ/3, B ϵ/3). Then M must open at least one facility, say facility 1, otherwise the approximation ratio is unbounded. Consider another opening-cost proﬁle (ϵ/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 inﬁnity 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 sufﬁciently 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 proﬁle 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 sufﬁces 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 mechanism M with 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 which M can 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 approaching inﬁnity when ϵ 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 k B achieves approximation ratio better than 1 + 1 k 1 (1 + 1 k 2 1) for any constant k 2.

5.2 Mechanism with 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 = arg minlj F d(x1, lj) be the nearest facility to the leftmost agent 1, and lj2 = arg minlj 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, deﬁne δ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 by M2) 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. City U 11205619) and was partially sponsored by Project 11771365 supported by NSFC.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

[Amanatidis et al., 2017] Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis. On budget-feasible mechanism design for symmetric submodular objectives. In International Conference on Web and Internet Economics, pages 1 15, 2017.

[Archer and Tardos, 2001] Aaron Archer and Eva Tardos. Truthful mechanisms for one-parameter agents. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 482 491, 2001. [Aziz et al., 2019] Haris Aziz, Hau Chan, Barton E. Lee, and David C. Parkes. The capacity constrained facility location problem. In International Conference on Web and Internet Economics, page 336, 2019. [Babaioff et al., 2016] Moshe Babaioff, Moran Feldman, and Moshe Tennenholtz. Mechanism design with strategic mediators. ACM Transactions on Economics and Computation (TEAC), 4(2):1 48, 2016. [Bei et al., 2012] Xiaohui Bei, Ning Chen, Nick Gravin, and Pinyan Lu. Budget feasible mechanism design: from prior-free to bayesian. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, pages 449 458, 2012. [Chen et al., 2011] Ning Chen, Nick Gravin, and Pinyan Lu. On the approximability of budget feasible mechanisms. In Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 685 699, 2011. [Chen et al., 2018] Xujin Chen, Xiaodong Hu, Xiaohua Jia, Minming Li, Zhongzheng Tang, and Chenhao Wang. Mechanism design for two-opposite-facility location games with penalties on distance. In International Symposium on Algorithmic Game Theory, pages 256 260, 2018. [Chen et al., 2019] Xujin Chen, Minming Li, Changjun Wang, Chenhao Wang, and Yingchao Zhao. Truthful mechanisms for location games of dual-role facilities. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, pages 1470 1478, 2019. [Cheng et al., 2013] Yukun Cheng, Wei Yu, and Guochuan Zhang. Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theoretical Computer Science, 497:154 163, 2013. [Feldman and Wilf, 2013] Michal Feldman and Yoav Wilf. Strategyproof facility location and the least squares objective. In Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pages 873 890, 2013. [Fong et al., 2018] Chi Kit Ken Fong, Minming Li, Pinyan Lu, Taiki Todo, and Makoto Yokoo. Facility location games with fractional preferences. In Proceedings of the 32th AAAI Conference on Artiﬁcial Intelligence (AAAI), pages 1039 1046, 2018. [Fotakis and Tzamos, 2014] Dimitris Fotakis and Christos Tzamos. On the power of deterministic mechanisms for

facility location games. ACM Transactions on Economics and Computation, 2(4):15, 2014. [Khalilabadi and Tardos, 2018] Pooya Jalaly Khalilabadi and Eva Tardos. Simple and efﬁcient budget feasible mechanisms for monotone submodular valuations. In International Conference on Web and Internet Economics, pages 246 263, 2018. [Leonardi et al., 2017] Stefano Leonardi, Gianpiero Monaco, Piotr Sankowski, and Qiang Zhang. Budget feasible mechanisms on matroids. In International Conference on Integer Programming and Combinatorial Optimization, pages 368 379, 2017. [Lu et al., 2010] Pinyan Lu, Xiaorui Sun, Yajun Wang, and Zeyuan Allen Zhu. Asymptotically optimal strategy-proof mechanisms for two-facility games. In Proceedings of the 11th ACM Conference on Electronic Commerce, pages 315 324, 2010. [Myerson, 1981] Roger B Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58 73, 1981. [Nisan and Ronen, 2001] Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1-2):166 196, 2001. [Nisan et al., 2007] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. Algorithmic game theory. Cambridge University Press, 2007. [Procaccia and Tennenholtz, 2009] Ariel D Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. In Proceedings of the 10th ACM Conference on Electronic Commerce, pages 177 186, 2009. [Seraﬁno and Ventre, 2015] Paolo Seraﬁno and Carmine Ventre. Truthful mechanisms without money for nonutilitarian heterogeneous facility location. In Proceedings of the 29th Conference on Artiﬁcial Intelligence (AAAI), pages 1029 1035, 2015. [Singer, 2010] Yaron Singer. Budget feasible mechanisms. In Proceedings 51st IEEE Symposium on Foundations of Computer Science, pages 765 774, 2010. [Wada et al., 2018] Yuho Wada, Tomohiro Ono, Taiki Todo, and Makoto Yokoo. Facility location with variable and dynamic populations. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, pages 336 344, 2018. [Yao, 1977] Andrew Chi-Chin Yao. Probabilistic computations: Toward a uniﬁed measure of complexity. In Proceedings 18th IEEE Symposium on Foundations of Computer Science, pages 222 227, 1977. [Yuan et al., 2016] Hongning Yuan, Kai Wang, Ken CK Fong, Yong Zhang, and Minming Li. Facility location games with optional preference. In Proceedings of the Twenty-second European Conference on Artiﬁcial Intelligence, pages 1520 1527, 2016.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)