*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
