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.

Introduction

In classic one-sided matching problems, such as assigning students to dormitories or tasks to workers, the allocation is typically treated as a one-off event. However, many real-world scenarios involve repeated resource allocation where resources are reusable but temporarily unavailable after use. For instance, in cloud computing platforms, once a GPU is assigned to a specific user's task, it remains "blocked" for several rounds until that task is completed.

This paper introduces the Sequential Blocked Matching (SBM) model to address these dynamics. The central planner faces two primary challenges: an Information Gap, where agents only provide ordinal rankings rather than cardinal utilities, and Strategic Behavior, where agents may misreport preferences to secure better services in future rounds when certain items become unblocked. We investigate how to maximize social welfare under these constraints in both offline (known preferences) and online (unknown preferences) settings.

Mechanism Design for Offline SBM

In the offline setting, agents are aware of their true preferences but may act strategically. The authors build their solutions on the foundation of Random Serial Dictatorship (RSD), a classic mechanism where agents take turns selecting their favorite available items. To adapt this to the SBM model, two primary mechanisms are proposed:

  1. Repeated Random Serial Dictatorship (RRSD): A randomized greedy approach for the offline setting. It selects a random permutation of agents; each agent then "claims" their favorite available service for as many future time slots as possible without violating existing blocking constraints.
  2. Derandomized RRSD (DRRSD): A deterministic variant that utilizes a specific set of permutations to ensure that every agent receives a fair opportunity to access their top choices over time.

Theoretical Performance and Distortion

The performance of these mechanisms is evaluated using two key metrics: Distortion (the loss in social welfare due to having only ordinal information) and the Incentive Ratio (a measure of approximate truthfulness, representing how much an agent can gain by lying).

Summary of theoretical bounds for distortion and incentive ratios in deterministic and randomized SBM mechanisms.

As shown in the table above, there is a fundamental performance gap between deterministic and randomized policies. While deterministic mechanisms are limited to a distortion of $\Omega(s)$, randomized policies achieve a significantly better distortion of $O(\sqrt{s})$. Regarding truthfulness, both the DRRSD and RRSD mechanisms achieve an incentive ratio of $1 - 1/e$. This bound, derived from the mathematics of greedy interval scheduling, implies that an agent cannot gain more than approximately 36% extra utility through strategic misreporting.

Online SBM: Learning with Bandit Feedback

In many practical applications, agents may not initially know their own preferences. The authors address this in the online SBM setting using a Bandit RRSD (BRRSD) mechanism based on the Explore-then-Commit (ETC) paradigm:

  • Exploration Phase: The planner implements a uniform allocation strategy, allowing agents to learn the true rewards and utilities of various services through direct experience.
  • Commitment Phase: Once preferences are sufficiently clear, the planner transitions to the RRSD mechanism to maximize welfare based on the learned rankings.

By decoupling the learning and matching phases, the mechanism prevents agents from strategically manipulating their reports while they are still uncertain. The BRRSD algorithm achieves logarithmic dynamic approximate regret, meaning the average performance loss compared to an omniscient oracle diminishes rapidly over time.

Conclusion and Future Directions

This work establishes a comprehensive framework for sequential matching with blocking constraints. The results highlight the power of randomization in reducing distortion and provide robust mechanisms for both known and unknown preference environments.

Future research may extend this model to account for dynamic preferences that evolve over time, decentralized control structures where agents interact autonomously, or two-sided matching markets where services also have preferences over agents. Additionally, exploring stochastic blocking durations—rather than fixed time periods—remains an open and promising area for investigation.

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 \emph{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 \emph{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 \emph{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