The design of online policies for stochastic matching and revenue management settings is usually bound by the Bayesian prior that the demand process is formed by a fixed-length sequence of queries with unknown types, each drawn independently. This assumption of serial independence implies that the demand of each type, i.e., the number of queries of a given type, has low variance and is approximately Poisson-distributed. Thus, matching policies are often based on "fluid" LPs that only use the expectations of these distributions.

Online service platforms have transformed how customers and suppliers connect in real-time, using centralized dispatch and pricing systems. However, by acting as "central planners", platforms risk undermining the workers' flexibility endorsed by the gig economy. Hence, there has been significant scrutiny on the classification of gig workers as independent contractors and their freedom in decisions that directly influence their earnings, such as prices. To alleviate such concerns, several platforms in the ride-hailing industry have adopted or tested decentralized pricing schemes, where workers set prices flexibly. However, this approach presents a complex trade-off. On the one hand, platforms' pricing systems enable an efficient matching process by balancing demand and supply. Individual suppliers' pricing decisions may overlook market-wide effects on supply-demand equilibrium. On the other hand, suppliers possess private information about their preferences and costs that platforms cannot easily infer and use for price discrimination. Decentralized pricing can accommodate supplier-side heterogeneity, potentially increasing workers' participation in the market.

Motivated by online labor markets, we consider the online assortment optimization problem faced by a two-sided matching platform that hosts a set of suppliers waiting to match with a customer. Arriving customers are shown an assortment of suppliers, and may choose to issue a match request to one of them. After spending some time on the platform, each supplier reviews all the match requests he has received and, based on his preferences, he chooses whether to match with a customer or to leave unmatched. We study how platforms should design online assortment algorithms to maximize the expected number of matches in such two-sided settings. We show that, when suppliers do not immediately accept/reject match requests, our problem is fundamentally different from standard (one-sided) assortment problems, where customers choose over a set of products. We establish that a simple greedy algorithm is 1/2-competitive against an optimal clairvoyant algorithm that knows in advance the full sequence of customers' arrivals. However, unlike related online assortment problems, no randomized algorithm can achieve a better competitive ratio, even in asymptotic regimes. To advance beyond this general impossibility, we consider structured settings where suppliers' preferences are described by the Multinomial Logit and Nested Logit choice models. We develop specialized balancing algorithms, which we call preference-aware, that leverage general information about the suppliers' choice models. In certain settings, the resulting competitive ratios are provably larger than the standard "barrier" of 1-1/e in the adversarial arrival model. Our results suggest that the shape and timing of suppliers' choices play critical roles in designing online two-sided assortment algorithms.

Motivated by centralized matching markets, we study an online stochastic matching problem on edge-weighted graphs, where the agents' arrivals and abandonments are stochastic and heterogeneous. The problem is formulated as a continuous-time Markov decision process (MDP) under the average-cost criterion. While the MDP is computationally intractable, we design simple matching algorithms that achieve constant-factor approximations in cost-minimization and reward-maximization settings. Specifically, we devise a 3-approximation algorithm for cost minimization on graphs satisfying a metric-like property. We develop a (e-1)/(2e)-approximation algorithm for reward maximization on arbitrary bipartite graphs. Our algorithms possess a greedily-like structure informed by fluid relaxations. In extensive experiments, we simulate the matching operations of a car-pooling platform using real-world taxi demand data. The newly-developed algorithms have the potential to significantly improve cost efficiency in certain market conditions against the widely used batching algorithms.