On the Optimality of Greedy Policies in Dynamic Matching
研究了有限类型和异质匹配值的集中式动态双向匹配市场，证明了适当设计的贪婪策略（如贪婪最长队列策略和贪婪静态优先级策略）能实现事后最优，即几乎在所有时刻最大化总匹配价值。
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.