Abstract: We consider centralized dynamic matching markets with finitely many agent types and heterogeneous match values. A network topology determines the feasible matches in the market and the value generated from each match. An inherent trade-off arises between short- and long-term objectives. A social planner may delay match decisions to thicken the market and increase match opportunities to generate high value. This inevitably compromises short-term value, and the planner may match greedily to maximize short-term objectives.

A matching policy is hindsight optimal if the policy can (nearly) maximize the total value simultaneously at all times. We first establish that in multi-way networks, where a match can include more than two agent types, acting greedily is suboptimal, and a periodic clearing policy with a carefully chosen period length is hindsight optimal. Interestingly, in two-way networks, where any match includes two agent types, suitably designed greedy policies also achieve hindsight optimality. This implies that there is essentially no positive externality from having agents waiting to form future matches.

Central to our results is the general position gap, ε, which quantifies the stability or the imbalance in the network. No policy can achieve a regret that is lower than the order of 1/ε at all times. This lower bound is achieved by the proposed policies.

The talk is based on joint work with Suleyman Kerimov and Itai Ashlagi.