key: cord-0552548-c5dyuplj authors: Castro, Francisco; Ma, Hongyao; Nazerzadeh, Hamid; Yan, Chiwei title: Randomized FIFO Mechanisms date: 2021-11-21 journal: nan DOI: nan sha: 5bac30977b1a6c9985c2c96b5c8ff8afbd741fba doc_id: 552548 cord_uid: c5dyuplj We study the matching of jobs to workers in a queue, e.g. a ridesharing platform dispatching drivers to pick up riders at an airport. Under FIFO dispatching, the heterogeneity in trip earnings incentivizes drivers to cherry-pick, increasing riders' waiting time for a match and resulting in a loss of efficiency and reliability. We first present the direct FIFO mechanism, which offers lower-earning trips to drivers further down the queue. The option to skip the rest of the line incentivizes drivers to accept all dispatches, but the mechanism would be considered unfair since drivers closer to the head of the queue may have lower priority for trips to certain destinations. To avoid the use of unfair dispatch rules, we introduce a family of randomized FIFO mechanisms, which send declined trips gradually down the queue in a randomized manner. We prove that a randomized FIFO mechanism achieves the first best throughput and the second best revenue in equilibrium. Extensive counterfactual simulations using data from the City of Chicago demonstrate substantial improvements of revenue and throughput, highlighting the effectiveness of using waiting times to align incentives and reduce the variability in driver earnings. Matching marketplaces play an instrumental role in economic exchanges and the allocation of public and private resources. Over the past decade, the rise of online platforms connecting people with gig workers has also radically changed many aspects of our daily lives. To improve efficiency and reduce waiting times, platforms often aim to match rider or grocery delivery trips with the closest available drivers. When requests are concentrated in space, however, matching by proximity has unintended consequences. As an example, Amazon drivers have been reportedly hanging their smartphones in trees near Amazon delivery stations and Whole Foods stores, in order to appear even closer and gain higher priority for job offers. 1 A similar problem existed for Uber and Lyft at airports and event venues. 2 Matching riders to the closest drivers incentivizes drivers to get as close to the terminal or venue as possible, leading to traffic congestion. 3 Many ridesharing platforms now maintain virtual queues at airports for drivers who are waiting in designated areas, and dispatch drivers from the queue in a first-in-first-out (FIFO) manner. 4 This resolves the congestion issues and is also considered more fair by many since drivers who have waited the longest in the queue are now the first in line to receive trip offers. At major U.S. airports, however, a driver at the head of the queue will receive the next trip offer in a few seconds under FIFO dispatching, if she declines an offer from the platform (see Figure 12 ). As we shall see, this lowered cost of cherry-picking substantially exacerbates existing problems on incentive alignment. Figure 1 shows the average trip fare by destination Census Tract in Chicago, for trips originating from the O'Hare and Midway airports. A short trip from O'Hare to a nearby area pays an average of $10-$20, but a long trip can pay an average of $60. During busy hours, instead of accepting an average trip, drivers who are close to the head of the queue are better off declining most trip offers and waiting for only the highest earning trips. Riders, however, have finite patience, despite being willing to wait for some time for a match. When each driver decline takes an average of 10 seconds, 2 minutes had passed after a trip with low or moderate earnings (e.g. trips to downtown Chicago) was offered to and declined by the top 12 drivers in the queue. 5 At this point, it is very likely that the rider cancels her trip request, not knowing when a driver will be assigned, if at all. What we have seen is that in the presence of heterogeneous earnings and finite rider patience, trips with moderate or low earnings never reach drivers in the queue who are willing to accept them. This undercuts the platforms' mission of providing reliable transportation for riders, and leads to low revenue and trip throughput for the platform. Moreover, fulfilling only the small number of high earning trips is also a poor outcome for the drivers, since many drivers who just dropped off a rider at the airport will have to relocate back to the city with an empty car, and those who do join the queue would need to wait for a very long time for a ride. Simple fixes by limiting dispatching transparency or drivers' flexibility are not desirable-in recent years, ridesharing platforms are moving towards sharing trip destination and earnings estimation upfront, as well as providing drivers the options to accept or decline any trips without penalties. 6 Hiding information or imposing penalties are not fully effective either. For example, experienced drivers often call riders to ask about trip details when destinations are hidden before the pick-up [Cook et al., 2018] . Forcing drivers to accept every dispatch improves reliability in the short run, but also imposes a lottery (with possible outcomes ranging from $9 to over $60) on drivers who might have waited for two hours in line. Such high variance in earnings discourages future engagement, and leads to drivers' churning from the platform in the long run. Recognizing the inefficiencies under FIFO dispatching, alternative mechanisms have been studied extensively in the literature. In particular, last-in-first-out (LIFO) dispatching is shown to be optimal in the presence of waiting costs, with or without heterogeneous rewards [Hassin, 1985, Su and Zenios, 2004] . Intuitively, participants' losing (instead of gaining) priority over time substantially reduces the incentive to "wait for a better offer". However, LIFO dispatching is perceived as "blatantly unfair" by many Zenios, 2004, Breinbjerg et al., 2016] . Moreover, as discussed by Hassin [1985] and Su and Zenios [2004] , LIFO dispatching is easy to manipulate since participants may rejoin the queue at the end to (re)gain priority. This renders LIFO unsuitable and ineffective for ridesharing platforms, as drivers have the option to go offline and online again to rejoin the end of the virtual queue at any time. Ideally, platforms may properly price trips by destination and eliminate drivers' incentives to cherry-pick. In recent work, Ma et al. [2019] propose the spatio-temporal pricing mechanism, which is welfare optimal, incentive aligned, and guarantees that drivers at the same origin are indifferent towards trips to all destinations. This remains an idealized target for our current setting, but is hard to achieve in practice. Consider, again, the O'Hare example as shown in Figure 1a . Tripling the fares of the short trips to match the earnings from the long trips is suboptimal. On the other hand, the platform is unable to decrease driver payouts below some pre-determined per-minute and per-mile rates, thus earnings from long trips cannot be effectively reduced either. We study the dispatch of trips to drivers who are waiting in a virtual queue, where some trips are necessarily more lucrative than the others due to operational constraints. Without the power to adjust trip prices, the mechanisms we design use drivers' waiting times in the queue to align incentives, improve reliability and efficiency, and reduce the variability in drivers' total payoffs. The model. We study a continuous time, non-atomic model, with one origin (e.g. the airport) and stationary arrival rates of riders and drivers. Riders request trips to a number of destinations with heterogeneous earnings for drivers. Upon the arrival of each rider, or after a rider's trip request is declined, the platform offers the rider's trip to a driver in the queue. Riders are willing to wait for some time for a match, but have finite patience and will cancel their requests after a certain number of declines from drivers. Drivers' waiting in the queue (as opposed to driving elsewhere in the city, for example) is costly for both the drivers and the platform. Drivers are strategic, aiming to optimize their total payoff, i.e. the earnings from trips minus the waiting costs they incur. We study mechanisms that are fully transparent and flexible (see Footnote 6). At any point in time, drivers know about the supply, demand, the length of the queue and their positions in their queue. When offered trip requests, drivers are provided trip destinations and earnings upfront so that they can decide whether to accept based on this information. Moreover, drivers are not penalized for any actions they take, and have the flexibility to (i) decline any number of trip dispatches without losing their positions in the queue, (ii) rejoin the virtual queue at the tail at any point of time, and (iii) decide to not join the queue upon arrival, or leave the queue at any point of time to perhaps relocate back to the city without a rider. Main results. To optimize trip throughput and the platform's net revenue (i.e. total earnings from completed trips, minus the opportunity costs the platform incurs due to drivers' waiting in the queue), the first best outcome has no driver in the queue, and dispatches all drivers upon arrival to destinations in decreasing order of earnings. However, under the status quo strict FIFO dispatching where trips are dispatched to each and every driver starting from the head of the queue, drivers close to the head of the queue are incentivized to cherry-pick and wait for higher-earning trips. We analyze the equilibrium outcome under strict FIFO and show that with finite rider patience, most trips except for the highest earning ones become unfulfilled. Drivers' excessive waiting in the queue further reduces drivers' total payoffs as well as the net revenue of the platform. Recognizing that the moderate and low earning trips never reach drivers in the queue who are willing to accept them, we first present the direct FIFO mechanism, which offers lower-earning trips directly to drivers further down the queue. We prove that accepting all dispatches forms a subgame perfect equilibrium among drivers, and that the equilibrium outcome achieves the first best trip throughput, and the second best net revenue (i.e. the highest steady state net revenue achievable by any flexible and transparent mechanism). The direct FIFO mechanism, however, would be considered unfair in practice since a driver may have lower priority for trips to many destinations than drivers further down the queue, even when all drivers are non-strategic and accept every dispatch. Consider the Chicago Midway airport (Figure 1b) as an example. A driver close enough to the head of the queue will no longer receive any trip back to downtown Chicago, since direct FIFO skips drivers at the head of the queue when dispatching lower and moderate earning trips, and all high-earning trips the driver may receive will be heading to the suburbs. To achieve optimal throughput and revenue without the use of an unfair dispatch rule, we introduce a family of randomized FIFO mechanisms. A randomized FIFO mechanism is specified by a set of "bins" in the queue (e.g., the top 10 positions, the 10 th to 20 th positions, and so on). Each trip request is first offered to a driver in the first bin uniformly at random. After each decline, the mechanism then offers the trip to a random driver in the next bin. By sending trips gradually down the queue in this randomized manner, the randomized FIFO mechanisms appropriately align incentives using waiting times, achieving the first best throughput and second best net revenue: the option to skip the rest of the line incentivizes drivers further down the queue to accept trips with lower earnings; randomizing each dispatch among a small group of drivers increases each individual driver's waiting time for the next dispatch, thereby allowing the mechanism to prioritize drivers closer to the head of the queue for trips to every destination without creating incentives for excessive cherry-picking. Extensive counterfactual simulations using data from the City of Chicago suggest that in comparison to strict FIFO dispatching, the randomized FIFO mechanism achieves substantial improvements in revenue, throughput, and driver earnings. Moreover, the variance in drivers' total payoffs is small, and diminishes rapidly as riders' patience increases-with higher rider patience, the mechanism can more effectively match higher-earning trips with drivers who have incurred higher waiting costs in the queue. This demonstrates the desirable balance achieved by the randomized FIFO mechanisms between efficiency, reliability, fairness, and the variability in driver earnings, and highlights the effectiveness of using waiting times in queue to align incentives and to reduce earning inequity when the flexibility to set prices is limited due to operational constraints. Ridesharing platforms. The literature on pricing and matching in ridesharing platforms is rapidly growing. Castillo et al. [2017] and establish the importance of dynamic pricing in maintaining the spatial density of open driver supply, which reduces waiting times and improves operational efficiency. In the presence of spatial imbalance and temporal variation of supply and demand, Bimpikis et al. [2019] and Besbes et al. [2020] study revenue-optimal pricing; Ma et al. [2019] propose origin-destination based pricing that is appropriately smooth in space and time, achieving welfare optimality and incentive compatibility; Garg and Nazerzadeh [2020] show that additive instead of multiplicative "surge" pricing is more incentive aligned for drivers when prices need to be origin-based only. Considering the online arrival of supply and demand and their distribution in space, Kanoria and Qian [2020] , Qin et al. [2020] andÖzkan and Ward [2020] study dynamic matching policies that dispatch drivers from areas with relatively abundant supply, and Ashlagi et al. [2019] , Dickerson et al. [2018] and Aouad and Saritaç [2020] focus on the online matching between riders and drivers and the pooling of shared rides. In this work, we focus on a single origin where the optimal destination-based pricing is infeasible due to operation constraints such that some trips are necessarily more lucrative than the others. This leads to the need of using drivers' waiting times to align incentives and to reduce the variability in driver earnings. The operation of ridesharing platforms is also studied using queueing-theoretic models. Banerjee et al. [2015] compare optimal dynamic and static pricing policies; Banerjee et al. [2018] propose state-dependent dispatching policies to minimize unfulfilled demand; Afeche et al. [2018] study the impact of admission control on platform revenue and driver income; Besbes et al. [2019] show that in comparison to traditional service settings, higher capacity is needed when spatial density of available supply affects operational efficiency; Castro et al. [2020] study practical dispatching policies when drivers have heterogeneous compatibility with trips. These works use queueingtheoretic frameworks to analyze the availability of driver supply, but study settings where drivers are spread out in space, and do not consider cherry-picking by drivers. In contrast, we focus on the matching of trips to drivers who are waiting in a virtual queue, addressing the problem of dispatching heterogeneous trips to drivers who have incurred different waiting costs in a way that is reliable, efficient and fair. Various empirical studies analyze the Uber platform as a two-sided marketplace, focusing on the labor market of Uber drivers [Hall et al., 2017] , the longer-term labor market equilibration [Hall and Krueger, 2016] , the value of flexible work arrangements [Chen et al., 2019] , learning-by-doing and the gender earnings gap [Cook et al., 2018] , and the surplus of consumers [Cohen et al., 2016] . In regard to the dynamic "surge" pricing, Hall et al. [2015] , Chen and Sheldon [2015] , and Lu et al. [2018] demonstrate its effectiveness in improving reliability and efficiency, increasing driver supply during high-demand times, as well as incentivizing drivers to relocate to higher demand areas. In contrast, we use data from ridesharing platforms (including Uber and Lyft, made public by the City of Chicago) to estimate the heterogeneity in driver earnings by trip destination. We also demonstrate via counterfactual simulations the inefficiencies of FIFO dispatching when drivers are strategic, as well as the substantial improvements achieved by our proposed mechanisms. Queueing mechanisms. The allocation of resources or jobs to participants waiting in a queue has been studied extensively in the literature. Naor [1969] first demonstrates the negative externalities from waiting: when agents make self-interested decisions on whether to join a FIFO queue, in equilibrium more agents line up in the queue in comparison to the socially optimal outcome. When monetary transfers are allowed, Naor shows that the optimal outcome can be achieved by levying an entrance toll, and a large body of subsequent work has studied how to align incentives and improve system efficiency in various settings (see Hassin [2016] for a comprehensive review). In many practical settings including ours, however, the use of monetary incentives is restricted due to regulatory or business constraints. Without the use of monetary transfers, Hassin [1985] shows that the last-in-first-out (LIFO) queueing discipline achieves the socially optimal outcome in equilibrium, since when the agent who has waited the longest in the queue decides whether to leave, she imposes no externality on any current or future agents. With homogeneous agents who prefer items of higher quality (i.e. when all patients prefer kidneys from younger and healthier donors in the context of kidney transplantation), Su and Zenios [2004] demonstrate the excessive organ wastage resulting from patients' cherry-picking under FIFO, and proves that LIFO dispatching optimizes organ utilization. These works highlight the important role of the queueing discipline in shaping participants' strategic considerations. As is discussed in these papers, however, LIFO is practically infeasible since the dispatch rule (i) would be perceived as unfair, and (ii) can be easily manipulated by re-joining the queue. In this work, we propose practical mechanisms that allow drivers to decline dispatches and to re-join the queue at any point of time. Moreover, we model the fact that riders' finite patience limits the number of times a trip can be dispatched, and prove that no transparent and flexible mechanism can achieve a better outcome than ours even when assuming infinite rider patience. On the flip side, Che and Tercieux [2021] establish the optimality of FIFO when the planner has full flexibility to (i) prevent participants from joining the queue and remove participants from the queue, and (ii) design the information provided to the participants. The objective is to optimize a weighted sum of the participants' utility and the service provider's profit. Intuitively, when the planner has the power to ensure that the queue is not too long, FIFO dispatching is the most effective since it provides the strongest incentive for participants to join and to stay in the queue. Su and Zenios [2006] and Ashlagi et al. [2020] study settings where an agent's value for an item depends on the type of the item and the private type of the agent. Su and Zenios [2006] design disjoint queue mechanisms that optimize either efficiency or equity (i.e. the minimum utility across all agent types). Assuming that the value for a match is supermodular in the types of the agent and the item, Ashlagi et al. [2020] establishes that a monotone disjoint queue mechanism is welfareoptimal. In both settings, agents cannot decline the allocated items. 7 Therefore, the mix of items dispatched to each queue effectively determines a lottery over items, and the waiting times in the different queues function as prices and incentivize an agent to choose the lottery intended for her type. In contrast, instead of eliciting private information, we focus on improving reliability without using penalties or hiding information. Our mechanism effectively dispatches every trip according to "a sequence of lotteries over positions in the queue", aligning incentives using (i) the option to skip the rest of the line and (ii) the additional cost of cherry-picking introduced by randomization. Existing work also compare FIFO and randomized allocation rules in various settings. Assuming an overloaded queue with fixed length, Bloch and Cantala [2017] show that agents in the queue prefer FIFO, but randomizing offers among all agents in the queue reduces waste, thus improves turnover and benefits agents who are not yet in the queue. Also assuming an overloaded queue, Leshno [2019] focuses on inefficiencies arising from the "mismatch", i.e. agents accepting their less preferred item since the wait for the more preferred item is too long. In a buffer queue for agents who have declined a less preferred item, randomizing offers reduces the variability of the expected waiting time for the more preferred item and reduces mismatches compared to FIFO. When agents have heterogeneous preferences over affordable housing developments, Arnosti and Shi [2020] prove that "individual lotteries" (one for each development) achieves the same outcome as a "wait-list without choice", both compelling agents to accept poor matches. More choices (via e.g., wait-list with choice) leads to better matching, but the authors also establish a trade-off between matching and targeting agents with worse outside options. In all three settings, the randomization is among all agents in the queue. In contrast, our proposed mechanisms randomize each dispatch among drivers from a small segment in the queue, which increases the costs of cherry-picking without introducing excessive variability in drivers' total payoffs. In this work, we focus on settings where participants have the flexibility to decline dispatches without losing their positions in the queue. Schummer [2021] analyze the impact of limiting this "deferral right" for various settings, where participants are risk averse or discount the future. We study a continuous time model, with one origin (e.g. an airport) where trips are dispatched to drivers who are waiting in a queue. L = {1, 2, . . . , } denotes the set of ∈ Z >0 discrete trip types (e.g. trips to different destinations). Rider demand and driver supply are non-atomic and are stationary over time. For each location i ∈ L, µ i > 0 denotes the arrival rate of riders requesting trips to location i (i.e. the mass of riders arriving per unit of time). Upon arrival, riders' trip requests need to be dispatched to the drivers. All riders have a patience level of P ∈ Z >0 , meaning that a rider may be willing to wait for a while for a driver to accept her trip request, but she will cancel her request and leave after the P th time that her trip is declined by the drivers. Each driver can drive any rider to her destination, and riders do not have preferences over drivers. Let λ > 0 be the arrival rate of drivers. Upon arrival, the driver may decide whether to join the queue. The net earnings of a trip to each location i ∈ L is w i , meaning that a driver who completes a rider trip to location i gets a payoff of w i from the trip, and the payoff of a driver who does not join the queue or leaves the queue without a rider is normalized to be zero. For each unit of time a driver spends waiting in the queue, the driver incurs an opportunity cost of c > 0, and the platform incurs an opportunity cost of c p ∈ [0, c]. 89 Drivers are strategic, aim to optimize their earnings from trips minus their waiting costs, and do not have preferences over riders or destinations. An informal timeline of a dispatching mechanism is as follows (see Section 3 for the formal definition). Upon the arrival of each rider, the mechanism may dispatch the rider's trip request to a driver in the queue. If the driver accepts the dispatch, she leaves the queue to pick up the rider. Otherwise, the trip may be dispatched again, until (i) some driver accepts the trip, or (ii) the rider cancels her request when her patience runs out (after the trip is declined for P times), or (iii) the mechanism decides to not dispatch the trip again. 10 We consider a setting where the platform has complete information about demand, supply, opportunity costs, and the earnings from trips to different destinations. We assume drivers have the same information, and that this is common knowledge amongst the drivers. We study mechanisms that are fully transparent and flexible. At any point in time, all drivers know the total length of the queue and their positions in the queue. When offered trip dispatches, drivers are provided trip destinations and earnings upfront, so that they can decide whether to accept a dispatch based on this information. Moreover, drivers are not penalized for actions they take, and have the options to (i) decline dispatches they do not want to accept without losing their position in the queue, (ii) rejoin the virtual queue at the tail at any point of time, and (iii) decide to not join the queue upon arrival, or leave the queue at any point of time to perhaps relocate back to the city without a rider. A platform's trip throughput is the mass of trips completed per unit of time by drivers in the queue. A platform's net revenue is the sum of the net earnings from trips made by drivers per unit of time, minus the opportunity cost the platform incurs due to drivers' waiting in the queue (this opportunity cost models the platform's loss of revenue elsewhere in the city, due to driver supply being tied-up in the queue). When drivers are non-strategic and accept all dispatches from the platform, we refer to the highest achievable trip throughput and net revenue as the first best. For simplicity of notation, we assume the destinations are ordered such that w 1 > w 2 > · · · > w ≥ 0. 11 With stationary and infinitesimal demand and supply, a platform does not need a nonzero driver queue. In steady state, a platform that aims to optimize its net revenue should keep no driver in the queue, but dispatch drivers upon their arrival to destinations in decreasing order of w i until either all drivers are dispatched or all riders are picked-up. Denote the lowest-earning trip that is (partially) completed as (1) Proposition 1 (The first best). The steady state first best outcome has zero drivers in the queue. Upon arrival, drivers are dispatched to pick up arriving riders in decreasing order of w i . The remaining drivers (if any) are suggested to leave without joining the queue. The first best trip throughput is 10 It takes some time for trip dispatches to be accepted or declined by the drivers (see Footnote 5). Drivers in the queue will be moving forward during the time a trip is repeatedly dispatched, but this does not affect our results since (i) the dispatch rules and driver strategies we study depend on the positions in the queue instead of the identities of individual drivers, and (ii) the optimality results we establish focus on the equilibrium outcome in steady state. 11 Combining destinations with the same net earnings does not affect the equilibrium outcome of any mechanism we study. For drivers who are free to decline dispatches based on trip destinations, no trip with wi < 0 will be accepted since completing one such trip is worse than declining the dispatch and leave the queue immediately without a rider. and the first best net revenue is (3) The FIFO queue discipline is considered fair by most, and is the default discipline in many everyday situations [Larson, 1987 , Breinbjerg et al., 2016 , Platz and Østerdal, 2017 . We show that when drivers have the flexibility to decline undesired trips, offering each trip to every driver incentivizes excessive cherry-picking and leads to poor outcomes for the riders, drivers, and the platform. To avoid ambiguity, we refer to this mechanism as strict FIFO dispatching. We start by analyzing the equilibrium outcome under strict FIFO dispatching. Consider a rider request for a trip to location 1. Under strict FIFO, the trip will be accepted by the driver at the head of the queue, since a trip to location 1 has the highest earnings among all trips the driver may receive in the queue. Moreover, the (infinitesimal) driver at the head of the queue will be willing to accept only trips to location 1, since she is the first in line to receive all incoming trip dispatches, thus she does not have to wait any time for a trip dispatch to location 1. Similar reasoning holds for drivers who are very close to the head of the queue, and a driver is willing to accept a trip to location 2 only if the additional waiting cost for a trip to location 1 outweighs the earnings gap w 1 − w 2 . Let τ 1,2 be the maximum additional time a driver is willing to wait for a trip to location 1, in comparison to immediately taking a trip to location 2. We know By Little's Law, the first position in the queue where the driver is willing to accept a location 2 trip is n 2 µ 1 τ 1,2 = µ 1 (w 1 − w 2 )/c, since the waiting time from this position to the head of the queue is τ 1,2 when all drivers ahead of this position only accept trips to location 1. For a driver at position n 2 , her continuation payoff (i.e. net earnings from the trip the driver accepts minus the waiting costs the driver incurs from this point of time onward) is w 2 , regardless of whether the driver accepted a trip to location 2, or if the driver continued to wait for a trip to location 1. Similarly, in comparison to accepting a trip to location i + 1, a driver is willing to wait an additional τ i,i+1 = (w i − w i+1 )/c units of time for a trip to location i. We can compute the first positions in the queue where drivers are willing to accept trips to each location i ∈ L, assuming that riders have infinite patience and will not cancel their trip requests regardless of how many times their trips have been declined by the drivers (see Figure 2 ). Lemma 1 (informal). Assume that riders have infinite patience. Under strict FIFO dispatching, it is an equilibrium for a driver to accept trip dispatches to each location i ∈ L only if the driver is at position q ≥ n i in the queue, where n 1 0 and We provide in Appendix A.1 the formal statement and the proof of the equilibrium outcome under strict FIFO dispatching. Briefly, we prove by induction that assuming infinite rider patience, for each location i ∈ L, a driver at position n i in the queue gets a continuation payoff of w i regardless of whether she accepted a trip to location i or not. Drivers at positions earlier than n i in the queue are, however, better off waiting for trips with higher earnings. Head of the queue n 1 τ 1,2 periods n 2 τ 2,3 periods n 3 . . . When riders have a finite patience level P , however, trip requests to locations i ∈ L with n i > P will not reach a driver who is willing to accept this trip before the rider's patience runs out. As a result, trips to these destinations become unfulfilled, leading to poor efficiency and reliability. The following example demonstrates that drivers' excessive waiting in the queue further reduces drivers' total payoffs as well as the net revenue of the platform. Example 1. Consider an airport queue, where riders request trips to three destinations L = {1, 2, 3}. The arrival rate of riders to each destination is µ 1 = 1, µ 2 = 6, and µ 3 = 3, and the net earnings from these trips are w 1 = 75, w 2 = 25, w 3 = 15, respectively. Intuitively, trips to location 1 represent the rare but high-earning long trips from the airport. Location 2 can be considered as the downtown area with high trip volumes and medium earnings, and think about location 3 trips as short rides to the hotels and towns surrounding the airport with low earnings. Drivers arrive at a rate of λ = 5 per unit of time, and the opportunity costs for the drivers and the platform are c = c p = 1/3. Considering each unit of time as one minute, this corresponds to a scenario where a driver driving for the platform elsewhere in the city will make $20 per hour. Riders have a patience level of P = 12. When it takes an average of 10 seconds for each driver to decline a dispatch, this corresponds to the riders' being willing to wait for two minutes for a match before canceling their trip requests. The first best. The first best outcome accepts all trips to location 1, and dispatches the remaining 4 units of drivers to trips to location 2. No driver waits in the line. The first best trip throughput is T FB = 5, and the first best net revenue is R FB = w 1 +4w 2 = 175. This outcome can be implemented, for example, by forcing each driver to always accept the first trip dispatch she receives. This, however, introduces a high variance in drivers' total payoffs (net earnings from trip minus waiting costs): the average total payoff of a driver who arrived at the queue is 35, and the variance is 400. Strict FIFO dispatching. Under strict FIFO dispatching, when drivers have the flexibility to decide which trips to take, the driver at the head of the queue is only willing to accept trips to location 1. A driver with a location 2 trip in hand is willing to wait an additional τ 1,2 = (w 1 − w 2 )/c = 150 minutes for a trip to location 1. Therefore, the first position in the queue where the driver is willing to go to location 2 is n 2 = τ 1,2 µ 1 = 150. With a patience level of 12, riders requesting trips to location 2 will cancel their trip requests after their requests are declined by the 12 th driver in the queue. Location 3 trips are similarly unfulfilled, thus strict FIFO dispatching achieves a trip throughput of only T strict = 1 per minute. The remaining 4 units of drivers will need to leave the queue without a rider trip in steady state. The drivers, however, will not leave if the payoff from joining the queue at the tail is better than that from relocating without a rider. Drivers are willing to wait for w 1 /c = 225 minutes for a trip to location 1, thus the steady state queue length will be µ 1 w 1 /c = 225 by Little's Law. In equilibrium, drivers get a payoff of zero regardless of whether they joined the queue or left without a rider. The large number of drivers waiting in the queue is also very costly for the platform, which achieves in this example a net revenue of zero: R strict = w 1 µ 1 − c p (µ 1 w 1 /c) = 0. Strict FIFO dispatching is fair in the sense that drivers who are closer to the head of the queue have higher priority for trips to every destination. However, as we have seen in the above example, dispatching each trip to each and every driver in the queue leads to poor reliability for the riders, low trip throughput and net revenue for the platform, and zero earnings for the drivers despite their strategizing for better earnings. In the next section, we will see that by deprioritizing drivers at the head of the queue for trips to certain destinations (thereby violating what is typically perceived as fair dispatching), we are able to substantially improve the outcome for the riders, drivers, and the platform, even without the power to adjust trip prices. In this section, we introduce the direct FIFO mechanism. The mechanism is based largely on FIFO dispatching, but sends lower-earning trips starting from positions further down the queue where drivers are willing to accept the dispatches for the option to skip the rest of the line. Accepting all trips forms a subgame perfect equilibrium among drivers, and the mechanism achieves the highest possible revenue and throughput under any mechanism that is flexible and transparent. We first formally define a dispatching mechanism. Let Q ≥ 0 denote the length of the queue, and let q ∈ [0, Q] be a particular position in the queue. q = 0 and q = Q are the head and the tail of the queue, respectively, i.e. positions where the drivers have waited the longest and the shortest time in line. Let h denote the past dispatching history of a particular rider's trip request. This represents the positions in the queue to which the trip was offered (if any). Finally, we use φ to denote the decision to not dispatch a rider's trip request to any driver. Definition 1 (Dispatching mechanism). Given the queue length Q, the past dispatching history h of a trip, and the trip's destination, a dispatching mechanism determines a probability distribution over [0, Q] ∪ {φ}. Upon the arrival of a rider, or after a rider's trip is declined by some driver, the mechanism either (i) dispatches the trip to a driver at some position q ∈ [0, Q] in the queue, or (ii) decides to not dispatch the trip (which we denote as φ). The queue length Q represents the state of the queue. The dispatching mechanisms we study make dispatch decisions for each trip based on the state and the past dispatch history of this particular trip, but not on other factors such as how the state had evolved over time, or what actions the drivers had taken in the past. 12 Similarly, we focus on driver strategies that depend on the queue length and a driver's position in the queue, and we denote a strategy as a tuple σ = (α, β, γ). For any queue length Q ≥ 0, and at any position q ∈ [0, Q] in the queue, (i) α(q, Q, i) ∈ [0, 1] for each location i ∈ L is the probability with which the driver at position q in the queue accepts the trip dispatch if she is dispatched a trip to location i, (ii) β(q, Q) ∈ [0, 1] determines the probability with which the driver at position q in the queue re-joins the queue at the tail (by going offline and online again, for example), and (iii) γ(q, Q) ∈ [0, 1] is the probability for the driver at q to leave the queue without a rider. Let U (q, Q, σ, σ ) denote the random variable representing the continuation payoff of the driver at position q in the queue, when the current length of the queue is Q, when this driver adopts strategy σ, and when all other drivers employ strategy σ (including those drivers who will arrive in the future). This includes the net earnings from the trip the driver may complete in the future, minus the total opportunity cost she incurs from this point of time onward waiting in the queue. Denote π(q, Q, σ, σ ) E [U (q, Q, σ, σ )] as the driver's expected continuation payoff from position q onward, where the expectation is taken over randomness in both the mechanism's decisions and the strategies of drivers. π(Q, Q, σ, σ ) thus represents the expected payoff of a driver with strategy σ, who joins the queue when the queue length is Q, and when all other drivers employ strategy σ . We define the following properties. Definition 2 (Subgame-perfect equilibrium). A strategy σ * forms a subgame perfect equilibrium (SPE) among drivers under a mechanism if for any economy and any feasible strategy σ, Definition 3 (Individual rationality). A mechanism is individually rational in SPE if under a strategy σ * that forms an SPE among drivers, for any economy, Definition 4 (Envy-freeness). A mechanism is envy-free in SPE if under a strategy σ * that forms an SPE among drivers, for any economy, Intuitively, under a mechanism that is individually rational and envy-free in SPE, a driver anywhere in the queue always gets non-negative continuation payoff, and does not envy the expected continuation earnings of any driver who is further down the queue. Given a mechanism M and a strategy σ * that forms an SPE under M, let Q * denote the length of the queue under σ * in steady state. This is the case if the number of drivers joining the queue per unit of time is equal to the number of drivers dispatched from the queue when (i) the length of the queue is Q * and (ii) all drivers adopt strategy σ * . Moreover, let z i (σ * ) denote the fraction of trips to location i ∈ L that are completed in steady state when all drivers adopt σ * . The trip throughput of mechanism M is the amount of trips completed per unit of time under σ * in steady state: The net revenue achieved by mechanism M is the total net earnings all drivers made from trips per unit of time under σ * in steady state, minus the total opportunity costs the platform incurs due to drivers' waiting in the queue: When c p = c, the net revenue of the platform is R M (σ * ) = i∈L z i (σ * )µ i w i − Q * c, i.e. the total net payoffs to all drivers who arrive at the queue. The objective of a mechanism is to optimize trip throughput and net revenue achieved in equilibrium in steady state. 13 We say a mechanism is optimal if in equilibrium in steady state (i) the mechanism achieves the first best trip throughput, and (ii) the mechanism achieves the second best net revenue i.e., the highest steady sate equilibrium net revenue that is achievable by any dispatching mechanism that is flexible and transparent, provides trip information to drivers upfront, and does not penalize drivers for any actions they take. 14 3.2 Optimality of Direct FIFO Definition 5 (Direct FIFO). Under the direct FIFO mechanism, trips to each location i ∈ L are dispatched in a FIFO manner to drivers starting from position n i (as defined in (5)) in the queue, when the length of the queue is Q ≥ n i . When Q < n i , trips to location i are not dispatched. Under the direct FIFO mechanism, the highest earning trips to location 1 are dispatched to the head of the queue, where the driver have waited for the longest time (thus have incurred the highest waiting costs). For a trip to location i > 1, the mechanism skips drivers close to the head of the queue who will be unwilling to accept, and dispatches the trip starting from the n th i positionthe first position in the queue where the driver is willing to accept a trip to location i under strict FIFO dispatching assuming infinite rider patience. The following theorem proves that this option to "skip the rest of the line" incentivizes drivers to accept all dispatches they receive. Theorem 1 (Incentive compatibility of direct FIFO). It is a subgame-perfect equilibrium for drivers to accept all dispatches from the direct FIFO mechanism, and to join the queue if and only if the length of the queue is at mostQ Moreover, the equilibrium outcome is individually rational and envy-free. The proof is via induction on queue positions, and is provided in Appendix A.2. Intuitively, this is a "direct implementation" of the equilibrium outcome under strict FIFO dispatching when riders have infinite patience (see Lemma 1). Trips are dispatched starting from the positions in the queue where the drivers are indifferent towards accepting the trip or continuing to wait, and the equilibrium payoff from joining the queue is non-negative when the queue length is at mostQ. When there are more drivers than needed to complete all trips to location 1, the direct FIFO mechanism does not achieve the first best net revenue-drivers are willing to spend time waiting for trips with higher earnings, leading to a queue of non-zero length and lowering the net revenue of the platform. This kind of "strategic waiting" is, however, not avoidable. We prove in the following theorem that the outcome under direct FIFO achieves the second best net revenue, i.e. the highest equilibrium net revenue achievable in steady state by any dispatching mechanism that provides trip destinations upfront and does not penalize drivers for declining dispatches. 13 When the platform takes as commission a fixed fraction of the earnings made by the drivers (from the queue as well as from driving elsewhere in the city), the problem of maximizing a platform's total commission is equivalent to that of maximizing the net revenue as defined in (10). 14 As we shall see later in this section, a platform may not be able to achieve the first best net revenue in certain settings, despite achieving the first best trip throughput. This is the case when a mechanism completes the same set of trips as those under the first best outcome, but drivers' strategically waiting for higher earning trips leads to a non-zero equilibrium queue length, thus increasing opportunity cost and reducing the net revenue of the platform. Head of the queue n 1 n 2 n 3 . . . n i * −1 Tail of the queue n i * (a) The under-supplied scenario, with λ ≤ i∈L µ i . Head of the queue n 1 n 2 n 3 . . . n Tail of the queuē Q (b) The over-supplied scenario, with λ > i∈L µ i . Theorem 2 (Optimality of direct FIFO). For every economy, the direct FIFO mechanism achieves in SPE the first best trip throughput. Moreover, the equilibrium outcome achieves the first best net revenue when c p = 0, and the second best net revenue when c p ∈ (0, c]. We prove this theorem in Appendix A.2. Briefly, we first show that the steady state equilibrium outcome under direct FIFO is as illustrated in Figure 3 . When λ ≤ i∈L µ i , i * as defined in (1) is the lowest-earning trip that is (partially) completed in equilibrium. Drivers will line up for trips to locations j < i * (which have higher earnings than w i * ), but the equilibrium queue length is Q * = n i * and there is no wait for a trip to location i * . See Figure 3a . Every driver gets a total payoff of w i * regardless of which trip they take, and all trips that are completed under the first-best outcome are completed. When λ > i∈L µ i , the queue is over-supplied such that all trips are accepted and completed, and the equilibrium queue length is Q * =Q (see Figure 3b ). At this point, the drivers are indifferent between joining the queue and leaving, and all drivers get a zero payoff. Given that all trips completed under the first best outcome are completed, direct FIFO achieves the first best trip throughput, and also the first best net revenue if c p = 0 (i.e. when the platform does not incur any opportunity cost due to drivers' waiting in the queue). To prove that the direct FIFO mechanism achieves the second best net revenue when c p > 0, we first establish that no mechanism can achieve in equilibrium a strictly higher total payoff for all drivers combined. This implies that if the same set of trips are completed, reducing the equilibrium queue length in comparison to that under direct FIFO (thereby reducing the total opportunity costs for the drivers as well as the platform) is not possible. We then prove that completing a different set of trips in return for a shorter queue cannot be an improvement. We now revisit the economy analyzed in Example 1 in Section 2. Example 1 (Continued). Consider the economy in Example 1, for which strict FIFO dispatching achieves trip throughput T strict = 1 and net revenue R strict = 0. Under direct FIFO, trips to each location will be dispatched to drivers in the queue starting at positions n 1 = 0, n 2 = 150, and n 3 = 360, respectively. With λ = 5, µ 1 = 1 and µ 2 = 6, the lowest earning trip accepted in equilibrium will be trips to location i * = 2, and the steady state queue length is Q * = n 2 = 150. Upon arrival at the tail of the queue at n 2 , one unit of driver moves on to wait for trips to location 1, and the remaining 4 units of drivers immediately accept trips to location 2 and leave. In equilibrium, all drivers get the same total payoff of w 2 = 25. The platform achieves a trip throughput of T direct = 5 and a net revenue of R direct = 1 · w 1 + 4 · w 2 − Q * c p = 125 per unit of time. Since c = c p this net revenue is also the total payoff for all drivers combined. In comparison to strict FIFO dispatching, the direct FIFO mechanism substantially improves driver earnings, trip throughput, and the net revenue of the platform. The mechanism is, however, not fair because even when all drivers are non-strategic and accept all dispatches from the platform, a driver closer to the head of the queue may still receive trips to certain destinations at a lower rate than drivers further down the queue. Take the Midway airport as an example. A driver who has waited long enough in the queue will never receive a trip back to downtown Chicago againas we can see from Figure 1b , all high-earning trips direct FIFO dispatches to her will be heading to the suburbs. This renders the direct FIFO mechanism ill-suited for practice. In this section, we introduce a family of randomized FIFO mechanisms, which achieve optimal equilibrium throughput and revenue without using unfair dispatch rules-when drivers are straightforward and accept all dispatches, a driver closer to the head of the queue receives trip dispatches to every destination at a (weakly) higher rate than any driver further down the queue. To demonstrate the effectiveness of randomization for aligning incentives, we first analyze the steady state Nash equilibrium under random dispatching, where every trip request is simply dispatched to drivers in the queue uniformly at random. 15 Definition 6 (Nash equilibrium in steady state). A strategy σ * forms a Nash equilibrium among drivers in steady state under a mechanism if there exists a queue length Q * ≥ 0 such that (i) for any feasible strategy σ and any position in the queue q ∈ [0, Q * ], π(q, Q * , σ * , σ * ) ≥ π(q, Q * , σ, σ * ), (ii) when all drivers adopt strategy σ * , the steady state queue length is Q * . Proposition 2 (Optimality of random dispatching). In Nash equilibrium in steady sate, dispatching every trip to all drivers in the queue uniformly at random achieves the first best trip throughput and the second best net revenue. When c p = 0, the equilibrium net revenue is also the first best. See Appendix A.3 for the proof of this result. Briefly, we show that under random dispatching, every driver in the queue is willing to accept a trip to location i * (the lowest earning trip accepted in equilibrium under direct FIFO) despite the fact that the drivers may still receive higher-earning trips later. This is different from the outcome under strict FIFO, because in comparison to the driver at the head of the queue under strict FIFO, a driver who declines a dispatch under random dispatching will need to wait for a much longer time to receive her next dispatch. This additional waiting time introduced by randomization increases drivers' costs of cherrypicking, and allows random dispatching to align incentives without deprioritizing drivers at the head of the queue when dispatching trips to any location. Naively randomizing among all drivers in the queue, however, introduces substantial uncertainty in drivers' waiting times. This contributes to the variability in drivers' total payoffs, on top of the variability in the net earnings from trips. This is in stark contrast to direct FIFO, which matches lower-earning trips with drivers who have waited less time in the queue, thereby reducing the variation in drivers' total payoffs. Head of the queuē Figure 4 : Illustration of a randomized FIFO mechanism. The randomized FIFO mechanisms we now introduce make proper use of drivers' waiting times in the queue in both ways. By gradually sending declined trips down the queue in a randomized manner, a randomized FIFO mechanism aligns incentives, and also guarantees that drivers in earlier segments in the queue (who have incurred higher waiting costs) will take trips with higher earnings. . For the k th time a trip is dispatched, the mechanism dispatches the trip to a driver in the k th bin [b (k) ,b (k) ] uniformly at random. See Figure 4 for an illustration. Intuitively, all rider requests are first dispatched to drivers in the first bin [b (1) ,b (1) ] uniformly at random. If a dispatch is declined, the mechanism will then dispatch the trip to a random driver in the next bin. With a rider patience level of P , each trip may be dispatched a maximum of P times before the rider cancels her request. Recall that i * as defined in (1) is the lowest-earning trip that is (partially) completed under the first best outcome. Given any economy, let ( (iii) (monotone) for all k 1 , k 2 ≤ m s.t. k 1 < k 2 , we have i < j for all i ∈ L (k 1 ) and all j ∈ L (k 2 ) . Condition (iii) requires that trips in an earlier partition have higher earnings than those in a later partition. Given an economy and any ordered partition (L (1) , . . . , L (m) ) of the top i * destinations, we construct a corresponding set of m bins in the queue ([b (1) In Lemma 4 in Appendix A.4 we show thatb (1) = 0,b (k) ≥b (k) ≥ 0 for each k ≤ m, and b (k+1) ≥b (k) for all k ≤ m − 1. This guarantees that the bins start from the head of the queue, are well defined, and do not overlap with each other. We now present the main result of this paper, that the family of randomized FIFO mechanisms constructed in this way achieves the optimal steady state outcome in Nash equilibrium. Theorem 3 (Optimality of randomized FIFO). For any economy and any ordered partition of the top i * destinations (L (1) , . . . , L (m) ) with m ≤ min{i * , P }, a randomized FIFO mechanism corresponding to (13) and (14) achieves the first best trip throughput and the second best net revenue in Nash equilibrium in steady state. When c p = 0, the net revenue is also the first best. We provide the proof of this theorem in Appendix A.4. Briefly, let Q * denote the steady state equilibrium queue length under the direct FIFO mechanism. We first show that under a randomized FIFO mechanism, it is a Nash equilibrium in steady state that (i) all drivers in the k th bin in the queue accept all and only trips in the top k partitions ∪ k k =1 L (k ) (with potential randomization over trips to location i * ), (ii) after joining the queue, no driver leaves the queue without a rider trip, or rejoins the queue at its tail, (iii) drivers join the queue with probability min{1, i∈L µ i /λ} upon arrival, and (iv) the length of the queue remains constant at Q * . Under this equilibrium outcome, all trips that are completed under the first best are also completed, so that the randomized FIFO and direct FIFO mechanisms complete the same set of trips in steady sate. The queue lengths being the same then implies that randomized FIFO also achieves the optimal net revenue, given the optimality of the direct FIFO mechanism we have established in Theorem 2. More formally, let π * (q) π(q, Q * , σ * , σ * ) be the continuation payoff of a driver at position q ∈ [0, Q * ] in the queue, when the queue length is Q * and when all drivers adopt the equilibrium strategy described above (which we denote as σ * ). We show that π * (q) is non-negative, piece-wise linear, and monotonically non-increasing in q. Moreover, π * (q) = min i∈L (k) for each k ≤ m, i.e. the continuation earning of any driver in the k th bin is equal to the net earning of the lowest earning trip in the k th partition. This allows us to prove by induction on k that σ * forms a Nash equilibrium. The non-negativity and monotonicity of π * (q) imply that the randomized FIFO mechanism is individually rational and envy free in Nash equilibrium in steady state. We now demonstrate via the following example that the randomized FIFO mechanism substantially reduces the variability in drivers' earnings in comparison to dispatching every request to all drivers in the queue uniformly at random. Example 2. Consider an economy with three destinations L = {1, 2, 3}, rider arrival rates µ 1 = 1, µ 2 = 6, µ 3 = 3, and net earnings from trips w 1 = 75, w 2 = 25, w 3 = 15. The opportunity costs per minute are c = c p = 1/3, and drivers arrive at a rate of λ = 8 per minute. Moreover, assume for simplicity that riders have a patience level of P = 2, i.e. each trip can be dispatched only twice before riders cancel their requests. Strict FIFO dispatching. Trips to locations 2 and 3 cannot reach drivers in the queue who are willing to accept them. T strict = 1 as a result. Moreover, R strict = 0 since queue is long enough that drivers get a payoff of zero regardless of whether they had joined the queue, and when c p = c the platform's net revenue is equal to the total payoff of all drivers. Random dispatching. When the length of the queue is Q * = 360, it is an equilibrium for drivers to accept all trips to locations 1 and 2, and randomize on trips to location 3. In steady state, all location 1 and 2 trips, and a third of location 3 trips are completed. The throughput is T rand = 8, and the platform achieves a net revenue of R rand = 120 per minute. The average waiting time in the queue is Q * /T rand = 45 minutes, and the drivers get an average total payoff of 15. However, due to the high level of variability in (i) a driver's waiting time for a trip, and (ii) the net earnings from the trip a driver may accept, the variance of drivers' total payoffs is 500 (see Appendix B.4 for the computation of the equilibrium outcome and earning variance). Randomized FIFO. Consider a randomized FIFO mechanism corresponding to the ordered partition (L (1) , L (2) ) = ({1}, {2, 3}). The corresponding bins are given byb (1) =b (1) = 0,b (2) = 180, and b (2) = 360. All trips are first sent to drivers in [b (1) ,b (1) ] = {0}, i.e. the head of the queue. In equilibrium, drivers at the head of the queue accept only trips to location 1.The remaining trips to locations 2 and 3 will then be randomly dispatched to drivers at positions 180 to 360 in the queue. In equilibrium, the length of the queue is Q * = 360. Compared to random dispatching, the randomized FIFO mechanism achieves the same trip throughput, net revenue, average driver wait-ing time, and average driver payoff. In contrast, the variance of the total payoffs of the drivers is reduced from 500 to 75 (see Appendix B.5 for more details). By matching higher earning trips with drivers in earlier bins who have incurred a higher waiting cost, the randomized FIFO mechanism is able to substantially reduces the variability in drivers' total payoffs. A higher patience level of riders increases the number of times a trip can be dispatched before the rider cancels her request. This allows the randomized FIFO mechanisms to use a larger number of bins and better match higher-earning trips with drivers who have waited longer in the queue. When riders are sufficiently patient, the randomized FIFO mechanism is able to achieve zero variance in drivers' total payoffs. Consider an economy where riders' patience level is higher than the number of trip types completed in equilibrium, i.e. when P ≥ i * . The randomized FIFO mechanism corresponding to m = i * partitions has a single trip in each partition, and offers a trip to the driver at position n k in the queue if it is the k th time that the trip is dispatched. In equilibrium, trips to each location k ≤ i * are accepted by the drivers at n k , and the equilibrium outcome is the same as that under direct FIFO, where all drivers have the same total payoff. In real-life systems with the richness of a ridesharing platform, there typically exist multiple notions of fairness. In the context of the airport queues, a platform could be perceived as not treating drivers fairly if some drivers receive much more lucrative trips than others after waiting a similar amount of time, or if drivers who arrived later in time have higher priority for trips to certain destinations. Under the randomized FIFO mechanisms, the small variance in drivers' total payoffs and the envy-freeness of the equilibrium outcome (which guarantees that no driver would want to swap positions with any other driver who joined the queue later in time) can both be considered as fairness properties for the equilibrium outcome (see Avi-Itzhak and Levy [2004] , Platz and Østerdal [2017] , and Wierman [2011] ). The direct FIFO mechanism achieves zero earning variance in theory, but severely violates what is typically required of a fair dispatch rule since even when all drivers are straightforward and accept every dispatch, drivers closer to the head of the queue may still receive trips to certain destinations at a lower rate than drivers further down the queue. Under a randomized FIFO mechanism, trips are only dispatched to drivers closest to the head of the queue when all drivers are straightforward. With strategic drivers, in equilibrium, it is possible for drivers in later bins to receive certain low-earning trips at a higher rate than drivers in an earlier bin, after these trips are first dispatched to and declined by drivers in the earlier bins. 16 As we have seen from the analysis of strict FIFO dispatching, improving efficiency and average driver earnings does require that lower-earning trips be quickly dispatched to drivers further down the queue who are willing to accept them, before riders' patience runs out. 17 In addition to the optimality of revenue and throughput, the proof of Theorem 2 also establishes that no mechanism can achieve a better total payoff for drivers, if drivers are provided trip details upfront as well as the flexibility to freely decline any dispatches. It is tempting to think that a mechanism that imposes penalties could easily achieve a better outcome. However, the same proof also implies that even if a mechanism is allowed to move drivers to the tail of the queue for 16 There may also be segments in the queue where the drivers do not receive any dispatches under the randomized FIFO mechanisms. It is possible forb (k−1)