Two-sided marketplaces such as Amazon, Alibaba, Google, and Yelp connect customers with providers and commonly rank providers based on quality while allowing them to promote themselves through sponsored ads. This paper develops a game-theoretic model of such platforms, where providers strategically choose customer prices and advertising intensity in response to the platform's ad placement and pricing policy. The analysis characterizes equilibrium outcomes and examines how platforms can design policies to optimize key objectives. The results show that ranking sponsored ads by the product of bid and clickthrough rate—a widely used heuristic—always maximizes supply-side surplus, defined as the sum of provider profits and platform revenue. To also enhance customer surplus, platforms should discount the per-impression cost of ads based on estimated provider quality, enabling providers that better meet customer needs to pay less per impression. This quality-adjusted pricing rule achieves the best possible multiplicative guarantee relative to the first-best social welfare, which includes both supply-side and customer surplus. In contrast, when provider quality is imperfectly estimated, removing sponsored ads and relying solely on organic rankings yields strictly worse welfare guarantees. These results offer prescriptive guidance for platform design and establish normative benchmarks for evaluating digital marketplace policies.

Digital platforms that help customers find suitable service providers often monetize by selling customer leads to interested service providers. Examples of such platforms include Bark, Google Local Services, HomeAdvisor, Modernize, Porch, and Thumbtack. I analyze this platform design using a game-theoretic model and obtain insights on how the pricing of leads affects customer and provider welfare. When the platform raises the fee per lead for a customer type, providers who buy these leads quote more competitive prices to these customers, which benefits the customers whose leads are bought. However, providers may also buy fewer such leads, switch to other customer types, or exit the platform. For maximizing social welfare, the simple policy of charging a market-clearing fee-per-lead for every customer type guarantees at least 1/(e - 1) ≈ 58.19% of the first-best welfare, and at least 79.15% of the welfare under the optimal fees. Higher welfare can be achieved by paying providers an additional subsidy upon each job well done, so that experienced providers with cheaper sources of leads do not exit the platform. Understanding the nuances of these welfare effects can help platforms better grow both sides of the marketplace while maintaining an adequate revenue stream.

Many two-sided marketplaces rely on match recommendations to help customers find suitable service providers at suitable prices. (Examples include Angi, HomeAdvisor, Thumbtack and To8to.) This paper develops a tractable methodology that a platform can use to optimize its match recommendation policy so as to maximize the total value generated by the platform while accounting for the endogeneity of transaction prices, which are determined by the providers and can depend on the platform's match recommendation policy. Despite the complications due to price endogeneity, an optimal match recommendation policy can be computed efficiently using stochastic subgradient descent. Under additional regularity conditions on the distribution of preferences, an optimal policy has a simple form: for each customer segment and each provider, the platform has a certain target on the rate that the provider is recommended to this segment. Any policy that achieves these targets is optimal. Finally, accounting for the endogeneity of prices is crucial: if the platform were to optimize its match recommendations while erroneously assuming that prices are exogenous, then the market is likely to get stuck at a strictly sub-optimal equilibrium, even if the platform were to continually re-optimize its match recommendation policy after prices re-equilibrate.

While online platforms such as Uber, Lyft and Airbnb have upended the transportation and accommodation industries, similar startups have struggled to realize comparable levels of success in other industries. For example, in the home services industry, the startup Homejoy, which aspired to be the Uber for home cleaning, went bankrupt in 2015 despite having raised $40 million of funding and having assembled an impressive engineering team. Among the host of competing platforms in the home services industry, there is no consensus on how to best facilitate matches: some platforms have customers initiate contact, while others have customers post their information and wait for providers to reach out. Other platforms recommend matches and prices based on more sophisticated algorithms.

We consider a setting in which agents and items match dynamically over time. We show that repeated independent lotteries with unlimited entry (which are commonly used in practice) encourage agents to enter many lotteries, and may result in low match value.

We study how much communication is needed to find a stable matching in a two-sided matching market with private preferences. Segal (2007) and Gonczarowski et al.~(2015) showed that in the worst case, any protocol that computes a stable matching requires the communication cost per agent to scale linearly in the total number of agents. In real-world markets with many agents, this communication requirement is implausibly high. This casts doubts on whether stable matching can arise in large markets. We study markets with realistic structure on the preferences and information of agents, and show that in "typical" markets, a stable matching can be found with much less communication effort. In our model, the preferences of workers are unrestricted, and the preferences of firms follow an additively separable latent utility model. Our efficient communication protocol modifies workers-proposing DA, by having firms signal workers they especially like, while also broadcasting qualification requirements to discourage other workers who have no realistic chances from applying. In the special case of tiered random markets, the protocol can be modified to run in two-rounds and involve only private messages. Our protocols have good incentive properties and give insights on how to mediate large matching markets to reduce congestion.

We study the optimal allocation of heterogeneous services without using monetary transfers. Agents have private, multi-dimensional utilities over the services, and a social planner has arbitrary priors on the utilities, which may depend on the agents' observable characteristics. The social planner's goal is to maximize a public objective, which may be complex, taking into account diverse considerations such as social welfare, equity, and system costs. Potential applications include the allocation of seats to public schools, spaces in college dorms or courses, and spots in subsidized housing.

The restless bandit problem is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit (MAB) problem in decision theory. In its ultimate generality, the restless bandit problem is known to be PSPACE-Hard to approximate to any nontrivial factor, and little progress has been made on this problem despite its significance in modeling activity allocation under uncertainty. In this article, we consider the Feedback MAB problem, where the reward obtained by playing each of n independent arms varies according to an underlying on/off Markov process whose exact state is only revealed when the arm is played. The goal is to design a policy for playing the arms in order to maximize the infinite horizon time average expected reward. This problem is also an instance of a Partially Observable Markov Decision Process (POMDP), and is widely studied in wireless scheduling and unmanned aerial vehicle (UAV) routing. Unlike the stochastic MAB problem, the Feedback MAB problem does not admit to greedy index-based optimal policies. We develop a novel duality-based algorithmic technique that yields a surprisingly simple and intuitive (2+ϵ)-approximate greedy policy to this problem. We show that both in terms of approximation factor and computational efficiency, our policy is closely related to the Whittle index , which is widely used for its simplicity and efficiency of computation. Subsequently we define a multi-state generalization, that we term Monotone bandits, which remains subclass of the restless bandit problem. We show that our policy remains a 2-approximation in this setting, and further, our technique is robust enough to incorporate various side-constraints such as blocking plays, switching costs, and even models where determining the state of an arm is a separate operation from playing it. Our technique is also of independent interest for other restless bandit problems, and we provide an example in nonpreemptive machine replenishment. Interestingly, in this case, our policy provides a constant factor guarantee, whereas the Whittle index is provably polynomially worse. By presenting the first O(1) approximations for nontrivial instances of restless bandits as well as of POMDPs, our work initiates the study of approximation algorithms in both these contexts.

In this paper, we consider the restless bandit problem, which is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit problem in decision theory. In its ultimate generality, the restless bandit problem is known to be PSPACE-Hard to approximate to any non-trivial factor, and little progress has been made on this problem despite its significance in modeling activity allocation under uncertainty. We make progress on this problem by showing that for an interesting and general subclass that we term Monotone bandits, a surprisingly simple and intuitive greedy policy yields a factor 2 approximation. Such greedy policies are termed index policies, and are popular due to their simplicity and their optimality for the stochastic multi-armed bandit problem. The Monotone bandit problem strictly generalizes the stochastic multi-armed bandit problem, and naturally models multi-project scheduling where the state of a project becomes increasingly uncertain when the project is not scheduled. We develop several novel techniques in the design and analysis of the index policy. Our algorithm proceeds by introducing a novel “balance” constraint to the dual of a well-known LP relaxation to the restless bandit problem. This is followed by a structural characterization of the optimal solution by using both the exact primal as well as dual complementary slackness conditions. This yields an interpretation of the dual variables as potential functions from which we derive the index policy and the associated analysis.