Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Value of Excess Supply in Spatial Matching Markets
363
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study dynamic matching in a spatial setting. Drivers are distributed at random on some interval. Riders arrive in some (possibly adversarial) order at randomly drawn points. The platform observes the location of the drivers, and can match newly arrived riders immediately, or can wait for more riders to arrive. Unmatched riders incur a waiting cost $c$ per period. The platform can match riders and drivers, irrevocably. The cost of matching a driver to a rider is equal to the distance between them. We quantify the value of slightly increasing supply. We prove that when there are $(1+epsilon)$ drivers per rider (for any $epsilon > 0$), the cost of matching returned by a simple greedy algorithm which pairs each arriving rider to the closest available driver is $O(log^3(n))$, where $n$ is the number of riders. On the other hand, with equal number of drivers and riders, even the emph{ex post} optimal matching does not have a cost less than $Theta(sqrt{n})$. Our results shed light on the important role of (small) excess supply in spatial matching markets.
rate research
Read More
We study the problem of matching agents who arrive at a marketplace over time and leave after d time periods. Agents can only be matched while they are present in the marketplace. Each pair of agents can yield a different match value, and the planners goal is to maximize the total value over a finite time horizon. We study matching algorithms that perform well over any sequence of arrivals when there is no a priori information about the match values or arrival times. Our main contribution is a 1/4-competitive algorithm. The algorithm randomly selects a subset of agents who will wait until right before their departure to get matched, and maintains a maximum-weight matching with respect to the other agents. The primal-dual analysis of the algorithm hinges on a careful comparison between the initial dual value associated with an agent when it first arrives, and the final value after d time steps. It is also shown that no algorithm is 1/2-competitive. We extend the model to the case in which departure times are drawn i.i.d from a distribution with non-decreasing hazard rate, and establish a 1/8-competitive algorithm in this setting. Finally we show on real-world data that a modified version of our algorithm performs well in practice.
The Arrow-Debreu extension of the classic Hylland-Zeckhauser scheme for a one-sided matching market -- called ADHZ in this paper -- has natural applications but has instances which do not admit equilibria. By introducing approximation, we define the $epsilon$-approximate ADHZ model, and we give the following results. * Existence of equilibrium under linear utility functions. We prove that the equilibrium satisfies Pareto optimality, approximate envy-freeness, and approximate weak core stability. * A combinatorial polynomial-time algorithm for an $epsilon$-approximate ADHZ equilibrium for the case of dichotomous, and more generally bi-valued, utilities. * An instance of ADHZ, with dichotomous utilities and a strongly connected demand graph, which does not admit an equilibrium. Since computing an equilibrium for HZ is likely to be highly intractable and because of the difficulty of extending HZ to more general utility functions, Hosseini and Vazirani proposed (a rich collection of) Nash-bargaining-based matching market models. For the dichotomous-utilities case of their model linear Arrow-Debreu Nash bargaining one-sided matching market (1LAD), we give a combinatorial, strongly polynomial-time algorithm and show that it admits a rational convex program.
We study dynamic matching in an infinite-horizon stochastic market. While all agents are potentially compatible with each other, some are hard-to-match and others are easy-to-match. Agents prefer to be matched as soon as possible and matches are formed either bilaterally or indirectly through chains. We adopt an asymptotic approach and compute tight bounds on the limit of waiting time of agents under myopic policies that differ in matching technology and prioritization. We find that the market composition is a key factor in the desired matching technology and prioritization level. When hard-to-match agents arrive less frequently than easy-to-match ones (i) bilateral matching is almost as efficient as chains (waiting times scale similarly under both, though chains always outperform bilateral matching by a constant factor), and (ii) assigning priorities to hard-to-match agents improves their waiting times. When hard-to-match agents arrive more frequently, chains are much more efficient than bilateral matching and prioritization has no impact. We further conduct comparative statics on arrival rates. Somewhat surprisingly, we find that in a heterogeneous market and under bilateral matching, increasing arrival rate has a non-monotone effect on waiting times, due to the fact that, under some market compositions, there is an adverse effect of competition. Our comparative statics shed light on the impact of merging markets and attracting altruistic agents (that initiate chains) or easy-to-match agents. This work uncovers fundamental differences between heterogeneous and homogeneous dynamic markets, and potentially helps policy makers to generate insights on the operations of matching markets such as kidney exchange programs.
The Glosten-Milgrom model describes a single asset market, where informed traders interact with a market maker, in the presence of noise traders. We derive an analogy between this financial model and a Szilard information engine by {em i)} showing that the optimal work extraction protocol in the latter coincides with the pricing strategy of the market maker in the former and {em ii)} defining a market analogue of the physical temperature from the analysis of the distribution of market orders. Then we show that the expected gain of informed traders is bounded above by the product of this market temperature with the amount of information that informed traders have, in exact analogy with the corresponding formula for the maximal expected amount of work that can be extracted from a cycle of the information engine. This suggests that recent ideas from information thermodynamics may shed light on financial markets, and lead to generalised inequalities, in the spirit of the extended second law of thermodynamics.
How does supply uncertainty affect the structure of supply chain networks? To answer this question we consider a setting where retailers and suppliers must establish a costly relationship with each other prior to engaging in trade. Suppliers, with uncertain yield, announce wholesale prices, while retailers must decide which suppliers to link to based on their wholesale prices. Subsequently, retailers compete with each other in Cournot fashion to sell the acquired supply to consumers. We find that in equilibrium retailers concentrate their links among too few suppliers, i.e., there is insufficient diversification of the supply base. We find that either reduction of supply variance or increase of mean supply, increases a suppliers profit. However, these two ways of improving service have qualitatively different effects on welfare: improvement of the expected supply by a supplier makes everyone better off, whereas improvement of supply variance lowers consumer surplus.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
