An official website of the United States government
A core tension in the operations of online marketplaces is between segmentation (wherein platforms can increase revenue by segmenting the market into ever smaller sub-markets) and thickness (wherein the size of the sub-market affects the utility experienced by an agent). An important example of this is in dynamic online marketplaces, where buyers and sellers, in addition to preferences for different matches, also have finite patience (or deadlines) for being matched. We formalize this trade-off via a novel optimization problem that we term as 'Two-sided Facility Location': we consider a market wherein agents arrive at nodes embedded in an underlying metric space, where the distance between a buyer and seller captures the quality of the corresponding match. The platform posts prices and wages at the nodes, and opens a set of virtual clearinghouses where agents are routed for matching. To ensure high match-quality, the platform imposes a distance constraint between an agent and its clearinghouse; to ensure thickness, the platform requires the flow to any clearinghouse be at least a pre-specified lower bound. Subject to these constraints, the goal of the platform is to maximize the social surplus subject to weak budget balance, i.e., profit being non-negative. Our work characterizes the complexity of this problem by providing both hardness results as well as algorithms for this setting; in particular, we present an algorithm that for any constant ε > 0 yields a (1 + ε ) approximation for the gains from trade, while relaxing the match quality (i.e., maximum distance of any match) by a constant factor.
more »
« less
Asymptotically Optimal Control of a Centralized Dynamic Matching Market with General Utilities
The utility of a match in a two-sided matching market often depends on a variety of characteristics of the two agents (e.g., a buyer and a seller) to be matched. In contrast to the matching market literature, this utility may best be modeled by a general matching utility distribution. In “Asymptotically Optimal Control of a Centralized Dynamic Matching Market with General Utilities,” Blanchet, Reiman, Shah, Wein, and Wu consider general matching utilities in the context of a centralized dynamic matching market. To analyze this difficult problem, they combine two asymptotic techniques: extreme value theory (and regularly varying functions) and fluid asymptotics of queueing systems. A key trade-off in this problem is market thickness: Do we myopically make the best match that is currently available, or do we allow the market to thicken in the hope of making a better match in the future while avoiding agent abandonment? Their asymptotic analysis derives quite explicit results for this problem and reveals how the optimal amount of market thickness increases with the right tail of the matching utility distribution and the amount of market imbalance. Their use of regularly varying functions also allows them to consider correlated matching utilities (e.g., buyers have positively correlated utilities with a given seller), which is ubiquitous in matching markets.
more »
« less
- PAR ID:
- 10483203
- Publisher / Repository:
- Operations Research
- Date Published:
- Journal Name:
- Operations Research
- Volume:
- 70
- Issue:
- 6
- ISSN:
- 0030-364X
- Page Range / eLocation ID:
- 3355 to 3370
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Hindsight Optimality in Two-Way Matching Networks In “On the Optimality of Greedy Policies in Dynamic Matching”, Kerimov, Ashlagi, and Gurvich study centralized dynamic matching markets with finitely many agent types and heterogeneous match values. A matching policy is hindsight optimal if the policy can (nearly) maximize the total value simultaneously at all times. The article establishes that suitably designed greedy policies are hindsight optimal in two-way matching networks. This implies that there is essentially no positive externality from having agents waiting to form future matches. Proposed policies include the greedy longest-queue policy, with a minor variation, as well as a greedy static priority policy. The matching networks considered in this work satisfy a general position condition. General position is a weak (but necessary) condition that holds when the static-planning problem (a linear program that optimizes the first-order matching rates) has a unique and nondegenerate optimal solution.more » « less
-
Abstract We consider the problem of optimal investment with intermediate consumption in a general semimartingale model of an incomplete market, with preferences being represented by a utility stochastic field. We show that the key conclusions of the utility maximization theory hold under the assumptions of no unbounded profit with bounded risk and of the finiteness of both primal and dual value functions.more » « less
-
null (Ed.)We study the dynamic assortment planning problem, where for each arriving customer, the seller offers an assortment of substitutable products and the customer makes the purchase among offered products according to an uncapacitated multinomial logit (MNL) model. Because all the utility parameters of the MNL model are unknown, the seller needs to simultaneously learn customers’ choice behavior and make dynamic decisions on assortments based on the current knowledge. The goal of the seller is to maximize the expected revenue, or, equivalently, to minimize the expected regret. Although dynamic assortment planning problem has received an increasing attention in revenue management, most existing policies require the estimation of mean utility for each product and the final regret usually involves the number of products [Formula: see text]. The optimal regret of the dynamic assortment planning problem under the most basic and popular choice model—the MNL model—is still open. By carefully analyzing a revenue potential function, we develop a trisection-based policy combined with adaptive confidence bound construction, which achieves an item-independent regret bound of [Formula: see text], where [Formula: see text] is the length of selling horizon. We further establish the matching lower bound result to show the optimality of our policy. There are two major advantages of the proposed policy. First, the regret of all our policies has no dependence on [Formula: see text]. Second, our policies are almost assumption-free: there is no assumption on mean utility nor any “separability” condition on the expected revenues for different assortments. We also extend our trisection search algorithm to capacitated MNL models and obtain the optimal regret [Formula: see text] (up to logrithmic factors) without any assumption on the mean utility parameters of items.more » « less
-
In 1979, Hylland and Zeckhauser [26] gave a simple and general mechanism for a 6 one-sided matching market, given cardinal utilities of agents over goods. They use the power of a 7 pricing mechanism, which endows their mechanism with several desirable properties – it produces an 8 allocation that is Pareto optimal and envy-free, and the mechanism is incentive compatible in the 9 large. It therefore provides an attractive, off-the-shelf method for running an application involving 10 such a market. With matching markets becoming ever more prevalent and impactful, it is imperative 11 to characterize the computational complexity of this mechanism. 12 We present the following results: 13 1. A combinatorial, strongly polynomial time algorithm for the dichotomous case, i.e., 0/1 14 utilities, and more generally, when each agent’s utilities come from a bi-valued set. 15 2. An example that has only irrational equilibria; hence this problem is not in PPAD. 16 3. A proof of membership of the problem in the class FIXP; as a corollary we get that an 17 HZ equilibrium can always be expressed via algebraic numbers. For this purpose, we give 18 a new proof of the existence of an HZ equilibrium using Brouwer’s fixed point theorem; 19 the proof of Hylland and Zeckhauser used Kakutani’s fixed point theorem, which is more 20 involved. 21 4. A proof of membership of the problem of computing an approximate HZ equilibrium in the 22 class PPAD.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1287/opre.2021.2186
