Ariel Waserhole

Vincent Jost

Pricing in Vehicle Sharing Systems: Optimization in queuing networks with product forms

Keywords: Vehicle Sharing Systems, Pricing, Demand regulation, Closed Queuing Networks, Product forms and BCMP theory, Continuous-time Markov decision process, Stochastic Optimization, Approximation algorithms, Network flows, Greedy Algorithm

One-way Vehicle Sharing Systems (VSS) such as Vélib' Paris are flourishing. The usefulness of VSS for users is highly impacted by the availability of vehicles and parking spots. Most existing systems are ruled by the trips of users. We study the potential interest of influencing the users in order to improve the performance of the system. We assume that each user is associated with a pair origin-destination (O-D) of stations, and only interacts with the system if his O-D trip is available. We consider leverage that can influence the rate of user requests for each pair O-D, such as a price that will be prohibitive for a prescribed proportion of users. We focus on optimizing the number of trips taken in the system.

In order to provide exact formulas and analytical insights, transportation times are assumed to be null, stations to have infinite capacities and the demand to be stationary over time. In other words, VSS are modelled as closed queuing networks with infinite buffer capacity and Markovian demands. We propose a heuristic based on computing a Maximum Circulation on the demand graph together with a convex integer program solved optimally by a greedy algorithm. For M stations and N vehicles, the performance ratio of this heuristic is proved to be exactly N/(N + M -1). We discuss our understanding on the possibility of extending this result to more realistic models in the perspectives. The complexity of computing optimum policies remains open. Insights on this issue are provided in the appendix. The appendix also contains an example showing that VSS can have poor performances without regulation.

Introduction 1.Context

Recently, the interest in Vehicle Sharing Systems (VSS) in cities has increased significantly. Indeed, urban policies intend to discourage citizens to use their personal car downtown by reducing the number of parking spots, street width, etc. VSS seem to be a promising solution to reduce jointly traffic and parking congestion, noise, and air pollution (proposing bikes or electric cars). They offer personal mobility allowing users to pay only for the usage (sharing the cost of ownership).

Based on a sample of 22 US studies, [START_REF] Shoup | The High Cost of Free-Parking[END_REF] reports that car drivers looking for a parking spot contribute to 30% of the city traffic. Moreover cars are used less than 2 hours per day on average but still occupy a parking spot the rest of the time. However it is not clear how to improve this situation. Can a suitable design and management of VSS contribute any progress ?

We are interested in short-term one-way sharing systems in which vehicles can be taken and returned at different places. Associated with classic public transportation systems, short-term one-way sharing systems help to solve one of the most difficult public transit network design problems: the last kilometer issue [START_REF] Demaio | Bike-sharing: History, impacts, models of provision, and future[END_REF]. Round-trip sharing systems, where vehicles have to be returned at the station where they were taken, cannot address this issue.

The first large-scale short-term one-way sharing systems was the Bicycle Sharing System (BSS) Vélib'. It was implemented in Paris in 2007. Today, it has more than 1200 stations and 20 000 bikes selling around 110 000 trips per day. It has inspired several other cities all around the world: Now more than 300 cities have such a system, including Montréal, Bejing, Barcelona, Mexico City, Tel Aviv.

A new type of VSS has appeared recently: one-way car sharing systems as Autolib' in Paris and Car2go in more than 15 cities (Vancouver, San Diego, Amsterdam and Ulm among other). Cars are bigger and more expensive; Car Sharing Systems (CSS) have usually less vehicles and stations with smaller capacities. For instance Autolib' has 1800 cars, 800 stations with capacity ranging from 1 to 6 parking spots. As CSS stations need more space than BSS ones, it can be an issue to install them in dense cities. Autolib' and Car2go have chosen small cars (respectively a Bluecar and a Smart) probably for this reason. Rental prices are higher in CSS since people are more willing to pay for renting a car than a bike. Pricing in this context should be a better leverage.

One-way Vehicle Sharing Systems: a management issue

One-way systems increase the user freedom at the expense of a higher management complexity. In round trip rental systems, while managing the yield, the only stock that is relevant is the number of available vehicles. In one-way systems, vehicles are not the only key resource anymore: parking stations may have limited number of spots and the available parking spots become an important control leverage.

Since first BSS, problems of bikes and parking spots availability have appeared frequently. [START_REF] Côme | Model-based clustering for BSS usage mining: a case study with the vélib ' Äô system of paris[END_REF], among others, applies data mining to operational BSS data. He offers insights on typical usage patterns to understand causes of imbalances in the distribution of bikes. Reasons are various but we can highlight two important phenomenons: the gravitational effect which indicates that a station is constantly empty or full (as Montmarte hill in Vélib'), and the tide phenomenon representing the oscillation of demand intensity during the day (as morning and evening flows between working and residential areas).

To improve the efficiency of the system, different perspectives are studied in the literature. At a strategic level, some authors consider the optimal capacity and locations of stations. [START_REF] Shu | Bicycle-sharing system: Deployment, utilization and the value of re-distribution[END_REF] propose a stochastic network flow model to support these decisions. Their model is used to design a BSS in Singapore based on demand forecast derived from current usage of the mass transit system. [START_REF] Lin | Strategic design of public bicycle sharing systems with service level constraints[END_REF] consider a similar problem but formulate it as a deterministic mathematical model.

At a tactical level, other authors investigate the optimal number of vehicles given a set of stations. [START_REF] George | Fleet-sizing and service availability for a vehicle rental system via closed queueing networks[END_REF] study the fleet sizing problem with constant demand and infinite parking capacities. Fricker and Gast (2012) and Fricker et al. (2012) consider the optimal sizing of a fleet in "toy" cities, where demand is constant over time and identical for every possible trip, and all stations have the same capacity K. They show that even with an optimal fleet sizing in the most "perfect" city, if there is no operational system management, there is at least a probability of 2 K+1 that any given station is empty or full. At an operational level, in order to be able to meet the demand with a reasonable standard of quality, in most BSS, trucks are used to balance the bikes among the stations. The balancing problem amounts to scheduling truck routes to visit stations performing pickup and delivery. In the literature many papers deal already with this problem. A static version of the BSS balancing problem is analyzed in [START_REF] Raviv | Static repositioning in a bike-sharing system: models and solution approaches[END_REF] and a dynamic one in [START_REF] Contardo | Balancing a dynamic public bike-sharing system[END_REF].

Towards VSS regulated with incentives

For one-way car sharing systems such as Autolib' or Car2go, due to the size of cars, operational balancing optimization through relocation with trucks seems inappropriate. Another way for optimizing the system has to be found.

From an experimental point view, pricing heuristics are studied by [START_REF] Chemla | Self-service bike sharing systems: Simulation, repositioning[END_REF] and [START_REF] Pfrommer | Dynamic vehicle redistribution and online price incentives in shared mobility systems[END_REF]. They appear to perform well in their simulations. However, they do not provide any analytical/mathematical insight on the potential gain of a pricing optimization. Fricker and Gast (2012) analyze a heuristic, that can be seen as a dynamic pricing, called "power of two choices": When a user arrives at a station to take a vehicle, he gives randomly two possible destination stations and the system is directing him toward the least loaded one. For their perfect cities, they show that this policy allows to drastically reduce the probability to be empty or full for each station from 2 K+1 to 2 -K 2 . A VSS stochastic pricing model is proposed in Waserhole and Jost (2013) considering timedependent demand and station capacities. They study a fluid approximation that provides a static heuristic policy and an upper bound. The fluid approximation is deterministic; one can wonder if a stochastic model, even considering less constraints, can have a better performance.

Structure of the paper

We investigate stochastic models allowing an analytic formula for the performance evaluation of the system.

In Section 2, we consider VSS in which each user is interested in a specific origin-destination (O-D) pair of stations, but is sensitive to the price of this trip. We discuss how prices can be made implicit when considering objectives such as the maximization of the expected number of trips sold by the system.

In Section 3, we consider VSS with stationary O-D demands and infinite station capacities, as in [START_REF] George | Fleet-sizing and service availability for a vehicle rental system via closed queueing networks[END_REF], but we also assume null transportation times. Under these assumptions, the VSS can be modelled as a closed queuing network of BCMP type [START_REF] Baskett | Open, closed, and mixed networks of queues with different classes of customers[END_REF]. Its performance can therefore be computed analytically. We define static and dynamic stochastic pricing problems on such queuing networks.

In Section 4 we study a static heuristic policy, and prove that for M stations and N vehicles, its guaranty of performance is N N +M -1 . This result is the main goal and contribution of the paper. This heuristic is mainly based on a Maximum Circulation on the demand graph. It may occur that the Maximum Circulation disconnects the city, in which case, vehicles have to be spread among the connected components. The vehicle distribution problem is proved to be solved optimally by a greedy algorithm.

In Section 5, we mention several extensions that shall be addressed before attempting to apply our results to real life VSS. We discuss how these extensions would impact the results discussed here.

In Appendix A, we discuss the properties of optimal dynamic and static policies. An optimal dynamic policy can be computed with an action decomposable Markov decision process. An example shows that VSS can have poor performances without regulation.

Protocol, incentives and implicit pricing

In this section we specify how each user interacts with the system. This interaction is formalized as an chart of events, that we call the protocol. The protocol required for this study is extremely simple thanks to the assumptions made on VSS. The only subtlety (and originality) is the interaction between the price of a trip and the willingness of a user to take the trip. This interaction can be seen in two equivalent ways. Either the user asks the price and then decides whether he wants to take the trip. Or the system sets the price and then users who find it too expansive never exist in the system. The later description is used in this paper since it is simpler for our purpose.

A simple protocol

We consider a real-time station-to-station protocol as defined in Figure 1. A user asks for a vehicle at station a (here and now), with destination b. The system offers a price (or rejects the user = infinite price). The user either pays the price and the vehicle is transferred from a to b, or leaves the system.

Concept of maximum potential demand

We assume that for each trip (a, b) and independently of the other trips, there is a pool of potential users that may try to take trip (a, b) in the time horizon of the model. We denote this pool Λ a,b , which, in this paper is interpreted as a Poisson arrival of users with intensity Λ a,b per time unit (but other deterministic interpretations of Λ a,b are discussed in (Waserhole et al., 2013b;Waserhole and Jost, 2013)).

Pricing policies and incentives

We assume that there exist leverages (incentives) able to decrease the maximum demand (separately for each trip). A classic incentive is the price to take a trip; the demand is then a function of the price: basically, the higher the price, the lower the demand. A pricing/incentive policy is static if the price to take each trip is independent of the state of the system. A policy is dynamic otherwise.

Continuous elastic demand

In this study we focus on continuous pricing optimization with the following hypothesis: Let Λ a,b be the maximum demand of users who want to take a trip between stations a and b. There exists a price p(λ a,b ) to obtain any demand λ a,b ∈ [0, Λ a,b ]. A price function is schemed Figure 2. Notice that, in this example, the maximum demand Λ is obtained with a minimum price p(Λ) that is negative. Indeed it is conceivable that the system chooses to pay users (or employees) to take certain trips (instead of paying trucks for relocation).

Implicit pricing

One problem with pricing incentives is the hardness to make explicit the elasticity function (also calld dmand curve). It can be a complex function (not continuous, with thresholds...). Moreover, setting the proper prices to obtain a fixed (optimized) demand might require the skills of an economist and experimental studies. On the other hand, there exist some objectives such as maximizing the number of trips sold (transit) or the total travel time that do not need an explicit elasticity function. The only data necessary for such optimization is the space of the possible demand, for instance λ ∈ [0, Λ] for continuous elastic demand. With such assumptions, prices become implicit and pricing policies can be seen as incentive policies or simply policies regulating demand.

For these reasons, the results in this paper focus on the transit optimization. The first question one might raise is whether it is possible to improve on the number of trips sold by the generous pricing policy that is accepting the maximum potential demand (for every trip (a, b) the generous pricing policy sets the demand λ a,b = Λ a,b ). Let us explain why this question is not trivial. For a given pricing/incentive policy λ, for each trip (a, b) we distinguish between the potential demand λ a,b ∈ [0, Λ a,b ] and the satisfied demand y λ a,b ∈ [0, λ a,b ] (the average flow of users served). This difference is schemed in Figure 3. The question amounts to finding a pricing policy λ such that a,b y λ a,b > a,b y Λ a,b . Finally, one interest of having an explicit formulation of the demand elasticity function is to maximize the revenue of the system. However, solving the revenue induces non-linearities in the optimization model. While the transit maximization (or any other linear function in y λ , such as the maximization of "the total travel time" or "the total gain of travel time by using the system"...) leads to linear optimization models. Avoiding non-linearities (computational complexity) is therefore another reason to focus on transit maximization. We model the VSS dynamics by a stochastic process: the VSS stochastic evaluation model. It measures VSS performances for a given policy (demand vector). We use this evaluation model to compare the performance of the proposed pricing policies in terms of number of trips sold. We now define formally the VSS stochastic evaluation model under the real-time station-to-station protocol (defined in Figure 1).

ÎËË ËØÓ ×Ø Ú ÐÙ Ø ÓÒ ÅÓ Ð

• ÁÒÔÙØ

• A number N of vehicles and a set M of stations:

-A set S of states: S n a : a ∈ M / a∈M n a = N ; -State s = (n a : a ∈ M) represents the vehicle distribution in the city space: n a is the number of vehicles in station a ∈ M.

• A policy λ:

-λ s a,b is the arrival rate of users to take the trip (a, b) ∈ D = M×M, between state s = (. . . , n a ≥ 1, . . . , n b , . . .) ∈ S and state (. . . , n a -1, . . . , n b + 1, . . .) ∈ S; -The graph spanned by s ∈ S / ∃(a, b) ∈ D, λ s a,b > 0 is supposed to be strongly connected.

• ÇÙØÔÙØ The expected number of trips sold in the steady state behaviour of the continuous-time Markov chain defined by states S and transition rates λ.

In general, the number of states is exponential in the number of vehicles and stations, its exact value can be computed using a well-known combinatorial formula.

Proposition 1. The number of state of the Markov chain for N vehicles and M stations with infinite station capacities and null transportation time is equal to N +M -1 N .

Proof. The states of the Markov chain for N vehicles and M stations are in one to one mapping with non-decreasing functions from {1, . . . , N} to {1, . . . , M} which are in one to one mapping with strictly increasing functions from {1, . . . , N} to {1, . . . , M + N -1}.

Steady-state distribution of the continuous-time Markov chain

For any strongly connected dynamic policy, the unique stationary distribution π over the state space S of the continuous-time Markov chain with transition rate λ satisfies Equations (1) (Guo and Hernánde 2009, p. 47). Let e a be the characteristic vector of coordinate a ∈ M: e a = (0, . . . , 0, n a = 1, 0, . . . , 0).

s∈S π s = 1, ( 1a
) (a,b)∈D s-ea+e b ∈S π s λ s a,b = (b,a)∈D, s ′ ∈S s ′ -e b +ea=s π s ′ λ s ′ b,a , ∀s ∈ S, (1b)
π s ≥ 0, ∀s ∈ S. (1c)

Closed queuing network model for static policies

The VSS stochastic evaluation model can be represented as a closed queueing network for static policies. An example with 2 stations is schemed in Figure 4. This closed queuing network is built as follows.

Since there is a fixed number of vehicles circulating in the network, it is natural to see the system from a vehicle's perspective. Each station a ∈ M is represented by a server a with infinite capacity queue. The N vehicles are N jobs waiting in these queues for users to take them. The service rate λ a of server a is equal to the average number of users willing to take a vehicle at station a:

Analytic evaluation for static policies

The stochastic evaluation model for static policies is the same as the one considered by George and Xia (2011) but with null transportation times. They provide a compact form to compute the system performance using the BCMP network theory [START_REF] Baskett | Open, closed, and mixed networks of queues with different classes of customers[END_REF]. In Section 4.2, we consider static policies providing demands for which the performance evaluation is slightly simpler than the formula of [START_REF] George | Fleet-sizing and service availability for a vehicle rental system via closed queueing networks[END_REF], see Lemma 1.

An important concept that we use for a static policy (with demand λ) is the availability A a of (a vehicle at) station a ∈ M which is the probability that station a contains at least one vehicle. Availabilities satisfy steady-state equations:

b∈M A a λ a,b = b∈M A b λ b,a , ∀a ∈ M. (2)
Notice that availabilities are not totally determined by (2) because they also depend on the number of vehicles.

The VSS stochastic pricing problem

We want to maximize the VSS performance assuming we have a control on the demand for each trip (using pricing). The efficiency of a pricing policy is measured by the VSS stochastic evaluation model. We call this problem the VSS stochastic pricing problem.

ÎËË ËØÓ ×Ø ÓÒØ ÒÙÓÙ× ÈÖ Ò ÌÖ Ò× Ø Å Ü Ñ Þ Ø ÓÒ

• ÁÒ×Ø Ò :

• A number N of vehicles available;

• A set M of stations with infinite capacities;

• The maximum demand per time unit Λ a,b to take every trip (a, b) ∈ D.

• ËÓÐÙØ ÓÒ:

[Dynamic Policy] A demand λ a,b (s) ∈ [0, Λ a,b ], to take each trip (a, b) ∈ D function of the system's state s ∈ S. [Static Policy] A tuple (λ, k, -→ M, -→ N )
, where:

• λ a,b ∈ [0, Λ a,b ] is the demand to take each trip (a, b) ∈ D, • λ defines a set of k strongly connected components -→ M = {M 1 , . . . , M k }, • -→ N = (N 1 , . . . , N k ) is the vehicle distribution over -→ M, ( k i=1 N i = N).
• Å ×ÙÖ : The expected number of trips sold of the pricing policy measured by the stochastic evaluation model.

We restrict the study of dynamic policies to the (dominant) class for which the graph spanned by (a, b) ∈ D, s ∈ S, λ s a,b > 0 has only one strongly connected component. Otherwise, the stationary distribution on the state graph is not unique: it depends on the initial state of the system.

Sometimes optimal static policies need more than one strongly connected components on the station graph. An example is given in Proposition 7 Section A.3. The k strongly connected components of the static policy graph G(M, λ) divides the city into k independent VSS, sharing a number N of vehicles. The vehicle distribution has then to be dealt with since it influences the performance of the policy. For dynamic policies, the vehicle distribution is explicit (defined by the system states for single component policies). That is why for ease of notations the stochastic evaluation model is defined for dynamic policies (any static policy can be represented as a dynamic one).

The previous formal problem definition enables to define tractability, polynomiality or simply efficiency for VSS stochastic pricing optimization. To tackle large scale (real-world) systems, we need solution methods that have computational time polynomial in N and M.

The solutions (pricing policies) produced (output) need also to be of moderate size. Notice that the state graph (of exponential size) representing all possible vehicle distributions (system's states) is not part of the input. The explicit representation of dynamic policies is hence not tractable.

George and Xia (2011) provide a product form formula and algorithms to compute the stochastic evaluation model for a static pricing policy. However, this formula does not seem sufficient to prove membership in NP (the complexity class of problems that are non-deterministic polynomial time solvable) of the following decision problem: "Is there a static pricing policy that sells at least X trips in the stochastic evaluation model?".

All stochastic processes follow exponential distributions (which are totally defined by their means). Assuming that Λ a,b ∈ Z + , ∀(a, b) ∈ D, the size of the input is then M 2 log(Λ max ) + log(N). The size of the instance is polynomial in M, N, log(Λ max ).

Still, to the best of our understanding, the membership of this problem to NP is an open question. Also open is the membership in P (existence of a polynomial time algorithm).

We discuss in Appendix A the problem of characterizing dynamic and static optimal policies. The complexity is unknown for both classes of policies. The deterministic version of the stochastic pricing problem is shown NP-hard in Waserhole et al. (2013b). Nevertheless no known reduction allows using this result in the present paper.

Å Ü ÑÙÑ ÖÙÐ Ø ÓÒ approximation

In this section we study an algorithm approximating the policy maximizing the transit. Our algorithm is based on the Maximum Circulation problem [START_REF] Edmonds | Theoretical improvements in algorithmic efficiency for network flow problems[END_REF], which is a network flow problem with flow conservation at all nodes (no source no sink).

Å Ü ÑÙÑ ÖÙÐ Ø ÓÒ Upper Bound

A vector λ is called a circulation if it is a (feasible, not necessarily optimal) solution of the following LP. Intuitively, in our problem, a demand vector λ is a circulation if at each station, the number of users willing to take a vehicle at the station is the same as the number of users willing to drop a vehicle. . We show that λ ′ is a circulation. The capacity constraints are satisfied by λ ′ since s∈S π s = 1 and hence:

λ ′ a,b = s∈S π s λ s a,b ≤ s∈S π s Λ a,b = Λ a,b , ∀(a, b) ∈ D.
Flow conservation constraints are satisfied by λ ′ because in the steady state of a dynamic policy, a station receives as many vehicles as it is sending. Finally, the expected transit of the system under the dynamic policy λ is equal to (a,b)∈D λ ′ a,b which is the value of circulation λ ′ .

Å Ü ÑÙÑ ÖÙÐ Ø ÓÒ policy

A optimum solution of the Maximum Circulation problem is a demand vector λ ≤ Λ. It is natural to try to use this demand vector as a static policy. However, whenever the Maximum Circulation λ is not strongly connected, one has to specify a vehicle distribution -→ N over the k strongly connected component

-→ M = {M 1 , . . . , M k } defined by λ.
In Proposition 2 we show that this issue may indeed occur. We call a static policy φ = (λ, k,

-→ M, - → N ) a circulation policy if λ is a circulation.
Proposition 2. The optimal solution(s) of Maximum Circulation may consist of more than one strongly connected component (even if the demand graph is strongly connected).

Proof. Consider the demand graph in Figure 5 consisting of Λ = 1 for all arcs (both dotted and solid). The unique Maximum Circulation sets λ = 1 for solid arcs and 0 elsewhere. Its policy demand graph is not strongly connected.

1 1 1 1 1 1 1 1 1 Λ a,f = 1 a b c d e f

Evaluation for a given vehicle distribution

Recall that for a static policy φ, the availability A a (φ) of (a vehicle at) station a ∈ M is the probability that station a contains at least one vehicle. Moreover, to any static policy φ = (λ, k, -→ M, -→ N ) is associated a Continuous-Time Markov Chain, CTMC(φ), that is used for its evaluation.

Lemma 1 explains how to compute the expected transit of a circulation policy. It essentially says that the availability of a station is N N +M -1 for a circulation spanning only one strongly connected component with M stations.

Lemma 1. For any circulation λ and any vehicle distribution

-→ N , the expected transit T (φ) of the circulation policy φ = (λ, k, -→ M, -→ N ) is equal to: T (φ) = k i=1 N i N i + |M i | -1 a,b∈M i λ a,b .
The remaining of Section 4.2.1 is devoted to a proof of Lemma 1. It is done by expressing relations between transit, availability and the continuous-time Markov chain formulation.

Lemma 2. For a static policy φ with a given vehicle distribution, the stationary distribution π over the states of the continuous-time Markov chain CMTC(φ) is unique.

Proof. A Markov chain is said to be irreducible if its state space is a single communicating class (a single strongly connected component); in other words, if it is possible to get to any state from any state. The continuous-time Markov chain CMTC(φ) defined by a static policy φ is irreducible, therefore there is a unique stationary distribution (see for instance, [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]).

The availability A a (π) of station a ∈ M is equal to the sum of the stationary distributions π s of the states s ∈ S where there is at least one vehicle in station a:

A a (π) := s=(s 1 ,...,s M ) / sa≥1 π s .

(3)

Since for any static policy φ, a stationary distribution π can be computed on CTMC(φ), for convenience we also denote:

A a (φ) := A a π(φ) .
The expected transit T (φ) of the static policy φ is then:

T (φ) = a∈M A a (φ) b∈M λ a,b .
We now state a couple of lemmas that combined will prove Lemma 1.

Lemma 3. For a static policy φ, CTMC(φ) is the product of k independent CTMC(φ i ), where

φ i = (λ (a,b)∈M 2 i , 1, {M i }, (N i )
) is a static policy with one single strongly connected component. The expected transit T (φ) is then decomposed as follows:

T (φ) = a∈M A a (φ) b∈M λ a,b = k i=1 a∈M i A a (φ i ) b∈M i λ a,b .
An invariant probability measure of a continuous-time Markov chain is the stationary distribution associated with some initial distribution (over the states of the chain). From Lemma 2, static policies have a unique stationary distribution. Hence strongly connected circulation policies have a unique invariant probability measure. However, for disconnected circulations there exist several invariant probability measures.

The following lemma will be used both to prove Lemma 1 and in Section 4.3.2. We denote by S(N, M) the state set of all distributions of N vehicles among M stations.

Lemma 4. For any circulation λ, π s = 1 |S(N,M )| , ∀s ∈ S(N, M), is an invariant probability measure of the continuous-time Markov chain defined by states S(N, M) and transition rates λ.

Proof. Let λ + a = b∈M λ a,b and λ - a = b∈M λ b,a . Since λ is a circulation we have λ + a = λ - a . Let δ + (s) (resp. δ -(s)) be the sum of the outgoing (resp. incoming) transition rates on state s = (n a : a ∈ M) ∈ S(N, M), we have:

δ + (s) = (a,b)∈D s-ea+e b ∈S(N,M ) λ s a,b = a∈M | na>0 λ + a , and
δ -(s) = (b,a)∈D, s ′ ∈S(N,M ) s ′ -e b +ea=s λ s ′ b,a = a∈M | na>0 λ - a .
Therefore δ + (s) = δ -(s) and hence the vector π satisfying π s = 1 |S(N,M )| , ∀s ∈ S(N, M), is solution of system of Equations (1) of the continuous-time Markov chain with states S(N, M) and transition rates λ: 3)) amounts to computing a ratio between two numbers of states:

(a,b)∈D s-ea+e b ∈S(N,M ) π s λ s a,b = (b,a)∈D, s ′ ∈S(N,M ) s ′ -e b +ea=s π s ′ λ s ′ b,a , ∀s ∈ S(N, M), s∈S(N,M ) π s = 1, π s ≥ 0, ∀s ∈ S(N, M).
A(φ) = |S(N -1, M)| |S(N, M)| = N +M -2 N -1 N +M -1 N = (N +M -2)! (N -1)!(M -1)! (N +M -1)! (N )!(M -1)! = N N + M -1
.here Lemma 6. For a circulation policy φ and for any strongly connected component M i , the availability A(φ i ) of a vehicle at any station a ∈ M i is equal to:

A(φ i ) = N i N i + |M i | -1 .
Proof. Combining Lemma 2 and 4, the unique stationary distribution over the states S(N i , M i ) of CTMC(φ i ) for any circulation policy

φ i = (λ (a,b)∈M 2 i , 1, {M i }, (N i )) is π s = 1 |S(N i ,M i )| , s ∈ S(N i , M i ).
We can hence apply Lemma 5 to conclude.

Proof of Lemma 1. Combine Lemma 3 and 6.

Optimality of the greedy distribution of vehicles

Let {M 1 , . . . , M k } be the set of the k strongly connected components of a circulation λ. If we allocate N i vehicles to component i, the expected transit of the policy

φ i = (λ (a,b)∈M 2 i , 1, {M i }, {N i }) is: T (φ i ) = f i (N i ) = N i N i + M i -1 a,b∈M i λ a,b . (4)
For a distribution -→ N = (N 1 , . . . , N k ) of the N vehicles, the expected transit of policy φ = (λ, k, -→ M, -→ N ) is hence:

T (φ) = f ( -→ N ) = k i=1 f i (N i ). ( 5
)
The optimal distribution -→ N * of the N vehicles among the k strongly connected components is then solution of the following problem:

-→ N * ∈ arg max f ( -→ N ) s.t. k i=1 N i = N, -→ N ∈ Z k + .
Consider Algorithm 1 for finding a feasible solution to the previous problem:

Algorithm 1 Greedy algorithm for load distribution 1:

-→ N := (0, . . . , 0) 2: for n = 1 to N do 3:

Choose j ∈ arg max i∈{1,...,k} f ( -→ N + e i );

4:

-→ N := -→ N + e j ; 5: end for 6: return -→ N .

In general Algorithm 1 may not provide an optimal solution. A function f ( -→ N ) for which there exist functions

f i such that ∀ -→ N , f ( -→ N ) = k i=1 f i (N i ), is called separable. Moreover if each f i is concave, f is called separable concave.
Separable concave functions are of interest in mathematical economics, an example is the gain function ( 5). It turns out that separable concavity is enough for the greedy algorithm to find an optimal solution under the constraint k i=1 N i = N (see Theorem 2). Maximizing separable concave functions can also be done over more complex feasible spaces, such as polymatroids [START_REF] Glebov | About one class of convex integer programs[END_REF][START_REF] Vv Shenmaier | A greedy algorithm for some classes of integer programs[END_REF].

Theorem 2. Let k be a positive integer, {f i } i∈{1,...,k} be concave functions and

N ∈ Z + . Also denote f ( -→ N ) := i f i (N i ).
Then the solution of the following integer program is attained by greedy Algorithm 1.

max k i=1 f i (N i ) s.t. k i=1 N i = N, -→ N ∈ Z k + .
Proof. We give a proof by induction on N. The case N = 0 is trivial since -→ N = (0, . . . , 0) is the only feasible solution. Assume case N is correct: the greedy algorithm provides an optimal solution, say -→ N * for N. Now, let -→ N ′ be an optimal solution for N + 1. Choose j ∈ {1, . . . , k} such that N ′ j > N * j . By induction hypothesis, f (

-→ N * ) ≥ f ( -→ N ′ -e j )
. Also, by concavity of f j and because N ′ j -1 ≥ N * j , one has:

f ( -→ N * + e j ) = f ( -→ N * ) + f j (N * j + 1) -f j (N * j ) ≥ f ( -→ N * ) + f j (N ′ j ) -f j (N ′ j -1) ≥ f ( -→ N ′ -e j ) + f j (N ′ j ) -f j (N ′ j -1) = f ( - → N ′ ).
A solution found by the greedy algorithm is hence at least as good as f ( -→ N * + e j ) which is at least as good as f ( -→ N ′ ).

Corollary 1. For any fixed λ and any

N ∈ Z + , a vehicle distribution - → N ∈ Z k(λ) +
maximizing the expected transit under the constraint k i=1 N i = N can be computed with greedy Algorithm 1. Proof. Let {M 1 , . . . , M k } be the set of the strongly connected components of the static policy graph G(M, λ). For any static policy, the expected transit of the system is the sum of the expected transit of each component, hence the gain function is separable. The concavity of the gain function in each component can be deduced from (4) for circulation policies, and is proved in (George and Xia, 2011, Theorem 2) for general static policies.

Performance evaluation

We study the performance of the Maximum Circulation policy together with its optimal vehicle distribution.

An upper bound on the approximation ratio

The expected transit of the Maximum Circulation policy together with its optimal vehicle distribution can be arbitrarily close to N N +M -1 times the value of a static policy: Proposition 3. For any number M ≥ 2 of stations and any number N of vehicles, the ratio between the value of Maximum Circulation policy and an optimum static policy can be arbitrary close to N N +M -1 . Proof. We consider instances with N vehicles, M ≥ 2 stations M = {1, . . . , M} and demand graph consisting of a circuit {1, . . . , M, 1} with maximum demand Λ i,i+1 = k, i ∈ {1, . . . , M -1} and Λ M,1 = 1 (all other demands are equal to 0).

The Maximum Circulation policy opens all trips of the circuit to 1. Its transit value P Circ * is equal to: P Circ * = N M N +M -1 . Consider the generous static policy opening all trips to their maximum value: λ = Λ. The generous static policy demand graph is a circuit, hence the expected transit (A a × Λ a,b ) is the same for all trips (a, b) of the circuit. The Availability vector A associated with the generous policy satisfies Equations (2), hence:

A M × 1 = A i × k, ∀i ∈ {1, . . . , M -1}, so: a∈M A a = A M 1 + M -1 k .
Since a∈M A a = 1 for one vehicle, and ∀a ∈ M, A a is a non decreasing function of the number of vehicles [START_REF] George | Fleet-sizing and service availability for a vehicle rental system via closed queueing networks[END_REF], we have that a∈M A a ≥ 1. Hence, lim k→∞ A M (k) = 1 and lim k→∞ A i (k) = 0, ∀i ∈ {1, . . . , M -1}. When k → ∞, the value of the generous static policy is then lim k→∞ P Gen (k) = M.

The ratio between the static generous policy and the Maximum Circulation policy can then be arbitrary close to:

N N + M -1 = lim k→∞ P Gen (k) P Circ * (k)
.here

A tight guaranty of performance

Actually, the N N +M -1 upper bound of Proposition 3 is also a lower bound. In other words N N +M -1

is the tight approximation ratio of the proposed heuristic, compared to dynamic (and hence static) policies:

Theorem 3. The transit of the Maximum Circulation policy together with its optimal vehicle distribution is at least N N +M -1 times the transit of an optimum dynamic policy. To the best of our understanding, it is not easy to prove directly that Maximum Circulation policy together with the optimal deterministic vehicle distribution is a N N +M -1 -approximation. We use a probabilistic proof (Lemma 8) relying on a specific random vehicle distribution, for which the expected availability of any station is exactly

N N +M -1 .
Remark 1. The previous proof really relies on the properties of the random uniform vehicle distribution -→ N U . Other random distributions, such as assigning each vehicle independently and with probability proportional to the size of the connected components lead to different availabilities. Actually we observed numerically and we conjecture that this last random distribution leads to availabilities always greater than N N +M -1 . From the perspective of Lemma8, this conjecture is of little importance for the concern of this paper. What remains crucial though, is to realize that these distributions behave differently, and that -→ N U is the one appropriate to prove Theorem 3.

We can now prove the approximation ratio of Maximum Circulation policy together with its optimal vehicle distribution.

proof of Theorem 3. Let Circ * be the optimal value of Maximum Circulation with k strongly connected components {M 1 , . . . , M k }. Component M i is composed with M i stations and contributes to a value C * i in the optimal Maximum Circulation:

k i=1 C * i = Circ * . Let -→
N * be the optimal vehicle distribution for the Maximum Circulation policy. Let -→ N U be the random uniform vehicle distribution. Let P

- → N * Circ * (respectively, P -→ N U Circ * ) be the value of the Maximum Circulation policy with vehicle distribution -→ N * (respectively - → N U ). P - → N * Circ * ≥ E P --→ N U Circ * = E k i=1 A( -→ N U , M i )C * i = k i=1 E A( -→ N U , M i ) C * i = N N + M -1 Circ *
where the first equality comes from Lemma 3, the second is the linearity of expectancy, and the third comes from Lemma 8. Let P dyn * be the value of an optimum dynamic policy. We have finally:

P -→ N * Circ * ≥ N N + M -1 Circ * ≥ N N + M -1 P Dyn * .here

Conclusion and perspectives

We investigated an optimization/control problem of queuing networks, and used it to model regulation through pricing of vehicle sharing systems (VSS). Micro-economical and non-linearity issues related to the elasticity of demand can be avoided for some objectives, including the maximization of the number of trips sold. We proposed a heuristic combining Maximum Circulation and a greedy algorithm and studied its performance ratio for the transit maximization. It provides a static policy whose performance is proved to be at least N N +M -1 that of the best dynamic (and therefore static) policy. On the other hand, the complexity of computing an optimum dynamic or static policy remains open.

Several substantial extensions are required in order study real-life VSS using our approach. We believe that including transportation times has only a minor impact on the nature of our results. Indeed the BCMP theory still applies and the analytical formulas obtained here shall be extended to this context. However, adding transportation times raises the choice of an objective function.

We believe that taking into account station capacities preserves the performance of circulation policies since they spread very well vehicles among stations. However, slightly different proof techniques are likely to be required since the BCMP theory doesn't apply.

Unfortunately, the specification of the system is more complex when taking into account both transportation times and station capacities, since a customer might try and fail to drop his vehicle at a full station.

Moreover, demands that are not stationary over time (such has house-work commute) are hardly well managed using only steady-state goals: stations in residential areas shall be full in mornings and empty after work. However, Maximum Circulation heuristics can be generalized to optimize over non-stationary demands, as discussed in Waserhole and Jost (2013), although no guaranty of performance is provided. Moreover, the availability of stations is still not correctly estimated by (efficient) optimization models dealing with non-stationary demands. This seems to be the main issue in order to provide high quality solutions.

Finally, in dense networks of stations such as Vélib's Paris, some users have flexibilities in their origin and destination stations. The classical (BCMP) queuing network results fall apart under such generalization. Highly different theoretical tools might be required.

All these issues are about the optimization business. But many other tools need to be developed. For instance, numerical results using simulations require data on the demand. However, the demand is not easy to estimate since exploitation data usually report the trips sold, but not potential users who were not sold a trip.

We therefore believe that VSS optimization problems should be investigated in various ways. Methods to decompose the problems raised by VSS help making reliable progress by isolating the impact of some factors. Integrating the various aspects using simulations is even more important in our opinion, but this goal seems too difficult to target in the short term. Indeed such simulations require high quality specifications and data, which will be achieved by steps if the problems are decomposed properly. each possible trip. Solving the VSS MDP model computes the optimal dynamic discrete pricing policy.

MDPs are known to be polynomially solvable in the number of states |S| and actions |A| available in each state. To solve an MDP, efficient solution methods exist such as value iteration, policy iteration algorithm or linear programming; see [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] textbook. In each state s ∈ S, the VSS MDP model's action space A(s) is the Cartesian product of the available prices for each trip, i.e. A(s) = Q |M| 2 . The action space size is then exponential in the number of stations. However, to avoid suffering from this explosion, we can model this problem as an action decomposable Markov decision process; see (Waserhole et al., 2013a). Thanks to this general framework, based on the event-based dynamic programming [START_REF] Koole | Structural results for the control of queueing systems using event-based dynamic programming[END_REF], the complexity of solving the VSS MDP model becomes polynomial in |S| and |Q||M| 2 (that is far less than |Q| |M| 2 ). Nevertheless, the VSS MDP model has another problem: the explosion of its state space S with the number of vehicles and stations. This phenomenon is known as the curse of dimensionality [START_REF] Bellman | Bottleneck problems and dynamic programming[END_REF].

A.2 Structures of optimal dynamic policies

Recall that Dynamic policies have prices to take a trip that depend on the state of the system, i.e. the vehicle distribution. Unfortunately, even with homogeneous demand (Λ a,b = Λ) optimal dynamic policies seem hard to describe.

Since the number of states is exponential, we would like to restrict to dynamic policies allowing a compact description. Capacity policies amount to specifying a virtual station capacity K, and to accept a trip from station a to station b if only if the number of vehicles in b is not exceeding K b .

We show in the next proposition that capacity policies are suboptimal among dynamic policies for the VSS stochastic pricing optimization problem.

Proposition 4. Capacities policies are suboptimal among dynamic policies, even in homogeneous cities.

Proof. Figure 6 compares the induced Markov chain (state graph) of three policies in an homogeneous city (Λ = 1) with 3 stations and 8 vehicles. An edge represents that the trip is open to its maximum in both directions, an arc indicates that it is open only in one way. Figure 6a represents the generous policy opening all trips and expects to sells 4.8 trips per time unit. Figure 6b represents the optimal dynamic capacity policy and increases the gain to ≈ 4.857. Finally, the optimal dynamic policy is represented in Figure 6c, and increases the number of trips sold to ≈ 4.865.

Figure 6 shows that using dynamic pricing policies can increase the number of trips sold by the system even in homogeneous cities (perfectly balanced). Figure 7 represents the optimal dynamic policies in an homogeneous cities with 3 stations when the number of vehicles increases: from 8 vehicles (as in Figure 6b), to 14 and 30 vehicles. Only the "spikes" of the dynamic policies' induced Markov chain are represented since, the solution is invariant under the group S 3 of permutation of the stations. These solutions are the unique optimum. The optimal dynamic policy is solved with the VSS (decomposed) MDP model. This model is of exponential size in N and |M| but still solvable for the size of these 3 instances. The solution uniqueness has been checked greedily solving several decomposed MDPs. It seems hard to find a compact description of optimal solutions in general.

A.3 Suboptimal classes of static policies A.3.1 Generous policies / No regulation

When investigating (pricing) policies, the most important practical issue is the trade-off between the simplicity (and in particular, the readability for users) and the performance. The first practical question might always be whether "unoptimized" policies perform well.

The (static) generous policy sets all demands to their maximum value (λ = Λ). To the best of our understanding, the generous policy is the most natural and relevant to compare with in theoretical studies, as long as the objective function is in terms of service quality and not in terms of monetary gain.

In Proposition 5, provides an example in which the number of trips sold by the generous policy can be arbitrarily far from an optimal static policy. It contains a "gravitational" phenomenon, which occurs in particular for bike sharing systems in non-flat cities.

Proposition 5. The ratio between the number of trips sold by the (static) generous policy (λ = Λ) and the static optimal policy is unbounded.

Figure 7: "Spikes" of optimal dynamic policies' state graph for an homogeneous city with 3 stations and N=8, 14 or 30 vehicles.

Proof. Consider a complete demand graph where all trip maximum demands are equal to 1 except the trips from a special station z ∈ M to any other station that are worth L

-1 : Λ a,b = 1, Λ z,a = 1, ∀a ∈ M, ∀b ∈ M \ {z}.
For any number of vehicle, when L → ∞ the expected number of trips sold T (G) for the generous policy G tends to 0: The stationary distribution for one vehicle is π a = 1 L+M -1 , ∀a ∈ M \ {z} and π z = L L+M -1 , hence lim L→∞ π a = 0, ∀a ∈ M \ {z} and π z = 1. Since for all N, the availability vector A satisfies A = α N π for some scalar α N , we have:

∀N ≥ 1, lim L→∞ A a = 0, ∀a ∈ M \ {z} and lim L→∞ A z = 1, hence ∀N ≥ 1, T (G) = a∈M A a (M -1) + A z L -1 (M -1) ⇒ lim L→∞ T (G) = 0.
On the other hand, the static circulation policy C closing only trips to and from station a has a expected number of trips sold T (C) > 1 that is independent of L:

∀L > 0, ∀N ≥ 1, A b = N N + M -2
, ∀b ∈ M \ {a} and A a = 0, hence independently of L, and for all N ≥ 1 and M ≥ 3

T (C) = a∈M\{z} A a (M -2) = N(M -1)(M -2) N + M -2 ≥ 1.here

A.3.2 Bang bang policies

Static policies directly have a compact representation: only one price per trip needs to be set, independently of the system's state. However, a compact formulation does not directly lead to a polynomial optimization. When considering only two possible prices per trip, a brute force solution method still needs 2 |M| 2 calls to the stochastic evaluation model. We need to exhibit structures to design efficient algorithms.

With the continuous demand assumption, static policies optimization amounts to setting the user arrival rates λ with 0 ≤ λ a,b ≤ Λ a,b , ∀(a, b) ∈ D. We investigate bang-bang policies (all or nothing) that set each trip (a, b) ∈ D to be either open (λ a,b = Λ a,b ), or closed (λ a,b = 0). One can wonder if bang-bang policies are dominant for the transit maximization. It is true for dynamic policies: bang-bang dynamic policies optimization can be reduced to a discrete price dynamic policies optimization in which deterministic policies are dominant(classic MDP results [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]). Nevertheless, we show that bang-bang policies are not dominant among static policies even (which is more surprising) when the number of vehicles tends to infinity. Proposition 6. Bang-bang policies are suboptimal among static policies even when the number of vehicles tends to infinity.

Proof. Figure 8 exhibits a counter example with 4 stations (a, b, c, d) and maximum trip demands Λ a,b = Λ b,c = 3, Λ c,d = Λ d,a = Λ c,a = 2, all others are equal to 0. There are only 2 bang-bang static policies λ defining a strongly connected demand graph: λ i,j = Λ i,j , (i, j) = (c, a) and either λ c,a = 0 or λ c,a = 2. When the number of vehicles tends to infinity, the availability of a vehicle at station a equals πa max b∈M π b , where π is the stationary distribution for one vehicle [START_REF] George | Fleet-sizing and service availability for a vehicle rental system via closed queueing networks[END_REF]. For the λ c,a = 0 policy, we have π a = π b = 2 10 and π c = π d = 3 10 = π max , so the expected transit when N → ∞ is worth πa πmax (3 + 3) + πc πmax (2 + 2) = 8. For the λ c,a = 2, policy we have π a = π b = 4 14 and π c = π d = 3 14 , so the expected transit when N → ∞ is worth 10.5 which is thus the optimal bang-bang static policy. Yet, for the non bang-bang policy with λ c,a = 1 and still λ i,j = Λ i,j , (i, j) = (c, a), we have π a = π b = π c = π d = 1 4 , so the expected transit when N → ∞ is worth 11 > 10.5. Hence, bang-bang policies are suboptimal even when the number of vehicles tends to infinity.

A.3.3 Single component policies

One may wonder whether it is useful to have a policy dividing the city. Notice that when considering static pricing policies with more than one strongly connected component, one should explicitly consider the vehicle distribution among these components. In fact, dividing the city sometimes lead to better performances: It is a leverage to prevent the system from being in unprofitable (unbalanced) states.

Proposition 7. Static policies with one single strongly connected component are suboptimal among static policies.

Proof. An example is schemed Figure 9 with 4 stations and a symmetric demand matrix. For two vehicles, the optimal static policies in this case is to close the trips (b, c

Figure 1 :

 1 Figure 1: The real-time station-to-station protocol.

Figure 2 :

 2 Figure 2: Continuous elasticity function (demand curve) λ ∈ [0, Λ].

Figure 3 :

 3 Figure 3: Can pricing improve on the transit of the generous policy? Equivalently, is there a pricing policy λ such that a,b y λ a,b > a,b y Λ a,b ?

Figure 4 :

 4 Figure 4: A closed queuing network model: servers represent users demands.

0

  ≤ λ a,b ≤ Λ a,b , ∀(a, b) ∈ D. Theorem 1. The objective value of Maximum Circulation on the demand graph is an upper bound on any dynamic policy for any number of vehicles. Proof. From any dynamic policy, with transition rate λ s a,b ≤ Λ a,b in state s ∈ S for trip (a, b) ∈ D, we construct a circulation λ ′ on the demand graph with same value. Under the dynamic policy, the stationary distribution π over the state space S of the continuous-time Markov chain defined by λ satisfies Equations (1). Let λ ′ a,b be the expected transit for any trip (a, b) ∈ D: λ ′ a,b = s∈S π s λ s a,b

Figure 5 :

 5 Figure 5: Example where Maximum Circulation consists of two strongly connected components.

Lemma 5 .

 5 For the uniform stationary distribution π s = 1 |S(N,M )| , s ∈ S(N, M), the availability of any station is equal to N N +M -1 . Proof. From Proposition 1, the number of distributions of N vehicles among M stations is equal to |S(N, M)| = N +M -1 N . For any station a ∈ M, there are |S(N -1, M)| states with at least one vehicle available in station a. If each state has the same steady state probability, π s = 1 |S(N,M )| , s ∈ S(N, M), computing the availability A(π) of a vehicle at any station (Equation (

  dynamic capacity policy, value ≈ 4.857. (c) Optimal dynamic policy, value ≈ 4.865.

Figure 6 :

 6 Figure 6: Induced Markov chain of 3 policies evaluated in an homogeneous city with 8 vehicles and 3 stations. Legend: (•) reachable state; (•) unreachable state; (-) trip between two states open in both directions; (→) trip open in only one direction.

Figure 8 :

 8 Figure 8: Bang-bang policies are suboptimal even when the number of vehicles tends to infinity.

Figure 9 :

 9 Figure 9: Static policies with a single strongly connected component are suboptimal.

For a random distribution of vehicles -→ N R , and a static policy λ with k strongly connected components -→ M , let φ R = (λ, k, -→ M, -→ N R ) be the associated (random) static policy and let π R (φ R ) be the stationary distribution over the states of CMTC(φ R ).

Lemma 7. The stationary distribution π R (φ R ) over the CMTC(φ R ) defined by a static policy φ R with random vehicle distribution -→ N R is unique.

Proof. Recall that π(φ) is the stationary distribution over the states of the CMTC(φ) associated to static policy φ with deterministic vehicle distribution. We have:

From Lemma 2, for any deterministic vehicle distribution static policy φ, π(φ) is unique. Summing over all the possible realisations of -→ N R also defines a unique π R for any static policy with a random vehicle distribution.

Consider the uniform probability measure over the set of states S(N, M). Define the random uniform vehicle distribution -→ N U as the implied random repartition of vehicles to the k components:

For any vehicle distribution

Let φ U be the random static circulation policy defined by the random uniform distribution -→ N U over S(N, M).

Lemma 8. Let N, M > 0 and λ be a circulation with k strongly connected components ( k i=1 |M i | = M). For any circulation policy with the random uniform vehicle distribution φ U = (λ, k, -→ M, -→ N U ), the availability A a (φ U ) of a vehicle at any station a ∈ M is N N +M -1 . In other words, ∀i ∈ {1, . . . , k}, ∀a ∈ M i :

Proof. From Lemma 4, for any circulation, π s (φ U ) = 1 S , ∀s ∈ S(N, M), is an invariant probability measure of CMTC(φ U ).

Using Lemma 7, π s (φ U ) = 1 S , ∀s ∈ S(N, M) is then the unique stationary distribution for any circulation policy under the random uniform vehicle distribution -→ N U . Finally we apply Lemma 5 to conclude that A a (φ U ) = N N +M -1 .

Appendix A Toward computing optimal policies

In this appendix, we discuss structures of optimal policies in order to develop tractable stochastic models to optimize a VSS through pricing. We discuss in Section A.2 the problem of characterizing dynamic optimal policies and in Section A.3 the problem of characterizing static ones. Simple classes of policies, easier to optimize, are shown suboptimal.

A.1 Markov Decision Process -The curse of dimensionality

Computing optimal dynamic policies The continuous-time Markov chain formulation of the VSS stochastic evaluation model leads directly to a Markov Decision Process (MDP), named the VSS MDP model. This model considers, in each state s ∈ S, a set Q of discrete prices for