On the Stackelberg fuel pricing problem?

Abstract

We consider the Stackelberg fuel pricing problem in which a company has to decide the fuel selling price at each of its gas stations in order to maximize its revenue, assuming that the selling prices of the competitors and the customers' preferences are known in advance. We show that, even in the basic case in which the road network is modeled by an undirected planar graph and the competitors discriminate on two different selling prices only, the problem is APX-hard. On the positive side, we design a polynomial time algorithm for instances in which the number of gas stations owned by the company is constant, while, in the general case, we show that the single-price algorithm (which provides the best-known solutions for essentially all the Stackelberg pricing problems studied in the literature up to date) achieves an approximation ratio which is logarithmic in some parameters of the input instance. This result, in particular, is tight and holds for a much more general class of Stackelberg network pricing problems.

-

A fundamental decisional process in many business activities concerns how to set the selling prices so as to maximize its own revenue, once knowing the selling prices of the competitors and the customers’ preferences. The scenario in which the latter are implicitly defined in terms of some optimization problem are usually referred to as Stackelberg pricing problems [ 15 ]. These problems can be modeled as multi-player one-round games in which there is a special player, the leader, while all the others are followers. The first action is undertaken by the leader who decides on some parameters (e.g., the selling prices) and then the followers respond by deciding their actions. Each follower adopts, as her action, the optimal solution of a certain optimization problem (e.g., satisfying her own demand at the minimum cost) which depends on some of the parameters fixed by the leader and on some other values on which the leader has no control (e.g., the selling prices of the competitors). Since the followers’ choices influence, in turn, the leader’s revenue, the determination of the best possible action for the leader often results in a challenging algorithmic problem.

A considerable research attention, see [ 2–8, 11, 12, 14 ], has been devoted in the last years to the study of Stackelberg network pricing problems based on some fundamental (polynomial time solvable) optimization problems, such as shortest paths, shortest path trees and minimum spanning trees. In this paper, we study the Stackelberg fuel pricing problem (SFPP) which is a Stackelberg network pricing problem based on the gas station problem (GSP): an optimization problem introduced in [ 9 ] to model situations in which drivers have to go from one location to another and have to decide where to fill their cars with fuel so as to minimize the travel cost, once knowing the fuel prices at the various gas stations along the road network.

Model and Notation. For a positive integer k, let [k] denote the set {1, . . . , k}. A road network is an edge-weighted directed graph G = (V, E, w), with |V | = n, |E| = m and w : E → R≥0 such that, for each e = (u, v) ∈ E, w(e) specifies the amount of fuel (expressed in gallons) needed to go from u to v.

An instance (G, s, t, S, p) of the GSP is defined by a road network G, a pair of nodes s, t ∈ V , a set of nodes S ⊆ V and a function p : S → R≥0. The set of nodes S represents the locations of gas stations and the function p models the selling prices (per gallon) at each of the gas stations. There is a driver who needs to go from s to t. For the sake of simplicity, we assume that the driver’s car is equipped with a tank of unlimited capacity and that s ∈ S, so that the driver can fill with as much fuel as she wants at price p(s) when starting her trip. The driver wants to determine the best possible itinerary, that is, which (s, t)-path to drive through and which gas stations to stop at for fueling so as to minimize the total fuel cost3.

An instance (G, (si, ti, λi)i∈[k], L, C, pC , e) of the SFPP is defined by a road network G, k source-destination pairs (si, ti) with an associated integer weight λi ≥ 1 for each i ∈ [k], two sets L, C ⊆ V , a function pC : C → R≥0 and a value e ≥ 0. The sets of nodes L and C represent the locations of gas stations: the gas stations located at nodes in L are owned by the leader, while those located at nodes in C are owned by her competitors, so that the function pC models the selling prices established by the competitors at each of their gas stations4. Note that we do not require L and C to be disjoint, i.e., either the leader and one of her competitors may own a gas station at the same location. The leader buys (or produces) the fuel at price e per gallon. There are k types of drivers (the followers) such that, for each i ∈ [k], the driver of type i wants to go from si to ti along the cheapest path in G, where λi denotes the number of drivers of type i, that is, how many drivers want to go from si to ti. Once the leader has established a pricing function pL : L → R≥0 defining the fuel prices at her own gas stations, each follower of type i ∈ [k] determines her action by 3 The amount of fuel bought at each gas station s is implicitly defined by the minimum distance between s and the successive station chosen for fueling 4 In the case in which more than one competitor owns a gas station in a given location v, pC (v) will denote the cheapest fuel price among them. solving the instance (G, si, ti, L ∪ C, p) of the GSP, in which, for each v ∈ L ∪ C, p(v) := min{pL(v), pC (v)}. The leader has to determine the pricing function pL : L → R≥0 providing her with the highest possible revenue. To this aim, we make the following simplifying assumption which is common in the setting of Stackelberg pricing problems: when the gas station problem has more than one optimal solution, the follower always chooses the one providing the leader with the highest revenue5. Furthermore, we assume that si ∈ C ∀i ∈ [k], otherwise, either the problem is not feasible or the revenue is unbounded.

More formally, given a node v ∈ V and a pricing function pL for the leader, let q(pL, v) := 1pL(v)≤pC(v). For a pair of nodes u, v ∈ V , let d(u, v) be the distance from u to v in G and B(u, v) be the set of itineraries connecting u to v, that is, the set of sequences of nodes [u = vi1 , vi2 , . . . , vir = v] such that vis ∈ L ∪ C for each s ∈ [r − 1]. Set ps := p(vis ), ds := d(vis , vis+1 ) and qs := q(pL, vis ) for each s ∈ [r − 1]. Given pL and B ∈ B(u, v), a driver choosing itinerary B experiences a cost c(pL, B) and yields a contribution g(pL, B) to the leader’s revenue which are defined as follows: r−1 X ps · ds, s=1 c(pL, B) := g(pL, B) := r−1 X(ps − e) · ds · qs. s=1 Let cg(pL, B) = (c(pL, B), g(pL, B)) and define a total ordering relation ≺ on R≥0 × R≥0 such that [x1, y1] ≺ [x2, y2] ⇔ x1 < x2 ∨ {x1 = x2 ∧ y1 > y2}. Let B∗(u, v) ⊆ B(u, v) be the set of itineraries B ⊆ B(u, v) minimizing cg(pL, B) according to the ordering relation ≺. Let cg(pL, u, v) := [c(pL, u, v), g(pL, u, v)] := minB∈B(u,v) cg(pL, B). Given a driver of type i, we have that c(pL, si, ti) is the cost of her cheapest path, and g(pL, si, ti) is her contribution to the leader’s revenue, so that g(pL) := Pk

i=1 λi · g(pL, si, ti) is the leader’s total revenue that has to be maximized. Let pM := maxi∈[k] pC (si). It is easy to prove that, if we set pL(v) > min{pM , pC (v)} for some v ∈ L, no driver will stop at station v for fueling. Similarly, whenever pC (v) > pM for some v ∈ C, no driver will stop at station v for fueling. Therefore, we can suppose without loss of generality that pC (v) ≤ pM ∀v ∈ C, the leader’s revenue g(pL) is bounded and, in order to be maximized, pL can be chosen in such a way that e ≤ pL(v) ≤ pC (v) ∀v ∈ L. Related Work. The GSP has been introduced by Khuller, Malekian and Mestre in [ 9 ]. They give polynomial time algorithms for the basic problem and for some of its variations.

Briest, Hoefer and Krysta author an influential work [ 6 ] on Stackelberg network pricing problems which widely generalizes previous results in the field. In particular, they consider the case in which the edges of the network are partitioned into two sets: the set of fixed-price edges and that of priceable edges, with the latter owned by the leader. Each follower buys a subnetwork of minimum cost and so the leader wants to assign suitable prices to the priceable edges so 5 In fact, if this is not the case, the leader can decrease some selling price of a negligible amount so as to achieve almost the same revenue as in the case in which the assumption holds. as to maximize her revenue. They study the approximation guarantee of the single-price algorithm in this general class of problems. This algorithm, which assigns the same (suitably computed) price to all priceable edges, has been first analyzed in [ 7 ] for the case of a single follower buying a minimum spanning tree. Briest, Hoefer and Krysta show that, for the case of a single follower, the approximation guarantee is (1 + )Hh, where > 0 is an arbitrary value, h is the number of priceable edges and Hi is the ith harmonic number, while, for the case of k followers, it becomes (1 + )(Hh + Hk). Finally, when the followers may have different weights, they show that the single-price algorithm achieves an approximation guarantee of (1 + )h2 and also provide a lower bound of O(h ) on the approximability of the problem.

Determining whether there are approximation algorithms better than the single-price one is, perhaps, the most important open problem in this field of research. In fact, while the performance of this algorithm remains essentially the same even when instantiated to specific optimization problems such as shortest paths, shortest path trees and minimum spanning trees, the impossibility results known so far in these cases only refer to APX-hardness, see [ 3, 5, 7 ]. Our Contribution. We show that the SFPP is APX-hard even in the basic case in which the road network is modeled by an undirected planar graph and the competitors discriminate on two different selling prices only, by means of a reduction from the maximum independent set problem on cubic graphs. This reduction, however, requires that |L| is a non-constant value. This assumption is essential, anyway, since, for the case in which |L| = O(1), we show that the problem can be solved in polynomial time.

We stress that the SFPP does not fall within the scope of the Stackelberg network pricing problems defined by Briest, Hoefer and Krysta in [ 6 ] and that the presence of additional parameters in the definition of the problem (in particular, the edge-weights) makes the performance of the single-price algorithm unlikely to be uninfluenced by the characteristics of the road network given in input. To this aim, we define a general class of Stackelberg network pricing problems which extends the one given by Briest, Hoefer and Krysta and includes the SFPP. For this class of problems, we show that the single-price algorithm provides an approximation guarantee which is logarithmic in some parameters of the input instance (see the claim of Theorem 4 for the exact characterization) and that this bound is tight.

Due to space limitations, some details and proofs have been removed. 2

Complexity Results

We first show that the SFPP is APX-hard even under some restrictions. Theorem 1 The SFPP is APX-hard even when pC assigns only two different prices and G is an undirected planar graph as long as |L| ∈ Θ(n). Proof. We consider a polynomial reduction from the Maximum Indipendent Set Problem on cubic graphs (MISP). Given a cubic graph (U, F ), with |U | = n and |F | = m, and an arbitrary value θ ∈]0, 1/2] polynomially representable with respect to n, consider an instance (G, (si, ti, λi)i∈[k], L, C, pC , e) of the SFFP that we define incrementally as follows. Suppose that the sets V , E, L and C are initially empty. Fix an arbitrary orientation on the edges in U , insert a node v∗ in V with pC (v∗) = 1 + 3θ, then, ∀i ∈ [n], insert in V three nodes vi1, vi2 and vi3 with pC (vi1) = pC (vi3) = 1 + 3θ and pC (vi2) = 4θ; vi1 belongs to L. Then, ∀i ∈ [n], insert in E three edges ei1 = {vi1, vi2}, ei2 = {vi2, v∗} and ei3 = {vi3, vi1} with ω(ei1) = θ, ω(ei2) = 1/2 − θ and ω(ei3) = 1 − θ. ∀ej = (ui, uh) ∈ F , denote vi1 with vj1, vi2 with vj2, v2h with vj3, v1h with vj4 and v3h with vj5. There is a driver (vi1, vi2) ∀i ∈ [n], and a driver (vj1, vj5) ∀j ∈ [m]. Finally, set e = 3θ.

We stress that the constructed road network G is a planar graph.

Lemma 1 Consider the instance obtained by the reduction from (U, F ). Given a pricing function pL, let p0L be the pricing function such that p0L(vi1) = 4θ if pL(vi1) ≤ 4θ and p0L(vi1) = 1 + 3θ otherwise. It holds that g(p0L) ≥ g(pL). Proof (Sketch). We first prove that, independently from pL, the cheapest path for driver (vi1, vi2) is [vi1, vi2] ∀i ∈ [n] and that the cheapest path for driver (vj1, vj ) 5 is [vj1, vj2, v∗, vj3, vj4, vj5] ∀j ∈ [m] . At this point, we prove that, by setting to 4θ all the prices not bigger than 4θ and to 1 + 3θ the remaining ones (thus obtaining p0L), the leader gets a revenue of g(p0L) ≥ g(pL). tu Lemma 2 Given the pricing function p0L of the previous lemma, there exists a pricing function p∗L which can be obtained in polynomial time from p0L such + that p∗L(vi1) = 4θ if exists fj ∈ δ(U,F )(ui) such that p0L(vj1) = p0L(vj4) = 1 + 3θ, and p∗L(vi1) = p0L(vi1) otherwise. Moreover, it holds that g(p∗L) ≥ g(p0L) and that g(p∗L) = |{i ∈ [n] : p∗L(vi) = 1 + 3θ}|(θ − θ2) + θ2n + (2θ − θ2)m.

Proof (Sketch). First we prove that, given j ∈ [m] such that p0L(vj1) = p0L(vj4) = 1 + 3θ, the leader’s revenue does not decrease when decreasing the value p0L(vj1) to 4θ. By repeating this operation ∀j ∈ [m] such that p0L(vj1) = p0L(vj4) = 1 + 3θ, we obtain p∗L which, by induction, satisfies g(p∗L) ≥ g(pL). Hence, we get g(p∗L, vi1, vi2) = (p∗L(vi1) − 3θ)θ ∀i ∈ [n] and g(p∗L, vj1, vj5) = 2θ − θ2. By summing these values for all drivers, we obtain the claimed value for g(p∗L). tu Now, we prove the theorem. Let 1 + be a lower-bound on the approximability of MISP (see [ 1 ] for a proof of the APX-hardness of MISP). We prove, by contradiction, that SFPP cannot be (1 + δ)-approximable ∀δ < 13 . Suppose that there exists a (1 + δ)-approximation algorithm for the SFPP with δ < 13 . Let p∗L be an optimal pricing function and pL be the pricing function returned by the approximation algorithm. We have that g(p∗L)/g(pL) ≤ 1 + δ. By Lemma 2, we can suppose without loss of generality that pL verifies pL(vi1) ∈ {4θ, 1 + 3θ} ∀i ∈ [n] and pL(vj1) = 4θ or pL(vj4) = 4θ ∀j ∈ [m]. In fact, if this is not the case, we can apply the polynomial time transformation outlined in the proof of Lemma 2 so as to obtain from pL a pricing function p0L verifying the assumption and such that p∗L/p0L ≤ p∗L/pL. Clearly, again by Lemma 2 and the optimality of p∗L, the same assumption can also be made for p∗ .

L Let M (pL) := {ui ∈ U : pL(vi1) = 1 + 3θ}. From the assumptions on p∗ L and pL, it follows that M ∗ := M (p∗L) and M := M (pL) are independent sets of (U, F ). By the optimality of p∗L and because of the characterization of g(p∗L) given in Lemma 2, M ∗ has to be a maximum independent set of (U, F ). Let θ := n−2. Again by the characterization of the leader’s revenue given in Lemma 2, for a sufficiently big n, we have g(p∗L) = (|M ∗| + 2m + (n − |M ∗| − m)n−2)n−2 |M ∗| + 2m g(pL) (|M | + 2m + (n − |M | − m)n−2)n−2 ∼ |M | + 2m ≤ 1 + δ. (1) By manipulating (1), we have that |M ∗|/|M | ≤ 1 + δ + 2mδ/|M |. In a graph of degree 3 and m edges, we can find in polynomial time an independent set with at least dm/6e nodes. So, we can suppose that |M | ≥ m/6. Therefore, |M ∗|/|M | ≤ 1 + δ + 2mδ/|M | ≤ 1 + 13δ < 1 + ⇒ |M ∗|/|M | < 1 + , thus contradicting the 1 + lower bound on the approximability of the MISP. tu

Note that, in the claim of Theorem 1, we required that |L| = Θ(n). However, if we consider instances of the SFPP such that |L| = O(1), then the problem can be efficiently solved. We prove this fact by designing an algorithm, called SFPPCL, which solves a polynomial number of linear systems in order to determine the best possible pricing function for the leader.

Let K = {(si, ti) : i ∈ [k]}. For a pair of nodes (u, v), let c∞(u, v) be the minimum cost paid by a driver to go from u to v without stopping at gas stations in L. Given a driver going from u to v, consider an optimal itinerary B ∈ B∗(pL, u, v). There exists an itinerary D extracted from B, that we call strong itinerary, of the form D = (u = v11, v21, . . . vt1(1) = v1C , v12, v22, . . . vt2(2) = v2C , . . . . . . vrC−1, v1r, v2r, . . . vtr(r) = v), with vsC ∈ C \ L ∀s ∈ [r − 1] while all the other nodes belong to L, such that the cost c and the revenue g with respect to B can be computed as follows (set psz := pL (vzs), dsz := d(vzs, vzs+1) and c∞(vrC , v1r+1) := 0):

r t(s)−1 c(pL, D) := X X psz · dsz + cs∞, Set cg(pL, D) := [c(pL, D), g(pL, D)] and let D(u, v) be the set of strong itineraries starting at u and ending at v. It holds that cg(pL, u, v) = minD∈D(u,v) cg(pL, D). From this fact, it follows that an optimal pricing function p∗L is an optimal solution to an LP problem LP ({Duv}(u,v)∈K ), yielded by a set of optimal strong itineraries {Duv}(u,v)∈K , whose objective function to be maximized is g(pL) and the constraints are: (i) c(pL, Duv) ≤ c(pL, D) for each D ∈ D(u, v), and (ii) e ≤ pL(v) ≤ pC (v) for each v ∈ L. From the LP Theory, we know that there exist |L| constraints in LP ({Duv}(u,v)∈K ) defining a linear system of |L| equations in |L| variables whose unique solution is p∗ . By evaluating L the revenue yielded by all the pricing functions that solve all the possible linear systems and returning the one giving the highest leader’s revenue, we obtain an optimal pricing function p∗ .

L

We now describe algorithm SFPP-CL, which is based on a refinement of the ideas outlined above. SFPP-CL is divided into two phases: an initializing phase, in which several data structures are created and a running phase, in which SFPPCL evaluates the leader’s revenue yielded by several pricing functions obtained trough the data structures defined during the initializing phase. Let KU = {u ∈ V : (u, v) ∈ K} and KV = {v ∈ V : (u, v) ∈ K}.

SFPP-CL: initializing phase

Step 1 Compute c∞(u, v) ∀u, v ∈ V .

Step 2 ∀u ∈ L, v ∈ L ∪ KV , let Xuv := [e = xuv(0), xuv(1), . . . , xuv(ruv) = pC (u)] be the vector given by the abscissa of all the vertices of the polyhedron Puv := Tz∈C∪{v} {[x, y] : e ≤ x ≤ pC (u), y ≤ fuzv(x) := d(u, z) · x + c∞(z, v)} listed in increasing order (in order to compute Xuv, see [ 13 ]). Let Zuv := [zuv(s)]s∈[ruv] be the vector such that zuv(s) = arg maxz∈C∪{v}{d(u, z) : [xuv(s), fuzv(xuv(s))] is a vertex of Puv} ∀s ∈ [ruv]. The usefulness of the vectors Xuv and Zuv is that, if an optimal pricing function p∗L verifies that p∗L(u) ∈]xuv(s − 1), xuv(s)] (set xuv(−1) = −∞), then the itinerary Du∗v := [u, zuv(s), v] minimizes cg(p∗L, D) among all the itineraries of the form D = [u, z, v] with z ∈ C ∪ {v}. This observation will imply the correctness of the running phase of SFPP-CL. Before describing this phase, we present an algorithm that, given pL, computes g(pL) and which will be used as a subroutine in the running phase (note that this algorithm can also be used to certify that the SFPP belongs to NP).

SFPP-CL-C algorithm (SFPP-CL-Certificate algorithm)

Step 1 Given a ∈ L and b ∈ L ∪ KV , let sab be the smallest strictly positive integer such that pL(a) ≤ xab(sab) and, given (u, v) ∈ K, let Guv = (Vuv, Euv, wuv) be a connected weighted graph that has an edge (a, b) with w(a, b) = [c∞(a, b), 0] if a ∈ {u} \ L and b ∈ L ∪ {v}, w(a, b) = [pL(a) · d(a, zab(sab)) + c∞(zab(sab), b), (pL(a) − e) · d(a, zab(sab))] if a ∈ L and b ∈ L ∪ {v}.

Step 2 Evaluate the length of the shortest path from u to v in the graph Guv ∀(u, v) ∈ K, which is equal to g(pL, u, v) (because of the observation we did when discussing the initializing phase). Finally, compute and return g(pL).

SFPP-CL: running phase

Step 1 Fix a set KL ⊆ K of |L| elements. Let KUL := KU ∩KL and KVL := KV ∩ KL. Given u ∈ L, let Xu = [e = xu(0), xu(1), . . . , xu(ru) = pC (u)] be the vector obtained by sorting the elements of the vectors Xuv with v ∈ L ∪ KVL. Let Zu = (zu(t, v))t∈[ru],v∈L∪KV be a matrix of nodes in V , in which the generic zu(t, v) is equal to the node zuv(s) if xuv(s − 1) < xu(t) ≤ xuv(s), where s ∈ [ruv].

Step 2 Let T = [t(u)]u∈L be a vector of integers indexed in L, such that 1 ≤ t(u) ≤ ru ∀u ∈ L. Let GT = (VT , ET ) be a connected graph such that ET has the edges (u, zu(t(u), v)), (zu(t(u), v), v), (z, v) with z ∈ KUL, u ∈ L, v ∈ L ∪ KVL.

Step 3 Fix L−, L+ ⊆ L such that L− ∩ L+ = ∅ and set r := |L| − |L−| − |L+|.

Let DT2 := {(Ds, Ds0)}s∈[r] be a set of r pairs of strong itineraries such that, ∀s ∈ [r], Ds and Ds0 both start at u and end at v, with (u, v) ∈ KL and are simple paths in GT .

Step 4 Solve a linear system in the unknown variables yielded by pL, with the following |L| equations: c(pL, Ds) = c(pL, Ds0) ∀s ∈ [r], pL(u) = xu(t(u) − 1) ∀u ∈ L− and pL(u) = xu(t(u)) ∀u ∈ L+. If the system has only one solution pL with pL(u) ∈]xu(t(u) − 1), xu(t(u))[ ∀u ∈ L \ {L− ∪ L+}, compute g(pL) by using SFPP-CL-C.

Step 5 Run Steps 1, 2, 3 and 4 for all possible choices of KL, T , L−, L+ and DT2 and return the best pricing function among the considered ones.

The following theorem holds.

Theorem 2 SFPP-CL solves the SFPP in polynomial time when |L| = O(1). 3

An Approximation Algorithm: the Class SGPS

Given a generic pricing problem, a uniform pricing function, or UPF, is an assignment of the same price to all the priceable elements. An optimal uniform pricing function, or UPF∗, maximizes the leader’s revenue among all the UPFs. We introduce the class of Stackelberg Games with Priceable Sets, or SGPS, extending that of Stackelberg Network Pricing Games described in [ 6 ], and characterize the approximation factor provided by an UPF∗ in these games. Furthermore, we define an algorithm that finds an UPF∗, prove that the SFPP belongs to class SGPS and adapt such an algorithm to the SFPP.

A game in SGPS is a tuple (E, C, L, pC , w, E, K, {λi}i∈K , {Fi}i∈K , ) such that E is a set, {C, L} is a partition of E, pC : C → R≥0 is a pricing function, w : L → R≥0 is a weight function, E := {E1, E2, . . . Er} is a partition of L, K is a set of followers and, ∀i ∈ K, λi is the weight of follower i and Fi ⊆ P(E) is the family of sets that can be purchased by follower i. We call competitor’s elements the elements of C and leader’s elements the elements of L. Given pL : E → R≥0 and F ⊆ E, we define a cost c and a revenue g as follows: g(pL, F ) := X

X E0∈E e∈E0∩F w(e) · pL(E0), c(pL, F ) :=

X pC (e) + g(pL, F ). e∈F ∩C Let cg(pL, F ) := [c(pL, F ), g(pL, F )]. Given i ∈ K, let [c(pL, i), g(pL, i)] := cg(pL, i) := minF ∈Fi cg(pL, F ), where the minimum is defined according to the ordering relation ≺. Informally, c(pL, i) is the cost of follower i when choosing a subset F ∈ Fi of minimum cost and g(pL, i) is the contribution of follower i to the leader’s revenue recalling that, when a follower has different optimal choices, she adopts the one providing the highest revenue to the leader. Let F ∗(pL, i) ∈ Fi be a set minimizing the function cg(pL, i), that is, an optimal choice for follower i. The leader’s revenue g(pL) is equal to Pi∈K λi · g(pL, i). In order for g to be bounded, we suppose that, ∀i ∈ K, ∃F ∈ Fi such that F ⊆ C. Our objective is to find a pricing function p∗L maximizing g. Different families of games in SGPS can be defined by different choices of {Fi}i∈K . The main differences with the Stackelberg Network Pricing Games are that single elements cannot be priced independently in general, since the leader has to assign the same price to every set in E, and that the prices are weighted by the function w.

Given θ ≥ 0, pθ is an UPF such that pθ(E0) = θ ∀E0 ∈ E. Let SG1 be a game in SGPS with one follower only (it is then possible to avoid considering the follower’s weight and to omit the index 1 in several functions) and let SG2 be the game obtained from SG1 by setting E = {{e}}e∈L. Note that the maximum leader’s revenue g1∗ in SG1 is lower than the maximum leader’s revenue g2∗ in SG2 and that a same UPF gives the same leader’s revenues in both games. Hence, given the leader’s revenues g1∗,θ and g2∗,θ yielded by an UPF∗ for SG1 and SG2, respectively, we have that g1∗/g1∗,θ ≤ g∗/g2∗,θ. From this observation, in order to find un upper 2 bound on the approximation factor yielded by an UPF∗ for both games SG1 and SG2, we can restrict our analysis only to SG2. Let W, C : P(E) → R≥0 be two functions such that W (F ) = Pe∈F ∩L w(e) ∀F ⊆ E and C(F ) = Pe∈F ∩C pC (e). Let X := {W (F ∗(pθ)) > 0 : θ ≥ 0} be the optimal weights vector of follower 1 and consider it as a vector X := [x(j) := xj]j∈[n] sorted in increasing order.

We define three functions θ, c, Δ : X → R≥0 such that, given xj ∈ X, it holds that θ(xj) := θj := max{θ ∈ R≥0 : W (F ∗(pθ)) = xj}, c(xj) := cj := min{C(F ) : W (F ) = xj, F ∈ F } and Δ(xj) := Δj := c(x0) − c(xj). Note that the function θ is decreasing in its argument. We call functions θ and c, respectively, the optimal prices function and the optimal costs function of follower 1. We observe that, ∀j ∈ [n], assuming that θ0 · x0 = ∞ · 0 = 0, it holds that (2) (3) c(pθj ) = cj + θj · xj = cj−1 + θj · xj−1. This implies the following equation: θj = cj−1 − cj = Δj − Δj−1 .

xj − xj−1 xj − xj−1 Let p∗L be an optimal pricing function, the following relationship holds: c(p∗L) − g(p∗L) = C(F ∗(p∗L)) ≥ min{C(F ) : F ∈ F } = C(F ∗(p0)) = cn. Moreover, we have c(p∗L) ≤ c0. By using the previous inequalities, we get

g(p∗L) = c(p∗L) − (c(p∗L) − g(p∗L)) ≤ c0 − cn = Δn.

Let Wm := x1, WM := xn, θm := θn, θM := θ1. By exploiting inequalities (2) and (3), it is possible to prove the following fundamental theorem in analogy with the results in [ 6 ].

Theorem 3 Any UPF∗ pθ∗ provides an approximation guarantee of 1 + ln(min{WM /Wm, θM /θm}) to both SG1 and SG2.

Now we can generalize the previous theorem to the case of more followers. We use the subscript i to denote the quantities previously defined for the case of a single follower when instantiated to follower i. Let SG0 be a generic game in SGPS and define θm ≤ mini∈K θm,i, θM ≥ maxi∈K θM,i, Wm ≤ mini∈K Wm,i, WM ≥ maxi∈K WM,i. Let λm := mini∈K λi and λM := Pi∈K λi.

The following result holds.

Theorem 4 Any UPF∗ pθ∗ provides an approximation guarantee of 1 + ln(min{(WM /Wm) · (λM /λm), θM /θm}) to SG0.

Now, we design an algorithm to find an UPF∗. Given i ∈ K, let Xi := [xi(j) := i xj]j∈[ni] be the optimal weights vector of follower i and let X := [x(h) := xh]h∈[n] be a vector sorted in increasing order containing all the values in Xi and such that ∃F ∈ Fi : x(h) = W (F ) ∀h ∈ [n], ∀i ∈ K. Moreover, let Ci := [ci(h) := cih]h∈[n] be the vector such that, ∀h ∈ [n], ci(h) = c(xh), where c denotes the optimal costs function of follower i. We suppose that the vectors X and (Ci)i∈K are known. Let Θi := [θi(j) := θj]j∈[ni] be the vector such that, i ∀j ∈ [ni], θi(j) = θ(xij), where θ denotes the optimal prices function of follower i. Observe that Θi is the vector given by the positive abscissa of all the vertices of the polyhedron Pi := T ih + θ · xh , and Xi is the vector such that xij h=∈[nm]a[xθ{,xyh]::θ[∈θji ,Rf,hiy(θ≤ji )f]hiis(θa) v:=ertcex of Pi}. By these characterizations we can compute (Xi)i∈K and (Θi)i∈K in O(|K|n log(n)) time (see [ 13 ] for further details). Let Θ = [θ(h) := θh]h∈[m] be the sorted fusion of the vectors (Θi)i∈K without the eventual null element. Θ can be computed in O(|K|n log(|K|)) time. Given i ∈ K and h ∈ [m], let j(h, i) ∈ [ni] be such that i i i i θj(h,i) ≥ θh > θj(h,i)+1 (set θn1+1 := 0). Observe that W (F ∗(pθh , i)) = xj(h,i) i and then g(pθh , i) = θh · xj(h,i). Since there exists h∗ ∈ [m] such that pθh∗ is a UPF∗, by the above arguments, we have that g(pθh∗ ) = max g(pθh ) = max X λi · g(pθh , i) = max X λi · θh · xj(h,i). (4) i h∈[m] h∈[m] i∈K h∈[m] i∈K

Observe that g(pθh∗ ) can be computed in O(|K|n) time, by using the characterization provided in (4). So, we can define an algorithm that returns a UPF∗ starting from X and (Ci)i∈K , and that runs in O(|K|n(log(|K|) + log(n))) time. We call this algorithm Perfect-Single-Price algorithm (PSP); it differs from the Single-Price algorithm given in [ 6 ] since the approximation ratio of the latter (which is worse than the one of PSP algorithm) and its complexity depend on an arbitrary given in input. An approximation ratio provided by this algorithm can be obtain by setting Wm := x(1), WM := x(m), θm := θ(m), θM := θ(1).

To apply the PSP algorithm to the SFPP, we reformulate the SFPP as a game in SGPS. Given an instance I := (G, K, {λuv}(u,v)∈K , L, C, pC , e) of the SFPP, define an instance I0 := (E0, C0, L0, p0C , w0, E, K, {λuv}(u,v)∈K , {Fuv}(u,v)∈K ) in the class SGPS as follows. Let E0 = C0 ∪ L0 be a set of edges in a graph (V 0, E0) defined as follows: given u ∈ L, v ∈ C and z ∈ V , create a node zu0v, insert in L0 an edge (u, zu0z) with w0((u, zu0z)) = d(u, z), insert in C0 an edge (zu0z, z) with p0C ((zu0z, z)) = e · d(u, z), insert in C0 an edge (v, z) with p0C ((v, z)) = pC (v) · d(v, z). Given u ∈ L, set Eu = {(u, zu0z) ∈ L0} and E := {Eu}u∈L. Set, ∀(u, v) ∈ K, Fuv equal to the set of all the paths connecting u to v in (V 0, E0). Given two pricing functions pL and p0L for the problems I and I0, respectively, such that pL(u) = p0L(Eu) + e ∀u ∈ L, we have that g(pL) = g(p0L). Moreover, by assigning uniformly the prices θ and θ0 := θ − e to I and I0, respectively, we obtain that the length of the sub-path covered by follower (u, v) ∈ K by using fuel bought from the leader in I, is equal to W (Fu∗v(pθ0 )). From these observations, if one transforms I into I0 and applies the PSP algorithm to I0, I can be approximated according to the performance guarantee stated in Theorem 4.

To apply the PSP algorithm, we need a preliminary procedure to find the vectors X and (Cuv)(u,v)∈K . Observe that we can set X := {d(u, v) > 0 : u ∈ L, v ∈ C ∪ KV } := [x(h)]h∈[l] to apply the PSP algorithm, since every follower, given an UPF, can always choose a path such that only a subpath is covered using fuel bought from the leader. Because of this fact, we also have that Cuv(h) = min{c∞(u, z) + e · d(z, z0) + c∞(z0, v) : d(z, z0) = x(h), z ∈ L, z0 ∈ C ∪ {v}} ∀h ∈ [l] and ∀(u, v) ∈ K. Observe that, given (u, v) ∈ K, Cuv can be computed in O(|L| · |C|) ⊆ O(n2) time. To approximate the SFPP, compute the vectors X and (Cuv)(u,v)∈K and apply the PSP algorithm to these vectors. The resultant algorithm, that we call SFPP-PSP, requires O(n4) time in the worst-case.

We conclude by showing that the approximation ratio provided by the SFPPPSP algorithm is tight and also significantly high. Consider an instance with 2Vi−=n a{nvdi}ip∈C[n(+vi1)], =E 2=n−{i(vi, vi+1)}i∈[n], C = L = V \ {vn+1}, w((vi, vi+1)) = ∀i ∈ [n], e = 0, K = {(v1, vn+1)}. Observe that the optimal assignment p∗L verifies that p∗L(vi) = pC (vi) ∀i ∈ [n − 1] and so g(p∗L) = Pin=1 2i−n · 2n−i = n. Observe that an UPF∗ is of the form p(2i), with i ∈ [n − 1] ∪ {0}, and we have that g(p(2i)) = Pn−1−i 2−j. Therefore p(20) = p(1) j=0 is an UPF∗ and g(p(1)) = Pjn=−01 2−j n−→→∞ 2. Hence, the approximation ratio provided by the SFPP-PSP algorithm is asymptotically equal to g(p∗)/g(p(1)) = n/2, and so it is very high. Since this instance verifies 1 + ln(WM /Wm) = 1 + ln(Pin=1 w((vi, vi+1))/w((v1, v2))) = 1 + ln(Pin=−01 2i) = 1 + ln(2n − 1) ∼ ln(2n) = ln(4) · n/2 ' 1.386 · n/2 and 1 + ln(θM /θm) = 1 + ln(2n−1) ∼ ln(4) · n/2, we have that the approximation ratio claimed in Theorem 3 for the SFPP may not be asymptotically improved. By using an instance of SFPP similar to the previous one, it is possible to prove that also the approximation ratio 1 + ln(λM /λm) claimed in Theorem 4 is asymptotically tight.

References

1. P. Alimonti and V. Kann . Hardness of approximating problems on cubic graphs . In Proc. of the 3rd Italian Conference on Algorithms and Complexity (CIAC) , LNCS 1203 , Springer, pp 288 - 298 , 1997 .

2. D. Bilo`, L. Guala`, S. Leucci , and G. Proietti . Specializations and generalizations of the Stackelberg minimum spanning tree game . In Proc. of the 6th Workshop on Internet and Network Economics (WINE) , LNCS 6484 , Springer, pp. 75 - 86 , 2010 .

3. D. Bil`o, L. Guala`, G. Proietti, and P. Widmayer . Computational aspects of a 2-player Stackelberg shortest paths tree game . In Proc. of the 4th Workshop on Internet and Network Economics (WINE) , LNCS 4858 , Springer, pp. 251 - 262 , 2008 .

4. M. Bouhtou , A. Grigoriev , S. van Hoesel , A. van der Kraaij , F. Spieksma , and M. Uetz . Pricing bridges to cross a river . Naval Research Logistics , 54 ( 4 ): 411 - 420 , 2007 .

5. P. Briest , P. Chalermsook , S. Khanna , B. Laekhanukit , and D. Nanongkai . Improved hardness of approximation for Stackelberg shortest-path pricing . In Proc. of the 6th Workshop on Internet and Network Economics (WINE) , LNCS 6484 , Springer, pp. 444 - 454 , 2010 .

6. P. Briest , M. Hoefer , and P. Krysta . Stackelberg network pricing games . Algorithmica , 62 ( 3-4 ): 733 - 753 , 2012 .

7. J. Cardinal , E. D. Demaine , S. Fiorini , G. Joret, S. Langerman , I. Newman , and O. Weimann . The Stackelberg minimum spanning tree game . Algorithmica , 59 ( 2 ): 129 - 144 , 2011 .

8. J. Cardinal , E. D. Demaine , S. Fiorini , G. Joret, I. Newman , and O. Weimann . The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs . Journal of Combinatorial Optimization , 25 ( 1 ): 19 - 46 , 2013 .

9. S. Khuller , A. Malekian , and J. Mestre . To fill or not to fill: The gas station problem . ACM Transactions on Algorithms , 7 ( 3 ): 36 , 2011 .

10. D. G. Kirkpatrick, and R. Seidel . The ultimate planar convex hull algorithm . SIAM Journal on Computing , 15 ( 1 ): 287 - 299 , 1986 .

11. M. Labb´e, P. Marcotte, and G. Savard . A bilevel model of taxation and its application to optimal highway pricing . Management Science , 44 ( 12 ): 1608 - 1622 , 1998 .

12. S. Roch, G. Savard, and P. Marcotte . An approximation algorithm for Stackelberg network pricing . Networks , 46 ( 1 ): 57 - 67 , 2005 .

13. M. I. Shamos , and D. Hoey . Geometric intersection problems . In Proc. of the 17th Annual Symposium on Foundations of Computer Science (FOCS) , IEEE Computer Society , pp. 208 - 215 , 1976 .

14. S. van Hoesel. An overview of Stackelberg pricing in networks . Research Memoranda 042 , Maastricht: METEOR, Maastricht Research School of Economics of Technology and Organization, 2006 .

15. H. von Stackelberg. Marktform und Gleichgewicht (Market and Equilibrium) . Verlag von Julius Springer , Vienna, 1934 .