Hugo E Silva

Robin Lindsey
email: robin.lindsey@sauder.ubc.ca

André De Palma
email: andre.depalma@ens-cachan.fr

Vincent A C Van Den Berg

On the Existence and Uniqueness of Equilibrium in the Bottleneck Model with Atomic Users

Keywords: Bottleneck model, Large users, Atomic users, Existence of Equilibrium, Uniqueness of Equilibrium

This paper investigates the existence and uniqueness of equilibrium in the Vickrey bottleneck model when each user controls a positive fraction of total traffic. Users simultaneously choose departure schedules for their vehicle fleets. Each user internalizes the congestion cost that each of its vehicles imposes on other vehicles in its fleet. We establish three results. First, a pure strategy Nash equilibrium (PSNE) may not exist. Second, if a PSNE does exist, identical users may incur appreciably different equilibrium costs. Finally, a multiplicity of PSNE can exist in which no queuing occurs but departures begin earlier or later than in the system optimum. The order in which users depart can be suboptimal as well. Nevertheless, by internalizing self-imposed congestion costs individual users can realize much, and possibly all, of the potential cost savings from either centralized traffic control or time-varying congestion tolls.

Introduction

Individual users of roads and other transportation facilities are usually assumed to be small in the sense that they control a negligible fraction of total traffic. Yet large users are prevalent in many settings. Commercial airlines and rail companies often account for a sizable fraction of total traffic at airports and on rail networks. Postal services and major freight shippers operate large vehicle fleets that travel long distances each day. For example, FedEx handles about 150 daily flights out of Memphis International Airport and its air-cargo operations support tens of thousands of jobs. UPS operates on a similar scale out of Louisville, Kentucky (The Economist, 2013). Major employers such as government departments and large corporations can add substantially to traffic on certain roads at peak times. Large users such as these suffer from the congestion delays their own aircraft, trains, trucks, or other vehicles impose on each other. Thus, at airports, on rail networks, on congested roads, and on other transportation infrastructure networks, one would expect large users to internalize their self-imposed delays, and therefore to make different triprelated decisions than small users controlling the same aggregate traffic.

Following the terminology of game theory we will refer to small users as non-atomic, and large users that control a positive fraction of traffic as atomic. This terminology contrasts with the terminology used in the literature on airport congestion, beginning with [START_REF] Daniel | Congestion pricing and capacity of large hub airports: A bottleneck model with stochastic queues[END_REF], in which users that control a negligible fraction of traffic and treat the congestion levels as parametric are called atomistic users. Somewhat confusingly, atomistic users are therefore non-atomic, and non-atomistic users are atomic.

There are several branches of literature on congestion with atomic users. In the aviation literature, [START_REF] Daniel | Congestion pricing and capacity of large hub airports: A bottleneck model with stochastic queues[END_REF] was the first to recognize that airlines with market power and large shares of total traffic could internalize the delays their aircraft impose on each other. [START_REF] Brueckner | Airport congestion when carriers have market power[END_REF] showed that under Cournot competition airlines fully internalize selfimposed congestion. Further contributions in this line have been made by [START_REF] Pels | The economics of airport congestion pricing[END_REF], [START_REF] Brueckner | Internalization of airport congestion: A network analysis[END_REF], [START_REF] Zhang | Airport capacity and congestion when carriers have market power[END_REF], [START_REF] Basso | Congestible facility rivalry in vertical structures[END_REF], [START_REF] Brueckner | Atomistic congestion tolls at concentrated airports? seeking a unified view in the internalization debate[END_REF], and [START_REF] Silva | Optimal pricing of flights and passengers at congested airports and the efficiency of atomistic charges[END_REF]. In the context of road transportation, route-choice decisions by atomic users have been studied (e.g., [START_REF] Devarajan | A note of network equilibrium and noncooperative games[END_REF][START_REF] Marcotte | Algorithms for the network oligopoly problem[END_REF][START_REF] Harker | Multiple equilibrium behaviors on networks[END_REF][START_REF] Catoni | Technical note-traffic equilibrium paradoxes[END_REF][START_REF] Miller | Stackelberg games on a network with cournot-nash oligopolistic competitors[END_REF][START_REF] Cominetti | The impact of oligopolistic competition in networks[END_REF][START_REF] De Palma | Network market conduct with atomic and non-atomic players[END_REF]. There is also a literature in operations research and computer science on atomic congestion games (e.g., [START_REF] Fotakis | Atomic congestion games among coalitions[END_REF][START_REF] Hoefer | Altruism in atomic congestion games[END_REF].

The above-mentioned studies have used static models of congestion except for [START_REF] Daniel | Congestion pricing and capacity of large hub airports: A bottleneck model with stochastic queues[END_REF] who uses a stochastic queuing model empirically. Other studies that use a dynamic stochastic model of congestion with atomic users include [START_REF] Daniel | When) do hub airlines internalize their self-imposed congestion delays?[END_REF] and [START_REF] Molnar | Congesting the commons: A test for strategic congestion externalities in the airline industry[END_REF]. Except for a few studies described below, traffic congestion with atomic users has not been studied with deterministic dynamic models. This is surprising because the timing of trips matters a great deal for both passenger and freight transportation, and congestion is largely a consequence of peak-period loads.

The goal of this paper is to investigate the fundamental questions of existence and uniqueness of equilibrium in trip-timing decisions with atomic users. To focus the analysis on fundamentals while minimizing mathematical complications we use [START_REF] Vickrey | Congestion theory and transport investment[END_REF] bottleneck model. The essence of the bottleneck model is that users trade off the costs of queuing delay at the bottleneck with the costs of schedule delay (i.e., arriving earlier or later than desired). The bottleneck model has been used to study many aspects of trip-timing decisions with congestion including: congestion pricing, route choice on simple road networks, mode choice, trip chaining, parking congestion, staggered work hours, and flextime. Existence and uniqueness of equilibrium in the bottleneck model have also been established under relatively general assumptions about trip-timing preferences and heterogeneity of non-atomic users (e.g., [START_REF] Newell | The morning commute for nonidentical travelers[END_REF][START_REF] Lindsey | Existence, uniqueness, and trip cost function properties of user equilibrium in the bottleneck model with multiple user classes[END_REF]. However, very little consideration has been given to atomic users in studies that use either the bottleneck model or other dynamic models.

A few studies have employed a variant of the bottleneck model in which time is discretized, and the number of users is finite, so that each user controls a positive measure of traffic (e.g., [START_REF] Levinson | Micro-foundations of congestion and pricing: A game theory perspective[END_REF][START_REF] Zou | A multi-agent congestion and pricing model[END_REF][START_REF] Otsubo | Vickrey's model of traffic congestion discretized[END_REF][START_REF] Werth | Atomic routing in a deterministic queuing model[END_REF]. However, these studies assume that each user controls only one vehicle so that self-internalization of congestion does not come into play. To the best of our knowledge, only [START_REF] Daniel | The deterministic bottleneck model with non-atomistic traffic[END_REF] and [START_REF] Silva | Airlines' strategic interactions and airport pricing in a dynamic bottleneck model of congestion[END_REF] have explored the scheduling decisions of atomic agents in the standard, continuous-time bottleneck model. These studies consider, in the context of aviation, a sequential competition between a Stackelberg leader with market power and a group of perfectly competitive airlines (non-atomic users). Both studies show that, when users have homogeneous preferences, non-atomic users schedule all their flights during the peak period when passengers prefer to arrive. The Stackelberg leader schedules a fraction of its flights during the peak as well. Queuing time at the bottleneck evolves at the same rate as in the standard model of non-atomic players. The leader schedules its remaining flights earlier and later in the off-peak (and less popular) periods and limits its departure rate to bottleneck capacity so that no queue develops.

The existence of a unique equilibrium in [START_REF] Daniel | The deterministic bottleneck model with non-atomistic traffic[END_REF] and [START_REF] Silva | Airlines' strategic interactions and airport pricing in a dynamic bottleneck model of congestion[END_REF] hinges on the sequential nature of the game they consider, and the assumption that there is only one atomic agent. By contrast, we focus in this paper on settings with two atomic users who make scheduling decisions simultaneously. The solution concept we employ is pure strategy Nash equilibrium (PSNE). We establish three major results. First, we show that a PSNE may not exist. We demonstrate this for an example featuring two identical atomic users who each control half of the total traffic. The trip-timing preferences of each vehicle in each fleet are described by parameters {α,β,γ,t * }, where α is the cost of travel time, β is the cost of schedule delay early, γ is the cost of schedule delay late, and t * is the desired arrival time. We show that if γ > α, a PSNE does not exist.

Second, for the same example, we show that if γ ≤ α a multiplicity of PSNE exists in which no queuing occurs and the timing of departures is system optimal. The PSNE differ according to the departure rates of individual users and the equilibrium costs they incur. Depending on parameter values, one of the two users can incur up to three quarters of total costs. The cases γ > α and γ ≤ α are both of theoretical interest, and each may be relevant in particular settings. Most empirical studies of scheduling preferences for automobile drivers have obtained estimates that satisfy γ > α (e.g., [START_REF] Small | The scheduling of consumer activities: work trips[END_REF][START_REF] Wardman | A review of british evidence on time and service quality valuations[END_REF][START_REF] Asensio | Commuters valuation of travel time variability[END_REF]. In addition, de Palma and Fontan (2001) list estimates from eleven studies and, including their own estimates, there are ten cases with γ > α, and two cases with γ < α. By contrast, [START_REF] Daniel | When) do hub airlines internalize their self-imposed congestion delays?[END_REF] find that γ < α holds for most airlines at major US airports.

Third, we consider a variant of the example in which the two users differ in their desired arrival times t * and can have fleets of different size. We show that -independent of the relative size of α and γ -a multiplicity of PSNE can exist in which no queuing occurs but the timing of departures is not optimal. Depending on parameter values, the PSNE may begin earlier than, later than, or at the same time as the system optimum. The order in which users depart can be suboptimal as well. Nevertheless, by internalizing self-imposed congestion costs the two users realize much, and possibly all, of the potential cost savings from either centralized traffic control or time-varying congestion tolls.

These examples demonstrate that neither the existence of equilibrium nor the uniqueness of an equilibrium (if one exists) is guaranteed under conditions where a unique PSNE does exist if all the traffic were controlled by non-atomic users. Given the central role of equilibrium models in the analysis of transportation systems, these results are troubling and highlight the need for further research.

The paper is organized as follows. Section 2 reviews the no-toll equilibrium and the system optimum in the standard bottleneck model with non-atomic users. Section 3 demonstrates the possible non-existence of PSNE, and the non-uniqueness of individual departure rates and costs where a PSNE does exist. Section 4 demonstrates the possible nonuniqueness of PSNE in the timing of departures when no queuing occurs, and the degree of inefficiency relative to the system optimum. Section 5 concludes.

The bottleneck model with homogeneous non-atomic users

The bottleneck model was developed by [START_REF] Vickrey | Congestion theory and transport investment[END_REF] and extended by [START_REF] Arnott | Economics of a bottleneck[END_REF][START_REF] Arnott | A structural model of peak-period congestion: A traffic bottleneck with elastic demand[END_REF]. It is reviewed in [START_REF] Arnott | Recent developments in the bottleneck model[END_REF] and [START_REF] De Palma | Dynamic traffic modeling[END_REF], and the summary here is brief. In the model, all users travel from a common origin to a common destination along a single link that has a bottleneck with fixed flow capacity, s. Without loss of generality, travel times from the origin to the bottleneck and from the bottleneck to the destination are normalized to zero. If there is no queue upstream of the bottleneck, travel time through the bottleneck is also zero and departure time from the origin coincides with arrival time at the destination. If the departure rate exceeds s, a queue develops. Let t be the most recent time at which there was no queue, and r(t) the aggregate departure rate from the origin at time t. The number of vehicles in the queue is then:

Q(t) = t t (r(u) -s)du.
Travel time through the bottleneck is T (t) = Q(t)/s, and a traveler who departs at time t arrives at time t a = t + T (t).

Following [START_REF] Small | The scheduling of consumer activities: work trips[END_REF] and [START_REF] De Palma | Stochastic equilibrium model of peak period traffic congestion[END_REF], users are assumed to have a desired arrival time t * . They incur a unit cost of β > 0 for arriving early, and a unit cost of γ > 0 for arriving late. Travel time is valued at α, with α > β. The costs of schedule delay and travel time are additive so that the generalized cost of a trip, c(t), is:

c(t) = α • T (t) + β • (t * -t -T (t)) , t + T (t) ≤ t * γ • (t + T (t) -t * ) , t + T (t) ≥ t * . (1)
The number (or measure) of users, N , is assumed to be exogenous (i.e., independent of trip cost). Each user decides when to depart from the origin by trading off schedule delay against travel delay. A pure strategy Nash equilibrium (PSNE) is a set of departure times such that no user can benefit (i.e., reduce trip cost) by unilaterally changing departure time while taking the departure times of all other users as given.

No-toll equilibrium

Let superscript n denote the no-toll non-atomic PSNE, and t n s and t n e denote the start and end of the travel period. Let t be the departure time for which a user arrives on time (i.e., t + T ( t) = t * ). In a PSNE with no toll, c(t) must be constant during the travel period [t n s , t n e ]. Users who arrive closer to t * must incur longer queuing delays in order to offset their lower schedule delay costs. The equilibrium aggregate departure rate is derived by differentiating Eq. ( 1) and setting the derivative to zero:

r n (t) = α•s α-β , t ∈ t n s , t α•s α+γ , t ∈ t, t n e . (2)
The assumption α > β assures that the departure rate for early arrivals is positive and finite. This condition is plausible since a user who is destined to arrive early is likely to prefer arriving early to prolonging the trip by making a detour. The condition is also supported by [START_REF] Small | The scheduling of consumer activities: work trips[END_REF] estimates for automobile commuting trips. For ease of reference we will sometimes call the departure rate for early arrivals the early departure rate, and the departure rate for late arrivals the late departure rate.

There are two further equilibrium conditions. One is that the first and last users to depart, who encounter no queue, must incur equal schedule delay costs:

β • (t * -t n s ) = γ • (t n e -t * ) . (3)
The other condition is that the travel period lasts for N/s:

t n e -t n s = N s . (4)
Together, equilibrium conditions (2), ( 3) and (4) yield:

t n s = t * - γ β + γ • N s , (5a)
t n e = t * +

β β + γ • N s , (5b) t =t * - β α • γ β + γ • N s , (5c)
c n (t) = δ • N s , t ∈ [t n s , t n e ] with δ ≡ β • γ β + γ . ( 5d
)
Total costs are:

T C n = δ • N 2 s . (6)

System optimum

Queuing delay at the bottleneck is a deadweight loss. The system optimum therefore avoids queuing and minimizes total schedule delay costs. The departure rate is maintained at s over a continuous time interval chosen so that the first and last users incur the same schedule delay cost. The departure period is therefore the same as in the laissez-faire PSNE (cf. Eqs. (5a) and ( 5b)). Using superscript o to denote the system optimum, these results are recorded for future reference as:

r o (t) = s, t ∈ (t o s , t o e ) , r o (t) = 0 otherwise, (7a)
t o s =t * - γ β + γ • N s , (7b)
t o e =t * + β β + γ • N s . ( 7c
)
Total system costs are only half as large as in Eq. ( 6) for the no-toll equilibrium:

T C o = δ 2 • N 2 s = 1 2 • T C n . (8)
The difference between total costs in the no-toll equilibrium and system optimum, T C n -T C o , serves as an upper bound on the benefits from self-internalization of congestion by atomic agents.

Existence and non-existence of equilibrium with homogeneous atomic users

In this section we study an example featuring two identical atomic users. We show that if γ > α, a PSNE in departure schedules does not exist. We then show that if γ ≤ α, a PSNE does exist that entails no queuing and coincides with the system optimum. During early departures the two users can depart at somewhat different rates that add up to s. If γ < α, their late departure rates can also differ. Moreover, with γ ≤ α the users can incur appreciably different total costs for their fleets. At the end of the section we briefly discuss how these results extend to more than two users.

Consider two atomic users, A and B. Each user controls a fleet of N/2 vehicles. triptiming preferences for each vehicle defined by the same {α,β,γ,t * } parameter values. Thus, the total cost of a user's fleet is simply the sum of the cost of each of its vehicles. This assumption seems realistic for delivery vans carrying merchandise or parcels to different customers. It may be inappropriate for vehicles in a military convoy or emergency vehicles traveling to an accident. Users A and B simultaneously choose departure schedules for their fleets. The schedule for user i is a departure rate function, r i (t) ≥ 0. The function can be seen as a distribution function of the N/2 vehicles over some extended time interval such as a day. This function is not restricted to be continuous, and the possibility of mass departures will be considered. Each user recognizes that dispatching a vehicle at time t may delay vehicles in its fleet that depart after t. A delay occurs if there is a queue at time t that persists when the later vehicles depart. A delay also occurs if there is no queue prior to t, but the bottleneck is at capacity so that adding a vehicle to the departure schedule at t creates a (small) queue.

As noted above, the existence of a PSNE in this example depends on whether γ > α, or γ ≤ α. The two cases are considered in the following two subsections.

Non-existence of PSNE with γ > α

When γ > α, a PSNE does not exist. This result is formalized in the following proposition.

Proposition 1. Consider two identical atomic users who each simultaneously schedule N/2 vehicles with trip-timing preferences for each vehicle defined by the same {α,β,γ,t * } parameter values. If γ > α, a PSNE in departure schedules does not exist.

We prove Proposition 1 in four steps. First, we prove that a PSNE without queuing does not exist (Lemma 1). Second, we prove that mass departures cannot arise in equilibrium (Lemma 2). With these two results we can restrict attention to cases in which there is queuing, but no mass departures. Third, we show that there is a unique departure pattern with queuing such that a user cannot reduce its fleet costs by rescheduling a single vehicle (Lemma 3). Given this third result, to prove non-existence we only need to find one deviation from this departure pattern by either user that reduces its total fleet costs. Any other candidate equilibrium will not be robust against rescheduling a single vehicle. Finally, we show that this departure pattern is not a PSNE because a user can reduce its fleet costs by rescheduling a positive measure of vehicles in the fleet (Lemma 4). This establishes that a PSNE with queuing does not exist either.

Lemma 1. Consider two identical atomic users who each simultaneously schedule N/2 vehicles with trip-timing preferences for each vehicle defined by the same {α,β,γ,t * } parameter values. When γ > α, a PSNE without queuing does not exist.

Proof : Consider a pair of departure schedules, {r A (•) , r B (•)}, such that no queuing occurs. Some vehicles must arrive late since otherwise a user could reduce its fleet costs by rescheduling some vehicles to just after t * . Consider a period (t 1 , t 2 ) of late arrivals and assume that both users depart during this period (the case where only one user departs is considered later). The bottleneck must be used to capacity since otherwise a user could exploit the residual capacity by advancing departures for vehicles that are scheduled to depart later.

If user i removes a vehicle from the departure schedule at time t, it saves a cost of

C - i (t) = γ • (t -t * ) . (9)
Removing the vehicle saves the late-arrival cost incurred by the vehicle itself, but it has no effect on the rest of the fleet because there is no queue. If user i instead adds a vehicle to the departure schedule, it increases its fleet costs by a marginal private cost (MPC) of

C + i (t) = γ • (t -t * ) + α + γ s • t t r i (u) du, ( 10
)
where t is the time when the queue created by the additional vehicle disappears.

The first term on the right-hand side of Eq. ( 10) matches the right-hand side of Eq. ( 9). The second term is the delay cost imposed on user i's other vehicles that depart from t to t. Each of them suffers an increase in travel time of 1/s valued at α, and an increase in late arrival of 1/s valued at γ.

The difference between the cost saved by removing a vehicle given by Eq. ( 9), and the cost of adding a vehicle to the same slot given by Eq. ( 10), arises when the bottleneck is at capacity but there is no queue. This asymmetry underlies the nonuniqueness of equilibrium considered later in the paper.

Suppose user i advances the departure of a vehicle from t to t where t 1 ≤ t < t ≤ t 2 . User i's fleet costs change by:

∆C i = -C - i (t) + C + i t = -γ • (t -t * ) + γ • t -t * + α + γ s t t r i (u) du. (11)
The queue induced by adding the vehicle at t vanishes at t because a departure time slot opened up at t when the vehicle was removed then. Let

λ i t,t = t t r i (u) du/ (s • (t -t )) ∈
[0, 1] be an auxiliary variable denoting the average fraction of capacity occupied by user i during the period [t, t ]. The change in user i's fleet costs can then be written as:

∆C i = α + γ s • λ i t,t • s • t -t -γ • t -t = ((α + γ) • λ i t,t -γ) • t -t .
For a PSNE to exist, ∆C i must be nonnegative for both users which requires:

λ i t,t ≥ γ α + γ , t 1 ≤ t < t ≤ t 2 , i = A, B. (12)
Since the bottleneck is fully utilized, λ A t,t + λ B t,t = 1. This condition is least restrictive if λ A t,t = λ B t,t = 1/2 in which case it reduces to γ ≤ α which is inconsistent with the assumption γ > α. Now consider the possibility that only one user, say user A, departs during (t 1 , t 2 ). This is not a PSNE if user B departs after t 2 since user B could reduce its costs by rescheduling some of its later vehicles into (t 1 , t 2 ). Doing so reduces their late-arrival costs, and the queue they create disappears during the time slots they vacated. Suppose user B does not depart after t 2 . If t 1 = t * , user B does not depart late at all. But this cannot be a PSNE because user B could gain by rescheduling some of its early-arriving vehicles to just after t * , thereby reducing their schedule delay costs without imposing any delay on its other vehicles. If t 1 > t * , there must exist a late arrival period (t 0 , t 1 ) during which both users depart. But this case has already been considered, and shown to be inconsistent with a PSNE when γ > α. QED

To this point we have assumed that users depart at a finite rate. In theory, a user could schedule a positive measure of vehicles to depart at a given moment. In practice, this might be achieved by assembling a convoy of vehicles on a link that has right-of-way over other links. Moreover, in the bottleneck model with non-atomic users and step tolls a PSNE may exist only if mass departures (of non-cooperating vehicles) are possible [START_REF] Arnott | Economics of a bottleneck[END_REF][START_REF] Lindsey | Step tolling with bottleneck queuing congestion[END_REF]. We now show that in the model with atomic users mass departures cannot occur in a PSNE, regardless of whether γ > α or γ ≤ α.

Lemma 2. Consider two identical atomic users who each simultaneously schedule N/2 vehicles with trip-timing preferences for each vehicle defined by the same {α,β,γ,t * } parameter values. A PSNE cannot exhibit mass departures.

Proof : See Appendix A. We now turn to the final possibility for a PSNE with γ > α in which departure rates remain finite and queuing occurs.

Lemma 3. Consider two identical atomic users who each simultaneously schedule N/2 vehicles with trip-timing preferences for each vehicle defined by the same {α,β,γ,t * } parameter values. When γ > α, there is a unique departure pattern with queuing in which a user cannot reduce its fleet costs by rescheduling a single vehicle.

Proof : Consider a pair of departure schedules, {r A (•) , r B (•)}, and let t denote the departure time for which a user arrives on time (i.e. t = t * -T ( t)). Assume that a queue exists during a late-departure period (t l , t qe ), where t l is an arbitrary time that satisfies t l > t and t qe is the time when the queue disappears. Since users A and B are identical, it suffices to consider the best response of user A to r B (•). The MPC to user A of scheduling a vehicle at time t ∈ (t l , t qe ) is

C A (t) = α • T (t) + γ • (t + T (t) -t * ) + α + γ s • tqe t r A (u) du. (13)
Eq. ( 13) has a similar interpretation to Eq. ( 10). The first two terms on the right-hand side comprise the cost incurred by the vehicle itself, and the third term is the delay cost imposed on user A's other vehicles that depart from t to t qe .

User A could reschedule a vehicle from t to another time t ∈ (t l , t qe ). This would leave t qe unchanged because the additional queuing time caused by inserting the vehicle at t is offset by the reduction in queuing time due to removing the vehicle at t. Eq. ( 13) therefore holds if t is replaced by any t ∈ (t l , t qe ). Hence, a necessary condition for r A (•) to be a best response to r B (•) is that C A (t) in Eq. ( 13) is constant during the interval (t l , t qe ). Differentiating Eq. ( 13) with respect to t, and setting the derivative to zero, yields

∂C A (t) ∂t = γ + (α + γ) • ∂T (t) ∂t - α + γ s • r A (t) = 0.
Using the relationship ∂T (t)/∂t = (r

A (t) + r B (t) -s) /s, this condition simplifies to r B (t) = α • s α + γ , t ∈ (t l , t qe ) . (14)
According to Eq. ( 14), user A is willing to schedule a vehicle for late arrival when there is a queue if, and only if, user B is departing at exactly the rate α • s/ (α + γ). This is none other than the equilibrium aggregate departure rate for the model with non-atomic users (cf. Eq. ( 2)). Eq. ( 14) also holds for user B with r A (t) in place of r B (t). The aggregate departure rate during an interval of late arrivals must therefore be r

(t) = r A (t) + r B (t) = 2 • α • s/ (α + γ). With γ > α, r (
t) < s and the queue must be shrinking for late arrivals. Consequently, a queue must exist at time t and it is possible to set t l = t, where t+T ( t) = t * . This in turn implies

r A (t) = r B (t) = α • s α + γ , t ∈ t, t qe .
Since a queue exists at time t, it must have built up during a period of early arrivals before t. Let t q be the time at which queuing begins. The MPC to user A of scheduling a vehicle at any time t ∈ t q , t is

C A (t) = α • T (t) + β • (t * -t -T (t)) + α -β s • t t r A (u) du + α + γ s • tqe t r A (u) du. (15)
Again, the first two terms on the right-hand side of Eq. ( 15) comprise the cost borne by the vehicle itself. The third term is the cost imposed on user A's other vehicles that depart after t but still arrive early. Each of them suffers an increase in travel time of 1/s valued at α, and benefits from a reduction in early arrival of 1/s valued at β. The last term in Eq. ( 15) is the cost imposed on user A's other vehicles that arrive late. A necessary condition for r A (•) to be a best response to r B (•) is for C A (t) to be constant during t q , t . Setting the derivative of C A (t) to zero, one obtains a counterpart to Eq. ( 14):

r B (t) = α • s α -β , t ∈ t q , t . (16)
An analogous necessary condition applies for user B. Hence, the aggregate early departure rate must be r

(t) = r A (t) + r B (t) = 2 • α • s/ (α -β).
In summary, the unique departure rate of the candidate PSNE during the full period of queuing is

r A (t) = r B (t) = r (t) 2 = α•s α-β , t ∈ t q , t α•s α+γ , t ∈ t, t qe , ( 17
) where t + T ( t) = t * . ( 18
)
Because queuing begins at t q , and ends at t qe , cumulative departures during the period (t q , t qe ) match cumulative arrivals:

tqe tq (r (u) -s) du = 0. ( 19
)
Eqs. ( 17), ( 18), and ( 19) define evolution of the queue for the candidate PSNE with queuing.

By Lemma 1, no vehicles can depart without queuing after t qe , so departures end at time t e = t qe . However, the cost of a vehicle trip at the beginning of the queuing period, c (t q ), is less than the cost at the end of the period, c (t e ), because the trip at t q imposes a private delay cost on subsequent vehicles whereas the trip at t e does not (if c(t q ) = c(t e ), C + (t q ) > C + (t e ) would hold and the user equilibrium condition would be violated). Departures must therefore occur during some time interval [t s , t q ) preceding t q . This interval is defined by two conditions. First, vehicle trip cost must be the same at t s and t e since otherwise a user could reschedule vehicles from the time with higher cost to the time with lower cost and reduce its overall fleet costs without causing any queuing. Second, the full departure period [t s , t e ] must be long enough for all N vehicles to pass the bottleneck. Eqs. ( 3) and (4) for the non-atomic PSNE therefore hold for the candidate PSNE:

β • (t * -t s ) = γ • (t e -t * ) , (20)
t e -t s = N s . (21)
The two users each control N/2 vehicles and schedule the same number of vehicles during the queuing period. Therefore, they must also schedule the same number during [t s , t q ]:

tq ts r A (u) du = tq ts r B (u) du, (22)
where

r A (u) + r B (u) = s, u ∈ (t s , t q ) . ( 23
)
The early departure schedule defined by Eqs. ( 22) and ( 23) is consistent with a PSNE as far as trip timing by individual vehicles. The first vehicle scheduled at t s creates the same MPC as all vehicles scheduled during [t q , t e ]. Vehicles scheduled during (t s , t q ) create a lower MPC, so that rescheduling them to any time outside (t s , t q ) would increase total fleet costs. Rescheduling any vehicle into (t s , t q ) would also increase fleet costs because it would impose a queuing delay on all vehicles departing later until t e , and would therefore create a higher MPC than a vehicle departing at t q . QED Together, Eqs. ( 17)-( 23) define the candidate PSNE with queuing. Using superscript c to denote this candidate, the critical times are:

t c s =t * - γ β + γ • N s , (24a)
t c e =t * + β β + γ • N s , ( 24b
) tc = t * - β • (γ -α) 2 • α • (β + γ) • N s , (24c)
t c q = t * - β • (γ -α) (α + β) • (β + γ) • N s . ( 24d
)
We now show that the candidate PSNE just derived is not a PSNE because either user can reduce its fleet costs by rescheduling a positive fraction of its vehicles. This result is formalized as: Lemma 4. Consider two identical atomic users who each simultaneously schedule N/2 vehicles with trip-timing preferences for each vehicle defined by the same {α,β,γ,t * } parameter values. When γ > α, the unique candidate departure pattern with queuing in which users cannot reduce costs by rescheduling a single vehicle is not a PSNE with respect to rescheduling a positive fraction of the fleet.

Proof : The candidate PSNE is depicted in Figure 1. Cumulative departures during the whole travel period are shown by the piecewise linear schedule OABC. During the first interval t c s , t c q , the two users depart early at rates consistent with Eq. ( 22). During the remaining interval t c q , t c e , user B contributes to cumulative departures the portion between schedule ADGE and the horizontal line AF . User A contributes the equally big portion between schedule ABC and schedule ADGE. During the interval t c q , tc , each user departs early at rate α • s/ (α -β), and during tc , t c e each user departs late at rate α • s/ (α + γ). At time t, each user's cumulative departures over the interval t c q , t match cumulative bottleneck throughput over the same interval.

Suppose user A reschedules all its vehicles from period t c q , t to period t, t c e , and maintains a departure rate of γ • s/ (α + γ) during t, t c e . As a consequence, the queue caused by B between t c q and t fully dissipates at t. Since user B departs at rate α•s/ (α + γ) during t, t c e , the total departure rate during this period equals s and the bottleneck is fully utilized without queuing. Moreover, since user B keeps the bottleneck fully utilized during t c q , t , all vehicles in both fleets complete their trips by t c e . Consequently, with the deviant schedule, all of user A's vehicles can complete their trips within the same time period as in the candidate PSNE, but without queuing. It is straightforward to show (see Appendix B) that user A's fleet incurs lower total costs with the deviant schedule than with the candidate PSNE schedule. Hence the candidate PSNE is not a PSNE. QED

The reader may wonder why the candidate PSNE is robust to deviations in which a user reschedules a single vehicle, but not robust to rescheduling part of the fleet. The reason is that the first type of deviation comprises a zero measure of traffic whereas the second type comprises a positive measure. Postponing departures of a positive mass of vehicles in the fleet reduces queuing delay, and allows subsequent vehicles to arrive early even after the other user has reduced its departure rate to the late departure rate in anticipation that its vehicles will arrive late.

t c s t c q tc t t * t c e t A C O B D E G F slope = α α + γ • s slope = s slope = 2 • α α + γ • s slope = 2 • α α -β • s slope = α α -β • s User B'
Proposition 1 establishes that a PSNE does not exist when γ > α. As noted in the introduction, most empirical studies of scheduling preferences for automobile drivers have obtained estimates that satisfy this inequality. However, there is little evidence either on the trip-timing preferences of users that may control large shares of road traffic (e.g., freight shippers), or on preferences for travel by other modes of transportation. [START_REF] Daniel | When) do hub airlines internalize their self-imposed congestion delays?[END_REF], without making explicit the role of the passengers' valuation of time, estimate that γ < α holds for many US airlines. Thus, it is of interest to study the existence and nature of PSNE when γ ≤ α.

Existence and Nature of PSNE with γ ≤ α

In this section we establish two results for the case γ ≤ α. First, we show that there exists a unique PSNE in the aggregate departure schedule that coincides with the system optimum (Proposition 2). Second, we show that the two users' individual departure rates are not uniquely defined in the PSNE (Proposition 3), and the users can incur different fleet costs (Section 3.2.3).

Existence of PSNE with

r i (t) ≥ r E , t ∈ (t o s , t * ) , i = A, B, where r E ≡ 2•α•(β+γ)+γ•(β+2•γ)- √ β 2 •γ 2 +4•α•(β+γ) 2 •(α+γ) γ•(α+γ) • s 2 ∈ 0, γ α+γ • s .
Proof : The proof entails establishing four results: 1) A PSNE with queuing does not exist. 2) All PSNE without queuing must coincide with the system-optimal departure pattern given by Eqs. (7a), (7b), and (7c). 3) Given the lower bound on individual departure rates for late arrivals, neither user can gain by rescheduling a single vehicle. 4) Given the lower bounds on individual departure rates for early and late arrivals, neither user can gain by rescheduling part of its fleet.

Result 1. A PSNE with queuing does not exist. By Lemma 2, mass departures cannot be part of a PSNE. Any candidate PSNE with queuing must satisfy conditions ( 17), ( 18), and ( 19). With γ ≤ α, these conditions cannot all be satisfied since the aggregate early departure rate exceeds capacity, and the aggregate late departure rate is no less than capacity. Hence any queue cannot dissipate while users are departing, which is inconsistent with a PSNE.

Result 2. The system-optimal departure pattern is the only possible PSNE in the aggregate departure schedule.

Given Result 1, in equilibrium, the aggregate departure rate cannot exceed the bottleneck capacity when γ ≤ α. Therefore, equilibrium departures must occur at rate s over a connected time interval since otherwise either user could reduce its fleet costs by rescheduling vehicles into "gaps" in the departure schedule when bottleneck capacity is not fully utilized. The departure period, [t s , t e ], must be as given by Eqs. (7b) and (7c) since otherwise trip costs at t s and t e would differ, and at least one user could reduce its fleet costs by rescheduling vehicles from the higher-cost endpoint to the lower-cost endpoint.

Result 3. A user cannot gain by rescheduling a single vehicle if each user's departure rate satisfies the conditions in Proposition 2.

In the candidate PSNE with a system-optimal aggregate departure pattern, there is no queuing but the bottleneck is used to capacity. As in the proof of Lemma 1, it is therefore necessary to distinguish between the cost saved by removing a vehicle from the departure schedule (which does not affect other vehicles' costs) and the cost of adding a vehicle (which creates a queue unless the vehicle is added at t o e ). The respective costs are:

C - i (t) = β • (t * -t) , t ∈ [t o s , t * ] γ • (t -t * ) , t ∈ [t * , t o e ] , C + i (t) =        β • (t * -t) + α-β s • t * t r i (u) du + α+γ s • t o e t * r i (u) du, t ∈ [t o s , t * ] γ • (t -t * ) + α+γ s • t o e t r i (u) du, t ∈ [t * , t o e ]
.

A vehicle can be rescheduled in four ways: (i) late to late, (ii) late to early, (iii) early to late, and (iv) early to early. Consider each possibility in turn.

i. Rescheduling late to late: Rescheduling a late vehicle to a later time is never beneficial because the vehicle's trip cost increases, and other vehicles do not gain. Suppose a vehicle is rescheduled earlier from t to t where t * ≤ t < t. The change in fleet costs is given by Eq. ( 11):

∆C i = -C - i (t) + C + i t = -γ • t -t + α + γ s • t t r i (u) du s = λ i t ,t - γ α + γ where s = means identical in sign. Given r i (t) ≥ γ • s/ (α + γ) for t ∈ (t * , t o e ), λ i t ,t ≥ γ/ (α + γ), ∆C i ≥ 0,
and the deviation is not beneficial.

ii. Rescheduling late to early: Rescheduling a late vehicle to an early time is clearly inferior to rescheduling it to t * because the vehicle incurs an early-arrival cost and creates a queue for a longer period. But rescheduling it to t * is not beneficial as per case i.

iii. Rescheduling early to late: The best option in this case is to reschedule a vehicle from t o s . However, the gain is the same as for rescheduling a vehicle from t o e , and this is not beneficial as per case i. Rescheduling early to late therefore cannot be beneficial.

iv. Rescheduling early to early: The best option in this case is to reschedule a vehicle from t o s to t * , but this, too, is not beneficial for the same reason as in case iii. This establishes that the candidate PSNE in Proposition 2 is robust to deviations in which a single vehicle is rescheduled.

Result 4. A user cannot gain by rescheduling a positive measure of its fleet.

If user A reschedules vehicles to depart outside [t o s , t o e ], its fleet costs necessarily increase since the rescheduled vehicles experience greater schedule delay costs without benefiting the rest of the fleet. If user A instead reschedules vehicles to depart inside [t o s , t o e ], queuing occurs. The optimal departure rate in the presence of a queue was derived in Section 3.1 and, although with γ ≤ α a PSNE cannot exhibit queuing, we need to check if a deviation from the candidate to a setting with queuing is cost reducing. For early arrivals, user A is willing to depart at a positive and finite rate only if condition ( 16) is satisfied; i.e. r B (t) = α•s/ (α -β) > s. Since user B departs at a rate less than s in the candidate PSNE, user A is better off scheduling the vehicles later. For late arrivals, user A is willing to depart at a positive and finite rate only if condition ( 14) is satisfied so that r

B (t) = α • s/ (α + γ) . Proposition 2 stipulates that r B (t) ≤ α • s/ (α + γ). If r B (t) = α • s/ (α + γ)
, and therefore r A (t) = γ • s/ (α + γ), user A is indifferent between departing or not so that the deviation does not reduce its fleet costs. If r B (t) < α • s/ (α + γ), user A is better off scheduling the vehicles later. The only remaining possibility for gainful deviation is one that involves mass departures. In Appendix C we prove that a deviation with mass departures is not gainful if the lower bounds on early and late departure rates stated in Proposition 2 are both satisfied. QED The intuition for Proposition 2 is as follows. The only way for user A to gainfully deviate from the candidate PSNE by rescheduling a single vehicle is to advance its departure during the late arrival period. Doing so reduces the vehicle's late-arrival cost, but imposes queuing delay on user A's vehicles that depart later. The tradeoff is not worthwhile if enough vehicles in A's fleet have yet to depart, and queuing is sufficiently costly relative to late arrival. The lower bound on the late departure rate stated in Proposition 2 assures this condition is met. If user A deviates by rescheduling vehicles in mass departures and imposes queuing delays on its other vehicles, the same argument holds. The tradeoff is not worthwhile because the lower bound on the late departure rate ensures that there are enough vehicles in the fleet yet to depart that will be negatively affected.

To avoid delaying other vehicles in its fleet, user A must advance departures for vehicles that participate in a mass. Since vehicles in the mass suffer queuing delay, user A can benefit from such a deviation only if the vehicles' schedule delay costs are reduced enough. This requires that the vehicles were departing late over a period longer than the time they take to pass the bottleneck when in the mass. This, in turn, is possible only if user B occupies a large enough share of bottleneck capacity during the candidate PSNE. The lower bound on the late departure rate identified in Proposition 2 ensures that this condition is not met.

To see why a lower bound on the early departure rate is also required, suppose that user A does not depart during some time interval (t, t * ). User A can then reschedule its vehicles departing in some interval (t * , t ) by launching them in a mass at a time t m ∈ (t, t * ). None of its fleet departing after t will be delayed by the mass. If t m is chosen to minimize the total schedule delay costs of vehicles in the mass, their total costs will fall. However, if user A is scheduling enough departures during (t m , t * ), the deviation will not be gainful since the mass departure either imposes queuing delays on its other vehicles, or it has to include vehicles that were arriving early, which will suffer higher early arrival costs and queuing costs. If the early departure rate is high enough, such a mass departure is unfavorable. Proposition 2 identifies a minimum early departure rate to guarantee this when the late departure rate is held fixed at its minimum value: γ • s/(α + γ).

Non-uniqueness of PNSE with γ ≤ α

Although the aggregate departure schedule in the PSNE described in Proposition 2 is unique when γ ≤ α, many pairs of departure schedules {r A (•) , r B (•)} are consistent with the aggregate pattern. Thus, the PSNE is not unique in terms of individual departure rates. This result is formalized in the following proposition: Proposition 3. Consider two identical atomic users who each simultaneously schedule N/2 vehicles with trip-timing preferences for each vehicle defined by the same {α,β,γ,t

(•) , r B (•)} that satisfies r E ≤ r A (t) ≤ s -r E and r B (t) = s -r A (t) satisfies the aggregate PSNE condition. QED
The non-uniqueness of individual departure rates in a PSNE implies that, unlike in the model for identical non-atomic users, users can experience different fleet costs in a PSNE. This prospect is examined further in the next subsection.

Asymmetric equilibrium costs with γ ≤ α

Clearly, if users A and B depart at the same rate throughout the departure period they incur the same fleet costs. In addition, there are many asymmetric PSNE departure schedules that result in the same average schedule delay costs for the two users and hence the same fleet costs. However, there are also many asymmetric departure schedules that result in different fleet costs.

Figure 2 depicts an illustrative example of a PSNE in which user A incurs lower fleet costs than user B. In the example, user A's departures are concentrated near t * so that user A has lower average schedule delay costs than B. User A's departure rate is shown by solid lines and user B's by broken lines. During the interval (t o s , t BA ), user A departs at the minimum rate r E defined in Proposition 2. During the next interval (t BA , t * ), user B departs at rate r E and user A at the complementary rate s -r E . During the first part (t * , t AB ) of the late-arrival period, user A departs at the maximum rate consistent with a PSNE for user B, α • s/ (α + γ). During the remaining part (t AB , t o e ) of the departure period, user A departs at the minimum rate consistent with a PSNE for itself, γ • s/ (α + γ). The transition times t BA and t AB are such that each user dispatches a total of N/2 vehicles. Expressed in terms of user A's fleet, the requisite condition is

r E •(t BA -t o s )+(s -r E )•(t * -t BA )+ α α + γ •s•(t AB -t * )+ γ α + γ •s•(t o e -t AB ) = N 2 . ( 25
)
Total costs in the PSNE, T C o , are a given; i.e. independent of users A's and B's individual departure rates. The maximum difference between the users' costs, T C B -T C A , can therefore be found by minimizing T C A with respect to t BA and t AB . As described in Appendix D, user A's costs as a fraction of total costs work out to

f ≡ T C A T C o = 3 + z 4 - 1 2 α α + γ + z 2 , where z ≡ β • γ/ ((α + γ) • (β + γ))
. The fraction f depends on α, β, and γ only through the ratios β/α < 1 and γ/α ≤ 1. It is readily shown that f is a monotonically increasing function of β/α and γ/α. At the upper limits with β/α ∼ = 1 and γ/α = 1, f ∼ = 0.4535. As β/α and γ/α approach their lower limits of 0, f approaches 1/4. This example illustrates that although there exists a unique PSNE in terms of the aggregate departure rate, individual user departure rates can differ substantially and so can their costs. If the unit schedule delay cost parameters, β and γ, are small compared to the cost of travel time, α, one user's fleet costs can be as little as one third the other user's costs. This is because one user can concentrate its departures around t * without the other user wanting to reschedule its fleet because the gain from reducing schedule delay costs would be outweighed by the high costs of queuing delay. This suggests that equity of access to a bottleneck can be an issue with atomic users.

t 0 s t BA t * t AB t o e t s rA(t) = rE rB(t) = rE rB(t) = s -rE rA(t) = s -rE rA(t) = α α + γ • s rB(t) = α α + γ • s rB(t) = γ α + γ • s rA(t) = γ α + γ • s Departure rates

Extension to multiple users

The analysis in this section can be generalized to m > 2 homogeneous users. Propositions 1 and 2 can be extended in a straightforward manner by following similar lines of reasoning. For example, condition (12) for existence of a PSNE without queuing, λ i t,t ≥ γ/ (α + γ), still holds. In the least restrictive case in which all m users depart at equal rates, this condition implies that 1/m ≥ γ/ (α + γ), or (m -1) • γ ≤ α. The intuition is similar to the case with m = 2. In a symmetric candidate PSNE, each user departs at rate s/m and contributes a fraction 1/m of the traffic. If user i reschedules one vehicle ∆T units of time earlier, it reduces the vehicle's late arrival cost by γ • ∆T . The vehicle imposes a delay of 1/s on the (s/m) • ∆T of user i's other vehicles that depart during the time interval. The unit cost of the delay is α + γ. User i benefits from rescheduling the vehicle unless γ

• ∆T ≤ (α + γ) • ∆T /m, which is equivalent to (m -1) • γ ≤ α.
The nonexistence of a PSNE with queuing can also be established using the same approach for m > 2 as for m = 2. Candidate equilibrium departure rates for other users during early and late departures are still given by Eqs. ( 16) and ( 14) respectively. The candidate equilibrium is well-defined and unique, and it breaks down because any user can reduce its costs by rescheduling a portion of its fleet. Clearly, the condition (m -1) • γ ≤ α becomes more stringent as m increases so that a PSNE without queuing becomes progressively less plausible. Indeed, given any fixed values of γ > 0 and α > 0, condition (m -1) • γ ≤ α necessarily fails if m is large enough. Thus, as m → ∞ the bottleneck model with atomic users does not converge in behavior to the non-atomic model which has a unique PSNE. The reason for this divergence is that even for large values of m, users in the atomic model take into account how they affect queuing times. The gains from deviation decrease in magnitude as m rises, but they remain positive. By contrast, in the standard bottleneck model users treat queuing times as given.

In this section we have shown that a PSNE may not exist when symmetric atomic users schedule vehicles simultaneously. In particular, if there are two identical users and γ > α, a PSNE does not exist. By contrast, if γ ≤ α, multiple PSNE exist and in all of them no queuing occurs. We now turn to the case where users are not identical and study the existence and uniqueness of PSNE.

Nonuniqueness of equilibrium with heterogeneous atomic users

In this section we consider a modified version of the model in which users A and B differ in their preferred arrival times and can have fleets of different size. [START_REF] Arnott | Bottleneck congestion with elastic demand[END_REF] studied this setting for the case of non-atomic users, and we draw on some of their results. We show that, regardless of the relative size of parameters α and γ, a multiplicity of PSNE without queuing can exist with two atomic users if preferred arrival times differ within a certain range. The PSNE differ both in the timing of aggregate departures and total costs. Departures can begin earlier than, later than, or at the same time as in the system optimum. Thus, a PSNE can be inefficient even if there is no queuing.

Suppose user i, i = A, B, has a fleet of N i vehicles, each with a preferred arrival time of t * i . Assume without loss of generality that t * B > t * A . To begin, assume t * B >> t * A so that the users can schedule their fleets at individually optimal time windows that do not overlap. Let t is and t ie denote the first and last departure times for user i, and let superscript d denote the PSNE with disjoint arrival times. Each user departs at a rate s during the interval that minimizes the total schedule delay costs of its fleet:

t d As , t d Ae = t * A - γ β + γ • N A s , t * A + β β + γ • N A s , (26a)
t d Bs , t d Be = t * B - γ β + γ • N B s , t * B + β β + γ • N B s . ( 26b
)
To rule out this uninteresting case we hereafter assume t d Bs < t d Ae , which is equivalent to assuming that:

t * B -t * A < β β + γ • N A s + γ β + γ • N B s . ( 27
)
Define the auxiliary variable

x ≡ β β + γ • N A s + γ β + γ • N B s -(t * B -t * A ) > 0. ( 28
)
Variable x measures how much the users' preferred departure schedules overlap, and thus the degree of "conflict"between them.

In addition to condition ( 27) we assume

t * B -t * A > γ β + γ • N B s - β β + γ • N A s . ( 29
)
Condition ( 29) assures that in the system optimum, derived next, some of user A's fleet arrives late and some of user B's fleet arrives early.

System optimum

In the system optimum, vehicles depart at an aggregate rate of s over a connected time interval. In general, the optimal individual departure rates, r * A (t) and r * B (t), are not unique. However, given condition ( 29), there is a unique optimum in which all of user A's fleet is dispatched before any of user B's fleet. Some of user A's fleet arrives late, and some of user B's fleet arrives early. Let t As be the time at which user A starts to depart. User A departs over the interval (t As , t As + N A /s), and user B departs over the interval (t As + N A /s, t As + (N A + N B )/s). Total costs are:

T C = β • s 2 • (t * A -t As ) 2 + γ • s 2 • t As + N A s -t * A 2 + β • s 2 • t * B -t As + N A s 2 + γ • s 2 • t As + N A + N B s -t * B 2 . ( 30
)
The first-order condition for minimizing T C with respect to t As yields:

t o As = t * A + t * B 2 - γ 2 • (β + γ) • N A + N B s - 1 2 • N A s , (31)
where superscript o again refers to the system optimum. Given condition (29

), t * A < t o Ae < t * B .
Substituting Eq. ( 31) into Eq. ( 30), total costs in the system optimum can be written as:

T C o = δ 2 • N 2 A + N 2 B s + β + γ 4 • s • x 2 , ( 32
)
where x is defined in Eq. ( 28). The first term in Eq. ( 32) equals total costs if condition (27) did not hold and the two users traveled in disjoint intervals. The second term in Eq. ( 32) is the additional costs incurred due to overlap in the users' preferred arrival times. This term is an increasing, quadratic function of the degree of conflict, x.

No-toll equilibrium with heterogeneous non-atomic users

Before considering the PSNE with users A and B, we briefly discuss the analogous no-toll PSNE with heterogeneous non-atomic users. In this case there is a measure N A of non-atomic users with a preferred arrival time t * A , and a measure N B of non-atomic users with a preferred arrival time t * B . [START_REF] Arnott | Bottleneck congestion with elastic demand[END_REF] show that when conditions ( 27) and ( 29) both hold, the equilibrium queuing pattern has two peaks. The first peak corresponds to on-time arrival for users with preferred arrival time t * A , and the second peak to on-time arrival for users with preferred arrival time t * B . Total costs are

T C n = δ • N 2 A + N 2 B s + βN A + γN B 2 • x. ( 33
)
The first term in (33) gives total costs if the equilibrium departure schedules of the two user groups do not conflict. This term is twice the first term in (32), just as total costs with homogeneous users in Eq. ( 6) are twice total costs in the system optimum in Eq. ( 8). The second term in ( 33) is a linear function of x. This contrasts with the second term in (32) which is a quadratic function of x. Thus, a small degree of conflict between the two user groups raises total costs disproportionately more in the no-toll equilibrium than in the system optimum. In the next subsection we use the difference between total costs in the no-toll equilibrium and system optimum as a metric to assess the efficiency achieved from self-internalization of congestion by atomic users.

PSNE

A PSNE without queuing exists if t Ae < t * B since the two users then do not arrive late at the same time and do not compete to complete their trips as soon as possible. Indeed, a continuum of PSNE exists. To see this, assume that both users depart in the period [t * A , t Ae ] and capacity is fully used. Suppose user A advances a vehicle's departure from t 2 to t 1 , where t * A ≤ t 1 < t 2 ≤ t Ae . User A's fleet costs change by:

∆C A = -C - A (t 2 ) + C + A (t 1 ) = -γ • (t 2 -t * A ) + γ • (t 1 -t * A ) + α + γ s • t 2 t 1 r A (u)du = (α + γ) • λ A t 1 ,t 2 -γ • (t 2 -t 1 ).
User A does not benefit from the rescheduling if

λ A t 1 ,t 2 ≥ γ α + γ .
This condition is satisfied for any choice of t 1 and t 2 as long as:

r A (t) ∈ γ α + γ • s, s , t ∈ [t * A , t Ae ]. ( 34
) User B's departure rate is then r B (t) = s-r A (t) ∈ [0, α • s/ (α + γ)].
There is no restriction on r B (t) because user B arrives early throughout [t * A , t Ae ]. Thus, any departure profile satisfying Eq. ( 34) is consistent with a PSNE. However, different departure profiles generally result in different total costs. An exhaustive treatment of all PSNE in this example would be tedious. Attention is limited to two illustrative cases. In Case 1, user A schedules its entire fleet during the same interval it would choose if user B did not exist. Hence, r A (t) = s during the interval (t d As , t d Ae ) given by Eq. (26a). User B departs at rate s during the ensuing interval (t d Ae , t Be ). In Case 2, user A departs at rate s during the interval (t As , t * A ). During the next interval (t * A , t Ae ), user A departs at the minimum rate consistent with Eq. ( 34), r A (t) = γ•s/ (α + γ). User B departs at the complementary rate r B (t) = α • s/ (α + γ). During the final interval (t Ae , t Be ), user B departs at rate s. Cases 1 and 2 are now examined in turn.

PSNE for Case 1

Figure 3 depicts a PSNE conforming with Case 1, using the following parameter values:

N A = 1, N B = 1, s = 1, α = 2, β = 1, γ = 2, t * A = 0, and t * B = 2/3. t 1 As t * A t 1 Ae = t 1 Bs t * B t 1 Be t N A N A + N B SDC E SDC L SDC E SDC L User A User B Figure 3 PSNE for Case 1 with t * B > t * A , NA = 1, NB = 1, s = 1, α = 2, β = 1, γ = 2, t * A = 0, and t * B = 2/3.
Since all of user A's fleet departs before any of user B's fleet,

t 1 Ae -t 1 As = N A s , (35)
where superscript 1 denotes Case 1. User A can schedule a vehicle either just before t 1 As or just after t 1

Ae without imposing a congestion delay on other vehicles in its fleet. The first and last vehicles must therefore incur equal schedule delay costs:

β • t * A -t 1 As = γ • t 1 Ae -t * A . (36)
Together, Eqs. ( 35) and (36) imply:

t 1 As =t * A - γ β + γ • N A s , (37a)
t 1 Ae =t * A + β β + γ • N A s . (37b)
As noted above, the departure interval t 1 As , t 1 Ae coincides with the interval t d As , t d Ae given by Eq. (26a). User B departs in a connected time interval immediately after user A. Hence,

t 1 Bs = t 1 Ae = t * A + β β + γ • N A s , (38a)
t 1 Be = t * A + β β + γ • N A s + N B s . (38b)
A notable feature of the departure schedule given by Eqs. (37a)-( 38b) is that it does not depend on t * B . To be consistent with the assumption that some of user B's fleet arrives early we require t 1 Ae < t * B , or:

t * B -t * A > β β + γ • N A s . ( 39
)
Case 1 is a PSNE if neither user has an incentive to deviate from it. User A clearly has no incentive to deviate because its fleet costs are the minimum possible. Two conditions must be satisfied for user B. First, user B cannot gain by rescheduling its last vehicle from t 1 Be to some time t between t 1

As and t 1 Ae . This condition is satisfied since rescheduling would impose queuing delay on all vehicles that depart after t without reducing schedule delay costs for user B's fleet.

Second, user B cannot gain by rescheduling its last vehicle from t 1 Be to just before the beginning of the travel period at t 1

As . The condition is

β • t * B -t 1 As > γ • t 1 Be -t * B , which reduces to: t * B -t * A ≥ γ β + γ • N B s . (40)
Conditions ( 39) and ( 40) together guarantee that condition (29) is satisfied.

The timing of departures in Case 1 and the system optimum can be compared using Eqs. (37a) and (31):

t 1 As -t o As = 1 2 • β β + γ • N A s + γ β + γ • N B s -(t * B -t * A ) = x 2 .
Since x > 0, t 1 As > t o As : departures in Case 1 begin later than in the system optimum. To see why, note that while early and late arrivals are balanced optimally for user A, user B's arrivals begin inefficiently late because user A occupies the bottleneck until t 1

Ae and effectively squeezes user B out. As shown in Appendix E, total costs in Case 1 can be written as:

T C 1 = δ 2 • N 2 A + N 2 B s + β + γ 2 • s • x 2 = T C o + β + γ 4 • s • x 2 . ( 41
)
Total costs are an increasing quadratic function of the degree of conflict, x. This is similar to the system optimum (cf. Eq. ( 32)), but unlike the non-atomic equilibrium where the dependence is linear (cf. Eq. ( 33)). The last expression in Eq. ( 41) , (β + γ) sx 2 /4, measures inefficiency of the PSNE in Case 1. This inefficiency can be expressed as a price of anarchy, P A, using the ratio

P A = T C 1 -T C o T C o . ( 42
)
P A is bounded below by 0. As shown in Appendix E, it is bounded above by 1/5. Thus, despite the fact that there is no queuing in the PSNE for Case 1, total costs can exceed the system-optimal level by up to 20 percent. Efficiency of the PSNE can also be measured relative to the non-atomic equilibrium using the index

w ≡ T C n -T C 1 T C n -T C o . ( 43
)
The numerator of ( 43) is the reduction in total costs achieved by self-internalization of congestion by the atomic users. The denominator is the reduction in total costs realized at the system optimum. Index w reaches its maximum value of 1 when x = 0. Appendix E establishes that it is bounded below by 6/7. Self-internalization of congestion by the atomic users independently therefore achieves most of the potential benefits from coordinating departure times centrally.

PSNE for Case 2

Figure 4 depicts an example of a PSNE in Case 2 using the same parameter values as for Figure 3. During the initial interval, t 2

As , t * A , user A departs at rate s. User B begins to depart immediately after t * A , and during the interval (t * A , t 2 Ae ) the two users depart simultaneously with an aggregate rate of s. User A departs at rate r A (t) = γ • s/ (α + γ), and user B departs at rate r B (t) = α • s/ (α + γ). During the final interval, (t 2 Ae , t 2 Be ), user B departs at rate s.

The PSNE for Case 2 is solved in Appendix E. The three transition times work out to:

t 2 As =t * A - α + γ α + β + γ • N A s , (44a)
t 2 Ae = t * A + β • (α + γ) γ • (α + β + γ) • N A s , (44b)
t 2 Be = t * A + β α + β + γ • N A s + N B s . (44c)
Similar to Case 1, the timing of the PSNE given by Eqs. (44a)-(44c) does not depend on t * B . As shown in Appendix E, departures in the PSNE of Case 2 can begin either earlier or later than in the system optimum. As t * B decreases, the system optimum begins earlier (cf. Eq. ( 31)), whereas the PSNE does not (cf. Eq. ( 44a)). Hence, as user B's preferred

t 2 As t 2 Bs = t * A t 2 Ae t * B t 2 Be t N A + N B SDC E SDC L SDC E SDC L User A User B Users A & B Figure 4 PSNE for Case 2 with t * B > t * A , NA = 1, NB = 1, s = 1, α = 2, β = 1, γ = 2, t * A = 0, and t * B = 2/3.
schedule moves closer to user A's and the conflict between them grows, the PSNE in Case 2 shifts from beginning too early to beginning too late. Unlike for Case 1, there is no simple formula for total costs in Case 2. Also unlike Case 1, total costs do not reach the system-optimal minimum value at the point where t 2

As coincides with t o

As . Thus, the price of anarchy is always positive. This is because both users depart during the interval (t * A , t 2 Ae ), with user A arriving late and user B arriving early. To see that simultaneous departure is inefficient, consider a vehicle of user B arriving at t 1 and a vehicle of user A arriving at t 2 > t 1 . If the two vehicles exchanged slots, user A's vehicle would arrive less late and user B's vehicle would arrive less early. The two users might agree to such an exchange if they cooperated, but the switch cannot occur in a Nash equilibrium.

We conclude this section with a numerical example featuring the same parameter values as those used to construct Figures 3 and4:

N A = 1, N B = 1, s = 1, α = 2, β = 1, γ = 2, t * A = 0,
and t * B = 2/3. Departures and arrivals last for two hours. The system optimum begins at t o As = -5/6, and total costs are T C o = 3/4. The PSNE for Case 1 begins at t 1 As = -2/3, and total costs are T C 1 = 5/6 which is 11.1% higher than T C o . User A's total costs are 1/3, and user B's total costs are 1/2. User B's total costs are 50% higher than user A's total costs even though the two users have the same size of fleet and the same unit costs α, β, and γ. The PSNE for Case 2 begins at t 2 As = -4/5, and total costs are T C 2 = 0.81 which is 8.4% higher than T C o but 2.4% lower than T C 1 . User A's total costs are 2/5, and user B's total costs are 0.413. User B's total costs are just 3.3% higher than user A's total costs so that the PSNE in Case 2 is both more efficient and more equitable than in Case 1. Finally, note that if user B's desired arrival time is increased from t * B = 2/3 to t * B = 4/5, t o As increases to -23/30 while t 2

As remains at -4/5. The PSNE in Case 2 then begins later than the system optimum.

Conclusion

In this paper we have explored the existence and uniqueness of pure strategy Nash equilibrium (PSNE) in the bottleneck model with atomic users. We consider a simple case featuring two users with piecewise linear and independent trip-timing preferences for each vehicle in their fleets. We show that if users are identical, and γ > α, a PSNE does not exist. By contrast, if γ ≤ α, multiple PSNE do exist in which no queuing occurs. The aggregate departure profile is unique. However, there exists a continuum of departure-time schedules for the two users that differ in the share of total costs borne by each user. We also consider a setting in which the two users differ in their preferred arrival times, t * A and t * B . For a range of values of t * B -t * A , there exists a continuum of PSNE that differ in the timing of trips, total costs, and the relative burden of costs borne by each user. There is no queuing. Departures may start earlier or later than optimal.

Table 1 Summary of results. The inefficiency is measured as the price of anarchy (see Eq. ( 42)). The results for heterogeneous users are valid only for the range of t * B -t * A described by Eqs. ( 27), ( 39) and ( 40).

The potential nonexistence of PSNE with atomic users is, we believe, the most significant of the results. In the standard bottleneck model a PSNE exists under relative general assumptions. It fails to exist only if trip-timing preferences have discontinuities such as discrete penalties for late arrival or discontinuities in the cost of travel time as a function of duration [START_REF] Lindsey | Existence, uniqueness, and trip cost function properties of user equilibrium in the bottleneck model with multiple user classes[END_REF]). In the model with non-atomic users nonexistence is a problem even with smooth preferences because atomic users face conflicting incentives. On the one hand they prefer to spread out departures of their fleets in order to avoid self-imposed queuing delays. If there is only one user, this results in a system-optimal departure schedule with no queuing. But when other users are present, an atomic user has an incentive to force vehicles into the departure stream near the peak in order to reduce its fleet's schedule delay costs. A user's best response can be to preempt other users by scheduling a mass departure near t * and hogging bottleneck capacity. Yet mass departures are inconsistent with PSNE, as we have shown.

The out-of-equilibrium behaviour in the bottleneck model bears some resemblance to firm behaviour in one-dimensional (Hotelling) spatial competition models (see [START_REF] Anderson | Discrete Choice Theory of Product Differentiation[END_REF], chapter 8). In location-choice games with parametric prices, firms leapfrog each other to gain market share. The outcome depends on the number of firms. With two or four firms a unique PSNE exists. But with five firms there are multiple PSNE, and with three firms a PSNE does not exist. In simultaneous location-and price-choice games with two firms, a PSNE does not exist. Firms face conflicting location-choice incentives that are broadly similar to the incentives of atomic users picking departure times in the bottleneck model. Moving closer to the centre (analogous to departing close to t * ) gains firms market share, but moving away softens price competition.

Preliminary analysis suggests that the difference between the standard bottleneck model and the model with atomic users remains as the number of atomic users increases because each user still recognizes how its scheduling choices affect queuing delays. Thus, simple congestion-prone systems with atomic users can exhibit fundamentally different dynamic behavior than with non-atomic users. Dynamic systems with non-atomic users have been well studied in the literature using the bottleneck model as well as various flow-congestion models. Yet, to our knowledge, this paper is the first to examine the existence and uniqueness of equilibrium in dynamic systems with atomic users that make scheduling decisions simultaneously.

Our analysis is exploratory and can be extended in various directions. One obvious priority is to determine how the bottleneck model can be modified to restore existence of equilibrium without restricting parameter values. One possibility is to consider both atomic and non-atomic users scheduling vehicles simultaneously. Although this setting may be more realistic in some markets, our preliminary analysis indicates that the presence of non-atomic agents does not restore existence of PSNE. Indeed, the conditions for existence of a PSNE are more stringent in the setting considered here even if atomic users control only a small share of traffic.

Another option to restore equilibrium is to consider mixed-strategy Nash equilibrium. However, since the strategy space in our setting allows discontinuous functions that may take a positive value only at a finite number of points, there is no guarantee that a Nash equilibrium in mixed strategies exists. It does not appear that the strategy space satisfies the necessary conditions for theorems of existence for infinite strategy spaces (e.g. a compact Hausdorff space as described in [START_REF] Reny | On the existence of pure and mixed strategy nash equilibria in discontinuous games[END_REF]). A discrete version of the bottleneck model with finite time steps and discrete vehicles is guaranteed to have a Nash equilibrium in mixed strategies because the strategy space is finite. Such an extension is beyond the scope of this paper. Moreover, studies that have used the discrete bottleneck model have found that a Nash equilibrium in pure strategies may not exist even if each player controls only one vehicle. Deriving pure or mixed strategy equilibria is also computationally-demanding for more than a few players. Adopting the discrete version of the bottleneck model therefore does not appear to be a promising approach.

A third option is to consider equilibrium under centralized pricing. In our setting, charging the first-best tolls for the model with non-atomic users restores equilibrium, but it is an open question whether a PSNE exists under more realistic step-tolling. Further possibilities for restoring equilibrium include: sequential decision-making (e.g. Stackelberg), consideration of repeated games, heterogeneity in unit values of time and schedule delay, and a more general specification of scheduling preferences.

Another direction for future research is to investigate more fully the benefits of coordination or other forms of cooperation. Self-internalization of congestion externalities by an atomic agent is one form of coordination, and its potential for welfare gains is apparent from Section 4. Cooperation between atomic agents can also be beneficial as shown by the examples in which the price of anarchy is positive. Major freight shippers might cooperate by harmonizing their delivery schedules although doing so without triggering concerns about illegal collusion might be tricky. Governments can also implement or encourage cooperative behavior. One example are staggered work hours and flextime programs that entail coordination on target arrival times (i.e., t * ). Staggered work hours were introduced in the 1970s in Washington, D.C., and Ottawa, Canada. Gutiérrez-i-Puigarnau and Van Ommeren (2012) report that one in three German firms uses staggered working hours. [START_REF] Mun | Flextime, traffic congestion and urban productivity[END_REF] note that in Japan, in 1998, 8% of employees worked at a firm with flexible working hours, and in the US, in 1994-1997, less than 6% of employees had a formal flexible working arrangement, but 28% of all full-time workers varied their working times to some degree. Thus, suppose that user A is considering a mass departure of M vehicles at time t, and assume that user B does not depart during the period t, t , where t > t. Variables M , t, and t are held fixed throughout the proof. The logic of the proof depends on whether or not a queue exists at t. Appendix A.1. A queue exists at t Assume Q (t) > 0. Pick any time t ∈ t, t such that Q (t ) > 0. We will show that user A is better off postponing the mass departure from t to t . Let m ∈ [0, M ] index vehicles in the order they are positioned in the mass, and let c(m, t) denote the cost incurred by vehicle m when the mass departs at t:

c(m, t) = α • T (t) + m s + β • t * -t -T (t) -m s if t + T (t) + m s ≤ t * γ • t + T (t) + m s -t * if t + T (t) + m s ≥ t * .
If the mass is rescheduled to depart at t instead, vehicle m incurs a cost:

c(m, t ) = α • T (t ) + m s + β • t * -t -T (t ) -m s if t + T (t ) + m s ≤ t * γ • t + T (t ) + m s -t * if t + T (t ) + m s ≥ t * .
Now, vehicle m arrives at the same time whether the mass is scheduled at t or t since a queue remains at t and user B does not depart between t and t . Hence t +T (t ) = t+T (t), and c(m, t ) can be written:

c(m, t ) = α • T (t) + m s -α • (t -t) + β • t * -t -T (t) -m s if t + T (t) + m s ≤ t * γ • t + T (t) + m s -t * if t + T (t) + m s ≥ t * = c(m, t) -α • (t -t) < c(m, t).
Postponing the mass departure therefore reduces costs for all M vehicles in the mass.

Since only user B departs during (t L , t L ),

T (t L ) = T (t L ) + t L t L r B (u) -s s du = T (t L ) -(t L -t L ) • 1 -λ B t L ,t L . (C.2) Substituting (C.2) in (C.1), we get: c(m, t L ) = c(m, t L ) -α • (t L -t L ) • 1 -λ B t L ,t L + γ • (t L -t L ) • λ B t L ,t L .
Postponing the mass departure changes costs by:

c(m, t L ) -c(m, t L ) = (t L -t L ) • λ B t L ,t L • (α + γ) -α ≤ 0 ,
where the inequality follows from the condition r B (t) ≤ α • s/(α + γ) in Proposition 2. We conclude that if there is a queue when the last mass departs, the mass departure can be postponed to the time where the queue just disappears without increasing costs (later vehicles are not affected by postponing the mass). Now assume there is no queue at t L when the last mass is launched. We show that vehicles in the mass can be rescheduled later to a time when they do not face a queue, and that doing so does not increase user A's fleet costs. Consider the cost of the last (i.e., M-th) vehicle in the mass:

c(M, t L ) = γ • (t L -t * ) + (α + γ) • M s .
Because user A does not depart until the queue has disappeared (result i), the queue produced by the mass departure disappears at time t L where:

M s + t L t L r B (u) -s s du = M s -(t L -t L ) • 1 -λ B t L ,t L = 0 . (C.3)
A vehicle that departs at t L incurs a cost:

c(t L ) = γ • (t L -t * ) = γ • (t L -t L ) + γ • (t L -t * ) = γ • (t L -t * ) + γ • M s • 1 -λ B t L ,t L ,
where the last equality uses Eq. (C.3). As removing a vehicle from the mass opens up a (queue-free) slot at t L , rescheduling the last vehicle to t L yields a change in cost of:

c(t L ) -c(M, t L ) = M s •   γ 1 -λ B t L ,t L -(α + γ)   ≤ 0 ,
where the inequality follows from condition r B (t) ≤ α • s/(α + γ) in Proposition 2.

This shows that, in any deviation from the candidate PSNE, the last mass departure launched at a time of late arrivals can be eliminated without increasing fleet costs. By induction, any mass departure launched at a time of late arrivals can be rescheduled without increasing fleet costs.

Next, we show that any deviation entailing multiple mass departures at times of early arrivals is dominated by scheduling a single mass departure before t * .

Result iii: Suppose that more than one mass departure is scheduled before t * . Assume the first mass is launched at time t E with M vehicles, and the second mass is launched at time t E > t E . If the queue from the first mass disappears before t E , fleet costs can be reduced by rescheduling vehicles in the first mass to depart at a rate equal to residual capacity (s -r B (t)). Since user A does not depart in the original deviation until the queue has dissipated, the rescheduled vehicles in the alternative deviation escape queuing and arrive less early -thereby reducing both their queuing and schedule delay costs. If the queue from the first mass does not disappear before t E , user A can still reduce its fleet costs by rescheduling s

• (t E -t E ) • (1 -λ B t E ,t E
) vehicles at a rate s -r B (t) during (t E , t E ), and letting the remaining M -s

• (t E -t E ) • (1 -λ B t E ,t E
) vehicles join the head of the second mass at t E . The first set of vehicles rescheduled at residual capacity avoid queuing and incur lower early arrival costs because they arrive closer to t * . The second set of vehicles also incur lower schedule delay costs since they arrive later. They also incur lower queuing costs as well since they no longer queue between t E and t E . Vehicles in the original mass that departs at t E still depart and arrive at the same time because the same number of vehicles depart before them and the bottleneck operates at capacity throughout.

By induction, all but one of the mass departures launched before t * can be eliminated in a way that decreases fleet costs. Thus, results (i)-(iii) show that a deviation with a single mass departure launched before t * is the most viable deviation, of deviations entailing mass departures, from the candidate PSNE. In the following section we show that the cost-minimizing deviation does not reduce fleet costs with respect to the candidate PSNE.

Appendix C.2. The optimal mass departure Following the logic of Appendix C.1, suppose user A launches a single mass departure of M vehicles at t m < t * . User A will not include in the mass vehicles that were scheduled to depart before t m because this would create a queue that lasts until after t e , and the cost of the delay imposed on A's later vehicles would outweigh any benefit. User A will include in the mass all vehicles scheduled to depart after t m that would be delayed by the mass. However, as discussed above, this would be counterproductive if all these vehicles were scheduled to depart before t * because they would suffer not only queuing delay but also greater early-arrival costs (the queue would disappear before t * ).

The mass departure is potentially beneficial only if it includes vehicles scheduled to depart both early and late. Therefore, the mass must be launched at a time t m < t * , and the queue must persist until a time t M > t * , where t M is defined by the condition: where r A (•) is user A's departure schedule in the candidate PSNE. Since the queuing costs incurred by the mass do not depend on when it is launched, t m should be chosen to minimize total schedule delay costs for vehicles in the mass. The first and last vehicles should therefore incur the same schedule delay cost:

β • (t * -t m ) = γ • t m + M s -t * .
This implies

t m = t * - γ β + γ • M s .
Vehicles in the mass incur total queuing time costs of α • M 2 / (2 • s), and total schedule delay costs of δ • M 2 / (2 • s). Total costs for the mass are therefore:

T C m = α + δ 2 • M 2 s . (C.5)
In the candidate PSNE, where r A (t) + r B (t) = s for t ∈ (t m , t M ), the M vehicles incur total costs of

T C e = β • t * tm r A (u) • (t * -u) du + γ • t M t * r A (u) • (u -t * ) du.
To complete the proof we must show that T C e ≤ T C m . User A's departure rate over the period (t m , t M ) must be consistent with condition (C.4). As shown in proving Result 3 of Proposition 2, during late arrivals r A (u) is bounded below by γ • s/(α + γ). Let r E denote the minimum departure rate of user A prior to t * . It follows by straightforward algebra that

T C e ≤ M 2 • β • γ 2 • r E • s + (α + γ) • (β + γ) 2 • s 2 + r 2 E • γ 2 -2 • (β + γ) • γ • s • r E 2 • (β + γ) 2 • s 3 . (C.6)
Setting the right-hand side of inequality (C.6) equal to Eq. (C.5) one obtains

r E = s 2 • 2 • α • (β + γ) + γ • (β + 2 • γ) -β 2 • γ 2 + 4 • α • (β + γ) 2 • (α + γ) γ • (α + γ) .
If user A's departure rate during early arrivals is at least r E , departing in a mass cannot reduce its fleet costs. The candidate PSNE is therefore robust to mass departure deviations. Straightforward algebra leads to:

0 < r E < γ α + γ
• s, which shows that in the limit γ → 0, r E → 0. QED

As 2 + γ • s 2 • t 1 As + N A s -t * A 2 = β • γ 2 (β + γ) • N 2 A s .
User B's fleet costs are:

T C 1 B = β • s 2 • t * B -t 1 Ae 2 + γ • s 2 • t 1 Be -t * B 2 = β • s 2 • t * B -t * A - β β + γ • N A s 2 + γ • s 2 • t * A + β β + γ • N A s + N B s -t * B 2 = β • s 2 • γ β + γ • N B s -x 2 + γ • s 2 x + β β + γ • N B s 2 = β • γ 2 • (β + γ) N 2 B s + β + γ 2 • s • x 2 ,
where x ≡ t * A -t * B + (β/(β + γ)) • (N A /s) + (γ/(β + γ)) • (N B /s). Total system costs are: ) since otherwise the PSNE does not exist unless γ ≤ α.This follows from the proof of Proposition 1. In particular, Lemma 1 holds and the only possible PSNE entails queuing. Using a similar reasoning as in Lemmas 3 and 4 it is possible to show that a PSNE will not exist.Given Eq. (44b) this implies

T C 1 = T C 1 A + T C 1 B = β • γ 2 • (β + γ) • s • N 2 A + N 2 B + β + γ 2 • s • x 2 . t * B -t * A ≥ γ β + γ • N B s - α • β (β + γ) • (α + β + γ) • N A s . (E.
t * B -t * A ≥ β • (α + γ) γ • (α + β + γ) • N A s . (E.8)
Using Eqs. ( 31) and (44a), the difference in timing of the system optimum and the PSNE in Case 2 can be written as Applying these values to Eq. (E.9) yields the feasible range for t 2 As -t o As :

t 2 As -t o As = -β • α (β + γ) • (α + β + γ) • N A s + x 2
t 2 As -t o As ∈   -β•(α-β) 2•(β+γ)•(α+β+γ) • N A s , M in β 2•(α+β+γ) • N A s , γ 2•(β+γ) • N B s - α•β•(β+2γ) 2•γ•(β+γ)•(α+β+γ) • N A s   .
The lower bound applies with t * B -t * A at its maximum value consistent with condition (E.7). The upper bound applies with t * B -t * A at its minimum value consistent with conditions (E.6) and (E.8).

Figure 1

 1 Figure 1 Candidate PSNE with γ > α and queuing.

Figure 2 A

 2 Figure 2 A PSNE with asymmetric costs: γ ≤ α, no queuing.

  implies a minimum value of x = (β•(α + β) /((β + γ)•(α + β + γ)))•(N A /s). Condition (E.6) implies a maximum value of x = (β • (2α + β + γ) /((β + γ) • (α + β + γ))) • (N A /s). Finally, Condition (E.8) implies a maximum value of x = (γ/(β + γ)) • (N B /s) -(α • β 2 /(γ • (β + γ) • (α + β + γ))) • (N A /s).

  γ ≤ α Proposition 2. Consider two identical atomic users who each simultaneously schedule N/2 vehicles with trip-timing preferences for each vehicle defined by the same {α,β,γ,t * } parameter values. If γ ≤ α, multiple PSNE exist. All of them have an aggregate departure schedule that coincides with the system optimum (i.e. r A (t) + r B (t) = s, t ∈ (t o s , t o e )). During the late-arrival period, each user's equilibrium departure rate is bounded in the range r i (t) ∈ γ α+γ • s, α α+γ • s , t ∈ (t * , t o e ), i = A, B. During the early-arrival period, each user's equilibrium departure rate is bounded below:

  A (t) = r B (t) = s/2 if α = γ, but they can depart at different rates if γ < α. During the early departure period t ∈ (t o s , t * ), a continuum of departure schedules {r A (•) , r B (•)} are consistent with the PSNE.Proof : By Proposition 2, for t ∈ (t * , t o e ), γ/(α + γ) ≤ r A (t)/s ≤ α/(α + γ) and r B (t) = s -r A (t). If γ = α, γ/(α + γ) = 1/2 and therefore r A (t) = r B (t) = s/2. If γ < α,there is a continuum of pairs of {r A (t), r B (t)} that satisfy the equilibrium condition while assuring that all vehicles depart during the interval [t o s , t o e ]. For t ∈ (t o s , t * ), the constraint r i (t) ≥ r E is less strict because r E < s/2. Any pair of departure schedules {r A

* } parameter values. During the late departure period t ∈ (t * , t o e ), the two users depart at the same rate r

  Table 1 summarizes the main results of the paper.

	Main case	Subcase Existence Inefficiency	Comments
	Homogeneous users	γ > α γ ≤ α	No PSNE Multiple PSNE	-0%	-One user can incur up to 75% of the total costs.
	Heterogeneous users in t * and fleet size	t * B > t * A	Multiple PSNE	≤ 20%

  6) Second, user B cannot gain by rescheduling a vehicle at t * A to t 2 Be . Thus, β • (t * B -t * A ) ≤ γ • t 2 Be -t * B which reduces to: Condition (E.7) is more stringent than condition (27). Third, user A must stop departing before user B starts to arrive late (i.e., t 2 Ae < t * B

	t * B -t * A ≤	β • γ (β + γ) • (α + β + γ)	•	N A s	+	γ β + γ	•	N B s	.	(E.7)

Acknowledgments

We are grateful to the Associate Editor and two anonymous referees for very helpful suggestions. Many thanks are also due to Erik Verhoef for his constructive and incisive comments which have significantly improved the paper. We would also like to thank participants at the Kuhmo Nectar Conference on Transportation Economics 2013 at Northwestern University. Any errors are ours. Financial support from ERC Advanced Grant OPTION (#246969) and the Social Sciences and Humanities Research Council of Canada is gratefully acknowledged.

Appendix A. Proof of Lemma 2

Suppose that user A schedules a mass departure at time t. Clearly, user B will not depart either at t or immediately after t since it would be better to depart either just before the mass or some time after t when the queue caused by the mass departure has diminished or disappeared. To prove that a mass cannot be part of a PSNE we will show that user A will never schedule a mass departure at t unless user B is scheduling vehicles either at t or immediately after t, which, as just argued, user B is not willing to do.

Appendix A.2. No queue exists at t Assume Q (t) = 0 and set t = t. If M ≤ s • (t -t), vehicles provisionally scheduled in the mass can instead be rescheduled to depart at rate s for a period of duration M/s. The M vehicles arrive at the same time as with the mass departure, but without incurring a queuing delay. If M > s•(t -t), then s•(t -t) of the vehicles can be rescheduled to depart at rate s for a period t -t, and the remaining M -s • (t -t) vehicles can be rescheduled to depart in a mass at t . All M vehicles will arrive at the same time as they do in the mass departure at t. The first s • (t -t) vehicles do not queue at all, and the last M -s • (t -t) vehicles do not queue during [t, t ]. Total queuing costs are therefore reduced, and total schedule delay costs are unchanged. Postponing the mass departure again reduces fleet costs, so that the mass departure is not optimal. QED

Appendix B. Proof of Lemma 4

It suffices to show that user A's vehicles that depart after t q incur lower total costs in the revised schedule than in the candidate PSNE schedule.

Appendix B.1. Costs in the candidate equilibrium

Total queuing time in the candidate PSNE is measured by area ABC in Figure 1. User A incurs half of this delay. User A's queuing time costs are therefore α • t * -t •s•(t e -t q ) /4. The number of user A's vehicles that queue and arrive early is s • (t * -t q ) /2, and their average schedule delay cost is β • (t * -t q ) /2. The number of vehicles that queue and arrive late is s • (t e -t * ) /2, and their average schedule delay cost is γ • (t e -t * ) /2. User A's queuing vehicles therefore incur total costs of

where superscript e denotes the candidate PSNE. Substituting Eqs. (24b), (24c), and (24d) into Eq. (B.1) gives

This solves to yield

where the inequality follows from γ > α > β.

The number of user A's vehicles that depart after t and arrive early in the revised schedule is γ • s • t * -t /(α + γ). These vehicles incur an average schedule delay cost of β • t * -t /2. The number of user A's vehicles that depart after t and arrive late is γ • s • (t e -t * ) /(α + γ) and their average schedule delay cost is γ • (t e -t * ) /2. Total costs are therefore

where superscript d denotes the deviant schedule. Substituting Eqs. (B.3) and (24b) into Eq. (B.4) gives

(B.5) Given Eqs. (B.2) and (B.5), the costs saved by deviating from the candidate PSNE work out to

Since the cost saving is positive, the candidate PSNE is not a PSNE. QED Appendix C. Proposition 2: Proof of Result 4 for mass departures Suppose that user A deviates from the candidate PSNE by scheduling multiple mass departures. We prove that such a deviation cannot reduce user A's costs. The proof is done in two steps. We first show that any deviation with multiple mass departures does not achieve lower costs than a deviation with a single mass departure launched before t * (Appendix C.1). We then show that this deviation is not gainful if the bounds on departure rates stated in Proposition 2 are satisfied (Appendix C.2).

Appendix C.1. Optimality of the single mass departure deviation

We show that any deviation from the PSNE involving multiple mass departures is dominated by a single mass departure. The proof involves establishing the following three results for either user: (i) Fleet costs can be (weakly) reduced by rescheduling any vehicles that suffer queuing delay, but are not part of a mass, to a period without queuing. (ii) Fleet costs can be (weakly) reduced by rescheduling any vehicles in a mass departure after t * to a period without queuing. (iii) Any deviation with multiple mass departures launched before t * entails strictly higher fleet costs than a deviation with a single mass departure. These three results establish that the candidate PSNE need only be tested against a single mass departure launched before t * .

Result i: When a queue exists, user A is willing to depart at a positive and finite rate only if condition ( 17) is satisfied. For early arrivals this requires r B (t) = α • s/ (α -β) > s. Since r B (t) < s in the candidate PSNE, condition ( 17) is violated, and user A will not deviate by departing early when there is a queue. For late arrivals, user A is willing to depart at a positive and finite rate when there is a queue only if r B (t) = α • s/ (α + γ). Proposition 2 stipulates that r B (t) ≤ α • s/ (α + γ). If r B (t) < α • s/ (α + γ), user A is better off scheduling its vehicles later. If r B (t) = α•s/ (α + γ), user A is indifferent between departing or not, and would not gain by rescheduling vehicles late when there is a queue.

Result ii: Assume that the last mass departure is launched at a time of late arrivals. We show that rescheduling vehicles in the mass to a later period in which they do not incur queuing delay is beneficial. By induction, it then follows that all mass departures launched at times of late arrivals can be gainfully rescheduled.

Suppose the last mass departure is launched at time t L and comprises M vehicles. Assume first that there is a queue at t L . We show that postponing the mass departure to the moment when the queue disappears (weakly) reduces fleet costs. Let m ∈ [0, M ] index vehicles in the order they are positioned in the mass, and let c(m, t L ) denote the cost incurred by vehicle m:

Now suppose the mass is postponed to t L > t L when a queue still exists. Vehicle m now incurs a cost of:

Appendix D. Asymmetric equilibrium costs with γ ≤ α User A's fleet costs in the PSNE depicted in Figure 2 are

Differentiating T C A with respect to t BA and t AB , and using Eqs. ( 7b), (7c) and condition (25) in the text, one obtains for the cost-minimizing transition times:

Substituting Eqs. ( 7b), (7c), and (D.2) into Eq. (D.1) gives

.

Appendix E. Heterogeneous desired arrival times

Appendix E.1. Case 1 User A's fleet costs in Case 1 are:

The price of anarchy is

. (E.1) P A is an increasing function of x. Condition (40) in the text, t * B -t * A ≥ (γ/(β +γ))•(N B /s), implies that x ≤ (β/(β + γ)) • (N A /s). Substituting this value for x into Eq. (E.1), and simplifying, yields

In the model variant in Section 4.1 the relative magnitudes of parameters β and γ are unrestricted so there is no upper or lower bound on β/γ. The formula in Eq. (E.3) reaches a maximum at β/γ = 1, for which P A = 1/5.

The lower bound on the efficiency index w is derived in the same way as the upper bound on P A. Imposing conditions ( 39) and (40) as equalities yields x = (β/(β + γ)) • (N A /s) = (γ/(β + γ)) • (N B /s). Substituting these equalities into Eq. ( 43) gives

(E.4) Eq. (E.4) achieves a minimum value of 6/7 with β = γ.

Appendix E.2. Case 2

The three transition times in Case 2, t 2 As , t 2 Ae , and t 2 Be , are solved using three conditions. First, Eq. ( 36) for Case 1 continues to apply, as otherwise user A could decrease its fleet costs by rescheduling a vehicle from t 2

As to t 2 Ae , or vice versa (cf Eq. (E.5a) below). Second, the bottleneck is fully utilized from t 2

As to t 2 Be (cf Eq. (E.5b)). Finally, user B's entire fleet must depart during the period [t * A , t 2 Be ] (cf Eq. (E.5c)).