On Manipulablity of Random Serial Dictatorship in Sequential Matching with Dynamic Preferences

Hadi Hosseini, Kate Larson, Robin CohenAAAI 2015 · DOI

Abstract

Random Serial Dictatorship (RSD) is a cornerstone mechanism for fair and strategyproof allocation in static matching problems. However, real-world resource allocation often occurs sequentially, where current assignments influence future preferences. This paper investigates the robustness of RSD in such dynamic environments. We prove that while sequential RSD maintains strategyproofness under static preferences, this property fails when preferences are dynamic. Through a formal framework and a specific counterexample, we demonstrate that agents can strategically misreport their current preferences to achieve a stochastically dominant outcome in the long run.

Introduction

Matching mechanisms without monetary transfers are essential for allocating public resources like school seats, dormitory rooms, or organ transplants. In static, one-shot scenarios, Random Serial Dictatorship (RSD) is widely regarded as the gold standard. By randomly ordering agents and allowing them to pick their most preferred available item, RSD ensures both ex-post efficiency and strategyproofness—meaning no agent can benefit from lying about their preferences.

However, many matching problems are inherently sequential. A student's dorm assignment this year may influence their preferences for next year. Despite its success in static settings, the performance of RSD in these dynamic contexts remains under-explored. This paper formally analyzes whether the "honesty is the best policy" guarantee of RSD persists when preferences evolve over time.

Theoretical Framework

To evaluate sequential matching, we define a dynamic environment where preferences transition based on current assignments. Key components of this framework include:

  • Global Strategyproofness: We extend the notion of strategyproofness to the entire sequence. A mechanism is globally strategyproof if being truthful at every step is a dominant strategy, considering the expected utility over all future periods.
  • Recursive Expected Probability: We introduce a formula to calculate the probability of an agent receiving an item of a certain rank or better across a sequence of time steps. This calculation incorporates a "transition kernel," which models how an agent's preferences shift from one state to another based on their current allocation.
  • Stochastic Dominance: Because RSD is a randomized mechanism, we compare outcomes using first-order stochastic dominance. An agent prefers one distribution of outcomes over another if it offers a higher probability of receiving better-ranked items without increasing the risk of receiving worse ones.

The Failure of Strategyproofness

The central finding of this research is a sharp distinction between static and dynamic preferences. While sequential RSD is globally strategyproof if preferences are fixed (Theorem 1), this guarantee evaporates in dynamic settings (Theorem 2).

The failure of strategyproofness arises from what we might call the "Static Trap": a mechanism that is locally strategyproof in a single round can be manipulated when the time dimension is introduced. In a dynamic setting, an agent might perform a "strategic sacrifice"—intentionally misreporting their preference to receive a less-desired item today if that assignment increases the probability of receiving a highly-coveted item in the future.

Counterexample Analysis

The paper provides a concrete counterexample involving three agents and three objects over two periods to illustrate this manipulability.

Preference profiles in the counterexample showing Agent 3's truthful vs. misreported preferences.

In this scenario, Agent 3 can gain an advantage by misreporting their ranking of objects $b$ and $c$. By lying about their current preference (as shown in the transition from $\succ_3$ to $\hat{\succ}_3$ in the figure), Agent 3 alters the probability distribution of future matchings. The resulting distribution stochastically dominates the outcome they would have received by being truthful, proving that RSD is manipulable when preferences are dynamic.

Conclusion and Future Directions

Our results highlight a fundamental tension between efficiency and strategyproofness in dynamic resource allocation. The manipulability of RSD suggests that simply repeating static mechanisms is insufficient for complex, temporal environments.

Future work should focus on designing mechanisms that account for temporal dependencies and transition kernels. This includes exploring "approximate" strategyproofness or mechanisms that are robust even when agents have imperfect information about their future preference states. The goal is to move beyond simple repeated RSD toward mechanisms that can handle the complexity of dynamic preferences more robustly.

Summary updated

BibTeX
@inproceedings{hosseini2015manipulablity,
  author = {Hadi Hosseini and Kate Larson and Robin Cohen},
  title = {{On Manipulablity of Random Serial Dictatorship in Sequential Matching with Dynamic Preferences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9744},
}
Figure