# facility_location_games_with_entrance_fees__95845df7.pdf

Facility Location Games with Entrance Fees

Mengfan Ma, Mingyu Xiao , Tian Bai, Bakh Khoussainov

School of Computer Science and Engineering, University of Electronic Science and Technology of China mengfanma1@gmail.com, myxiao@uestc.edu.cn, tian.bai.cs@outlook.com, bmk@uestc.edu.cn

The facility location game is an extensively studied problem in mechanism design. In the classical model, the cost of each agent is her distance to the nearest facility. In this paper, we consider a novel model where each facility charges an entrance fee, which is a function of the facility s location. Thus, the cost of each agent is the sum of the distance to the facility and the entrance fee of the facility. The generalized model captures more real-life scenarios. In our model, the entrance fee function can be an arbitrary function, and the corresponding preferences of agents may not be single-peaked anymore: this makes the problem complex and requires new techniques in the analysis. We systematically study the model and design strategyproof mechanisms with nice approximation ratios and also complement these with nearly-tight impossibility results. Specifically, for one-facility and two-facility games, we provide upper and lower bounds for the approximation ratios given by deterministic and randomized mechanisms, with respect to the utilitarian and egalitarian objectives. Most of our bounds are tight, and these bounds are independent of the entrance fee functions. Our results also match the results of the classical model.

Introduction Facility location games on real line. In one-dimensional facility location problem, agents are located on real line, and a planner is to build facilities on the line to serve the agents. The cost of an agent is her distance to the nearest facility. The problem asks for facility locations that minimize the total cost of all agents (the utilitarian objective) or the maximum cost among all agents (the egalitarian objective). It is well-known that both optimization problems can be solved in polynomial time. Over the past decade, these problems have been intensively studied from the perspective of mechanism design. A key conversion in the models is that now each agent becomes strategic and may misreport her position to decrease her cost. These new problems are called the facility location games, which require to design mechanisms that truthfully elicit the positions of agents and (approximately) minimize the objective of total or maximum cost. The seminal work of Procaccia and Tennenholtz (2009) initiates the study of mechanism design without money for

Corresponding author Copyright c 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

the facility location game. They study strategyproof mechanisms for one-facility and two-facility games through the lens of approximation ratio of the objective. Since then, the facility location game has become one of the main playgrounds for approximate mechanism design without money and has attracted numerous follow-up research (Lu, Wang, and Zhou 2009; Lu et al. 2010; Fotakis and Tzamos 2014). As shown by Fotakis and Tzamos (2014), when there are more than two facilities, no deterministic strategyproof mechanism can achieve a bounded approximation ratio. The current status of the classical facility location games on the real line with one or two facilities is summarized in Table 1. After the introduction of the classical facility location game, many variants have been studied flourishingly to accommodate more practical scenarios. The recent survey by Chan et al. (2021) depicts the state of the art. Here, we mention some of the models: obnoxious facility games where every agent wants to stay away from the facility (Cheng, Yu, and Zhang 2013); heterogeneous facility games where the acceptable set of facilities for each agent could be different (Li et al. 2020; Deligkas, Filos-Ratsikas, and Voudouris 2022); the games with different objectives or purposes (Cai, Filos-Ratsikas, and Tang 2016); the game with capacitated facilities (Aziz et al. 2020a,b; Walsh 2022); extensions to trees, and other graphs (Alon et al. 2010); and so on.

Facility location games with entrance fees. In all the above models, the cost of an agent is measured by her distance to the closest facility. This cost can be considered as the travel fee. In innumerable real-life scenarios, except for the travel fee, the agent may also need to pay a service or entrance fee to the facility, such as tickets for swimming pools and museums. The entrance fees may differ for facilities in different positions. An immediate example is that the cost to build a facility in downtown would be more expensive than in the suburbs. The entrance fee of the facility is decided by the building cost and thus also decided by the position where the facility is built. Another example is that the environment around the facility may have an impact on the entrance fee. For example, the entrance fee of a facility in a popular scenic spot can be higher than the entrance fee of the same facility in a desolate place. Various non-geographical settings also fit in the location-dependent entrance fee model: (1) The voters have a single-peaked preference over the

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

Total cost Maximum cost Upper bounds Lower bounds Upper bounds Lower bounds

Deterministic Mechanisms

Onefacility

1 (Procaccia et al. 2009)

1 (Procaccia et al. 2009) 2 (Procaccia et al. 2009)

2 (Procaccia et al. 2009)

Twofacility

n 2 (Procaccia et al. 2009)

n 2 (Fotakis and Tzamos 2014)

Randomized Mechanisms

Onefacility

1 (Procaccia et al. 2009)

1 (Procaccia et al. 2009)

3/2 (Procaccia et al. 2009) 3/2 (Procaccia et al. 2009)

Twofacility

4 (Lu et al. 2010)

1.045 (Lu et al. 2010)

5/3 (Procaccia et al. 2009)

Table 1: Upper and lower bounds for the approximation ratios of strategyproof mechanisms in the classical model.

Total cost Maximum cost Upper bounds Lower bounds Upper bounds Lower bounds

Deterministic

Onefacility

3 4 re+1 ( Thm. 2)

r2e+10re 7 ( Thm. 3)

2, if re 2 3 2 re , if re > 2

(Thm. 7 and Prop. 4)

2, if re 6 3 28

r2e+20re 12+re+10, if re > 6

( Thms. 8 and 9) ( Props. 5 and 6) Twofacility

n 2 ( Prop. 3)

n 2 if re = 1 (Fotakis and Tzamos 2014)

Onefacility

n ( Thm. 4)

2)re 2, if re <+ 2, if re =+ (Thms. 5 and 6) 2 if re = + ( Thm. 10 and Prop. 7)

Twofacility

n 2 ( Prop. 3)

1.045 if re = 1 (Lu et al. 2010)

Table 2: Upper and lower bounds for the approximation ratios of strategyproof mechanisms in our model, where re is the ratio of the maximum value to the minimum value of entrance fee function e( ). Theorems and propositions in bold are our results.

potential candidates, while after the election, the winning candidates will enforce their own tax policy on the voters. (2) The students in a classroom may need to decide the air conditioner s temperature. The electricity bill, which depends on the temperature, is then evenly divided among the students, which may be different for different temperature settings and can be considered as the entrance fee.

All of the above motivate us to initiate the study of the facility location games with entrance fees. In our setting, the planner needs to locate a given number of facilities on real line to serve agents on the line. Each facility, once located, has an entrance fee determined by its location. The cost of an agent is the sum of the travel fee (distance to the facility) and the entrance fee of the facility. Each agent will use one facility at a minimum cost. The position of each agent is private information. We want to design strategyproof mechanisms that guarantee that the agents report their true positions, and locate the facilities based on the reports such that either the

total or the maximum cost approximates the optimal value of the corresponding optimization problem as closely as possible. Figure 1 illustrates the concept of entrance fee function.

Our contribution. We investigate the facility location games with entrance fees. The main contributions are summarized in Table 2. We explain our contributions regarding the problem setting, results, and technical challenges. 1. We initiate the study of facility location games with entrance fees. In our model, the entrance fee function is arbitrary and part of the input. Different entrance fee functions can lead to different preferences of agents beyond single-peakedness (Moulin 1980; Barber a, Gul, and Stacchetti 1993). We stress that almost all mechanisms for the classical model are no longer strategyproof under our setting. These give rise to new challenges. Also, note that the idea of adding entrance fees can be applied to most of the previous variants of the problem, thus expanding research in this area.

𝑥𝑥𝑖𝑖 ℓ |𝑥𝑥𝑖𝑖 ℓ|

entrance fee function 𝑒𝑒( )

Figure 1: The concept of the entrance fee function. The three black dots are agents. The vertical axis stands for the value of entrance fee. The curve depicts an entrance fee function e : R R 0 {+ }. If the facility is located at ℓ, the entrance fee is e(ℓ) and the cost of agent i is |ℓ xi| + e(ℓ).

2. Our mechanisms are simple, but their analyses require new ideas and techniques. When the entrance fee is always 0, our model becomes the classical model. Thus, our mechanisms must also imply the mechanisms for the classical model. Some of our mechanisms are natural extensions of the standard ones. However, the analyses of strategyproofness and the approximation ratios require new insights. For instance, for strategyproofness, we consider the optimal location for each agent as the facility location that minimizes her cost and design mechanisms over the space of optimal locations of agents instead of their positions. These new locations must satisfy an important monotonicity property. The proofs of approximation ratios use new technical concepts such as domination and virtual facility. 3. We provide new lower bounds. The lower bounds for the classical model are also valid in our model since the classical model is a special case of our model. However, for most cases, we establish new and better bounds. The techniques to obtain lower bounds are new and different from that of the standard model due to the presence of entrance fees. Our lower bounds are tight for many cases (See Table 2). The rest of the paper is organized as follows. Section presents the formal definitions of our model. In Section , we derive some useful technical properties. Sections and present our main results for the one-facility game with the objectives of total cost and of maximum cost, respectively. In Section , we extend our results from one-facility games to two-facility games. Some conclusions are drawn in Section . The proofs of statements marked with are omitted here, which can be found in the full version of the paper.

Let N = {1, . . . , n} be a set of agents on real line R. Let xi be the location of agent i. The location profile of all agents is the vector x = (x1, , xn). We assume agents are ordered such that x1 xn. We need to build m facilities on R to serve the agents. If we put facility j at location ℓj, then this gives us the facilities location profile ℓ= (ℓ1, , ℓm).

If an agent i is served by a facility j, then the agent bears a travel fee measured by the distance |xi ℓj|. Furthermore, each facility charges its customers an entrance fee determined by its location. Formally, there is an entrance fee

function e : R R 0 {+ } 1. The entrance fee of the facility at location ℓis e(ℓ). So if an agent i selects facility j, the cost incurred by the agent is the sum: |xi ℓj| + e(ℓj). For an entrance fee function e, let emax = maxx R e(x) and emin = minx R e(x). The max-min ratio of e, denoted by re, is defined as re = 1 if emin = emax; re = + if emin = 0 and emax > 0; re = emax/emin otherwise. Each agent always selects a facility that minimizes the sum of her travel fee and entrance fee. So, we define the cost of agent i for a given facility location profile ℓas cost(xi, ℓ) := minℓ ℓ{|xi ℓ| + e(ℓ)}. If there is more than one facility that minimizes the agent s cost, we use the following tie-breaking rule: Definition 1 (Tie-breaking rule). Select the facility with the smallest entrance fee. If there are two such facilities with equal smallest entrance fees, select the rightmost one. We consider two classical objectives: the utilitarian objective and egalitarian objective. For utilitarian objective, we want to minimize the total cost of all agents that we denote by: TC(x, ℓ) = Pn i=1 cost(xi, ℓ). For egalitarian objective, we want to minimize the maximum cost of all agents that is denoted by MC(x, ℓ) = maxi N{cost(xi, ℓ)}. Remark 1. To keep our exposition as general as possible, we assume that there is an oracle that computes e(x) for a given x R, and for any integers a and b, finds the minimum of ae(x) + bx in a given interval. In the setting of mechanism design, each agent i s location xi is private. An agent reports a location x i that may differ from her true position. A (deterministic) mechanism outputs a facility location profile ℓbased on e and the reported location profile x = (x 1, , x n). Definition 2 (Deterministic mechanisms). A deterministic mechanism is a function f( , ) : E Rn Rm, where E is the set of all entrance fee functions e : R R 0. Moreover, for a given entrance fee function e, a deterministic mechanism is a function f(e, ) : Rn Rm. Not only we consider general mechanisms f( , ) taking the entrance fee function as a part of the input but also consider mechanisms f(e, ) for a given entrance fee function e. For e( ) = 0, mechanism f(e, ) is for the classical model. Let α 1 and E(α) := {e E|re = α}. We will also consider mechanisms under the constraint that the entrance fee function is within E(α), i.e., f( , ) : E(α) Rn Rm. Definition 3 (Randomized mechanisms). A randomized mechanism is a function f( , ) : E Rn (Rm), where E is the set of all entrance fee functions e : R R 0 and (Rm) is the set of all probability distributions over Rm. For a given e and a randomized mechanism f( , ), the cost of an agent i N is defined as the expected cost of i, i.e., cost(xi, f(e, x)) := Eℓ f(e,x)cost(xi, ℓ). Note that the number of facilities m and the entrance fee function e are publicly known. Given that an agent might misreport her location to decrease her cost, it is necessary to design (group) strategyproof mechanisms.

1Note that in our definition, a location s entrance fee can be + . This is justified by scenarios where such a location exists: the planner will never build a facility at it, or no agents will select it.

Definition 4 (Group strategyproof). A mechanism f( , ) is group strategyproof if for any entrance fee function e, any profile x, any coalition S N with any sub-location profile x S R|S|, there exists an agent i S such that cost(xi, f(e, x)) cost(xi, f(e, x )), where x = (x S, x S) is obtained from x by replacing the location profile of all agents in S with x S. In above definition, if S only contains one agent, then the definition is referred to as strategyproof. (Group) strategyproof mechanisms may not be able to achieve the optimal value for one of the two objectives. Thus we use approximation ratio to evaluate the performance of the mechanism. For an entrance fee function e and location profile x Rn, let OPTtc(e, x) and OPTmc(e, x) be the optimal total cost and maximum cost of the optimization problems, respectively. Definition 5 (Approximation ratio). For an entrance fee function e and location profile x, the approximation ratio of f(e, x) is γ(f(e, x)) := TC(x, f(e, x))/OPTtc(e, x), the approximation ratio of f(e, ) is defined as γ(f(e, )) := supx γ(f(e, x)), and the approximation ratio of f( , ) is defined as γ(f( , )) := supe E γ(f(e, )). The approximation ratio for the maximum cost is defined in the same way by replacing TC(x, f(e, x))/OPTtc(e, x) with MC(x, f(e, x))/OPTmc(e, x).

Structural Properties Monotone and Local Properties Given an entrance fee function e : R R 0 and an agent s position x R, let x be the facility location that minimizes the cost of the agent, i.e., x := arg minℓ R(|x ℓ|+e(ℓ)). If multiple locations minimize the cost, we use the tie-breaking rule in Definition 1. We call x the optimal location for x, and Ci := cost(xi, x i ) the optimal cost for the agent i. To find x for x, the definition asks to search the whole real line. If the facility is at x, the cost for the agent is e(x). So the optimal cost of x is at most e(x). Then the global search for x can be reduced to a local search in the neighborhood of x: x = arg minℓ:|ℓ x| e(x) |ℓ x|+e(ℓ). Then by Remark 1, x can be obtained in a constant time. Next, we derive an important property of x . Lemma 1 (Monotonicity). For any xi, xj R, we have x i x j if and only if xi xj.

Let I[x] be the closed interval between x and x . The next lemma depicts the relationship between different I[x]. Lemma 2. Either I[xi] I[xj] = or x i = x j. By Lemmas 1 and 2, we can prove the following property for three positions. Lemma 3. If xi xj xk, then cost(xi, x j) cost(xi, x k). Symmetrically, cost(xk, x j) cost(xk, x i ). Next, we capture the property that one location is preferred by each agent over another location. Definition 6 (Domination). Location ℓ1 dominates location ℓ2 if cost(xi, ℓ1) cost(xi, ℓ2) for all i N. Lemma 4. For any x R, x dominates all locations in I[x].

Solving the Optimization Problems By the Monotonicity Lemma, x 1 x n. For m = 1, let ℓtc be the location that minimizes the total cost, i.e., ℓtc = arg minℓ R TC(x, ℓ). If there are multiple solutions, then we use the tie-breaking rule from Definition 1. Define ℓmc as the location that minimizes the maximum cost similarly. Lemma 5. ℓtc and ℓmc are within the interval [x 1, x n]. We want to design effective algorithms that find the optimal facility location profile for either objective when the location profile of agents is given. Lemma 6. When only one facility exists, the two optimization problems can be solved in O(n) time. When m > 1, we have the following lemma that describes the structure of a solution. Lemma 7. For a given facility location profile, if two agents select the same facility, then any agent located between these two agents also selects the same facility. Equipped with Lemmas 5, 6 and 7, we can, in polynomial time, find the optimal values of the optimization problems for m > 1. Proposition 1. For the general m number of facilities, the two optimization problems can be solved in O(n3m) time.

Utilitarian Version With One Facility In this section, we study the one-facility game with the objective of minimizing the total cost. We will first investigate upper and lower bounds for deterministic mechanisms and then turn our attention to randomized mechanisms.

Deterministic Mechanisms Recall that it is assumed that x1 xn, and for any i N, we denote by mi( , ) the mechanism that outputs the optimal location x i for agent whose location is xi. Theorem 1. Mechanism mi( , ) is group strategyproof. Let mmed( , ) be the mechanism that always outputs the optimal location x med for the median agent med = n/2 . Let x Rn, ℓ R and eℓ R 0. To ease our analysis of the approximation ratio of mmed( , ) for the total cost, we introduce the notion of virtual total cost V T(x, ℓ, eℓ) := P i N |xi ℓ| + n eℓ, which is the total cost of x when a virtual facility is located at ℓwith entrance fee eℓ. It is possible eℓ = e(ℓ). When eℓ= e(ℓ), we have V T(x, ℓ, eℓ) = TC(x, ℓ). The virtual cost of agent i with respect to the virtual facility is vcost(xi, ℓ, eℓ) := |xi ℓ| + eℓ. Clearly, vcost(xi, ℓ, e(ℓ)) = cost(xi, ℓ) when eℓ= e(ℓ). Observation 1. Let x Rn, ℓ1, ℓ2 R and e1, e2 R 0 such that e1 < e2. If ℓ2 ℓ1 xmed or xmed ℓ1 ℓ2, then V T(x, ℓ1, e1) < V T(x, ℓ1, e2) V T(x, ℓ2, e2). Next, we show that the total cost approximation ratio of mmed( , ) can be bounded by a constant. Theorem 2. For each entrance fee function e with max-min ratio re, the approximation ratio of mmed(e, ) for the total cost is at most 3 4 re+1. Hence, the approximation ratio of mmed( , ) for the total cost is at most 3.

Proof. Assume w.l.o.g. that xmed x med. Denote by Cmed the optimal cost of the median agent. Let xi R be an arbitrary agent position. If xi xmed, we have cost(xi, x med)= vcost(xi, xmed, Cmed). If xi > xmed, by Lemma 4 we have cost(xi, x med) vcost(xi, xmed, Cmed). Thus TC(x, x med) V T(x, xmed, Cmed). (1) Next we prove e(ℓtc) Cmed. Suppose for contradiction that e(ℓtc) > Cmed. Then by Observation 1 and (1), we have TC(x, ℓtc) > V T(x, xmed, Cmed) TC(x, x med). This is a contradiction. Hence, there is a location ℓ tc between xmed and ℓtc such that vcost(xmed, ℓ tc, e(ℓtc)) = Cmed. Then we have |xmed ℓ tc| = Cmed e(ℓtc) . Let = |Cmed e(ℓtc)|. By Observation 1, we have TC(x, ℓtc) V T(x, ℓ tc, e(ℓtc)). Together with (1), we have

γ(mmed(e, x)) V T(x, xmed, Cmed)

V T(x, ℓ tc, e(ℓtc)) . (2)

We will identify a location profile x Rn for each x such that the bound given by (2) for x is no greater than that for x . Let n1 = |{i N|xi xmed < ℓ tc or xi xmed ℓ tc}| and n2 = n n1. Thus n1 n2. Let x be the profile where n1 agents are at xmed and the rest are at ℓ tc. By (2),

γ(mmed(e, x)) V T(x , xmed, Cmed)

V T(x , ℓ tc, e(ℓtc))

= (Cmed + ) n2

n1 + Cmed e(ℓtc) n2

n1 + Cmed . (3)

Since Cmed + e(ℓtc) and n2/n1 1, we know that (3) is maximized when n1 = n2. Then since emin e(ℓtc) Cmed emax, we have γ(mmed(e, x)) 2Cmed+ Cmed+e(ℓtc) 3 4 re+1. This proves the first claim of the theorem. The second claim follows immediately.

We illustrate in the full version of the paper the approximation ratio of 3 is tight for the mechanism mmed( , ). Next, we establish a lower bound of 3 for the total cost approximation ratio against all deterministic strategyproof mechanisms. Thus we can assert that no deterministic strategyproof mechanism can do better than mmed( , ). Theorem 3. For any given α 1, there exists an entrance fee function e with max-min ratio re = α such that no deterministic strategyproof mechanism f(e, ) : Rn R can achieve an approximation ratio less than 3 16 re+5+

r2 e+10re 7 for the total cost. Hence, no deter-

ministic strategyproof mechanism f( , ) : E Rn R can achieve a total cost approximation ratio less than 3.

Proof. Let d > 0 and D = d + 1 + (2d + 1) 1. Consider the entrance fee function e: e(ℓ)=d if ℓ= 1 and e(ℓ)=D for any ℓ = 1. Let f(e, ): Rn R be a deterministic strategyproof mechanism. Let x1 = ( 1, ϵ), x2 = ( ϵ, 1) and x3 = ( 1, 1) be three location profiles, where ϵ is a small positive. We illustrate this example in Figure 2. First, we consider profile x1. We have

TC(x1, ℓ) =

2d + 1 + ϵ, if ℓ= 1 2d + 3 ϵ, if ℓ= 1 |ℓ+ 1| + |ℓ ϵ| + 2D, otherwise .

Figure 2: The definitions of e( ), x1, x2 and x3. The red triangles denote facilities, and the dashed line represents the deviation of the agent.

When ℓ = 1, we have TC(x1, ℓ) = |ℓ+1|+|ℓ ϵ|+2D 2d+3. Thus OPTtc(e, x1) = 2d+1+ϵ. Assume, for contradiction, that γ(f(e, )) < (2d + 3 ϵ)/(2d + 1 + ϵ). Then we have TC(x1, f(e, x1)) γ(f(e, )) OPTtc(e, x1) < 2d+3 ϵ. Thus TC(x1, f(e, x1)) must be 2d+1+ϵ. Then we have f(e, x1) = 1 and cost(ϵ, f(e, x1)) = d + 1 + ϵ. By the symmetry between profiles x1 and x2, we have f(e, x2) = 1 and cost( ϵ, f(e, x2)) = d + 1 + ϵ. Now consider profile x3. We have TC(x3, ℓ) = 2d + 2 if ℓ= 1 and TC(x3, ℓ) = |ℓ+ 1| + |ℓ 1| + 2D if ℓ = 1. Thus, we have OPTtc(e, x3) = 2d + 2. By our assumption and the definition of D, we have γ(f(e, x3)) < (2d + 3)/(2d + 1) = (2D + 2)/(2d + 2). Since|ℓ+ 1| + |ℓ 1| + 2D 2D + 2, TC(x3, f(e, x3)) must be 2d + 2. Thus f(e, x3) = 1. If f(e, x3) = 1, then the agent at ϵ in x2 can deviate to 1 and decrease her cost from d+1+ϵ to d+1 ϵ, a contradiction. If f(e, x3) = 1, then the agent at ϵ in x1 can deviate to 1 and decrease her cost from d + 1 + ϵ to d + 1 ϵ, a contradiction. Due to the arbitrariness of ϵ > 0, we have γ(f(e, )) (2d + 3)/(2d + 1). Observing that re = 1+(2d + 2)/(2d2 + d), the desired result follows after simple computation.

Randomized Mechanisms For any input e and x, our randomized mechanism, denoted by r( , ), outputs each x i with probability 1/n for i N. Recall that for any even n, the approximation ratio of the deterministic mechanism mmed( , ) is exactly 3. Next we show that the randomized mechanism r( , ) can achieve a better approximation ratio of 3 2/n. Theorem 4. The mechanism r( , ) is strategyproof and achieves an approximation ratio of 3 2/n for the total cost. The approximation ratio is tight for this mechanism. Next, we establish a lower bound for the approximation ratio against all randomized strategyproof mechanisms. Theorem 5. There is an entrance fee function e with re = + so that no randomized strategyproof mechanism f(e, )

can achieve a total cost approximation ratio less than 2.

Proof. Consider the following entrance fee function e: e(ℓ) = 0 if ℓ= 1 and e(ℓ) = + for any ℓ = 1. Let f(e, ) : Rn (R) be a randomized strategyproof mechanism. To achieve a bounded total cost approximation ratio, it holds that Pr[f(e, x) = 1] + Pr[f(e, x) = 1] = 1 for any profile x Rn. Let x1 = ( 1, ϵ), x2 = ( ϵ, 1) and x3 = ( 1, 1) be three location profiles, where ϵ (0, 1) is a small positive. Let Pr[f(e, x1) = 1] = p and Pr[f(e, x2) = 1] = p . TC(x1, 1) = 1 + ϵ is the optimal total cost and TC(x1, 1) = 3 ϵ. Thus, the approximation ratio of f for x1 is γ(f(e, x1)) = 1 p + p (3 ϵ)/(1 + ϵ). Now consider the case that the agent at ϵ in x1 deviates to 1. Since this agent prefers location 1 to location 1, by the strategyproofness of f(e, ), we must have Pr[f(e, x3) = 1] p. Then consider the case that the agent at ϵ in x2 deviates to 1, again by the strategyproofness of f(e, ), we must have Pr[f(e, x3) = 1] p . Thus p + p Pr[f(e, x3) = 1] + Pr[f(e, x3) = 1] = 1. Without loss of generality, we assume p 1/2. Then we have γ(f(e, )) γ(f(e, x1)) 2/(1 + ϵ).

Thus, for n = 2, our randomized mechanism r( , ) achieves the best possible approximation ratio. Note that the max-min ratio in the above proof is + . Thus we can safely assume that the probability distribution of the mechanism is discrete. However, when the max-min ratio is finite, this assumption does not hold, and we have to deal with continuous distributions. In the following theorem, we show that we can discretize continuous distributions using the first mean-value theorem for integrals and establish a lower bound against all the entrance fee functions of a given max-min ratio. Theorem 6. For any α 1, there exists an function e with max-min ratio re = α such that no randomized strategyproof mechanism f(e, ):Rn (R) can achieve a total cost approximation ratio less than

Egalitarian Version with One Facility Now we study strategyproof mechanisms that approximate the maximum cost. Our mechanism is m1( , ), which outputs x 1 for a given function e and a location profile x. Theorem 7. For each entrance fee function e with max-min ratio re, the approximation ratio of m1(e, ) for the maximum cost is

( 2, if re 2 3 2

re , if re > 2 .

Hence, the approximation ratio of m1( , ) for the maximum cost is at most 3.

Proof. Given x Rn. Recall that ℓmc is the location that achieves the optimal maximum cost. Then OPTmc(e, x) = max{cost(x1, ℓmc), cost(xn, ℓmc)}. Let t {1, n} be the agent such that cost(xt, ℓmc) = OPTmc(e, x). Let ℓcen = (x1 + xn)/2 be the center of x. Assume a virtual facility is located at ℓcen with entrance fee E such that OPTmc(e, x) = vcost(xt, ℓcen, E) = L/2 + E. Then we

have E = |ℓcen ℓmc| + e(ℓmc) and E e(ℓmc) emin. Let L = |xn x1|. By MC(x, f(e, x)) L + C1 we get

γ(m1(e, x)) L + C1

L/2 + E = 2 + C1 2E

L/2 + E . (4)

Besides, due to C1 cost(x1, ℓmc) cost(xt, ℓmc), we have L 2C1 2E, and E C1 L/2 equivalently. If re 2, because C1 e(x1) emax and E emin, we have C1/E re 2. Then by (4), we get γ(m1(e, )) 2. For the case that re > 2, we divide all location profiles into two subcases based on L and C1. Subcase 1: L < C1. Considering E C1 L/2, by (4), we get γ(m1(e, x)) (L + C1)/(L/2 + C1 L/2) 2. Subcase 2: L C1. If C1 < 2E, we have γ(m1(e, x)) < 2 by (4). If C1 2E, then L > 2C1 2E C1. Let L = 2C1 2E in (4), and then we get γ(m1(e, x)) 3 2E/C1 Since C1/E re, we get γ(m1(e, x)) 3 2/re. When re > 2, we have (3 2/re) > 2. Thus we have γ(m1(e, x)) 3 2/re if re > 2. Together with the case that re 2, we get the desired result.

In the full version of the paper, we show the approximation ratio in this theorem is tight for the mechanism m1(e, ). Procaccia et al. (2013) proved that when e( ) = 0, no deterministic strategyproof mechanism can achieve a maximum cost approximation ratio smaller than 2. We extend this bound to a wider range of entrance fee functions. Theorem 8. For any given α 1, there exists an entrance fee function e with max-min ratio re = α such that no deterministic strategyproof mechanism f(e, ) : Rn R can achieve an approximation ratio for the maximum cost less than 2. This also implies that no deterministic strategyproof mechanism f( , ) : E(α) Rn R can achieve an approximation ratio for the maximum cost less than 2. By Theorems 7 and 8, we can conclude that for entrance fee functions with max-min ratio α 2, no strategyproof mechanism f( , ) : E(α) Rn R can do better than m1( , ). Next, when α 6, we establish a tighter lower bound for the maximum cost approximation ratio against all strategyproof mechanisms f( , ):E(α) Rn R. Theorem 9. For any α 1, there exists an entrance fee function e with max-min ratio re = α such that no deterministic strategyproof mechanism f(e, ) : Rn R can achieve a maximum cost approximation ratio less than 3 28

r2 e+20re 12+re+10. This also implies that no deter-

ministic strategyproof mechanism f( , ) : E Rn R can achieve a maximum cost approximation ratio less than 3.

Proof. Let d be a positive and D = d + 3 + 4(d + 1) 1. Consider the following entrance fee function e: e(ℓ) = d if ℓ= 1 and e(ℓ)=D for any ℓ = 1. Let f(e, ) : Rn R be a deterministic strategyproof mechanism. Let x1 = ( ϵ, 2), x2 = ( 2, ϵ) and x3 = ( 2, 2) be three location profiles, where ϵ (0, 1) is a small positive number. First we consider the profile x1, we have

MC(x1, ℓ) =

d + 3, if ℓ= 1 d + 1 + ϵ, if ℓ= 1 D + max{|ℓ 2|, |ℓ+ ϵ|}, otherwise .

Thus OPTmc(e, x1) = d + 1 + ϵ. Assume for contradiction that γ(f(e, )) < (d + 3)/(d + 1 + ϵ). Thus, it holds that

MC(x1, f(e, x1)) γ(f(e, )) OPTmc(e, x1) < d + 3 < D + max{|ℓ 2|, |ℓ+ ϵ|}.

Then MC(x1, f(e, x1)) must be d+1+ϵ. Thus f(e, x1) = 1 and cost( ϵ, f(e, x1)) = d + 1 + ϵ. By the symmetry between profiles x1 and x2, we can get f(e, x2) = 1 and cost(ϵ, f(e, x2)) = d + 1 + ϵ. Next we consider profile x3.

MC(x3, ℓ) = d + 3, if ℓ= 1 D + max{|ℓ 2|, |ℓ+ 2|}, otherwise .

By our assumption we have γ(f(e, )) < (d + 3)/(d + 1) = (D + 2)/(d + 3), which implies that f(e, x3) = 1. If f(e, x3) = 1, then the agent at ϵ in x2 can deviate to 2 and decrease her cost from d+1+ϵ to d+1 ϵ, a contradiction. If f(e, x3) = 1, then the agent at ϵ in x1 can deviate to 2 and decrease her cost from d+1+ϵ to d+1 ϵ, a contradiction. Due to the arbitrariness of ϵ > 0, we know that the total cost approximation ratio is no less than (d + 3)/(d + 1). Observing that re = 1 + (3d + 7)/(d2 + d), we can get the desired result by simple computation.

Lower bound for randomized mechanisms. We also obtain the following result on randomized mechanisms.

Theorem 10. There is an e( ) with re = + such that no randomized strategyproof mechanism f(e, ) can achieve a maximum cost approximation ratio less than 2.

Mechanisms with Two Facilities In this section, we investigate two-facility games. A mechanism is now a function f( , ) : E Rn R2, that given e and x, returns the facility location profile ℓ R2. Recall for ℓ= (ℓ1, ℓ2), the agent i selects the facility with smallest sum of travel and entrance fees. Thus, cost(xi, ℓ) = min{|ℓ1 xi| + e(ℓ1), |ℓ2 xi| + e(ℓ2)}.

Utilitarian Version with Two Facilities Let i, j N with i j. Denote by mi,j( , ) : Rn R2 the mechanism that puts one facility in x i and the other facility in x j for any input e and x.

Proposition 2. mi,j( , ) is group strategyproof.

When e( ) = 0, Fotakis and Tzamos (2014) prove that any deterministic strategyproof mechanism with bounded approximation ratio (for either of the objectives) must put facilities on x1 and on xn. Thus we only consider the mechanism m1,n( , ). The following result shows that the total cost approximation ratio of m1,n( , ) matches the lower bound of n 2 in the classical model.

Proposition 3. The approximation ratio of m1,n( , ) for the total cost is at most n 2.

Egalitarian Version with Two Facilities Our mechanism for the maximum cost objective is also m1,n( , ). We can show that the approximation ratio of m1,n( , ) for the maximum cost is the same as m1( , ).

Proposition 4. For each entrance fee function e with max-min ratio re, the approximation ratio of m1,n(e, ) for the maximum cost is

γ(m1,n(e, ))

( 2, if re 2 3 2

re , if re > 2 .

Hence, the approximation ratio of m1,n( , ) for the maximum cost is at most 3.

The following proposition obtains a similar lower bound for all deterministic strategyproof mechanisms as in Theorem 8.

Proposition 5. For any α 1, no deterministic strategyproof mechanism f( , ) : E(α) Rn R2 can achieve a maximum cost approximation ratio less than 2.

By a similar argument of this proposition, we can establish a lower bound against all deterministic strategyproof mechanisms as in Theorem 9.

Proposition 6. For any α 1, there exists an entrance fee function e with max-min ratio re = α such that no deterministic strategyproof mechanism f(e, ) : Rn R2 can achieve a maximum cost approximation ratio less than 3 28

r2 e+20re 12+re+10. This implies that no deterministic

strategyproof mechanism f( , ) : E Rn R2 can achieve a maximum cost approximation ratio less than 3.

Lower bound for randomized mechanisms. Next, we show that the lower bound of 2 in Theorem 10 for the onefacility game also holds for the two-facility game.

Proposition 7. There is an e( ) with re = + such that no randomized strategyproof mechanism f(e, ) can achieve a maximum cost approximation ratio less than2.

This paper presents an interesting extension of the classical facility location game on the real line. Our model introduces entrance fee functions, thus naturally enhancing the classical model. Not only this model is a new extension but also it brings in an idea of revisiting the existing facility location games, such as capacitated facilities (Aziz et al. 2020a), heterogeneous facilities (Li et al. 2020) and so on. This model is a more realistic fit in many application scenarios. The entrance fee function in our settings is arbitrary, and the preferences of agents may not be single-peaked. This gives rise to new challenges in designing mechanisms. We tackle this by simple yet powerful mechanisms and complement these with nearly-tight impossibility results. Our proofs of upper and lower bounds involve new techniques, which may be of independent interest. One interesting problem for further study is to close the gaps between bounds in Table 2. In the classical model, the left-right-middle mechanism (Procaccia et al. 2009) and the proportional mechanism (Lu et al. 2010) can achieve better approximation ratios than the deterministic ones. However, they can not be extended to our models keeping strategyproof. It is intriguing to design better randomized mechanisms for our model.

Acknowledgements The work is supported by the National Natural Science Foundation of China, under grants 61972070 and 62172077.

References Alon, N.; Feldman, M.; Procaccia, A. D.; and Tennenholtz, M. 2010. Strategyproof approximation of the minimax on networks. Mathematics of Operations Research, 35(3): 513 526. Aziz, H.; Chan, H.; Lee, B.; Li, B.; and Walsh, T. 2020a. Facility location problem with capacity constraints: Algorithmic and mechanism design perspectives. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, 1806 1813. Aziz, H.; Chan, H.; Lee, B. E.; and Parkes, D. C. 2020b. The capacity constrained facility location problem. Games and Economic Behavior, 124: 478 490. Barber a, S.; Gul, F.; and Stacchetti, E. 1993. Generalized median voter schemes and committees. Journal of Economic Theory, 61(2): 262 289. Cai, Q.; Filos-Ratsikas, A.; and Tang, P. 2016. Facility Location with Minimax Envy. In Proceedings of the Thirty First International Joint Conference on Artificial Intelligence, IJCAI-16, 137 143. Chan, H.; Filos-Ratsikas, A.; Li, B.; Li, M.; and Wang, C. 2021. Mechanism Design for Facility Location Problems: A Survey. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, 4356 4365. Cheng, Y.; Yu, W.; and Zhang, G. 2013. Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theoretical Computer Science, 497: 154 163. Deligkas, A.; Filos-Ratsikas, A.; and Voudouris, A. A. 2022. Heterogeneous facility location with limited resources. In Proceedings of the AAAI Conference on Artificial Intelligence, 4966 4974. Fotakis, D.; and Tzamos, C. 2014. On the power of deterministic mechanisms for facility location games. ACM Transactions on Economics and Computation (TEAC), 2(4): 1 37. Li, M.; Lu, P.; Yao, Y.; and Zhang, J. 2020. Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio. In Proceedings of the Twenty Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, 238 245. Lu, P.; Sun, X.; Wang, Y.; and Zhu, Z. A. 2010. Asymptotically optimal strategy-proof mechanisms for two-facility games. In Proceedings of the 11th ACM conference on Electronic commerce, EC-10, 315 324. Lu, P.; Wang, Y.; and Zhou, Y. 2009. Tighter bounds for facility games. In International Workshop on Internet and Network Economics, WINE-09, 137 148. Springer. Moulin, H. 1980. On strategy-proofness and single peakedness. Public Choice, 35(4): 437 455. Procaccia, A. D.; and Tennenholtz, M. 2009. Approximate Mechanism Design without Money. In Proceedings of

the 10th ACM Conference on Electronic Commerce, EC-09, 177 186. Walsh, T. 2022. Strategy Proof Mechanisms for Facility Location with Capacity Limits. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, 527 533.