Abstract: Waiting costs function as prices in waiting lists. These prices, the waiting costs for each item, are determined endogenously and adjust according to the stochastic arrivals and departures of agents. We study the allocative efficiency under such dynamically adjusting prices by drawing a connection between this price adjustment process and the stochastic gradient descent optimization algorithm. We show that the loss due to price fluctuations is bounded by the granularity of price changes, and that this bound is essentially tight. Our results show that a simple price adjustment heuristic can perform well, but may be slow to adjust to changes in demand because of a trade-off between the speed of adaptation and loss from price fluctuations.

Abstract: We revisit the popular random matching market model introduced by Knuth (1976) and Pittel (1989), and shown by Ashlagi, Kanoria and Leshno (2013) to exhibit a ‘stark effect of competition’, i.e., with any difference in the number of agents on the two sides, the short side agents obtain substantially better outcomes. We generalize the model to allow ‘partially connected’ markets with each agent having an average degree $d$ in a random (undirected) graph. Each agent has a (uniformly random) preference ranking over only their neighbors in the graph. We characterize stable matchings in large markets and find that the short side enjoys a significant advantage only for $d$ exceeding $(\log n)^2$ where $n$ is the number of agents on one side: For moderately connected markets with $d=o((\log n)^2)$, we find that there is no stark effect of competition, with agents on both sides getting a $\sqrt{d}$-ranked partner on average. Notably, this regime extends far beyond the connectivity threshold of $d=\Theta(\log n)$. In contrast, for densely connected markets with $d=\omega((\log n)^2)$, we find that the short side agents get $(\log n)$-ranked partner on average, while the long side agents get a partner of (much larger) rank $d/(\log n)$ on average. Numerical simulations of our model confirm and sharpen our theoretical predictions. Since preference list lengths in most real-world matching markets are much below $(\log n)^2$, our findings may help explain why available datasets do not exhibit a strong effect of competition.

Abstract: We study the problem of maximizing payoff generated over a period of time in a general class of closed queueing networks with a finite, fixed number of supply units which circulate in the system. Demand arrives stochastically, and serving a demand unit (customer) causes a supply unit to relocate from the ‘origin’ to the ‘destination’ of the customer. The key challenge is to manage the distribution of supply in the network. We consider general controls including customer entry control, pricing, and assignment. Motivating applications include shared transportation platforms and scrip systems. Inspired by the mirror descent algorithm for optimization and the backpressure policy for network control, we introduce a novel and rich family of $\textit{Mirror Backpressure}$ (MBP) control policies. The MBP policies are simple and practical, and crucially do not need any statistical knowledge of the demand (customer) arrival rates (these rates are permitted to vary slowly in time). Under mild conditions, we propose MBP policies that are provably near optimal. Specifically, our policies lose at most $O(\frac{K}{T}+\frac{1}{K} + \sqrt{\eta K})$ payoff per customer relative to the optimal policy that knows the demand arrival rates, where $K$ is the number of supply units, $T$ is the total number of customers over the time horizon, and $\eta$ is the maximum change in demand arrival rates per period (i.e., per customer arrival). A natural model of a scrip system is a special case of our setup. An adaptation of MBP is found to perform well in a realistic ride-hailing environment.

Abstract: We study the design of dynamic assignment control in networks with a fixed number of circulating resources (supply units). Each time a demand arises, the controller has (limited) flexibility in choosing the node from which to assign a supply unit. If no supply units are available at any compatible node, the demand is lost. If the demand is served, this causes to the supply unit to relocate to the ‘destination’ of the demand. We study how to minimize the proportion of lost requests in steady state (or over a finite horizon) via a large deviations analysis. We propose a family of simple state-dependent policies called Scaled MaxWeight (SMW) policies that dynamically manage the distribution of supply in the network. We prove that under a complete resource pooling condition (analogous to the condition in Hall’s marriage theorem), any SMW policy leads to exponential decay of demand-loss probability as the number of supply units scales to infinity. Further, there is an SMW policy that achieves the $\textbf{optimal}$ loss exponent among all assignment policies, and we analytically specify this policy in terms of the demand arrival rates for all origin-destination pairs. The optimal SMW policy maintains high supply levels adjacent to structurally under-supplied nodes. We discuss two applications: (i) Shared transportation platforms (like ride-hailing and bikesharing): We incorporate travel delays in our model and show that SMW policies for assignment control continue to have exponentially small loss. Simulations of ride-hailing based on the NYC taxi dataset demonstrate excellent performance. (ii) Service provider selection in scrip systems (like for babysitting or for kidney exchange): With only cosmetic modifications to the setup, our results translate fully to a model of scrip systems and lead to strong performance guarantees for a ‘Scaled Minimum Scrip’ service provider selection rule.