We investigate the e ectiveness of tolls to reduce the ine ciency of Nash equilibria in the classical fair cost facility location game. In this game, every terminal corresponds to a sel sh player who wants to connect to some facility at minimum cost. The cost of a player is determined by the connection cost to the chosen facility plus an equal share of its opening cost. We are interested in the problem of imposing tolls on the connections to induce a socially optimal Nash equilibrium such that the total amount of tolls is minimized. It turns out that this problem is challenging to solve even for simple special cases. We provide polynomial-time algorithms for (i) instances with two facilities, and (ii) instances with a constant number of facilities arranged as a star. Our algorithm for (ii) exploits a relation between our tolling problem and a novel bipartite matching problem without crossings, which we prove to be NP-hard.
Facility location problems are one of the fundamental classes of problems in computer science, with practical applications in many elds of industry and services. A common version of the facility location problem can be stated as follows: We are given a set F of facilities that can be opened and a set T of terminals (or clients) that need to be connected to the facilities. Each facility f 2 F has a non-negative opening cost cf that is incurred if it is opened. Further, the cost of connecting terminal t 2 T to facility f 2 F is given by a non-negative connection cost dtf . The goal is to choose a subset F 0 F of the facilities which are opened and to connect each terminal t 2 T to an open facility in F 0. The objective is to nd a solution that minimizes the total opening cost of all facilities in F 0 and the connection costs of the terminals to their respective facilities.
The facility location problem has been studied extensively in the literature. However, in most studies a centralized optimization perspective is adopted, i.e., it is assumed that there is a central authority, controlling all facilities and terminals, whose goal is to determine a solution of minimum cost. This assumption is not justi ed in settings where several agents are involved who want to minimize the costs of their own facilities or terminals.
In this paper, we study a game-theoretic variant of the facility location problem, which is also known as the Fair Cost Facility Location Game (FCFLG). Here each terminal t 2 T corresponds to an independent player (or agent) who wants to connect to some facility. Each player t 2 T sel shly chooses a facility in F to which his terminal is assigned to. The opening cost of a facility is shared equally between the players that have chosen it and the connection costs are paid individually by the players. Each player attempts to minimize his individual cost. The social cost objective that we consider throughout this paper is the sum of the individual player costs.
This game is known to su er from a high ine ciency. In particular, it is not hard to construct instances that show that the social cost ratio between a pure Nash equilibrium and a social optimum can be as large as the number of players.
For example, consider the instance with two facilities f1 and f2 and an even number of n 4 terminals as depicted in Figure 1. In the social t1 optimum, terminals t1 to tn=2 connect to f1 and 0 bb 1 terminals tn=2+1 to tn connect to f2, yielding a b social cost of 4. Suppose all terminals connect 2 0 t n 1 2 taondfatchileitsyecfo1n.dTn2hetnertmheinalrsstpan2y t1e+rmn2ineaalcshp. aTyhin2s f1 1 2 0 f2 is a Nash equilibrium because every player who t n2 +1 deviates to facility f2 needs to pay at least the 1 bb 0 opening cost of 2 > 1 + n2 . Note that this equilib- b rium is highly ine cient: its social cost is 2 + n2 , tn which is (n) times larger than the optimal so- Fig. 1. cial cost.
In light of this, it is imperative to seek e cient means to deal with this ine ciency. The idea of designing e cient algorithms, also known as coordination mechanisms, to reduce the ine ciency caused by sel sh behavior has recently attracted a lot of attention in the algorithmic game theory literature. For example, in the context of network routing games the use of tolling schemes was shown to be an e ective way to steer sel sh players into more favorable equilibrium outcomes. However, relatively little work has been done considering facility location games.
Suppose that in our facility location game there is a central authority that, while not being able to control the terminals directly, is capable to increase the perceived costs of the players through some form of external costs, such as tolls. This authority is interested to induce Nash equilibria which have optimal social cost, while altering the game as little as possible. Immediately, two possibilities for the placement of tolls come to one's mind: either on the opening costs of the facilities or on the connection costs between terminals and facilities.
When tolling facilities, it quickly becomes clear that there are instances where no tolling scheme can avoid highly suboptimal Nash equilibria, even if the connection costs constitute a metric. To see this, reconsider the example given above. Suppose we want to avoid ine cient equilibria by imposing non-negative tolls 1 and 2 on facilities f1 and f2, respectively. Assume that 1 2. Then all terminals connecting to facility f1 still constitutes a Nash equilibrium. To see this, note that the rst n2 terminals pay 2+n 1 and the second n2 terminals pay 1 + 2+n 1 . If a player deviates to facility f2 he needs to pay at least the opening cost of 2 + 2 > 1 + 2+n 1 . If 1 > 2 then by using symmetric arguments it follows that all terminals connecting to facility f2 is a Nash equilibrium. In either case a pure Nash equilibrium remains whose social cost is at least (n) times larger than the optimal social cost. We conclude that for this instance there is no way to avoid Nash equilibria of high ine ciency merely by tolling the facilities.
Given the above observations, we focus on tolling the connections in this paper. Clearly, it is possible to enforce an arbitrary optimal solution as a Nash equilibrium simply by increasing the costs of all connections which are not part of the solution to in nity. However, an intriguing question that arises is: How large would the tolls need to be in the worst case to ensure that an optimal solution is realized as a Nash equilibrium? And: Can we e ciently compute minimum cost tolls that induce a social optimum as a Nash equilibrium? Our Contributions. In this paper, we study a model for tolling the connection costs of fair cost facility location games with the objective to steer the players to some desirable strategy pro le (e.g., social optimum). We assume that the players start from an arbitrarily given strategy pro le and play best response moves sequentially, one player at a time, according to some order (see below for further justi cation of this assumption).
The main contributions presented in this paper are as follows: 1. We show that if a prede ned player order is given, nding optimal tolls which induce a given strategy pro le can be solved in polynomial-time (Section 2). The problem becomes inherently more di cult if the order of the players is not xed, but can be determined by the central authority. Even for simple special cases, this problem turns out to be very challenging to solve. 2. We identify some properties that optimal tolling schemes have to satisfy for certain restricted types of instances (Section 2). 3. We exploit these properties to derive polynomial-time algorithms for the following two special cases (Sections 3 and 4, respectively): (i) instances with two facilities, and (ii) instances with a constant number of facilities arranged as a star. Our algorithm for (ii) is based on a reduction of our tolling problem to a bipartite matching problem without crossings : Given an edge-weighted bipartite graph whose nodes on one side are partitioned into consecutive clusters, nd a minimum weight perfect matching such that no two edges incident to the same cluster cross. To the best of our knowledge, this problem has not been studied before and is of independent interest. 4. We provide a dynamic programming algorithm for the bipartite matching problem without crossings, which is polynomial if the number of clusters is constant. Further, we prove that this matching problem is NP-hard in general (Section 4).
We conjecture that the tolling problem is NP-hard in general. While we do not
have a proof for this yet, we feel that our NP-hardness result for the related
bipartite matching problem without crossings lends some support to this.
Related Work. Di erent versions of facility location games have been studied
in the literature. Cardinal and Hoefer [
For the metric facility location game, Hansen and Telelis [
The use of tolling schemes was intensively studied in the context of network
routing games. Beckman, McGuire and Winsten [
To the best of our knowledge, we are the rst to investigate the e ectiveness
of tolls in facility location games. On the other hand, for the more general
network design game with fair cost allocation, there are several works that focus on
improving the price of anarchy. Fanelli et al. [
Regarding the matching problem we describe in Section 4, the most relevant
work is due to Darmann et al. [
We rst formally de ne the Fair Cost Facility Location Game (FCFLG) that we consider in this paper: Let G = (T [ F; T F ) be a complete bipartite graph, where F is the set of facilities and T is the set of terminals. We use m = jF j and n = jT j to refer to the number of facilities and terminals, respectively. Each facility f 2 F has a non-negative opening cost cf and each terminal-facility pair (t; f ) 2 T F has a non-negative connection cost dtf . Each terminal t is a sel sh player who chooses to connect to a facility such that t is connected to exactly one opened facility. We use the terms player and terminal interchangeably.
Suppose that player t 2 T chooses facility St 2 F . We use S = (S1; : : : ; Sn) to refer to a strategy pro le of all players. We write f 2 S to denote that facility f is opened in strategy pro le S. Each player t 2 T wants to minimize his own payment (or cost) which is de ned as pt(S) = cft =xft (S) + dtft , where ft = St is the facility he chose and xft (S) = jfi 2 T : Si = ftgj is the number of players using facility ft in strategy pro le S.
Given a strategy pro le S = (S1; : : : ; Sn), a change for player i from
a strategy Si to a di erent strategy Si0 is called a move. Let S i =
(S1; : : : ; Si 1; Si+1; : : : ; Sn) be the strategy pro le resulting from S if we
remove i's strategy. We say that Si is a best response of player i with respect
to S if pi(Si; S i) pi(Si0; S i) for all Si0 2 F . A strategy pro le S is a
pure Nash equilibrium (PNE) if for every player i 2 T , Si is a best response
with respect to S. The social cost is a measure of the overall quality of a
particular strategy pro le. For facility location games, the social cost for a
strategy pro le S is de ned as the sum of all payments of the players, i.e.
C(S) = Pt2T pt(S) = Pf2S cf + Pt2T dtft . In order to analyze the ine
ciency of equilibria the Price of Anarchy (PoA) [
We next de ne the modi ed toll game that we consider. Let G = (G; c; d) be an instance of FCFLG. We assume that a central authority can alter G by placing some tolls : T F ! R 0 on every connection. We assume that the players perceive a modi ed cost function which includes the tolls, while these tolls are excluded from the social cost objective (i.e., tolls are refundable). More formally, de ne the modi ed toll game G = G( ) = (G; c; d + ) with respect to tolls , where every player i perceives a cost of pi(S) = pi(S) + ifi with fi = Si being the facility that i chooses under S. The social cost C(S) of S in G is the same as the social cost of S in G.
We say that a strategy pro le S is inducible if there exist tolls such that S is a pure Nash equilibrium in the modi ed toll game G. Given a desirable strategy pro le S , the central authority ideally would like to impose tolls such that S is inducible. However, the problem with this is that even though the tolls imposed on the connections might be su cient to impose S as a Nash equilibrium, S might not be reachable because there are multiple Nash equilibria in the modi ed toll game G( ). In fact, even if we start from a xed strategy pro le S there is no guarantee that S is reached if the players simply play best response. As a result, we may end up in a PNE whose social cost is signi cantly higher than the social cost C(S ) of the desired outcome S . On the other hand, enforcing that S is the unique PNE is also not desirable, since the amount of tolls needed for this can be very large.
In order to circumvent these problems, conceptually we adopt the following viewpoint: In a rst phase, all players arbitrarily play best responses in the (unmodi ed) facility location game until they reach a pure Nash equilibrium, say S. In a second phase, we then impose tolls on the connections such that S is reached from S if we let the players play one additional round of best responses according to some order . Our goal is to determine tolls and an ordering such that the total amount of tolls is minimized.
We formalize the above idea. Let S be a pure Nash equilibrium and S be an arbitrary strategy pro le of G. Let : T ! [1; : : : ; n] be an order according to which the players play best response in the game G, where the interpretation is that player i is the (i)-th player to move. If, starting at S and playing according to the order , there is a best response for every player such that S is reachable, then we say that S is reachable from S through . The Minimum Toll Problem (MTP) considered in this paper is de ned as follows: Minimum Toll Problem (MTP): Given: FCFLG instance G = (G; c; d), pure Nash equilibrium S, arbitrary strategy pro le S Goal: Determine tolls : T F ! R 0 and an ordering : T ! [1; : : : ; n] such that S is reachable from S through and the total amount of tolls T = P(t;f)2T F tf is minimized.
The theorem below shows that if the order of the players is xed, then determining the optimal tolls is easy. Due to lack of space, several proofs are omitted from this extended abstract and will be given in the full version of the paper. Theorem 1. Given an order , a starting strategy pro le S and a nal strategy pro le S , there is a polynomial-time algorithm that nds the minimum tolls such that S is reachable from S through .
Below we establish some useful properties for instances of MTP where the set of facilities used under S and S are disjoint.
We say that two terminals t; t0 2 T are similar if (i) St = St0 , (ii) St = St0 , and (iii) t and t0 do not have any other possible connections other than to St and St . Further, we say that A T is a similar set if for all terminals t; t0 2 A, t and t0 are similar.
Lemma 1 (Monotonicity). Let T be partitioned into similar sets T1; : : : ; Tp. Let t(x; y) be the toll that is needed to move terminal t 2 Tj , when it is the x-th terminal to move to facility St and the y-th terminal to move from facility St. Then, t(x; y) is monotonically decreasing in x and y.
Using this, we can infer an optimal terminal order for each similar set. For a terminal t 2 T , let d(t) = dtf dtf be the di erence in connection costs between St = f and St = f .
Lemma 2 (Sorting similar sets). Let T be partitioned into similar sets T1; : : : ; Tp. Then there is an ordering that induces minimum toll costs, where for every two terminals t; t0 2 Tj : if d(t) < d(t0), then (t) < (t0).
We derive an algorithm for the special case of MTP with two facilities only. Theorem 2 (2-MTP). When restricted to two facilities, there is a polynomialtime algorithm to solve MTP.
Proof. Let F = ff1; f2g. Consider a terminal t and suppose St = f1 (the case St = f2 follows similarly). Because t should not have an incentive to deviate under S , it must hold that tf2 + dtf2 + xf2 (cSf2 )+1 dtf1 + xf1cf(1S ) . This imposes a restriction on the toll tf2 which must be satis ed in any feasible solution and we can (implicitly) add this minimum toll to the connection cost dtf2 . We can thus assume that S is a PNE with respect to d.
Let A and B be the sets of all terminals connected to f1 and f2 in S, respectively, and de ne a = j j and b = jBj. Note that all terminals t 2 A with
A St = St = f1 and t 2 B with St = St = f2 do not require any tolls on their connections because S is a PNE. We can thus let them be the last terminals in the order .
Let Ai and Bi be the sets of terminals that are connected to f1 and f2, respectively, after the i-th terminal has moved to its facility in S . Let ai = jAij and bi = jBij. In particular, an (resp. bn) is the number of terminals in A (in B) at the nal strategy S . Note also that aj + bj = ai + bi, for any i; j 2 [1; n]. Among the terminals in A (resp. B) we denote by A0 (resp. B0) the terminals that have to move to the other facility, i.e, each ta 2 A0 (resp. tb 2 B0) is such that Sta = f1 and Sta = f2 (resp. Stb = f2 and Stb = f1).
Suppose we are considering the rst terminal to move and suppose that a1 > an (then b1 < bn). Since a1 > an and b1 < bn, moving any terminal t 2 B0 from f2 to St = f1 does not require tolls currently since at turn 1 we have ac1f+11 + dtf1 cafn1 + dtf1 and cbfn2 + dtf2 < cbf12 + dtf2 . Since S is a PNE we must have cafn1 + dtf1 bncf+21 + dtf2 ; which results in So at turn 1 terminal t 2 B0 has an incentive to move from f2 to f1 and no tolls are required. Suppose we move terminals t 2 A0 from f1 to f2 until a turn j such that aj = an + 1 > an and bj = bn 1 < bn. It is not hard to see that for all these turns equation (1) remains valid and for any terminal t 2 B0 no tolls would be required to move it to f1.
The algorithm constructs an order where rst we move terminals t 2 A0 from f1 to St = f2 until a time j where we have aj = an and bj = an. All these moves require positive tolls, but after we reach the point where aj = an and bj = an, we will show that no tolls are required to move the remaining terminals t 2 A0 or t 2 B0. In particular, for the terminals in B0 no tolls are required. The optimal solution necessarily moves rst terminals from A0 until aj = an and bj = an. To see this, note that moving terminals from B0 rst would only increase the total cost of moving terminals of A0 later, since the terminals in B0 have always toll cost equal to zero.
Until a turn j where aj = an and bj = an, only terminals from A0 move from f1 to f2 and it is not di cult to prove a result similar to Lemma 2 showing that the optimal order among terminals in A0 is to move them in decreasing order of d(t).
Now suppose we are at turn j where aj = an and bj = an. At this point we can move a terminal t 2 B0 from f2 to f1 with tolls cost equal to zero. To see this, note that cbfj2 + dtf2 = cbfn2 + dtf2 > bncf+21 + dtf2 cafn1 + dtf1 > acjf+11 + dtf1 ; where the third inequality ( ) is valid since S is a PNE. So at this point t has an incentive to move from f2 to f1 and no tolls are required.
In the next turn j + 1 we have aj+1 = an + 1 and bj+1 = bn 1, and to is a PNE and mbj+ov1+e1a+tedrtmf2in=al ctf22+Ad0tfn2o tolls are required either, since S
cf2 bn acnf+1 1 + dtf1 = bcjf+11 + dtf1 . So the amount t is paying for being connected to f1 is greater than or equal to the amount paid to be connected to f2. So the order follows a move from a terminal in B0 and a terminal in A0 until all terminals have moved. The cases where b1 > bn or b1 = bn are similar to the case a1 > an discussed above. tu 4
We consider a special case of MTP which we term the Star Minimum Toll Problem (Star-MTP): In an instance (G; S; S ) of Star-MTP all terminals have the same starting facility fc in strategy pro le S and can be partitioned into m similar sets T1; : : : ; Tm such that every terminal t 2 Ti has target facility St = fi. Furthermore, no terminal in Ti can connect to any facility other than fc and fi. We show that Star-MTP admits a polynomial-time algorithm for a constant number of facilities. To this aim, we rst reduce the problem to a new matching problem and then present a dynamic programming algorithm for it. Reduction to Bipartite Matching Without Crossing Edges. We can think of StarMTP as a bipartite matching problem, where the set of terminals corresponds to the set of nodes on one side of the bipartition and the other side contains the integers 1; 2; : : : ; n (n being the number of terminals). These integers represent the order in which each terminal moves from fc to its nal facility. For terminals belonging to the same set Ti, we know from Lemma 2 that they must move according to the order of non-decreasing di erences in connection cost between fc and fi, denoted by d. The partition containing the terminals is organized in such a way that we list the vertices from top to bottom grouped by similar sets, and vertices in the same similar set are sorted from top to bottom in increasing order of d value. For each terminal t and integer q 2 [1; n], the edge (t; q) in this bipartite graph has cost equal to the tolls required when t is the q-th terminal to move to its nal facility.
For terminals t; t0 2 Ti belonging to the same similar set, if d(t) < d(t0) then t must move before t0. We impose this restriction by requiring that in the Set A a1 a2 a3
Set B b1 b2 b3 fa fc fb b1 b3 a1 B b2 A a2 a3 1 2 3 4 5 6 matching there are no crossing edges between vertices of the same similar set. The problem reduces to nding a perfect matching of minimum cost without crossings.
De nition 1 (Perfect Matching Without Crossing Edges (PMC)). Given a bipartite graph G = (A = [i2[m]Ai; B; E), let A be a set of n integers from t1 to tn, partitioned into subsets Ai; i = 1; : : : ; m, and let B be another set of integers from 1 to n. For each pair tr 2 A, j 2 B there is an edge e = (tr; j) 2 E with cost wtrj 2 R. For vertices tr; ts 2 Ai where tr < ts, edges (tr; q) and (ts; p) are crossing if p < q. The problem is to nd a minimum cost perfect matching without crossing edges.
Now we present a reduction from Star-MTP to the PMC. Given an instance of the Star-MTP, rst sort terminals in each similar set Ti in decreasing order of d value: if d(t) < d(t0) then t < t0, for any t; t0 2 Ti. Each similar set Ti becomes a set Ai in the PMC instance, and we assume that all t 2 Ai have a smaller value then t0 2 Aj if i < j, i.e, t < t0. So in the PMC instance the terminal vertices are sorted from top to bottom from A1 to Am, and inside each set Ai, terminals are sorted by d value. The partition B of the PMC instance just contains the numbers 1 to n, where n is the number of terminals.
Let qi = jAij for i = 1; : : : ; m and let Ai = fti1; : : : ; tiqi g, with terminals sorted from t1 to tqi in the order they must move considering just terminals from Ai. For each tix 2 Ai and y 2 [x; n] we create an edge (tix; y) with cost wtix;y = max 0; cfi + dtix;fi x dtix;fc n cfc y + 1 which is equivalent to the toll cost required if tix is the y-th overall terminal to leave fc, and the x-th to move to fi among terminals in Ai. An example of the reduction is presented in Figure 2.
A perfect matching of minimum cost to the reduced instance corresponds to an optimal tolling for the MTP instance. To see this, note that no crossing edges are allowed in the matching, so for each Ti, i = 1; : : : ; m, terminals move according to the optimal order de ned by Lemma 2. Since the costs of any edge (t; y) represents the toll cost required when t is the y-th overall terminal to move, a minimum perfect matching corresponds to a minimum tolling. Dynamic Program. We now present a dynamic program algorithm to the PMC problem. Let G = (A = [i2[m]Ai; B; E) be an instance of PMC, with qi = jAij for i = 1; : : : ; m, and n = q1 + + qm. Let DP (q1; q2; : : : ; qm) be the cost of a minimum cost perfect matching without crossings for that instance. De ne DP (q1; : : : ; qm) = 0 if q1 = = qm = 0 and
DP (q1; : : : ; qm) =
min i = 1; : : : ; m such that qi > 0
DP (q1; : : : ; qi 1; : : : ; qm) + w(tiqi ;y) (2) where y in w(tiqi ;y) is equal to y = Pm
i=1 qi.
Theorem 3. The recurrence relation above correctly computes the optimal solution DP (q1; q2; : : : ; qm) for an instance of the PMC.
It is not hard to construct a dynamic program algorithm to solve PMC, since the algorithm only needs to create an m-dimensional table of size q1 q2 : : : qm = (nm) and compute the value of each cell in (m) time following the recurrence (2). The overall time of the algorithm is then (mnm) which is polynomial if m is a constant.
Hardness. We show that given an instance of PMC, it is NP-hard to decide whether it admits a perfect matching without crossings.
Theorem 4. The problem of deciding whether a given instance of PMC admits a perfect matching without crossings is NP-hard.
Proof. Let I be an instance of the 3-SAT with m clauses and n variables. We construct an instance of PMC as follows: for each variable xi we build vertices aiT < aiF in A and biT < bi < biF in B, with edges (aiT ; biT ), (aiT ; bi), (aiF ; bi) and (aiF ; biF ). For any occurrence of the literal xi or xi in a clause Cj , we add vertices aiCj to A and vertices biCjxi ; biCjxi to B, with edges (aiCj ; biCjxi ) and (aiCj ; biCjxi ), such that aiT < aiCj < aiF and biT < biCjxi < bi < biCjxi < biF . We call this gadget Xi. All vertices a from a gadget Xi form a subset Ai, so it is forbidden to have crossing edges in this gadget. Note that each vertex a 2 Ai can connect to exactly two vertices in B, where the one with smaller value is denoted by S(a), and the one with greater value G(a).
For each clause Cj , we also construct a vertex cj 2 A which connects to each biCjli 2 B for each literal li occurring in Cj , i.e., if literal xi (resp. xi) appears in Cj we include edge (cj ; biCjxi ) (resp. (cj ; biCjxi )). Each vertex cj belongs to its own partition Acj = fcj g. See Fig. 3 for an example of this construction.
Finally, note that each variable xi gives rise to two vertices in A (aiT ; aiF ) and three in B (biT ; bi; biF ). Each clause Cj adds four vertices to A (one in the clause gadget (cj ) plus one for each literal (aiCj )) and six in B (two for each
Ac1 c1
C1 literal (biCjxi ; biCjxi )), resulting in a total of 2n + 4m vertices in A and 3n + 6m in B. We add n + 2m dummy vertices all belonging to the same partition Ak which can connect to any vertex in B except the vertices bi, for i 2 [1; n], where k = n + m + 1 is the number of partitions.
Suppose there is a feasible assignment to the instance I of 3-SAT. We construct a perfect matching as follows: for each variable xi which is true, we assign each vertex a 2 Ai to its vertex S(a) 2 B. All b vertices of Xi larger than bi are unassigned, and therefore for any clause Cj which contains xi, its vertex cj can be assigned to biCjxi . Similarly the opposite is done if xi is false, i.e., assign each vertex a 2 Ai to its vertex G(a) 2 B, allowing each vertex cj , from a clause Cj containing xi, to connect to biCjxi . With this, all vertices from set A which belong to variable and clause gadgets are matched. To complete the perfect matching, just assign the vertices from subset Ak, from smallest to greatest, in this order to the smallest to greatest vertices in B which are still not matched.
Now assume there is a perfect matching with no crossing edges for the graph G. First notice that for each gadget Xi either aiT or aiF is assigned to bi. If aiT is assigned to bi, then all a vertices of Xi are assigned to their greater vertices G(a) since no crossing edges are allowed, and if aiF is assigned to bi then all a vertices are assigned to their S(a) vertices.
We construct an assignment for the 3-SAT instance by setting xi to true if all a 2 Ai are assigned their smaller vertices S(a) 2 B, and to false otherwise. Now we show that each clause Cj is satis able. Let cj 2 A be the corresponding vertex of a clause Cj . Since we have a perfect matching, cj must be connected to some biCjli corresponding to one of its literals li, which is either xi of xi. If li = xi then we know that all a vertices of Xi must be connected to their smaller vertices S(a) and so xi is true and Cj is satis able. Similarly, if li = xi then all a vertices of Xi must be connected to their greater vertices G(a), so xi is false and Cj is satis able. tu 5
The most natural open problem that our work suggests is to prove that the minimum toll problem is in fact NP-hard. While the NP-hardness result for the perfect matching problem without crossings provides some support to this, its proof does not translate directly to the more restricted scenario of choosing optimal tolls. Besides this, there are also di erent possibilities of consideration for the tolling model, such as allowing simultaneous moves or enforcing that the unique possible equilibrium is one with optimal social cost. However for these scenarios, nding optimal tolls often includes nding possible equilibria, which implies that these tolling problems might be even harder than the ones we consider here. Finally, an interesting consideration is to allow for negative tolls on either the connection or opening costs to encourage players to play a speci c strategy pro le.
Acknowledgments. This work was partially funded by CNPq (306358/2014-0, 425340/2016-3) Capes/PDSE and Fapesp (2015/11937-9, 2016/23552-7).