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.
]]>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.
]]>