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

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

Hugo E Silva
email: husilva@uc.cl

Equilibrium in a dynamic model of congestion with large and small users $

Keywords: Jel Classifications: C61, C62, D43, D62, R41 departure-time decisions, bottleneck model, congestion, schedule delay costs, large users, user heterogeneity, existence of Nash equilibrium

Individual users often control a significant share of total traffic flows. Examples include airlines, rail and maritime freight shippers, urban goods delivery companies and passenger transportation network companies. These users have an incentive to internalize the congestion delays their own vehicles impose on each other by adjusting the timing of their trips.

 for the case of symmetric large users. We also develop some examples to identify under what conditions a PSNE exists. The examples illustrate how self-internalization of congestion by a large user can affect the nature of equilibrium and the travel costs that it and other users incur.

Introduction

Transportation congestion has been a growing problem for many years, and road traffic congestion is now a blight in most large cities worldwide. [START_REF] Couture | [END_REF] estimate that the deadweight loss from congestion is about US$30 billion per year in large US cities. 1 [START_REF] Hymel | Does traffic congestion reduce employment growth[END_REF] shows that high levels of congestion dampen employment growth, and that congestion pricing could yield substantial returns in restoring growth. Congestion delays are also a problem at airports, on rail lines, at seaports and in the hinterland of major transportation hubs. [START_REF] Ball | Total delay impact study: a comprehensive assessment of the costs and impacts of flight delay in the united states[END_REF] estimate that in 2007 air transportation delays in the US imposed a cost of US$25 billion on passengers and airlines.

Research on congestion dates back to [START_REF] Pigou | The Economics of Welfare[END_REF]. Yet most economic and engineering models of congestible transportation facilities still assume that users are small in the sense that each one controls a negligible fraction of total traffic (see, e.g., [START_REF] Melo | Price competition, free entry, and welfare in congested markets[END_REF]. This is a realistic assumption for passenger trips in private vehicles. Yet large users are prevalent in all modes of transport. They include major airlines at their hub airports, railways, maritime freight shippers, urban goods delivery companies, large taxi fleets and postal services. In some cases large users account for an appreciable fraction of traffic. 2 Furthermore, major employers such as government departments, large corporations, and transportation service providers can add substantially to traffic on certain roads at peak times. 3 So can large shopping centres, hotels, and major sporting events. 4 Unlike small users, large users have an incentive to internalize the congestion delays 1 Methods of estimating the costs of congestion differ, and results vary widely. The Texas Transportation Institute estimated that in 2014, congestion in 471 urban areas of the US caused approximately 6.9 billion hours of travel delay and 3.1 billion gallons of extra fuel consumption with an estimated total cost of US$160 billion [START_REF] Schrank | 2015 urban mobility scorecard[END_REF]. It is unclear how institutional and technological innovations such as ridesharing, on-line shopping, electric vehicles, and automated vehicles will affect traffic volumes. The possibility that automated vehicles will increase congestion is raised in National Academies of Sciences, Engineering, and Medicine (2017) and The Economist (2018).

2 For example, the world market for shipping is relatively concentrated. According to [START_REF] Statista | Leading ship operator's share of the world liner fleet as of december 31[END_REF], as of December 31, 2017, the top five shipping operators accounted for 61.5% of the world liner fleet. The top ten accounted for 77.7%, and the top 15 for 85.5%. The top five port operators had a 29.9% global market share (Port Technology, 2014). The aviation industry is another example. The average market share of the largest firm in 59 major US airports during the period 2002-2012 was 42% [START_REF] Choo | Factors affecting aeronautical charges at major us airports[END_REF]. Similar shares exist in Europe.

3 For example, [START_REF] Ghosal | Advanced manufacturing plant location and its effects on economic development, transportation network, and congestion[END_REF] describe how the Kia Motors Manufacturing plant, a large automobile assembler in West Point, Georgia, affects inbound and outbound transportation flows on highway and rail networks, and at seaports. 4 Using data from US metropolitan areas with Major League Baseball (MLB) teams, [START_REF] Humphreys | Professional sporting events and traffic: Evidence from us cities[END_REF] estimate that attendance at MLB games increases average daily vehicle-miles traveled by about 6.9%, and traffic congestion by 2%.

their own vehicles impose on each other. This so-called "self-internalization" incentive can affect large users' decisions 5 and raises a number of interesting questions -some of which are discussed further in the conclusions. One is how much a large user gains from selfinternalization. Can it backfire and leave the large user worse off after other users respond?

Second, do other users gain or lose when one or more large users self-internalize? Does it depend on the size of the large users and when they prefer to schedule their traffic? Are mergers between large users welfare-improving? What about unions of small users that create a large user?

There is now a growing literature on large users and self-internalization -notably on large airlines and airport congestion. Nevertheless, this body of work is limited in two respects. First, as described in more detail below, most studies have used static models.

Second, much of the theoretical literature has restricted attention to large users. In most settings, however, small users are also present. Automobile drivers and most other road users are small. Most airports serve not only scheduled commercial service, but also general aviation movements by recreational private aircraft and other non-scheduled users. Lowcost carriers with small market shares serve airports where large legacy airlines control much of the overall traffic. 6 We contribute to the literature in this paper by developing and analyzing a dynamic model of congestion at a transportation facility with both large users and small users.

More specifically, we use the Vickrey bottleneck model to study how large users schedule departure times for their vehicle fleets when small users use the facility too. As we explain in the literature review below, to the best of our knowledge, we are the first to study trip-timing decisions in markets with a mix of large and small users.

Several branches of literature have developed on large users of congestible facilities. 7

They include studies of route-choice decisions on road networks and flight scheduling at congested airports. There is also a literature directed to computer and telecommunications 5 For example, some seaports alleviate congestion by extending operating hours at truck gates, and using truck reservation systems at their container facilities (Weisbrod and Fitzroy, 2011). Cities and travel companies are also attempting to spread tourist traffic by making off-peak visits more attractive and staggering the arrivals of cruise ships [START_REF] Sheahan | Europe works to cope with overtourism[END_REF]. Airports, especially in Europe, restrict the number of landings and takeoffs during specific periods of time called slot windows (see [START_REF] Daniel | The untolled problems with airport slot constraints[END_REF] for a discussion of this practice). 6 Using data from Madrid and Barcelona, Fageda and Fernandez-Villadangos (2009) report that the market share of low-cost carriers is generally low (3-5 carriers with 3-18% of market share). Legacy carriers themselves sometimes operate only a few flights out of airports where another legacy carrier has a hub. For example, at Hartsfield-Jackson Atlanta International (ATL) American Airlines has a 3% market share while Delta's is 73% (Bureau of Transportation Statistics, 2017). 7 See [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF] for a brief review.

networks on atomic congestion games. However, most studies have adopted static models that disregard the timing decisions of users despite the fact that congestion delays tend to be highly concentrated at peak times (see, e.g., [START_REF] Naroditskiy | Maximizing social welfare in congestion games via redistribution[END_REF]. The relatively small body of work that does address the temporal dimension of congestion has taken three approaches to incorporate dynamics. One approach has used dynamic stochastic models designed specifically to describe airport congestion (see, e.g., [START_REF] Daniel | Congestion pricing and capacity of large hub airports: A bottleneck model with stochastic queues[END_REF]. A second approach, also directed at studying airport congestion, features deterministic congestion and a sequential decision-making structure in which an airline with market power acts as a Stackelberg leader and schedules its flights before other airlines in a competitive fringe (see [START_REF] Daniel | Distributional consequences of airport congestion pricing[END_REF][START_REF] Silva | Airlines' strategic interactions and airport pricing in a dynamic bottleneck model of congestion[END_REF]. As [START_REF] Daniel | The untolled problems with airport slot constraints[END_REF] discusses, the presence of slot constraints at airports makes the Stackelberg approach relevant. The slots are allocated twice a year with priority for the incumbent airlines; slots allocation for new entrants, which are modeled as followers in this approach, occur only after the incumbents have committed to a slot schedule, and normally come from new airport capacity. In these cases, adopting a sequential decision-making structure seems to be accurate. Nevertheless, at most US airports, the capacity is assigned in a first-come, first-served basis, which makes the simultaneous structure, and Nash as an equilibrium concept, more relevant.

These two approaches lead to outcomes broadly consistent with those of static models.

Two results stand out. First, self-internalization of congestion by large users tends to result in less concentration of traffic at peak times, and consequently lower total costs for users in aggregate. Second, the presence of small users limits the ability of large users to reduce congestion. This is because reductions in the amount of traffic scheduled by large users, either at peak times or overall, are partially offset by increases in traffic by small users.

The Stackelberg equilibrium concept adopted in the second approach rests on the assumptions that the leader can schedule its traffic before other agents, and also commit itself to abide by its choices after other agents have made theirs. These assumptions are plausible in some institutional settings (e.g., Stackelberg leadership by legacy airlines at hub airports), but by no means in all settings. The third approach to incorporating trip-timing decisions, which we adopt, instead takes Nash equilibrium as the solution concept so that all users make decisions simultaneously.

Our paper follows up on recent work by Verhoef and Silva (2017) and [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF] who focus on determining under what conditions a Pure Strategy Nash Equilibrium (PSNE) in departure-time decisions exists. These two studies employ different deterministic congestion models that are best suited to describe road traffic congestion. Verhoef and Silva (2017) use the flow congestion model developed by [START_REF] Henderson | Road congestion: a reconsideration of pricing theory[END_REF], and modified by [START_REF] Chu | Endogenous trip scheduling: the henderson approach reformulated and compared with the vickrey approach[END_REF]. In this model, vehicles travel at a constant speed throughout their trips with the speed determined by the density of vehicles prevailing when their trip ends. Verhoef and [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF] show that, if there are two or more large users and no small users, a PSNE always exists. Self-internalization of congestion by the large users results in less concentration of trips at peak times and, not surprisingly, higher efficiency compared to the equilibrium without large users. However, this result is tempered by two well-known drawbacks of the [START_REF] Lindsey | Congestion modelling[END_REF]. [START_REF] Henderson | Road congestion: a reconsideration of pricing theory[END_REF] originally assumed that vehicle speed is determined by the density of traffic encountered when a vehicle starts its trip. This formulation has the additional disadvantage that a vehicle departing when density is low may overtake a vehicle that departed earlier when density was higher. As [START_REF] Lindsey | Congestion modelling[END_REF] explain, overtaking has no behavioral basis if drivers and vehicles are identical, and it is physically impossible under heavily congested conditions. By contrast, in [START_REF] Chu | Endogenous trip scheduling: the henderson approach reformulated and compared with the vickrey approach[END_REF] reformulated model overtaking does not occur in equilibrium. 9 A few experimental economics studies have tested the theoretical predictions of the bottleneck model; see [START_REF] Dixit | Understanding transportation systems through the lenses of experimental economics: A review[END_REF] for a review. The studies used a variant of the bottleneck model in which vehicles and departure times are both discrete. In all but one study, players controlled a single vehicle. The exception is [START_REF] Schneider | Against all odds: Nash equilibria in a road pricing experiment[END_REF] who ran two sets of experiments. In the first experiment each player controlled one vehicle, and in the second experiment each player controlled 10 vehicles which were referred to as trucks. Compared to the first experiment, the aggregate departure-time profile in the second experiment was further from the theoretical Nash equilibrium and closer to the system optimum. Schneider and Weimann conclude (p.151) that "players with 10 trucks internalize some of the congestion externality".

In this paper we extend [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF] by investigating the existence and nature of PSNE in the bottleneck model for a wider range of market structures and under more general assumptions about trip-timing preferences. Unlike both Verhoef and [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF] and [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF], we allow for the presence of small users as well as large users.

As in the standard bottleneck model, small users each control a single vehicle and seek to minimize their individual trip cost. Each large user operates a vehicle fleet that comprises a positive fraction or measure of total traffic, and seeks to minimize the aggregate trip costs of its fleet. 10 Each vehicle has trip-timing preferences described by a trip-cost function C(t, a), where t denotes departure time and a denotes arrival time. Trip cost functions can differ for small and large users, and they can also differ for vehicles in a large user's fleet.

Our analysis consists of several parts. After introducing the basic model and assumptions in Section 2, in Section 3 we use optimal control theory to derive a large user's optimal fleet departure schedule as a best response to the aggregate departure rate profile of other users. We show that the optimal response can be indeterminate, and the second-order condition for an interior solution is generally violated. Consequently, a candidate PSNE departure schedule may exist in which a large user cannot gain by rescheduling any single vehicle in its fleet, yet it can gain by rescheduling a positive measure of vehicles. These difficulties underlie the non-existence of a PSNE in [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF]. We then show in Section 4 that if vehicles in the large user's fleet have sufficiently diverse trip-timing preferences, a PSNE may exist in which some -or even all -of the large user's vehicles do queue. The fact that a PSNE exists given sufficient user heterogeneity parallels the existence of equilibrium in the Hotelling model of location choice given sufficient preference heterogeneity [START_REF] De Palma | The principle of minimum differentiation holds under sufficient heterogeneity[END_REF].

Next, in Section 5 we revisit the case of symmetric large users that [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF] consider, and derive the minimum degree of preference heterogeneity required to support a PSNE. We show that relative to the PSNE in which large users disregard self-imposed congestion, self-internalization results in substantial efficiency gains from reduced queuing delays even when the number of users is fairly large. Then, in Section 6 we modify the example of symmetric large users by assuming that part of the traffic is controlled by a single large user, and the rest by a continuum of small users. We derive conditions for existence of Unfortunately, they do not provide information on how the players distributed their vehicles over departuretime slots. Thus, it is not possible to compare their results with the predictions of our model as far as when large users choose to depart. 10 In game theory, small agents or players are sometimes called "non-atomic" and large agents "atomic".

In economics, the corresponding terms are "atomistic" and "non-atomistic". To avoid confusion, we do not use these terms. However, we do refer to the PSNE in which large users do not internalize their self-imposed congestion externalities as an "atomistic" PSNE.

a PSNE and show how the order in which users depart depends on the flexibility implied by the trip-timing preferences of large and small users. We also show that self-internalization of congestion can have no effect on the PSNE at all.

The model

The model is a variant of the classical bottleneck model.

(t) = Q(t)/s, or q(t) = t -t + s -1 R(t) -R( t) . (1)
A user departing at time t arrives at time a = t + q(t).

The cost of a trip is described by a function C (t, a, k), where k denotes a user's index or type. 12 Function C (t, a, k) is assumed to have the following properties:

Assumption 1: C (t, a, k) is differentiable almost everywhere with derivatives C t < 0,

C a > 0, C tt ≥ 0, C tt + C aa > 0, C ta = C at = 0, C tk ≤ 0, C ak ≤ 0, C tkk = 0, and C akk = 0.
The assumption C t < 0 implies that a user prefers time spent at the origin to time spent in transit. Similarly, assumption C a > 0 implies that a user prefers time spent at the destination to time spent in transit. User types can be defined in various ways. For much of the analysis, type is assumed to denote a user's preferred time to travel if a trip could be made instantaneously (i.e, with a = t). For type k, the preferred time is

t * k = Arg min t C (t, t, k). Given Assumption 1, t * k is unique. Types are ordered so that if k > j, t * k ≥ t * j .
As explained in the Appendix, Assumption 1 is satisfied for various specifications of the cost function including the piecewise linear form introduced by Vickrey (1969):

11 The bottleneck model is reviewed in [START_REF] Arnott | Recent developments in the bottleneck model[END_REF], [START_REF] Small | The Economics of Urban Transportation[END_REF], de Palma andFosgerau (2011), and[START_REF] Small | The bottleneck model: An assessment and interpretation[END_REF]. The exposition in this section draws heavily from [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF].

Literal excerpts are not marked as such and are taken to be acknowledged by this footnote.

12 As explained in the Appendix, the trip cost function can be derived from functions specifying the flow of utility or payoff received at the origin, at the destination, and while in transit.

C (t, a, k) = α k (a -t) + β k (t * k -a) for a < t * k α k (a -t) + γ k (a -t * k ) for a > t * k . (2)
In (2), parameter α k is the unit cost of travel time, β k < α k is the unit cost of arriving early, and γ k is the unit cost of arriving late. The first term in each branch of (2) denotes travel time costs, and the second term denotes schedule delay costs. We refer to this specification of costs as "step preferences". 13

Because step preferences have a kink at t * k , the derivative C a is discontinuous at a = t * k . This turns out to affect some of the results in this paper, and makes step preferences an exception to some of the propositions. It is therefore useful to know whether step preferences are reasonably descriptive of reality. Most studies that have used the bottleneck model have adopted step preferences, but this may be driven in part by analytical tractability and convention. Empirical evidence on the shape of the cost function is varied. [START_REF] Small | The scheduling of consumer activities: work trips[END_REF] found that step preferences describe morning commuter behaviour fairly well, but he did find evidence of discrete penalties for arriving late beyond a "margin of safety."

Nonconvexities in schedule delay costs have been documented (e.g., Matsumoto, 1988), and there is some empirical evidence that the marginal cost of arriving early can exceed the marginal cost of travel time (Abkowitz, 1981a,b;[START_REF] Hendrickson | The flexibility of departure times for work trips[END_REF]Tseng and Verhoef, 2008) which violates the assumption β k < α k .

The paper features examples with step preferences where the results depend on the relative magnitudes of parameters α, β, and γ. Estimates in the literature differ, but most studies of automobile trips find that β < α < γ. Small (1982, Table 2, Model 1) estimates ratios of β:α:γ = 1:1.64:3.9. These rates are representative of average estimates in later studies. 14 For benchmark values we adopt β:α:γ = 1:2:4.

In the standard bottleneck model, each user controls a single vehicle of measure zero and decides when it departs. A Pure Strategy Nash Equilibrium (PSNE) is a set of departure 13 These preferences have also been called "α -β -γ " preferences. 14 Estimates of the ratio γ/β vary widely. It is of the order of 8 in Geneva (Switzerland), and 4 in Brussels (Belgium), where tolerance for late arrival is much larger (see [START_REF] De Palma | Impact of adverse weather conditions on travel decisions: Experience from a behavioral survey in geneva[END_REF][START_REF] Khattak | The impact of adverse weather conditions on the propensity to change travel decisions: a survey of brussels commuters[END_REF]. Tseng et al. (2005) obtain a ratio of 3.11 for the Netherlands. [START_REF] Peer | Long-run versus short-run perspectives on consumer scheduling: Evidence from a revealed-preference experiment among peak-hour road commuters[END_REF] show that estimates derived from travel choices made in the short run can differ significantly from estimates derived from long-run choices when travelers have more flexibility to adjust their schedules. Most studies of triptiming preferences have considered passenger trips. Many large users transport freight rather than people.

Trip-timing preferences for freight transport can be governed by the shipper, the receiver, the transportation service provider, or some combination of agents. There is little empirical evidence for freight transportation on the relative values of α, β, and γ. The values are likely to depend on the type of commodity being transported, the importance of reliability in the supply chain, and other factors. Thus, it is wise to allow for a wide range of possible parameter values.

times for all users such that no user can benefit (i.e., reduce trip cost) by unilaterally changing departure time while taking other users' departure times as given. For brevity, the equilibrium will be called an "atomistic PSNE".

If small users are homogeneous (i.e., they all have the same type), then in a PSNE they depart during periods of queuing when the cost of a trip is constant. Their departure rate will be called their atomistic equilibrium departure rate, or "atomistic rate" for short. The atomistic rate for type k is derived from the condition that C (t, a, k) is constant. Using subscripts to denote derivatives, this implies

C t (t, a, k) + C a (t, a, k) 1 + dq (t) dt = 0.
Given (1), the atomistic rate is

r (t, a, k) = - C t (t, a, k) C a (t, a, k) s. (3) Since C t < 0 and C a > 0, r (t, a, k) > 0. Using Assumption 1, it is straightforward to establish the following properties of r (t, a, k): 15 ∂ r (t, a, k) ∂k ≥ 0, ∂ 2 r (t, a, k) ∂k 2 ≥ 0, Sgn ∂ r (t, a, k) ∂a = -C aa . (4)
For given values of t and a, the atomistic rate increases with a user's type, and at an increasing rate. In addition, the atomistic rate is increasing with arrival time if C aa < 0, and decreasing if C aa > 0. With step preferences, C aa = 0 except at t * k , and the atomistic rate is:

r (t, a, k) = α k α k -β k s for a < t * k α k α k +γ k s for a > t * k .
(5) [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF] consider a variant of the standard bottleneck model in which users are "large". A large user controls a vehicle fleet of positive measure, and internalizes the congestion costs its vehicles impose on each other. A PSNE entails a departure schedule for each user such that no user can reduce the total trip costs of its fleet by unilaterally changing its departure schedule while taking other users' departure schedules as given. We will call the equilibrium the "internalized PSNE". [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF] focus on the case of two large users with step preferences. In the next section we derive the departure schedule of a large user with general trip-timing preferences when other large users and/or small users may be departing too.

15 See the Appendix.

Fleet departure scheduling and equilibrium conditions

Optimal departure schedule for a large user

This section uses optimal control theory to derive and characterize the optimal departure schedule of a large user with a fleet of vehicles. Call the large user "user A", and let N A be the measure of vehicles in its fleet. Vehicle k has a cost function C A (t, a, k). Vehicles are indexed in order of increasing preferred arrival times so that t * k ≥ t * j if k > j. It is assumed that, regardless of the queuing profile, it is optimal for user A to schedule vehicles in order of increasing k. The departure schedule for user A can then be written r A (t) with

argument k suppressed. If R A (t) denotes cumulative departures of A, vehicle k = R A (t)
departs at time t.

User A chooses r A (t) to minimize the total trip costs of its fleet while taking as given the aggregate departure rate of other users, r -A (t). Trips are assumed to be splittable: they can be scheduled at disjoint times (e.g., some vehicles can travel early in the morning while others travel at midday). Let t As and t Ae denote the first and last departure times chosen by user A. User A's optimization problem can be stated as:

M in t As ,t Ae ,r A (t) t Ae t=t As r A (t) C A (t, t + q (t) , R A (t)) dt, (6)
subject to the equations of motion:

dq (t) dt + = s -1 (r -A (t) + r A (t)) -1 if q (t) > 0 or r -A (t) + r A (t) > s 0 otherwise (7)
(costate variable λ (t) ≥ 0), and

dR A (t) dt = r A (t) (costate variable µ (t) ), (8)
and the following constraints16 :

r A (t) ≥ 0 (multiplier ξ (t) ≥ 0), (9a) R A (t As ) = 0, R A (t Ae ) = N A , (9b)
q (t As ) = q (t As ) (multiplier φ), (9c)
t As , t Ae chosen freely. (9d)

Costate variable λ (t) for Eq. ( 7) measures the shadow cost to user A of queuing time.

Eq. ( 8) governs how many vehicles in user A's fleet have left the origin. Costate variable µ (t) measures the shadow cost of increasing the number of vehicles in the fleet that have started their trips. Condition (9a) stipulates that the departure rate cannot be negative.

Condition (9b) specifies initial and terminal values for cumulative departures. Condition (9c) describes how queuing time is evolving when departures begin. Finally, (9d) indicates that the choice of departure period is unconstrained.

The Hamiltonian for the optimization problem is

H (t) = r A (t) C A (t, t + q (t) , R A (t)) + µ (t) dR A (t) dt + λ (t) dq (t) dt + , ( 10
)
and the Lagrangian is

L (t) = H (t) + r A (t) ξ (t) . ( 11
)
Costate variable λ (t) for queuing time evolves according to the equation of motion

dλ (t) dt = - ∂H ∂q = -r A (t) C A a (t, t + q (t) , R A (t)) ≤ 0. ( 12
)
Variable λ (t) decreases as successive vehicles in the fleet depart because fewer vehicles remain that can be delayed by queuing.

Costate variable µ (t) for cumulative departures evolves according to the equation of

motion dµ (t) dt = - ∂H ∂R A = -r A (t) C A k (t, t + q (t) , R A (t)) ≥ 0. ( 13
)
If vehicles in the fleet are homogeneous, µ is independent of time.

With t Ae chosen freely, transversality conditions at t Ae are:

λ (t Ae ) = 0, (14)
H (t Ae ) = 0. ( 15
)
According to condition ( 14), the shadow cost of queuing time drops to zero when the last vehicle departs. Condition (15) dictates that the net flow of cost is zero when the last vehicle departs. Substituting ( 14) into (10), and applying (15) yields

µ (t Ae ) = -C A (t Ae , t Ae + q (t Ae ) , N A ) . ( 16
)
Condition ( 16) states that the benefit from dispatching the last vehicle in the fleet is the cost of its trip that has now been incurred, and is no longer a pending liability.

With t As chosen freely, a transversality condition also applies at t As . Following Theorem 7.8.1 in [START_REF] Leonard | Optimal control theory and static optimization in economics[END_REF], the transversality condition is:

H (t As ) -φ dq (t) dt t As = 0, ( 17
)
where φ is a multiplier on the constraint (9c). By continuity, φ = λ (t As ). Using ( 10) and ( 8), condition (17) reduces to

r A (t As ) C A (t As , t As + q (t As ) , 0) + µ (t As ) = 0. ( 18
)
It remains to determine the optimal path of r A (t). The optimality conditions governing r A (t) depend on whether or not there is a queue. Attention is limited here to the case with a queue.17 If q (t) > 0, the optimal departure rate is governed by the conditions

∂L ∂r A (t) = C A (t, t + q (t) , R A (t)) + ξ (t) + µ (t) + λ (t) s = 0, (19)
ξ (t) r A (t) = 0.
If r A (t) is positive and finite during an open time interval containing t, then ξ (t) = 0 and ( 19) can be differentiated with respect to t:

d dt ∂L ∂r A (t) = C A t (t, t + q (t) , R A (t)) + C A a (t, t + q (t) , R A (t)) 1 + dq (t) dt + +C A k (t, t + q (t) , R A (t)) r A (t) + dµ (t) dt + 1 s dλ (t) dt = 0.
Using Eqs. ( 7) and ( 12), this condition simplifies to

C A t (t, t + q (t) , R A (t)) + C A a (t, t + q (t) , R A (t)) r -A (t) s = 0. ( 20
)
The left-hand-side of (20) depends on the aggregate departure rate of other users, r -A (t), but not on r A (t) itself. In general, derivatives C A t (t, t + q (t) , R A (t)) and C A a (t, t + q (t) , R A (t)) depend on the value of q (t), and hence the value of R (t), but not directly on r A (t). Condition (20) will therefore not, in general, be satisfied regardless of user A's choice of r A (t). This implies that the optimal departure rate may follow a bang-bang solution between zero flow and a mass departure.18 This is confirmed by inspecting the Hessian matrix of the Hamiltonian:

    ∂ 2 H ∂r 2 A (t) ∂ 2 H ∂r A (t)∂q(t) ∂ 2 H ∂r A (t)∂R A (t) ∂ 2 H ∂r A (t)∂q(t) ∂ 2 H ∂q 2 (t) ∂ 2 H ∂q(t)∂R A (t) ∂ 2 H ∂r A (t)∂R A (t) ∂ 2 H ∂q(t)∂R A (t) ∂ 2 H ∂R 2 A (t)     =     0 C A a (t, t + q (t) , R A (t)) C A k (t, t + q (t) , R A (t)) C A a (t, t + q (t) , R A (t)) r A (t) C A aa (t, t + q (t) , R A (t)) r A (t) C A ak (t, t + q (t) , R A (t)) C A k (t, t + q (t) , R A (t)) r A (t) C A ak (t, t + q (t) , R A (t)) r A (t) C A kk (t, t + q (t) , R A (t))     .
Since the Hessian is not positive definite, the second-order sufficient conditions for a local minimum are not satisfied. As we will show, if users are homogeneous the necessary condition (20) cannot describe the optimal schedule unless C A aa = 0. In summary, user A will not, in general, depart at a positive and finite rate when a queue exists. To understand why, consider condition (20). Given C A t < 0 and C A a > 0, if r -A (t) is "small" the left-hand side of (20) is negative. The net cost of a trip is decreasing over time, and user A is better off scheduling the next vehicle in its fleet later. Contrarily, if r -A (t) is "large", the left-hand side of ( 20) is positive. Trip cost is increasing, and user A should dispatch a mass of vehicles immediately if it has not already done so. In either case, the optimal departure rate is not positive and finite.

In certain cases, described in the next section, condition (20) will be satisfied. The condition can then be written as a formula for the departure rate of other users:

r -A (t) = - C A t (t, t + q (t) , R A (t)) C A a (t, t + q (t) , R A (t)) s ≡ r A (t, t + q (t) , R A (t)) . ( 21
)
Condition ( 21) has the same functional form as Eq. ( 3) for the atomistic rate of small users.

Thus, with step preferences, the right-hand side exceeds s for early arrival and is less than s for late arrival. Moreover, the condition depends only on the aggregate departure rate of other users, and not their composition (e.g., whether the other users who are departing are large or small. However, condition ( 21) is only necessary, not sufficient, to have r A (t) > 0 because the second-order conditions are not satisfied. This leads to:

Lemma 1. Assume that a queue exists at time t. A large user will not depart at a positive and finite rate at time t unless the aggregate departure rate of other users equals the large user's atomistic rate given in Eq. ( 21).

Lemma 1 requires qualification in the case of step preferences because the atomistic rate is discontinuous at the preferred arrival time. If vehicles in a large user's fleet differ sufficiently in their individual t * k , it is possible to have a PSNE in which the fleet departs at a positive and finite rate with each vehicle arriving exactly on time. The aggregate departure rate of other users falls short of the atomistic rate of each vehicle in the fleet just before it departs, and exceeds it just after it departs. This is illustrated using an example in Section 6.

Equilibrium conditions with large users

We now explore the implications of Lemma 1 for the existence of a PSNE in which a large user departs when there is a queue and the atomistic rates of all users are continuous.

Conditions for a PSNE depend on whether or not small users are present, and the two cases are considered separately below.

Multiple large users and no small users

Suppose there are m ≥ 2 large users and no small users. User i has an atomistic rate ri (t, t + q (t) , R i (t)). For brevity, we write this as ri (t) with arrival time and the index k for vehicles both suppressed. Suppose that a queue exists at time t, and user i departs at rate r i (t) > 0, i = 1...m. 19 Necessary conditions for a PSNE to exist are

r -i (t) = ri (t) , i = 1...m. ( 22
)
This system of m equations has a solution

r i (t) = 1 m -1 j =i rj (t) - m -2 m -1 ri (t) = 1 m -1 j rj (t) -ri (t) , i = 1...m. ( 23
)
With m = 2, the solution is r 1 (t) = r2 (t), and r 2 (t) = r1 (t). With m > 2, the solution is feasible only if all departure rates are nonnegative. A necessary and sufficient condition for this to hold at time t is

M ax i ri (t) ≤ 1 m -2 j =i rj (t) . (24)
Condition ( 24) is satisfied if large users have sufficiently similar atomistic rates.

Multiple large users and small users

Assume now that, in addition to m ≥ 1 large users, there is a group of homogeneous small users comprising a positive measure of total traffic with an atomistic rate ro (t).

Suppose that large user i departs at rate r i (t) > 0, i = 1...m, and small users depart at an aggregate rate r o (t) > 0. If a queue exists at time t, necessary conditions for a PSNE are

r -i (t) = ri (t) , i = 1...m, ( 25
) j r j (t) + r o (t) = ro (t) . ( 26
)
The solution to this system of m + 1 equations is

r i (t) = ro (t) -ri (t) , i = 1...m, (27)
r o (t) = j rj (t) -(m -1) ro (t) . ( 28
)
The solution is feasible only if all departure rates are nonnegative. With m = 1, the necessary and sufficient condition is r1 (t) < r0 (t). With m > 1, necessary and sufficient

19 If a user does not depart at time t, it can be omitted from the set of m "active" users at t.

conditions for nonnegativity are 1 m -1 j rj (t) > ro (t) , ( 29)

ri (t) < ro (t) , i = 1...m. ( 30
)
Condition ( 30) requires that all large users have lower atomistic rates than the small users.

However, condition [START_REF] Daniel | Distributional consequences of airport congestion pricing[END_REF] dictates that the average atomistic rate for large users be close enough to the atomistic rate of small users. Together, ( 29) and ( 30) impose relatively tight bounds on the ri (t) .

Existence of PSNE with queuing by a large user

Silva et al. ( 2017) consider two identical large users with homogeneous vehicle fleets and step preferences. They show that a PSNE with queuing does not exist. In addition, they show that if γ > α, a PSNE without queuing does not exist either so that no PSNE exists. In this section we build on their results in two directions. First, we prove that if a large user has a homogeneous vehicle fleet, and C A aa = 0 at any time when the large user's vehicles arrive, a PSNE in which the large user queues does not exist for any market structure. Second, we show that if a large user has a heterogeneous vehicle fleet, and the derivative C A ak is sufficiently large in magnitude, a PSNE in which the large user queues is possible. We illustrate the second result in Section 5. Consider a large user, "user A", and a candidate PSNE in which queuing time is q (t) > 0 at time t. (A bar denotes quantities in the candidate PSNE.) User A never departs alone when there is a queue because it can reduce its fleet costs by postponing departures. Thus, if rA (t) is positive and finite, other users must also be departing. The aggregate departure rate of other users must equal user A's atomistic rate as per Eq. ( 22) or (25): r-A (t) = rA t, t + q (t) , RA (t) .

In addition, user A must depart at a rate rA (t) consistent with equilibrium for other users as per Eq. ( 23), or Eqs. ( 27) and (28). Figure 1 Cumulative departures of user A, RA (t) = R (t) -R-A (t), are measured by the distance between the two curves.

Suppose that user A deviates from the candidate PSNE during the interval (t A , t B ) by dispatching its vehicles slightly later so that section ADB of R (t) shifts rightwards to R (t)

∆C A (k) = C A (t E , t E + q (t E ) , k) -C A (t D , t D + q (t D ) , k) ,
where q (t D ) is queuing time at t D with the candidate equilibrium departure schedule R (t), and q (t E ) is queuing time at t E with the deviated schedule R (t). The path from point D to point E can be traversed along the dashed blue curve running parallel to R-A (t) between points y and z. Let q (t) denote queuing time along this path. The change in cost can then be written

∆C A (k) = t E t=t D C A t (t, t + q (t) , k) + C A a (t, t + q (t) , k) 1 + dq (t) dt dt. = t E t=t D C A t (t, t + q (t) , k) + C A a (t, t + q (t) , k) r A t, t + q (t) , RA (t) s dt = 1 s t E t=t D C A a (t, t + q (t) , k) r A t, t + q (t) , RA (t) -r A (t, t + q (t) , k) dt = 1 s t E t=t D C A a (t, t + q (t) , k)    r A t, t + q (t) , RA (t) -r A (t, t + q (t) , k) -( r A (t, t + q (t) , k) -r A (t, t + q (t) , k))    dt. ( 31
)
The sign of this expression depends on how r A varies with arrival time and vehicle index. We begin by showing that, if vehicles are homogeneous, ( 31) is negative so that ∆C A (k) < 0 and the candidate is not a PSNE.

Homogeneous vehicle fleets

If user A has a homogeneous fleet, the first line in braces in (31) is zero. Given C A aa > 0 and q (t) < q (t) for t ∈ (t D , t E ), rA (t, t + q (t) , k) > rA (t, t + q (t) , k) and the second line in braces is negative. Hence ∆C A (k) < 0, and rescheduling the vehicle from D to E reduces its trip cost. Since point D is representative of all points between A and B, all the rescheduled vehicles except those at the endpoints, A and B, experience a reduction in costs. User A therefore gains from the deviation, and the candidate schedule is not a PSNE.

In the Appendix we show that if C A aa < 0, user A can benefit by accelerating departures of its fleet. Deviation is therefore beneficial both when C A aa > 0 and when C A aa < 0. This result is formalized in Lemma 2. Consider large user A with a homogeneous vehicle fleet. If a queue exists at time t, and C A aa (t, t + q(t)) = 0, user A will not depart at a positive and finite rate at time t.

Lemma 2 shows that although the candidate PSNE is robust to deviations in the departure time of a single vehicle, it is not robust to deviations by a positive measure of the fleet. If C A aa > 0, the departure rate of other users must decrease over time in order for user A to maintain a positive and finite departure rate. By delaying departures, user A enables vehicles in its fleet to benefit from shorter queuing delays. Conversely, if C A aa < 0, the departure rate of other users must increase over time in a PSNE, and user A can benefit by accelerating departures of its fleet.

Lemma 2 contrasts sharply with the results of Verhoef and Silva (2017) who show that, given a set of large users with homogeneous vehicle fleets, a PSNE always exists in the Henderson-Chu model. As noted in the introduction, in the Henderson-Chu model vehicles that arrive (or depart) at different times do not interact with other. In particular, a cohort of vehicles departing at time t is unaffected by the number or density of vehicles that departed before t. Thus, if a large user increases or decreases the departure rate of its fleet at time t, it does not affect the costs incurred by other vehicles in the fleet that are scheduled after t. Equilibrium is determined on a point-by-point basis, and there is no state variable analogous to the queue in the bottleneck model that creates intertemporal dependence in costs.

Heterogeneous vehicle fleets

Suppose now that user A has a heterogeneous fleet. By (4), ∂ rA (t, a, k) /∂k ≥ 0 so that the first line in braces in (31) is positive. Expression ( 31) is then positive if the first line outweighs the second line. We show that this is indeed the case under plausible assumptions. Towards this, we introduce the following two-part assumption:

Assumption 2: (i) The trip cost function depends only on the difference between actual arrival time and desired arrival time, and thus can be written

C A (t, a, k) = C A (t, a -t * k ). (ii) t * k is distributed
) ≤ s ∀ t * k ∈ [t * s , t * e ]
), a PSNE in which user A queues may exist.

Theorem 1 identifies necessary conditions such that a large user may queue in a PSNE.

In light of Lemma 2 the key requirement is evidently sufficient heterogeneity in the triptiming preferences of vehicles in the large user's fleet. Condition f (t * k ) ≤ s stipulates that the desired arrival rate of vehicles in the fleet never exceeds bottleneck capacity. Put another way, if user A were the only user of the bottleneck, it could schedule its fleet so that every vehicle arrived precisely on time without queuing delay.

The assumption f (t * k ) ≤ s is plausible for road transport. Freight shippers such as Fedex or UPS operate large vehicle fleets out of airports and central warehouses, and they can make hundreds of daily trips on highways and connecting roads in an urban area. Nevertheless, deliveries are typically made to geographically dispersed customers throughout the day so that the fleet rarely comprises more than a small fraction of total traffic on a link at any given time. Thus, for any t * k , f (t * k ) is likely to be only a modest fraction of s.

In concluding this section it should be emphasized that Theorem 1 only states that a PSNE in which a large user queues may exist. A large user may prefer to avoid queuing by traveling at off-peak times. To determine whether this is the case, it is necessary to consider the trip-timing preferences of all users. We do so in Section 5 for the case of large users studied by [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF]. Section 6 examines a variant with both large users and small users.

Existence of PSNE and self-internalization: multiple large users

In this section we analyze the existence of PSNE with m ≥ 2 symmetric large users.

We begin with m = 2: the case considered by [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF]. Consider two symmetric large users, A and B, that each controls N/2 vehicles with step preferences. Such a market setting might arise with two airlines that operate all (or most of) the flights at a congested airport. This section revisits Proposition 1 in [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF] which states that a PSNE does not exist with homogeneous vehicles when γ > α. Their proof entails showing that with γ > α, a PSNE without queuing does not exist. The proof that a PSNE with queuing does not exist either follows the general reasoning used to prove Lemma 2 above. Here we relax the assumption that vehicles are homogeneous, and suppose that in each vehicle fleet, ] and height N . The two users schedule vehicles at the same rate. During the initial interval (t s , t q ), both users depart at an aggregate rate of s without creating a queue.

t * k is uniformly distributed with a density f (t * k ) = N/ (2∆)
Queuing begins at time t q , and ends at t e when the last vehicle in each fleet departs. Queuing time reaches a maximum at t for a vehicle arriving at t * = β β+γ t * s + γ β+γ t * e . Total departures after time t q are shown by the piecewise linear curve ALC. Cumulative departures by user B starting at t q are given by the piecewise linear curve AP E, and cumulative departures by user A are measured by the distance between AP E and ALC. If a PSNE exists, total costs in the internalized PSNE, T C i , are lower than total costs in the atomistic PSNE, T C n . As shown in the Appendix, the total cost saving from internalization with m users is

T C n -T C i = (m -1) β (α + γ) + mαγ 2m (m -1) βγ + 2mαγ Ψ • T C nH ,
where

T C nH = βγ β+γ N 2
s denotes total costs in the atomistic PSNE with homogeneous vehicles. The composite parameter Ψ depends on parameters α, β, and γ only through the ratios β/α and γ/α. Given the benchmark ratios of β:α:γ = 1:2:4, Ψ = 7m-3 4m(1+m) , which varies with m as shown in Table 1. With two users (m = 2) the saving is nearly as great as with a single user. Even with 10 users the savings is over 15 percent of the atomistic costs T C nH . These results are similar to those obtained by Verhoef and Silva (2017) with the Henderson-Chu model of congestion and a single desired arrival time, as they also find significant savings from selfinternalization. Moreover, with heterogeneity in t * , total costs in the atomistic PSNE are less than T C nH so that the proportional cost saving from internalization is actually larger than shown in Table 1. The example shows that self-internalization of congestion can boost efficiency appreciably even if no user controls a large fraction of total traffic. This is consistent with [START_REF] Brueckner | Airport congestion when carriers have market power[END_REF] who showed, using a Cournot oligopoly model, that internalization of self-imposed delays leads to an equilibrium that is more efficient than the atomistic equilibrium, and correspondingly offers smaller potential efficiency gains from congestion pricing.

Existence of PSNE and self-internalization: large and small users

In this section we modify the example in Section 5. We now assume that traffic is controlled by one large user, user A, with a vehicle fleet of measure N A , and a group of homogeneous small users with a measure N o . For ease of reference, vehicles in user A's fleet are called "large vehicles" and vehicles driven by small users are called "small vehicles".

Large vehicles have the same trip-timing preferences as in Section 5. Their unit costs are denoted by α A , β A , and γ A . Their desired arrival times are uniformly distributed over the interval [t * s , t * e ] with a range of ∆ ≡ t * e -t * s . For future use we define δ ≡ s∆/N A . The existence and nature of PSNE depend on how the trip-timing preferences of small vehicles compare with those of large vehicles. We adopt a specification that allows the preferences to be either the same, or different in a plausible and interesting way. Small vehicles have step preferences with unit costs of α, β, and γ. The cost of late arrival relative to early arrival is assumed to be the same as for large vehicles so that γ/β = γ A /β A . The distribution of desired arrival times is also the same as for large vehicles. 22 Small vehicles and large vehicles are allowed to differ in the values of β/α and β A /α A .

The ratio β A /α A measures the cost of schedule delay relative to queuing time delay for large vehicles. It determines their flexibility with respect to arrival time, and hence their willingness to queue to arrive closer to their desired time. If β A /α A is small, large vehicles are flexible in the sense that they are willing to reschedule trips in order to avoid queuing delay. Conversely, if β A /α A is big, large vehicles are inflexible. Ratio β/α has an analogous interpretation for small vehicles. To economize on writing, we use the composite parameter θ ≡ β A /α A β/α to measure the relative flexibility of the two types. We consider two cases. In Case 1, θ ≤ 1 so that large vehicles are (weakly) more flexible than small vehicles. To fix ideas, small vehicles can be thought of as morning commuters with fixed work hours and relatively rigid schedules. Large vehicles are small trucks or vans that can make deliveries within a broad time window during the day. We show below that for a range of parameter values, a PSNE exists in which large vehicles depart at the beginning and end of the travel period without queuing. Small vehicles queue in the middle of the travel period in the same way as if large vehicles were absent.

In Case 2, θ > 1 so that large vehicles are less flexible than small vehicles. This would be the case if large vehicles are part of a just-in-time supply chain, or have to deliver products to receivers within narrow time windows. 23 We show that for a range of parameter values a PSNE exists in which large vehicles depart simultaneously with small vehicles and encounter queuing delays. The PSNE is identical to the atomistic PSNE in which user A disregards the congestion externalities that its vehicles impose on each other. Cases 1 and 2 are analyzed in the following two subsections.

Case 1: Large vehicles more flexible than small vehicles

In Case 1, large vehicles are more flexible than small vehicles. In the atomistic PSNE, large vehicles depart at the beginning and end of the travel period, and small vehicles travel in the middle. A queue exists throughout the travel period, but it rises and falls more slowly while large vehicles are departing than when small vehicles are departing just before and after the peak. 24 One might expect the same departure order to prevail with self-internalization, but with user A restricting its departure rate to match capacity so that queuing does not occur. The candidate PSNE with this pattern is shown in Figure 3. Large vehicles depart during the intervals (t As , t os ) and (t oe , t Ae ), where t As = t * -23 Another possibility is that large vehicles are commercial aircraft operated by airlines with scheduled service, while small vehicles are private aircraft used mainly for recreational purposes.

24 This departure pattern was studied by [START_REF] Arnott | Schedule delay and departure time decisions with heterogeneous commuters[END_REF] and [START_REF] Arnott | The welfare effects of congestion tolls with heterogeneous commuters[END_REF]. . 25 Small vehicles depart during the central interval (t os , t oe ). The departure schedule for small vehicles and the resulting queue are the same as if user A were absent.

If the candidate departure schedule in Figure 3 is a PSNE, neither small vehicles nor any subset of large vehicles can reduce their travel costs by deviating. The requisite conditions are identified in the two-part assumption:

Assumption 3: (i) θ ≤ 1. (ii) α A ≥ (β A + γ A ) (1 -δ).
The following proposition identifies necessary and sufficient conditions for the pattern in Figure 3 to be a PSNE.

Proposition 2. Let Assumption 3 hold. Then the departure pattern in Figure 3 is a PSNE. The key to the proof of Proposition 2 is to show that user A cannot profitably deviate from the candidate PSNE by rescheduling vehicles departing after t oe to a mass departure at t os . Forcing vehicles into the bottleneck as a mass just as small vehicles are beginning to depart allows user A to reduce the total schedule delay costs incurred by its fleet. Doing so at t os is preferable to later because, with θ ≤ 1, large vehicles have a lesser willingness to queue than small vehicles. Queuing delay is nevertheless unavoidable because vehicles that depart later in the mass have to wait their turn. This trade-off is evident in the

condition α A ≥ (β A + γ A ) (1 -δ).
Moreover, the more dispersed desired arrival times are, the lower the fleet's costs in the candidate PSNE, and hence the less user A stands to gain from rescheduling. If δ > 1, rescheduling vehicles actually increases their schedule delay costs because they arrive too quickly relative to their desired arrival times. Rescheduling then cannot possibly be beneficial. Given the benchmark parameter ratios β:α:γ = 1:2:4,

condition α A ≥ (β A + γ A ) (1 -δ) simplifies to δ ≥ 3/5, or ∆ ≥ (3/5) (N A /s).
In words:

the range of desired arrival times for vehicles in the fleet must be at least 60 percent of the aggregate time required for them to traverse the bottleneck. This condition is plausible, at least for road users.

As noted above, the atomistic PSNE features the same order of departures and arrivals as the internalized PSNE, but with queuing by large vehicles as well as small vehicles. It is easy to show that both large vehicles and small vehicles incur lower travel costs with self-internalization. Thus, self-internalization achieves a Pareto improvement. [START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF] show that a PSNE without queuing exists for a symmetric duopoly and homogeneous users if α ≥ γ. We have effectively replaced one of the duopolists with a continuum of small users. The condition for a PSNE here (with δ = 0) is α A ≥ β A +γ A . This is more stringent than for the duopoly with the same unit costs. Hence, counterintuitively, the mixed market with a large user and small users may not have a PSNE even if a PSNE exists for both the less concentrated atomistic market and the more concentrated duopoly.

While this nonmonotonic variation in behavior is intriguing, it complicates the analysis of equilibrium with large users.

Case 2: Large vehicles less flexible than small vehicles

In Case 2, θ > 1 so that large vehicles are less flexible than small vehicles. Large vehicles prefer to travel in the middle of the travel period to reduce their schedule delay costs. However, queuing will be inevitable because small vehicles prefer the same range of arrival times. To meet the requirements of Theorem 1 for an internalized PSNE with queuing, it is necessary to assume that ∆ > N A /s. Given an additional assumption identified in Assumption 4 below, the internalized PSNE turns out to be identical to the atomistic PSNE. All large vehicles thus travel during a queuing period, and depart at the same time as in the atomistic PSNE.28 Thus, in contrast to Case 1, the large user's incentive to internalize self-congestion has no effect on either its fleet or small users. The candidate departure schedule in Figure 4 is an internalized PSNE if and only if neither small vehicles nor any subset of large vehicles can reduce their travel costs by deviating. The three requisite conditions are identified in Assumption 4:

Assumption 4: (i) θ > 1. (ii) ∆ > N A /s. (iii) N A s < (θ -1) βγ α (β + γ) N A + N o s -∆ . (32)
Using Assumption 4, the internalized PSNE is stated as: Proposition 3. Let Assumption 4 hold. Then the departure pattern in Figure 4 is a PSNE.

Large users depart during the queuing period and all arrive on time. Small vehicles arrive at a complementary rate so that the bottleneck is fully utilized. The aggregate departure rate and queuing time are the same as if all vehicles were small.

Proof: See the Appendix.

The roles of Conditions (i) and (ii) in Assumption 4 were explained above. Condition (iii) assures that user A's fleet is small enough that it prefers to schedule all its vehicles on-time during the queuing period, rather than scheduling some vehicles before queuing begins at t os .29

Conclusions

In this paper we have studied trip-timing decisions by large users in the Vickrey bottleneck model of congestion. We believe that the model is representative of many transportation settings including airlines scheduling flights at airports, rail companies operating on rail networks, and freight shippers using congested roads. We build on previous studies of trip-timing decisions by large users in three ways: (i) we allow for the presence of small users; (ii) we consider general trip-timing preferences; and (iii) we allow for heterogeneity of trip-timing preferences within a large user's fleet as well as between large and small users.

Our paper makes two main contributions. First and foremost, it identifies conditions under which a Nash equilibrium in pure strategies exists in a setting in which large users make trip-timing decisions simultaneously and queue in a dynamic model of congestion with realistic propagation of delays. More specifically, we show that if vehicles in a large user's fleet have sufficiently diverse trip-timing preferences, a PSNE in which the large user queues may exist. We also provide an example in which the conditions for existence of a PSNE become less stringent as the number of large users increases.

Second, we illustrate how self-internalization can affect equilibrium travel costs. In two of the three examples presented, self-internalization reduces costs for all users. In the first example with symmetric large users (Section 5), the cost savings are substantial and can be nearly as large as for a monopolistic user that controls all the traffic. In the second example with one large user and a group of small users, all parties also gain if the large user schedules its fleet during the off-peak period without queuing. However, in the third example in which the large user travels during the peak, the equilibrium is identical to the atomistic PSNE so that no one benefits. The three examples illustrate that the effects of self-internalization depend on both market structure and the trip-timing preferences of users.

The analysis of this paper can be extended in various directions. One is congestion pricing: either in the form of an optimal fine (i.e., continuously time-varying) toll that eliminates queuing, or a more practically feasible step-tolling scheme. Although the gains from self-internalization can be substantial, there is still scope to improve welfare by implementing congestion pricing. Indeed, this is what Verhoef and Silva (2017) find using the Henderson-Chu model for the case of large users with homogenous trip-timing preferences.

A second topic is mergers or other measures to enable users to coordinate their trip-timing decisions gainfully without intervention by an external authority using either tolls or direct traffic control measures. It is not obvious from our preliminary results which users, if any, stand to gain by merging, how a merger would affect other users, and whether there is a case for regulation.

A third extension is to explore more complex market structures and different types of user heterogeneity. Ride-sharing companies or so-called Transportation Network Companies (TNCs) have become a major mode of passenger transportation in some cities and evidence is emerging that they are contributing to an increase in vehicle-km and congestion [START_REF] Clewlow | Disruptive transportation: the adoption, utilization, and impacts of ride-hailing in the united states[END_REF]The New York Times, 2017). In Manhattan, the number of TNCs exceeds the number of taxis. Transportation services are offered by six types of operators in all:

yellow cabs that must be hailed from the street, for-hire vehicles or black cars that must be booked, and four TNC companies: Uber, Lyft, Via, and Juno [START_REF] Schaller | Empty seats, full streets: Fixing manhattan's traffic problem[END_REF]. 30 The firms differ in their operations and fare structures. Their trip-timing preferences are also dictated by those of their customers. The size of a firm's fleet is not fixed, but varies by time of day and day of week according to when drivers choose to be in service. The simple Vickrey model would have to be modified to incorporate these user characteristics.

A fourth topic that we are studying is whether self-internalization by a large user can make other users worse off, or even leave the large user itself worse off. Such a result is of policy interest because it suggests that the welfare gains from congestion pricing of roads, airports and other facilities in which large users operate could be larger than previously thought.

Figure A.5: Candidate PSNE with C A aa < 0 ∂ 2 r (t, a, k) ∂k 2 = C a (C t C akk -C a C tkk ) + 2C ak (C a C tk -C t C ak ) C 3 a ≥ 0, ∂ r (t, a, k) ∂a = s C 2 a (C t C aa -C a C ta ) = s C 2 a C t C aa s = -C aa ,
where s = means identical in sign.

Appendix A.3. Proof of Lemma 2 with C A aa < 0 Consider Figure A.5, which depicts a candidate PSNE similar to that in Figure 1, but with C A aa < 0 so that curve R-A (t) is convex rather than concave. Suppose that user A deviates from the candidate PSNE during the interval (t A , t B ) by dispatching its vehicles earlier so that section ADB of R (t) shifts leftwards to R (t). Vehicle k = RA (t D ) originally scheduled to depart at point D and time t D is rescheduled earlier to point E and time t E such that distance Ey equals distance Dz. Vehicle k experiences a change in costs of

∆C A (k) = C A (t E , t E + q (t E ) , k) -C A (t D , t D + q (t D ) , k) .
Let q (t) denote queuing time along the path from point D to point E shown by the dashed blue curve that runs parallel to R-A (t) between points y and z. The change in cost can be written

∆C A (k) = - t D t=t E C A t (t, t + q (t) , k) + C A a (t, t + q (t) , k) 1 + dq (t) dt dt = - t D t=t E C A t (t, t + q (t) , k) + C A a (t, t + q (t) , k) r A t, t + q (t) , RA (t) s dt = - 1 s t D t=t E C A a (t, t + q (t) , k) r A t, t + q (t) , RA (t) -r A (t, t + q (t) , k) dt.
Since q (t) > q (t) for t ∈ (t A , t B ), with C A aa < 0 and for any j, rA (t, t + q (t) , j) < rA (t, t + q (t) , j). If user A's fleet is homogeneous, the expression in braces is negative, ∆C A (k) < 0, and rescheduling the vehicle from D to E reduces its trip cost.

Appendix A.4. Proof of Theorem 1 (Section 4) Using Eq. ( 1), the term in braces in (31) can be written

Z = RA (t) j=k   ∂ r A (t, t + q (t) , j) ∂j + 1 s ∂ r A t, t + q (t) -j-k s , k ∂a   dj. (A.6)
A sufficient condition for Z to be positive is that the integrand be positive for all values of j. Given Assumption 2, there is a one-to-one monotonic correspondence between j and t * j . The integrand in (A.6), z, can therefore be written

z = ∂ r A (t, t + q (t) , j) ∂t * j 1 f t * j - 1 s ∂ r A t, t + q (t) -j-k s , k ∂t * j . (A.7) Now ∂ r A (t, t + q (t) , j) ∂t * j - ∂ r A t, t + q (t) -j-k s , k ∂t * j = j n=k ∂ 2 r A t, t + q (t) -n-k s , n ∂ (t * n ) 2 1 f (t * n ) + 1 s ∂ 2 r A t, t + q (t) -n-k s , n ∂a∂t * n dn = j n=k ∂ 2 r A t, t + q (t) -n-k s , n ∂ (t * n ) 2 1 f (t * n ) - 1 s dn (A.8)
By (4), the second derivative is positive, and by assumption, f (t * n ) ≤ s for all t * n . Hence (A.8) is positive. Using this result in (A.7) we have

z ≥ ∂ r A t, t + q (t) -j-k s , k ∂t * j   1 f t * j - 1 s   > 0.
This establishes that Z > 0 in (A.6), and hence that ∆C A (k) > 0.

s (t q -t s ) + m m -1 α α -β s t -t q = s (t * -t s ) . (A.12)
Eq. (A.9) stipulates that all vehicles complete their trips. Eq. (A.10) states that the first and last vehicles incur the same private cost. Eq. (A.11) stipulates that cumulative departures equal N . Finally, according to eq. (A.12) total departures from t s to t equals the number of vehicles that arrive early.

Solving (A.9)-(A.12), it is possible to show after considerable algebra that total costs in the candidate PSNE are

T C i = (m -1) (2m -1) βγ + mαγ -(m -1) αβ 2mγ (α + (m -1) β) βγ β + γ N 2 s .
Total costs in the atomistic PSNE are

T C n = βγ β + γ N 2 s .
When vehicles differ in their desired arrival times, schedule delay costs are reduced by the same amount in the two PSNE. The departure rate is unchanged in the candidate PSNE with internalization. The difference in total costs is thus the same with and without heterogeneity so that, as stated in the text

T C n -T C i = (m -1) β (α + γ) + mαγ 2m (m -1) βγ + 2mαγ βγ β + γ N 2 s . Appendix A.5.3. Proof of Proposition 2
It is necessary to show that neither user A nor a small user can gain by deviating from the candidate PSNE. In all, seven types of deviations need to be considered-Deviation 1. A small user cannot gain by deviating.

Small users incur the same cost throughout the candidate departure interval (t os , t oe ).

Hence, they cannot gain by retiming their trips within this interval. Rescheduling a trip either before t os or after t oe would clearly increase their cost. Thus, no small user can benefit by deviating. During the no-queuing period, the bottleneck is used to capacity. It is therefore necessary to distinguish between the cost that user A saves by removing a vehicle from the departure schedule (which does not affect the costs of other vehicles in the fleet) and the cost user A incurs by adding a vehicle (which creates a queue unless the vehicle is added at t Ae ). The respective costs are 33 :

C - A (t) = β A • (t * -t) , t ∈ [t As , t os ] γ A • (t -t * ) , t ∈ [t oe , t Ae ] , C + A (t) =        β A • (t * -t) + α A -β A s • tos t r A (u) du + α A +γ A s • t Ae toe r A (u) du, t ∈ [t As , t oe ] γ A • (t -t * ) + α A +γ A s • t Ae t r A (u)
∆C A = -C - A (t) + C + A t = -γ A • t -t + α A + γ A s • t t r A (u) du = -γ A • t -t + α A + γ A s • s t -t = α A t -t > 0.
Since fleet costs increase, the deviation is not gainful.

(ii). Rescheduling late to early: The best time to reschedule a vehicle is t os because this minimizes the vehicle's early-arrival cost as well as the queuing delay imposed on the rest of the fleet. But rescheduling the vehicle to t os is no better (or worse) than rescheduling it to t oe , which 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 As . However, the gain is the same as (or worse than) from rescheduling a vehicle from t Ae , 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 As to t os . Again, this is not beneficial for the same reason as in case (iii).

Deviation 4. User A cannot gain by rescheduling a single vehicle to a time within the queuing period, (t os , t oe ).

For any vehicle in user A's fleet that is scheduled to depart early at t, there is another vehicle scheduled to depart late at t that incurs the same cost (this follows from symmetry of the t * A distribution). Removing either vehicle saves the same cost: C - A (t) = C - A (t ). However, removing the early vehicle and inserting it at any time during the queuing period creates a (small) queue that persists until t Ae . Removing the late vehicle creates a queue only until t because the queue disappears during the departure-time slot opened up by the rescheduled vehicle. Rescheduling a late vehicle is therefore preferred. The best choice is to reschedule the first late-arriving vehicle at t oe so that no later vehicles in the fleet are delayed. Rescheduling a vehicle from t > t oe would reduce that vehicle's cost by more, but a queue would persist from t oe until t . The fleet's schedule delay costs would therefore not be reduced, and a greater queuing cost would be incurred as well.

Given θ ≤ 1, rescheduling a vehicle from t oe to any time t ∈ (t os , t oe ) will (weakly) increase its cost. So rescheduling it not gainful. But if θ > 1, the vehicle will benefit.

Hence the candidate can be a PSNE only if θ ≤ 1 as per Proposition 2. Deviation 5. User A cannot gain by rescheduling a positive measure of its fleet (i.e., a mass of vehicles) to times within the departure period when there is no queue.

If user A reschedules a positive measure of vehicles to depart during (t As , t os )∪(t oe , t Ae ), queuing will occur during some nondegenerate time interval. By Lemma 1, user A is willing to depart at a positive and finite rate during early arrivals only if r -A (t) = rA = α A • s/ (α A -β A ) > 0. Since no other users depart at t, r -A (t) = 0 and user A is better off scheduling vehicles later. Similarly, for late arrivals user A is willing to depart at a positive and finite rate only if r -A (t) = α A • s/ (α A + γ A ). Since r -A (t) = 0, user A is again better off scheduling vehicles later. Deviation 6. Any deviation by user A involving multiple mass departures is dominated by a deviation with a single mass departure. Suppose that user A deviates from the candidate PSNE by scheduling multiple mass departures. All vehicles in the fleet are assumed to depart in order of their index, including vehicles within the same mass. (This assures that fleet costs in the deviation cannot be reduced by reordering vehicles.) We show that such a deviation is dominated by a single mass departure. The proof involves establishing three results: (i) Fleet costs can be reduced by rescheduling any vehicles that are not part of a mass, but suffer queuing delay, to a period without queuing. (ii) Fleet costs can be 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 higher fleet costs than a deviation with a single mass departure at t os . These three results show that the candidate PSNE need only be tested against a single mass departure launched at t os .

Result (i): When a queue exists, user A is willing to depart at a positive and finite rate only if condition (21) is satisfied; i.e. r -A (t) = rA (t). For any vehicle that arrives early this requires r -A (t) = rAE = α • s/ (α -θβ) > 0, and for any vehicle that arrives late, r -A (t) = rAL = α • s/ (α + θγ) > 0. During the departure period (t As , t os ), r -A (t) = 0, so user A is better off scheduling all vehicles in the mass later. During the departure period t os , t , r -A (t) = α • s/ (α -β). Since θ ≤ 1, r -A (t) ≥ rAE > rAL and user A is (weakly) better off scheduling all vehicles in the mass earlier. During the departure period t, t oe , , r -A (t) = α • s/ (α + γ) ≤ rAL < rAE . User A is (weakly) better off scheduling all vehicles later. Finally, during the departure period (t oe , t Ae , ), r -A (t) = 0 and user A is again better off scheduling vehicles later.

Result (ii): Assume that user A launches the last mass departure after t. We show that user A can reduce its fleet costs by rescheduling vehicles in the mass to a later period in which they avoid queuing delay. This is true whether or not each vehicle in the mass is destined to arrive early or late relative to its individual t * . By induction, it follows that all mass departures launched after t can be gainfully rescheduled. In what follows it is convenient to use the auxiliary variable λ -A t,t ≡ t t r -A (u) du/ (s • (t -t )) which denotes average departures of small users as a fraction of capacity during the period [t , t].

Suppose user A launches the last mass departure at time t L with M vehicles. Assume first that at t L there is a queue with queuing time q (t L ). We show that postponing the mass departure to a later time when a queue still exists reduces user A's fleet costs. By induction, it follows that postponing the mass until the queue disappears is gainful. Let j be the vehicle that departs in position m of the mass, m ∈ [0, M ]. Let D j [•] be the schedule delay cost function of vehicle j, and c (j, t) its trip cost if the mass departs at time t.

If the mass departs at time

t L , vehicle j incurs a cost of c (j, t L ) = α • q (t L ) + m s + D j t L + q (t L ) + m s . (A.13)
If the mass departure is postponed to time t L > t L , and a queue still exists at t L , vehicle j incurs a cost of .14) By Result (i), user A does not depart during (t L , t L ) because a queue persists during this period. Hence .15) Substituting (A.15) into (A.14), and using (A.13), one obtains

c j, t L = α • q t L + m s + D j t L + q t L + m s . ( A
q t L = q (t L ) + t L t L r -A (u) -s s du = q (t L ) -t L -t L 1 -λ -A t L ,t L . ( A
c j, t L -c (j, t L ) = -α • 1 -λ -A t L ,t L t L -t L (A.16) +D j t L + q (t L ) + m s + λ -A t L ,t L t L -t L -D j t L + q (t L ) + m s .
The value of λ

) so that λ -A t L ,t L = α α+γ . If t L > t oe , λ -A t L ,t L < α α+γ . Hence, λ -A t L ,t L ≤ α
α+γ for all values of t L and the first line of (A.16) is negative. For the second line there are three possibilities to consider according to when vehicle j arrives:

(a) early both before and after the mass is postponed, (b) early before postponement and late after, and (c) late both before and after postponement. In case (a), the second line of (A.16) is negative, in case (c) it is positive, and in case (b) the sign is a priori ambiguous.

To show that (A.16) is negative it suffices to show this for case (c). The second line is an

increasing function of λ -A t L ,t L . Using λ -A t L ,t L ≤ α α+γ and D j [x] = γx for x > 0, (A.16) yields c j, t L -c (j, t L ) ≤ -α • γ α + γ t L -t L + θγ • α α + γ t L -t L < 0.
This proves that postponing the mass departure (weakly) reduces the cost for every vehicle in the mass. We conclude that if there is a queue when the last mass departs, user A can (weakly) reduce its fleet costs by postponing the mass departure to the time when the queue just disappears (user A's later vehicles are not affected by postponing the mass). To see this, let j be the index of the vehicle that departs in position m in the mass. In the mass departure, vehicle j incurs a cost of

c (j, t L ) = D j t L + m s + α • m s .
In the deviation where vehicle j delays departure until t

L = t L + m/s, it incurs a cost of c j, t L = D j t L + m s .
Its cost changes by The remaining vehicles in the first mass also incur lower queuing costs since they no longer queue between t E and t E . Vehicles in the second 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.

c j, t L -c (j, t L ) = -α • m s < 0.
Case 2 : t E < t os < t E . The second mass is scheduled after small users start to depart.

If the queue from the first mass disappears before t os , the reasoning for Case 1 applies.

If the queue from the first mass does not disappear before t os , the queue will not dissipate until after small users have stopped departing at t oe . However, user A can still reduce its fleet costs by rescheduling some of the M vehicles in the first mass to t os , and rescheduling the remainder to the head of the second mass at t E .

Case 3 : t os ≤ t E < t E . The first mass departs when, or after, small users begin to depart.

In this case, user A can reduce its fleet costs by rescheduling the second mass to depart immediately after the first mass. To show this, let q (t), t ≥ t E , denote queuing time after the first mass of M vehicles departs. Let j be the index of the vehicle that departs in position m of the second mass, where m ∈ [0, M ]. Vehicle j arrives at time a j = t E + q (t E ) + m/s and incurs a cost of c j, t E = α q t E + m s + D j a j .

If the second mass is instead dispatched immediately after the first mass at t E , vehicle j arrives at time a j = t E + q (t E ) + m/s and incurs a cost of c (j, t E ) = α q (t E ) + m s + D j [a j ] .

The cost saving is c j, t E -c (j, t E ) = α q t E -q (t E ) + D j a j -D j [a j ] .

(A.17) Now a j = a j + t E -t E + q t E -q (t E ) , (A.18) and (A.20) where ∆q -A ≡ α α-β (t E -t E ) is the gross contribution of small users to queuing time during the period (t E , t E ). The weak inequality in (A.20) holds as an equality if vehicle j arrives early when the second mass departs at t E . The inequality is strict if vehicle j arrives late.

q t E -q (t E ) = β α -β t E -
Since this conclusion holds for all vehicles in the second mass, user A can reduce its costs by merging the later mass with the earlier mass.

By induction, all but one of any mass departures launched before t can be eliminated in a way that decreases user A's fleet costs. Using similar logic, it is straightforward to show that user A can do no better than to schedule the single mass at t os rather than later. In summary, results (i)-(iii) show that, of all deviations from the candidate PSNE entailing mass departures, a deviation with a single mass departure launched at t os is the most viable. Deviation 7. User A cannot gain by rescheduling a positive measure of its fleet to times during the queuing period (t os , t oe ) .

To prove that Deviation 7 is not gainful, we must determine whether total fleet costs can be reduced by deviating from the candidate PSNE. Since user A has weaker preferences for on-time arrival than small users, user A prefers not to schedule departures in the interior of (t os , t oe ). User A's best deviation is to schedule a mass departure at t os . Let N Am be the measure of vehicles in the mass. If N Am is small, the best choice is to reschedule the first vehicles departing late during the interval (t oe , t oe + N Am /s). (As explained in proving that Deviation 4 is not beneficial, this strategy avoids queuing delay for large vehicles that are not part of the mass.) The first of the rescheduled vehicles has a preferred arrival time of t * . In the candidate PSNE, this vehicle incurs a cost The deviation is unprofitable if T C d dev ≥ T C c dev ; that is, if .28) When condition (A.28) is met, user A cannot profit by rescheduling some vehicles from the early-departure interval (t As , t os ) in addition to all large vehicles from the late-departure interval (t oe , t Ae ). To see why, note that the net benefit from rescheduling the vehicle at t As is the same as the net benefit from rescheduling the vehicle at t Ae . The benefit from rescheduling vehicles after t os is lower.

C A t
α A ≥ (β A + γ A ) (1 -δ) . (A
Appendix A.5.4. Proof of Proposition 3

The aggregate departure rate is given by Eq. ( 5) The last large vehicle imposes no delay on others in the fleet, whereas the first large vehicle imposes a delay of 1/s on all the others. The first vehicle can be rescheduled to just before the travel period at a lower cost than the other vehicles. Thus, if deviation from the candidate PSNE is profitable, it must be profitable to reschedule the vehicle departing at t As to t os . It is straightforward to show that user A can retime departures of the remaining large vehicles so that they continue to arrive on time and incur no schedule delay cost. The net gain to the other large vehicles is therefore α A N A /s. The first vehicle incurs a cost of (A.29) in the candidate PSNE, and a cost of (β A β/α) (t * s -t os ) if it rescheduled. The net change in costs for the fleet is

r (t
∆T C A = β A -α A β α γ β + γ N A + N o s -∆ -α A N A s = (θ -1) α A βγ α (β + γ) N A + N o s -∆ -α A N A s .
Deviation is not profitable if this difference is positive, which is assured by condition (32).

  depicts a candidate PSNE on the assumption that C A aa > 0. (The case C A aa < 0 is considered below.) Cumulative departures of other users, R-A (t), are shown by the blue curve passing through points y and z. Cumulative total departures, R (t), are shown by the black curve passing through points A, D and B.

Figure 1 :

 1 Figure 1: Candidate PSNE with C A aa > 0

Figure 2 :

 2 Figure 2: PSNE with two large users

Figure 3 :

 3 Figure 3: PSNE in which large user does not queue (Case 1)

Figure 4 :

 4 Figure 4: PSNE in which large user does not queue (Case 2).

  of the rescheduled vehicles is the unweighted mean of eqs. (A.24) and (A.25). Total costs for the rescheduled vehicles are therefore T C d dev = β A t * -t os + α A -β A (1denotes the deviation. Given (A.23) and (A.26), the change in total costs is T C d dev -T C c dev = [α A -(β A + γ A ) (1 -

  Henderson-Chu model. First, vehicles departing at any given time never interact with vehicles departing at other times. 8 Second, compared to the bottleneck model discussed below, the Henderson-Chu model is less analytically tractable, and for most functional forms it can only be solved numerically. The second paper to adopt Nash equilibrium, by Silva et al. (2017), uses the Vickrey (1969) bottleneck model in which congestion takes the form of queuing behind a bottleneck with a fixed flow capacity. Silva et al. consider two large users controlling identical vehicles with linear trip-timing preferences. In contrast to Verhoef and Silva (2017), Silva et al.

find that under plausible parameter assumptions a PSNE in departure times does not exist. They also prove that a PSNE never exists in which large users queue. These results readily generalize to oligopolistic markets with more than two large users.

Silva et al. also

show that more than one PSNE may exist in which no queuing occurs, and that ex ante identical users can incur substantially different equilibrium costs. These results are disturbing given the fundamental importance of existence and uniqueness of equilibrium for equilibrium models. The unease is heightened by the facts that the bottleneck model is widely used, and that when all users are small a unique PSNE with a deterministic and finite departure rate exists under relatively unrestrictive assumptions. 9

8 In essence, this means that every infinitesimal cohort of vehicles travels independently of other cohorts and is unaffected by the volume of traffic that has departed earlier -contrary to what is observed in practice. The Henderson-Chu model is a special case of the Lighthill-Whitham-Richards hydrodynamic model in which shock waves travel at the same speed as vehicles and therefore never influence other vehicles (see

  Theorem 1. Consider large user A with a heterogeneous vehicle fleet that satisfies Assumption 2. If the density of desired arrival times in user A's fleet never exceeds bottleneck capacity (i.e., f (t * k

according to a density function f (t * k ) over a range [t * s , t * e ]. The following result is proved in the Appendix:

  over the interval [t * s , t * e ] where ∆ ≡ t * e -t * s . It can be shown that introducing heterogeneity in this way does not upset the proof in Silva et al. (2017) that a PSNE without queuing does not exist. However, a PSNE with queuing does exist if the conditions of Theorem 1 are met. Both conditions of Assumption 2 are satisfied. The remaining condition, f (t * candidate PSNE with queuing is shown in Figure 2. 21 The cumulative distribution of desired arrival times for users A and B together is shown by the straight line W with

	The domain [t * s , t * e

k ) ≤ s, is also met if N/ (2∆) ≤ s, or ∆ ≥ N/ (2s).

Table 1 :

 1 Proportional cost saving from internalization as a function of m

22

  Within limits, this assumption can be relaxed. Suppose that t * is uniformly distributed over the interval [t * so , t * eo ] . The existence and nature of PSNE with self-internalization are unaffected if two conditions are satisfied. First, t

	β β+γ t * so + γ β+γ t * eo = β β+γ t * s + γ β+γ t *

* eo -t * so ≤ No/s. This condition assures that small vehicles queue in the PSNE. Second, e . This condition assures that small vehicles and large vehicles adopt the same queuing pattern in the atomistic PSNE.

  Given this assumption, the atomistic PSNE is as shown in Figure 4. Large vehicles depart during the interval (t As , t Ae ) and arrive at rate N A /∆ over the interval [t * s , t * e ]. Each large vehicle arrives on time. Small vehicles arrive at rate s -N A /∆ during this interval, and at rate s during the rest of the interval [t os , t oe ]. The aggregate departure rate and queuing time are the same as if all vehicles were small. 27

  Deviation 2. User A cannot gain by rescheduling vehicles outside the departure period (t As , t Ae ). User A does not queue in the candidate PSNE. Large vehicles therefore do not delay each other. Moreover, the highest costs are borne by the first and last vehicles departing at t As and t Ae , respectively. Rescheduling any vehicles either before t As or after t Ae would increase user A's fleet cost. Deviation 3. User A cannot gain by rescheduling a single vehicle to another time within the departure period when there is no queue; i.e. to any time t ∈ (t As , t os ) ∪ (t oe , t Ae ). 32 32 Much of the following text is drawn, verbatim, from Silva et al. (2017).

  du, t ∈ [t oe , t Ae ] 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 in the fleet do not benefit. Suppose a vehicle is rescheduled earlier from t to t where t oe ≤ t < t. User A's fleet costs change by an amount:

	.
	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).

  -A t L ,t L depends on the timing of t L and t L . If t L ≤ t oe , small users depart at rate α α+γ • s throughout the interval (t L , t L

  Every vehicle enjoys a reduction in queuing time cost with no change in schedule delay cost. Hence, in any deviation from the candidate PSNE, fleet costs can be reduced by eliminating the last mass departure. By induction, any mass departure launched after t can be rescheduled without increasing fleet costs.Next, we show that any deviation entailing multiple mass departures before t is dominated by scheduling a single mass departure at t os . 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 with M vehicles. There are three cases to consider depending on the timing of t E and t E . Case 1 : t E < t E ≤ t os . Both masses are scheduled before small users start to depart. Since r -A (t) = 0 for t < t E , by Result (i), there is no queue at t E . If the queue from the first mass disappears before t E , as in the proof of Result (ii), user A can reduce its fleet costs simply by rescheduling vehicles in the first mass to depart at a rate of s during

	Result (iii):

t ∈ (t E , t E ). Since user A does not depart in the original deviation until the first queue has dissipated, the rescheduled vehicles in the alternative deviation avoid queuing and arrive at the same time -thereby reducing their queuing delay costs without affecting their 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 ) vehicles at a rate s during (t E , t E ), and letting the remaining M -s • (t E -t E ) vehicles join the head of the second mass at t E . The first set of vehicles in the first mass avoids queuing and incur the same schedule delay costs.

  oe , t oe , t * = γ A t oe -t * .(A.21) The last of the rescheduled vehicles has a preferred arrival time of t * + δN Am /s. It incursThe average cost of the rescheduled vehicles is the unweighted mean of eqs. (A.21) and(A.22). Total costs for the N Am vehicles before they are displaced are thereforeT C c dev = γ A t oe -t * + γ A (1 -δ) N Am 2s N Am , (A.23)where superscript c denotes the candidate PSNE.The first of the rescheduled vehicles departs at t os and incurs a costC A t os , t os , t * = β A t * -t os . (A.24)The last of the rescheduled vehicles incurs a cost of C A t os , t os + N

	a cost
	C A t oe +	N Am s	, t oe +	N Am s	, t * +	δ s	N Am = γ A t oe -t * + (1 -δ)	N Am s	.	(A.22)
							Am s	, t * + δ	N Am s
			= β A	t * + δ	N Am s	-(t os +	N Am s	) + α A	N Am s
			= β A	t * -t os + δ	N Am s	+ (α

A -β A ) N Am

  Clearly, user A cannot reduce the cost for any single vehicle in its fleet by rescheduling it to another time. It is necessary to check that user A cannot reduce its fleet cost by rescheduling a positive measure of vehicles. The first and last large vehicles to depart incur the same travel cost of C A (t * s

		) =			α α-β s for t os < t < α α+γ s for t < t < t oe t	.
	Large vehicles depart at rate
	r A (t) =	          		0 α-β α N A ∆ for t As < t < for t < t As α α+γ N A ∆ for t < t < t Ae t 0 for t > t Ae .
	Critical travel times are	t os = t * -	γ β + γ	N A + N o s	,
	t As = t * s -	βγ α (β + γ)	N A + N o s	-∆ ,
		t = t * -	βγ α (β + γ)	N A + N o s	,
		t * =	β β + γ	t * s +	γ β + γ	t * e ,
	t Ae = t * e -	βγ α (β + γ)	N A + N o s	-∆ ,
		t oe = t * +	β β + γ	N A + N o s	.

The nonnegativity constraint on queuing time, q (t) ≥ 0, is guaranteed by (7).

The optimality conditions with no queue, which involve multiple cases, are not very instructive.

See Leonard and Long (1992, Chapter 8).

If vehicles are homogeneous, the order of departure does not matter. The assumption that they depart in the same order is useful for accounting purposes.

Figure2is a variant of Figure2in[START_REF] Silva | On the existence and uniqueness of equilibrium in the bottleneck model with atomic users[END_REF]. The main difference is that desired arrival times have a nondegenerate distribution rather than being the same for all vehicles.

Recall that γA/βA = γ/β.

In the candidate PSNE, large vehicles travel in the tails of the departure period. In the system optimum there is no queuing, and the optimal order of departure depends on the ranking of βA and β. If βA < β, large vehicles still travel in the tails, but if βA > β they would travel in the middle. Hence the PSNE may be inefficient not only because queuing occurs, but also because total schedule delay costs are excessive.

[START_REF] Newell | The morning commute for nonidentical travelers[END_REF] analyzed a more general version of this arrival pattern in the bottleneck model with small users. See also[START_REF] De Palma | Comparison of morning and evening commutes in the vickrey bottleneck model[END_REF].

Recall Condition (30) which requires that in a PSNE with queuing, all large users have lower atomistic rates than the small users. This condition is satisfied in Case 2 because each large vehicle has a lower atomistic rate than small users after its preferred arrival time.

In the candidate PSNE, large vehicles arrive at their individually preferred arrival times because they are less flexible than small vehicles. In the system optimum there is no queuing and, as in Case 1, the optimal order of departure depends on the ranking of βA and β. If βA > β, large vehicles would still be scheduled at their individually preferred arrival times, but if βA < β they would travel in the tails.

In addition, in 2013 Street Hail Liveries or green taxies began providing service in Northern Manhattan, theBronx, Brooklyn, Queens, and Staten Island (Taxi and Limousine Commission, 2016).

The world's top 5 terminal operators. December 4, https://www.porttechnology.org/news/the worlds top 5 terminal operators.

The New York Times (2017). Your uber car creates congestion. should you pay a fee to ride? December 26 (by Winnie Hu), https://www.nytimes.com/2017/12/26/nyregion/ubercar-congestion-pricing-nyc.html?smid tw-nytimes&smtypcur.

This formulation of scheduling preferences is due toVickrey (1969Vickrey ( , 1973) ) and has been used in several studies since; see de[START_REF] De Palma | Dynamic traffic modeling[END_REF]. Defining preferences in terms of utility is appropriate for commuting and certain other types of trips. For trips involving freight transport, the utility function can be interpreted as profit or some other form of payoff or performance metric.

i (t) can be derived by integrating (12) and applying transversality condition (14).

$ This research was partially funded by FONDECYT project No 11160294, the Complex Engineering Systems Institute (CONICYT -PIA -FB0816) and the Social Sciences and Humanities Research Council of Canada (Grant 435-2014(Grant 435- -2050)).

Tseng, Y., Ubbels, B., and Verhoef, E. (2005). Value of time, schedule delay, and reliabilityestimation results of a stated choice experiment among dutch commuters facing congestion. In Department of Spatial Economics, Free University of Amsterdam. (1973). Pricing, metering, and efficiently using urban transportation facilities. Highway Research Record, 476:36-48. Weisbrod, G. and Fitzroy, S. (2011). Traffic congestion effects on supply chains: Accounting for behavioral elements in planning and economic impact models. In Renko, S., editor, Supply Chain Management-New Perspectives. INTECH Open Access Publisher.

where t h and t w are such that all trips take place within the interval [t h , t w ]. Function u h (•) > 0 denotes the flow of utility at the origin (e.g., home), and function u w (•) > 0 denotes utility at the destination (e.g., work). It is assumed that u h (•) and u w (•) are continuously differentiable almost everywhere with derivatives u h ≤ 0 and u w ≥ 0, and

) for some time t * . Utility from time spent traveling is normalized to zero.

The cost of a trip is the difference between actual utility and utility from an idealized instantaneous trip at time t

Various specification are possible for the flow-of-utility functions. Vickrey (1969) adopted a piecewise constant form:

where u h > 0, 0 < u E w < u h , and u L w > u h . The cost function corresponding to (A.2) is:

where α = u h , β = u h -u E w , and γ = u L w -u h . Another specification adopted by [START_REF] Fosgerau | The value of travel time variance[END_REF], and called the "slope" model by [START_REF] Börjesson | Valuations of travel time variability in scheduling versus mean-variance models[END_REF], features linear flow-of-utility functions:

Preferred travel time is t * = u ho -uwo u h1 +u w1 , and the cost function is

where α = u ho -u h1 t * . To assure that the model is well-behaved, departure and arrival times are restricted to values such that u h (t) > 0 and u w (a) > 0.

A third specification -used in early studies by Vickrey (1973), [START_REF] Fargier | Effects of the choice of departure time on road traffic congestion: theoretical approach[END_REF], and [START_REF] Hendrickson | Characteristics of travel time and dynamic user equilibrium for travel-to-work[END_REF] -is a variant of (A.4) with u h1 = 0:

In (A.5), utility at the origin is constant and schedule delay costs depend on arrival time but not departure time. Cost functions (A.3), (A.4), and (A.5) all satisfy Assumption 1 in the text (with t * in place of k).

Appendix A.2. Atomistic departure rates (Section 2)

The atomistic rate for a user of type k is given by Eq. (3):

Derivatives of specific interest are (with arguments suppressed to economize on notation)

Vehicle k departs at time

and arrives at time

As shown by Silva et al. (2017, Eq. (24c)),

If user A deviates from the candidate PSNE so that vehicle k departs at t rather than t k , vehicle k arrives at

Vehicle k can benefit from deviation only if a k < t * k : a condition which reduces to ∆ < N A /s. Deviation is not profitable if ∆ > N A /s, or equivalently f = N A /∆ < s as per Theorem 1.

Appendix A.5.2. Gain from internalization with m users With m large users the aggregate equilibrium departure rate in the candidate PSNE during the period of queuing is given by eq. ( 23):

When all vehicles have the same desired arrival time, t * , the critical times t s , t q , t, and t e are determined by the following four equations: t e -t s = N/s, (A.9) β (t * -t s ) = γ (t e -t * ) , (A.10) (A.11)