Dynamic Type Matching

1. Introduction

• The firm matches heterogeneous demand and supply arriving in random quantities, carrying unmatched units forward while maximizing expected rewards net of waiting-compensation and inventory-holding costs.Source: §1 · p. 1

Main results, applications and implications

• Modified Monge conditions establish priority among neighboring demand–supply pairs, reducing within-period choices to the trade-off between matching now and preserving options for future periods.Source: Main results, applications and… · p. 3
• Both horizontally and vertically differentiated models satisfy the modified Monge condition; in the unidirectional horizontal model, shorter-distance matches have higher priority.Source: Main results, applications and… · pp. 3–4
• With two demand and two supply types, perfect pairs are matched greedily, while imperfect pairs are considered only above sufficient levels and matched down to a threshold.Source: Main results, applications and… · p. 3
• The results extend to generalized capacity management with upgrading and random replenishment.Source: Main results, applications and… · p. 4
• In fixed-route commuter carpooling, matching rewards combine the driver's travel disutility to pickup with the rider's travel utility along the route.Source: Main results, applications and… · p. 4
• For riders and drivers heading to the same destination, matching priority favors a shorter distance to pick up a rider.Source: Main results, applications and… · p. 4
• With quality-based rewards, the optimal policy matches demand and supply types from highest to lowest quality, down to a chosen level.The reward for a pair is the sum of its components’ contributions, which increase with quality; the policy is also called top-down matching or assortative mating.Source: Main results, applications and… · pp. 4–5
• The vertical model generalizes to nonlinear rewards that are not far from additive, and its current-versus-future trade-off can reserve lower-quality types for potential high-quality arrivals.This reservation reduces the chance of losing or delaying matches with high-quality demand or supply that may arrive later.Source: Main results, applications and… · p. 5
• In two special cases—patient demand and supply, and impatient demand with patient supply—the authors derive monotonicity properties and propose an OSA heuristic that beats greedy matching.The one-step-ahead policy is guaranteed to perform better than greedy matching and significantly reduces state-dependency.Source: Main results, applications and… · p. 5
• In dating platforms, dynamic random arrivals under centralized matching imply that agencies may limit current matches while anticipating higher-quality participants.The paper considers the same additive reward structure as prior marriage-market work, but with dynamic random arrivals and a centralized perspective.Source: Main results, applications and… · p. 5
• In organ allocation, the model prioritizes higher-quality organs and sicker patients, and may reject low-quality organs while anticipating better ones, subject to mutual-compatibility constraints.Source: Main results, applications and… · p. 5

2. Literature Review

• The framework generalizes inventory management, revenue management, and joint pricing and inventory control.Unlike those settings, sharing-economy supply is crowdsourced and uncertain.Source: §2 · p. 6
• College admissions and marriage matching seek stable outcomes in static, deterministic settings using submitted preferences, whereas this framework assigns monetary rewards to type-pair matches.Soliciting preferences may be impractical in day-to-day or real-time sharing-economy operations.Source: §2 · p. 6
• Unlike dynamic kidney exchange, which matches compatible patient-donor pairs under intertemporal random arrivals, this model allows unbalanced demand and supply arrivals and maximizes total reward minus cost.The review attributes the dynamic kidney-exchange model to Unver (2010).Source: §2 · p. 7
• Online bipartite matching focuses on online arrivals and competitive ratios, while this framework optimizes expected value and explicitly models inventory.In the online formulation, one side is always present and unmatched arrivals on the other side are lost.Source: §2 · p. 7
• Compared with the reviewed fluid matching and queueing work, this framework studies a stochastic model and optimal decision-making rather than fluid counterparts and performance evaluation.The review notes a shared possibility of waiting for inventory to build up to enable more rewardable future matches.Source: §2 · pp. 7–8

• Across T periods, random quantities of m demand and n supply types arrive, and the platform chooses matches to maximize expected total discounted surplus (reward minus cost).Source: §3 · pp. 8–9
• Demand and supply distributions may be exogenously correlated across periods, but future distributions are assumed independent of current matching decisions; discrete quantities are also supported.Source: §3 · pp. 8–9
• At each observed state, the platform chooses matching quantities, with linear per-unit rewards and nonnegative post-matching demand and supply.Source: §3 · p. 9
• Unmatched demand and supply carry over to the next period at fractions α and β, respectively, while the remainder leaves the system.The carry-over fractions may vary over time without affecting the results.Source: §3 · p. 9
• Waiting costs can be incorporated into matching rewards without changing the optimal policy, by using an updated per-unit benefit for each match.Source: §3 · p. 10
• For continuous states and decisions, the value functions are continuous and concave; with integer-valued states and decisions, concavity is undefined, but optimal decisions still exist and subsequent results hold.Source: §3 · p. 10

4. Structural Properties of the Optimal Policy

• Under the modified Monge condition, an optimal policy exists that prioritizes each pair over neighboring pairs it dominates.The paper also establishes a weaker form of compatibility when only the weak modified Monge condition holds.Source: §4 · pp. 10–12

Optimality of greedily matching a pair of demand and supply.

• A pair that dominates all its neighboring pairs under the modified Monge relation is optimal to match greedily in every period.This condition makes such a pair a “perfect pair”; other pairs are termed imperfect.Source: Optimality of greedily matching a pair… · p. 12
• For spatial types with Euclidean-distance rewards, a same-location pair is perfect when γ_t decreases, while decreasing R_t and γ_t makes that pair greedy each period.The reward is a fixed prize minus distance disutility; the corollary assumes types are uniquely characterized by spatial locations.Source: Optimality of greedily matching a pair… · p. 12
• The structural conditions are satisfied by the paper’s horizontal and vertical models.Source: Optimality of greedily matching a pair… · p. 13
• The results extend to time-dependent carryover rates when unmatched demand and supply carry over at type-independent fractions.The paper states that subsequent results, including Proposition 2, remain true with the corresponding condition changes.Source: Optimality of greedily matching a pair… · p. 13

5. Horizontally Differentiated Types

• Types are horizontally differentiated by location: shorter distance between demand and supply types implies a higher unit matching reward.Source: §5 · p. 13

5.1. Two demand types and two supply types

• For each type k, its same-type pair (k,k) is preferred to either cross-type pair, so each same-type pair is matched as much as possible first.Source: §5.1 · pp. 13–14
• Cross-type matches follow state-dependent match-down-to targets that depend only on the one-dimensional aggregate imbalance, not the full two-dimensional state.Source: §5.1 · pp. 15–16
• Optimal matching first greedily matches same-type pairs, then uses cross-type matches only when residual demand and supply coexist, subject to imbalance-dependent protection levels.Source: §5.1 · p. 15

Patient demand and supply types

• For infinitely patient types (α = β = 1), protection levels vary monotonically with aggregate imbalance, with increasing and decreasing rates no higher than 1.Source: Patient demand and supply types · p. 16
• When aggregate imbalance is nonnegative, greater demand excess makes it more imperative to consume demand by lowering the protection level for supply.Source: Patient demand and supply types · p. 16
• When IB < 0, supply is in excess; as IB rises, consuming that excess becomes less imperative, implying a higher protection level for demand.The described protection-level relations increase with IB at rates capped by 1.Source: Patient demand and supply types · p. 16
• With integer demand and supply quantities, compare the protection level with the next higher level and choose whichever yields higher matching rewards.The passage presents this as an implementation of Proposition 4.Source: Patient demand and supply types · p. 16
• Proposition 4 generalizes from α = β = 1 to arbitrary α and β when the two carry-over rates are equal.Source: Patient demand and supply types · p. 16

Impatient demand types and patient supply types

• With α = 0 and β = 1, unmatched demand is lost, and the round-2 optimal policy uses state-independent supply protection levels, targeting type 2 when z1,z2 > 0 and type 1 when both are negative.The policy reduces the targeted supply toward its protection level as far as available demand allows.Source: Impatient demand types and patient… · pp. 16–17
• For z1 > 0 and z2 > 0, type 1 demand is matched with type 2 supply in round 2; with ample type 1 demand, supply falls to its protection level if above it, otherwise no matching occurs.With low type 1 demand, type 2 supply can be reduced by at most z1.Source: Impatient demand types and patient… · p. 17

5.2. Multiple demand types and supply types

• For directed distance on a line, with matching reward decreasing linearly in reachable distance, the optimal policy matches shorter-distance pairs first along either the demand or supply side.The directed distance is measured by traveling from the supply location toward the demand location.Source: §5.2 · pp. 17–18
• If Rt decreases over time and no other types lie between a reachable demand-supply pair, the two types should be matched greedily.Source: §5.2 · p. 18
• The priority hierarchy groups pairs into tiers, matches each tier before the next, and leaves neighboring pairs unmatched when a higher-tier pair remains partially unmatched.The passage defines tiers recursively from pairs not dominated by neighboring pairs.Source: §5.2 · p. 18

A heuristic idea

• The heuristic reserves demand and supply for types between a pair, not for types outside it, and estimates the pair’s match using a subproblem with imbalance-dependent protection levels.The subproblem includes the pair and the types between them; its protection levels depend on the imbalance between the pair’s demand and supply.Source: A heuristic idea · p. 19
• The proposed procedure processes pairs by priority tier, and the order within a tier does not affect other pairs there, although computing each subproblem’s protection levels remains challenging.Source: A heuristic idea · p. 19

Commuter car pooling platforms

• For commuter pooling along a route, a match has higher priority when the rider is closer to the driver, and when the driver is closer to the rider.The setting considers riders sharing a destination, with drivers picking them up along the route.Source: Commuter car pooling platforms · p. 20

Product/Service general upgrading

• General upgrading indexes product classes by descending quality: class i demand can use class i or higher-class k≤i products, but not lower-quality class ℓ>i products.A class i product is intended for class i demand, and a higher-class product is more desirable than a lower one for that demand.Source: Product/Service general upgrading · pp. 20–21
• General upgrading places demand and product classes on a line, assigning products to the same or a closer customer class; upgrade reward subtracts the extra product cost from same-class unit profit.The extra cost is represented by the distance between the requested and assigned classes.Source: Product/Service general upgrading · p. 21

One-level product upgrading

• With only one-level upgrading allowed, the problem differs structurally from general upgrading, and prioritizing intended matches may not be optimal when supply is random.The concern is whether to prioritize (i,i) over adjacent upgrades (i,i−1) and (i+1,i).Source: One-level product upgrading · p. 22
• PIOU policies greedily match intended pairs (i,i) before the adjacent upgrade pairs (i,i−1) and (i+1,i).PIOU denotes the set of policies that prioritize intended pairs over upgrading.Source: One-level product upgrading · p. 22
• A policy prioritizing intended pairs over one-level upgrades retains at least 50% of the total expected reward under the optimal matching policy.The paper states that enforcing the best policy in PIOU limits the optimality loss to 50%.Source: One-level product upgrading · p. 22

6. Vertically Differentiated Demand and Supply Types

• Higher-quality supply (and symmetrically demand) takes priority across counterpart types, producing top-down matching from the highest-quality types down to a match-down-to level.The result follows under Assumption 3.Source: §6 · p. 23
• In transformed cumulative states, types i and j match only when their intervals overlap; matching then reduces both inventories toward state-dependent protection levels.The policy reduces demand and supply to their respective protection levels, or as close as possible.Source: §6 · p. 24

6.1. The one-step-ahead policy

• The one-step-ahead policy optimizes current matching using a next-period value estimate and assumes greedy matching thereafter; it has higher expected reward than the greedy policy.The estimate evaluates reward under greedy matching from the period after next through the horizon.Source: §6.1 · pp. 24–25

6.2. Patient demand and supply types

• With infinitely patient demand and supply, optimal total matching quantity increases in every demand and supply level at a rate no greater than one, and is more sensitive to higher-quality types.These properties concern the optimal total matching quantity as a function of the state.Source: §6.2 · p. 25
• Under the one-step-ahead policy for patient types, protection levels depend only on aggregate imbalance, and a demand-supply pair is matched only when its cumulative inventories overlap.The policy aims to reduce total available demand and supply toward the imbalance-dependent protection levels.Source: §6.2 · pp. 25–26
• Proposition 11 limits state-dependence: the protection levels depend on aggregate demand-supply imbalance rather than the full state (x,y).Source: §6.2 · p. 26
• For a prioritized pair, the one-step-ahead policy either skips that pair and lower-quality matches or matches the pair fully or down to its protection levels.The stated protection levels vary with aggregate imbalance, with the demand-side level increasing and the supply-side level decreasing at rates no greater than 1.Source: §6.2 · p. 26

6.3. Impatient demand and patient supply

• With impatient demand and patient supply, Proposition 10 remains true when demand is lost each period and supply is fully carried over; it also holds for any supply carry-over rate β in (0,1).Because demand does not carry over, the dynamic program has no demand state x, and the optimal policy does not depend on x.Source: §6.3 · p. 27

6.4. Non-additive reward structure

• Under Assumption 4, which requires rewards to decrease in type indices and be supermodular, Propositions 8 and 10 remain true.Source: §6.4 · p. 27
• Assumption 4 yields a priority policy favoring higher-quality types, and Proposition 10 holds for both patient demand and supply and patient supply with impatient demand.The passage states that the assumptions ensure an optimal policy respecting Ms, giving higher-quality demand or supply priority over lower-quality types.Source: §6.4 · p. 27

7. Conclusion

• The framework generalizes the Monge sequence with modified Monge conditions that establish when demand-supply pairs can be prioritized optimally.It considers stochastic, dynamic matching of heterogeneous types in discrete time.Source: §7 · p. 28
• Under vertical and unidirectional horizontal rewards, optimal matching follows a priority structure and uses match-down-to thresholds for each demand-supply pair.Quality determines priority under vertical rewards, while distance determines priority under unidirectional horizontal rewards.Source: §7 · p. 28
• The priority-and-threshold structure generalizes priority structures in balanced deterministic transportation and threshold policies in inventory management and quantity-based revenue management.Examples include base-stock levels and protection levels.Source: §7 · p. 28
• The framework generalizes inventory rationing and dynamic capacity allocation with upgrading by allowing multiple exogenous supply streams and arbitrary substitution.The authors identify joint pricing and matching decisions and competition among platforms as directions for further operational-level research.Source: §7 · p. 28

Weak compatibility

• Theorem 2 guarantees an optimal policy that weakly respects ≻M: a dominated pair is not matched while demand for its dominant pair remains.This is a conditional priority guarantee, not a requirement to match every dominant pair first.Source: Appendix Weak compatibility · p. 28
• The weak guarantee does not require a dominant pair to be matched before every dominated pair; an example shows cross-pair competition can prevent that ordering.The example has one pair dominating two others, yet matching one of those other pairs can leave no demand or supply for the dominant pair.Source: Appendix Weak compatibility · p. 29
• The stronger relation ≻Ms is sufficient to ensure that an optimal policy prioritizes dominant pairs over dominated pairs, unlike the weaker ≻M guarantee.The appendix contrasts the stronger relation's priority hierarchy with the weaker relation, which requires less of the reward structure.Source: Appendix Weak compatibility · pp. 29–30
• The partial relation ≻M is robustly necessary for Theorem 2: failure of its associated conditions permits a demand-and-supply instance whose optimal policy fails Definition 4’s property; ≻Ms is likewise robustly necessary for Theorem 1.Source: Appendix Weak compatibility · p. 29

Computation of protection levels in Heuristic 1

• For Heuristic 1 protection levels, the appendix consolidates non-i demand and non-j supply into artificial types, greedily matches other pairs by distance, then reduces the subproblem to a 2 × 2 model.The matching process stops just before matching (i,j), the lowest-priority pair in the subproblem.Source: Appendix Weak compatibility · pp. 30–31

A. Proofs

• Transfers from a dominated pair to a dominant pair weakly improve expected reward, and repeated transfers yield an optimal decision with the desired priority properties.Each transfer is feasible and weakly dominates the previous decision; the procedure terminates in finitely many steps or converges to an optimal decision.Source: A. Proofs · pp. 36–37
• Theorem 1’s proof adds transfers between pairs dominated along both type dimensions and repeats them to obtain a feasible decision satisfying the stated properties.If the procedure starts from an optimal decision, the resulting decision is also optimal because it weakly dominates the initial one.Source: A. Proofs · pp. 37–38
• Greedy matching of pair (i,j) is optimal when that pair dominates all its neighboring pairs under ≻Ms.The proof uses induction over periods and shows that increasing the matching quantity for (i,j) can weakly improve an optimal decision that does not match it greedily.Source: A. Proofs · pp. 38–39
• When rewards decrease over time, the distance-based priority relation follows from the triangle inequality and the resulting dominance of same-location matches.The proof shows that (i,i) dominates (i,j′) and (i′,j), then identifies the resulting relation with ≻Ms.Source: A. Proofs · p. 39
• Lemma A.3 establishes by induction a nonnegative inequality for 0 ≤ ε′ ≤ ε, with terminal-period r_{T+1,ij} defined as zero.The proof begins with the terminal case and advances by induction.Source: A. Proofs · p. 40
• The displayed expressions are L♮-concave with respect to all variables, although the cited passage does not identify them as ˜U_t or state conditions α = β = 1.Source: A. Proofs · p. 43
• The proof uses induction, establishing supermodularity and increasing differences within and across four inventory-sign regions.It establishes the property within each region and then checks it across region boundaries.Source: A. Proofs · p. 44
• The cited statements report d,+ increasing in IB and pt,IB, s,+ decreasing in IB, and t increasing in z1, with increases in z1 at a rate no greater than 1.Source: A. Proofs · p. 46
• For positive z1 and z2, Proposition 5 proves it is optimal to reduce type 2 supply by matching type 1 demand with type 2 supply; for negative values, reduce type 1 supply instead.The negative-state case uses matching of type 2 demand with type 1 supply.Source: A. Proofs · pp. 46–47
• Lemma 1 proves that, along the direction from o to d, the matching pair with the closer demand type has priority over the pair with the farther demand type.The proof compares distances to supply type j and concludes that the closer demand type’s pair has higher priority.Source: A. Proofs · p. 47
• Proposition 6 derives its first part from Lemma 1 and Theorem 1, and its second from decreasing R_t and Proposition 2.The proof says decreasing R_t over time ensures the required reward condition.Source: A. Proofs · p. 47
• Proposition 7 proves that any feasible policy can be transformed into one that greedily matches type k demand with type k supply.Its construction transfers quantities from lower-priority pairs to higher-priority pairs and proceeds by induction across periods.Source: A. Proofs · p. 48
• The constructed policy earns at least half the total reward of the original policy.The proof repeatedly modifies matching decisions and then constructs a policy whose total reward is at least one-half of the original policy's reward.Source: A. Proofs · p. 50
• For additive rewards, the proof establishes that matching pair (i,j) has priority over (i′,j) when i > i′.The proof says the symmetric statement follows by symmetry.Source: A. Proofs · p. 50
• Extending the one-step-ahead policy through period t improves on switching to greedy matching in period t, so the one-step-ahead policy outperforms greedy matching overall.The proof compares policies that coincide through period t−1; in period t, one-step-ahead is optimal given a greedy continuation, whereas greedy matching is suboptimal for that continuation.Source: A. Proofs · pp. 50–51
• When α = β = 1, the proof establishes L♮-concavity of the value and decision functions and derives that the optimal matching quantity is nondecreasing in transformed inventory.The appendix uses the concavity result to obtain monotonicity of the optimizer in transformed state (x̃, ỹ).Source: A. Proofs · pp. 51–52
• With vertically differentiated types, greedy matching follows a top-down structure without reserving demand or supply.Lemma A.6 further states that the greedy-policy value depends only on specified inventory aggregates, with a symmetric dependence for demand and supply.Source: A. Proofs · pp. 52–53
• Top-down matching uses type i demand with type j supply only when x̃_i > ỹ_{j−1} and ỹ_j > x̃_{i−1}, beginning at the larger preceding level and ending at the smaller current level.If either condition fails, the corresponding type is exhausted before the pair is used.Source: A. Proofs · p. 54
• Within that matching range, the change in expected reward depends only on the remaining levels of the last demand and supply types, x̃_m − Q and ỹ_n − Q.The preceding entries of both residual vectors are zero throughout this range, reducing the optimization to those two remaining levels.Source: A. Proofs · p. 56
• The one-step-ahead policy chooses an aggregate-demand target for matching i with j within the interval defined by the pair’s preceding and current levels.The proof expresses the target-level optimization in terms of aggregate demand and supply after matching quantity Q.Source: A. Proofs · p. 56

B. Connection between weak and strong compatibility

• Any policy weakly respecting ≻M can be transformed into one that strongly respects ≻M without changing its post-matching levels.The construction adjusts matching quantities for pairs ordered by ≻M.Source: B. Connection between weak and strong… · p. 57
• An optimal policy has the same post-matching levels as a strongly ≻M-respecting policy, and solving a single-period transportation problem each period recovers an optimal policy.Both policies consume the same demand and supply in each period because their post-matching levels are identical.Source: B. Connection between weak and strong… · p. 57
• Although a weakly respecting policy differs from a strongly respecting one by a single-period transportation problem, finding the latter by restricting the search is challenging.The passage describes this limitation for policies strongly respecting M.Source: B. Connection between weak and strong… · p. 57

C. Accounting for waiting costs

• Problem (W), with waiting costs for unmatched demand and supply, and Problem (NW), with zero waiting costs and adjusted matching rewards, share the same optimal matching policy.Proposition C.1 establishes their equivalence.Source: C. Accounting for waiting costs · p. 57
• For the same feasible matching decisions, total reward in Problem (NW) differs from reward less waiting costs in Problem (W) by a constant.The proof establishes this relationship for each demand-and-supply realization, so the difference does not alter which matching policy is optimal.Source: C. Accounting for waiting costs · pp. 59–60

• When z1 and z2 are nonnegative, 0 ≤ q ≤ min{z1,z2}; when both are negative, 0 ≤ −q ≤ min{−z1,−z2}.Source: D. An alternative formulation of the 2… · p. 60
• For pre-round-2 state z=(z1,z2), feasible choices form the lattice M(z)={q: 0≤q≤min(z1,z2) or max(z1,z2)≤q≤0 or q=0}; imperfect-pair matching requires z1z2≥0.Source: D. An alternative formulation of the 2… · p. 60
• J_t(q,z) denotes expected reward from round 2 of period t through T under choice q, while U_t(z) is the optimal expected reward over that horizon.Source: D. An alternative formulation of the 2… · p. 61
• The reformulated value U_t(z) is concave in z, and J_t(q,z) is concave in q for each fixed z.Source: D. An alternative formulation of the 2… · p. 61

E. An alternative formulation of the vertical model

• The reformulation uses total matching quantity Q as the decision variable, constrained by the minimum transformed demand and supply totals.The transformed system state replaces the original state representation.Source: E. An alternative formulation of the… · pp. 61–62
• Under top-down matching, combined demand types 1 through i consume min(˜x_i,Q), determining type i’s consumption from the difference between successive cumulative amounts.Source: E. An alternative formulation of the… · p. 62
• After matching, transformed remaining demand and supply are reduced by Q, and next-period transformed states add new arrivals to retained quantities scaled by α and β.The retained quantities are the positive parts of the post-matching levels.Source: E. An alternative formulation of the… · p. 62
• The transformed value function decreases in ˜x_i for i=1,…,m−1 and in ˜y_j for j=1,…,n−1.This monotonicity is stated in Lemma E.9.Source: E. An alternative formulation of the… · p. 63

F. One-step-ahead policy for the vertical model

• The policy chooses the current-period decision to maximize its immediate reward plus the future expected reward under greedy matching from the next period to the horizon.Thus, the continuation value is evaluated assuming greedy matching thereafter.Source: F. One-step-ahead policy for the… · p. 64
• The greedy-policy value function is decreasing in each demand and supply state coordinate and is concave in the state.These properties are established in Lemmas F.11 and F.12.Source: F. One-step-ahead policy for the… · p. 65
• The one-step-ahead policy has a top-down structure in every period: lower-quality types are not used unless all higher-quality types are fully used.This applies to both demand and supply types.Source: F. One-step-ahead policy for the… · p. 66
• The top-down structure means the matching decision is fully determined by total matching quantity Q, reducing each period’s choice to a one-dimensional problem.The current-period quantity is chosen while greedy matching is enforced from period t + 1 onward.Source: F. One-step-ahead policy for the… · p. 67
• The optimal quantity Q* maximizes a concave objective F_t(Q, x̃, ỹ), representing expected rewards through period T for using Q now and matching greedily thereafter.The proposition states both that Q* solves this problem and that F_t is concave in Q.Source: F. One-step-ahead policy for the… · pp. 67–68