Sequential Blocked Matching

Nicholas Bishop, Hau Chan, Debmalya Mandal, Long Tran-Thanh

Abstract

We consider a sequential blocked matching (SBM) model where strategic agents repeatedly report ordinal preferences over a set of services to a central planner. The planner's goal is to elicit agents' true preferences and design a policy that matches services to agents in order to maximize the expected social welfare with the added constraint that each matched service can be blocked or unavailable for a number of time periods. Naturally, SBM models the repeated allocation of reusable services to a set of agents where each allocated service becomes unavailable for a fixed duration. We first consider the offline SBM setting, where the strategic agents are aware of their true preferences. We measure the performance of any policy by distortion, the worst-case multiplicative approximation guaranteed by any policy. For the setting with $s$ services, we establish lower bounds of $\Omega(s)$ and $\Omega(\sqrt{s})$ on the distortions of any deterministic and randomised mechanisms, respectively. We complement these results by providing approximately truthful, measured by incentive ratio, deterministic and randomised policies based on random serial dictatorship which match our lower bounds. Our results show that there is a significant improvement if one considers the class of randomised policies. Finally, we consider the online SBM setting with bandit feedback where each agent is initially unaware of her true preferences, and the planner must facilitate each agent in the learning of their preferences through the matching of services over time. We design an approximately truthful mechanism based on the explore-then-commit paradigm, which achieves logarithmic dynamic approximate regret.

1. Introduction

Traditional resource allocation models, such as one-sided matching, typically focus on static, one-shot assignments. However, many modern applications—ranging from cloud computing resource management to recommendation systems—involve repeated interactions over time. A critical feature of these systems is "blocking": once a resource is allocated, it remains unavailable for a certain period. This temporal dependency complicates the design of efficient and truthful mechanisms.

This paper introduces the Sequential Blocked Matching (SBM) framework to model these scenarios. In SBM, a central planner must repeatedly match $s$ services to $n$ strategic agents over $T$ time steps, subject to blocking constraints.

2. The SBM Model

In the SBM model, each service $j \in [s]$, once matched to an agent, becomes unavailable for a fixed number of rounds. Agents have ordinal preferences over these services. The planner's objective is to maximize social welfare—the sum of agents' utilities—while ensuring the mechanism is robust against strategic manipulation.

The paper evaluates mechanisms based on two primary metrics:

  • Distortion: The worst-case ratio between the maximum possible social welfare (under full information) and the welfare achieved by the planner's policy.
  • Incentive Ratio: A measure of truthfulness, representing the maximum factor by which an agent can improve their utility by misreporting their preferences.

3. Offline SBM: Efficiency and Truthfulness

In the offline setting, agents are assumed to know their true preferences. The authors propose two main algorithms:

  • Repeated Random Serial Dictatorship (RRSD): A randomized approach where agents are ordered randomly and greedily select their best available services across the time horizon.
  • Derandomized RRSD (DRRSD): A deterministic variant of the RRSD algorithm.

While Random Serial Dictatorship is perfectly truthful in single-round settings, the temporal coupling in SBM introduces strategic complexities. The authors prove that RRSD and DRRSD achieve an incentive ratio of at least $1 - 1/e$, providing a strong guarantee against manipulation.

4. Online SBM: Learning with Bandit Feedback

In many practical scenarios, agents do not initially know their preferences and must learn them through experience. The authors extend SBM to the bandit setting, where agents receive stochastic rewards upon being matched with a service.

They propose Bandit RRSD (BRRSD), which utilizes an Explore-then-Commit (ETC) paradigm:

  1. Exploration Phase: The planner implements a sequence of matchings to ensure every agent samples every service enough times to form accurate reward estimates.
  2. Exploitation Phase: The planner switches to the RRSD policy using the estimated preferences.

This approach decouples the learning process from the incentive structure, preventing agents from manipulating the exploration phase to gain better long-term assignments.

5. Results and Analysis

The theoretical analysis reveals a significant performance gap between deterministic and randomized mechanisms. Specifically, deterministic mechanisms are limited by a distortion of $\Omega(s)$, whereas randomization allows for a much tighter bound of $\Omega(\sqrt{s})$.

Summary of theoretical bounds for distortion and incentive ratio in offline SBM.

The BRRSD algorithm is shown to achieve logarithmic dynamic approximate regret, indicating that the cumulative loss in welfare relative to an offline oracle grows only logarithmically with time. Furthermore, the exploration phase is shown to be efficient, requiring at most twice the duration of the shortest possible feasible matching sequence.

6. Conclusion

The SBM framework provides a robust model for repeated resource allocation with temporal constraints. By establishing tight bounds on distortion and incentive ratios, this work highlights the power of randomization in achieving efficiency. Future research directions include exploring decentralized matching protocols and adapting the model to environments with evolving agent preferences.

Summary updated

Abstract

We consider a sequential blocked matching (SBM) model where strategic agents repeatedly report ordinal preferences over a set of services to a central planner. The planner's goal is to elicit agents' true preferences and design a policy that matches services to agents in order to maximize the expected social welfare with the added constraint that each matched service can be blocked or unavailable for a number of time periods. Naturally, SBM models the repeated allocation of reusable services to a set of agents where each allocated service becomes unavailable for a fixed duration. We first consider the offline SBM setting, where the strategic agents are aware of their true preferences. We measure the performance of any policy by distortion, the worst-case multiplicative approximation guaranteed by any policy. For the setting with s services, we establish lower bounds of Ω(s) and Ω(√s) on the distortions of any deterministic and randomised mechanisms, respectively. We complement these results by providing approximately truthful, measured by incentive ratio, deterministic and randomised policies based on random serial dictatorship which match our lower bounds. Our results show that there is a significant improvement if one considers the class of randomised policies. Finally, we consider the online SBM setting with bandit feedback where each agent is initially unaware of her true preferences, and the planner must facilitate each agent in the learning of their preferences through the matching of services over time. We design an approximately truthful mechanism based on the explore-then-commit paradigm, which achieves logarithmic dynamic approximate regret.
BibTeX
@inproceedings{bishop2022sequential,
  author = {Nicholas Bishop and Hau Chan and Debmalya Mandal and Long Tran-Thanh},
  title = {{Sequential Blocked Matching}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=pTH1UkWXK_},
}
Figure