Matching with Dynamic Ordinal Preferences

Authors

  • Hadi Hosseini University of Waterloo
  • Kate Larson University of Waterloo
  • Robin Cohen University of Waterloo

DOI:

https://doi.org/10.1609/aaai.v29i1.9329

Keywords:

Matching, Random Assignment, Strategyproofness, Dynamic Preferences, Mechanism Design

Abstract

We consider the problem of repeatedly matching a set of alternatives to a set of agents with dynamic ordinal preferences. Despite a recent focus on designing one-shot matching mechanisms in the absence of monetary transfers, little study has been done on strategic behavior of agents in sequential assignment problems. We formulate a generic dynamic matching problem via a sequential stochastic matching process. We design a mechanism based on random serial dictatorship (RSD) that, given any history of preferences and matching decisions, guarantees global stochastic strategyproofness while satisfying desirable local properties. We further investigate the notion of envyfreeness in such sequential settings.

Downloads

Published

2015-02-16

How to Cite

Hosseini, H., Larson, K., & Cohen, R. (2015). Matching with Dynamic Ordinal Preferences. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9329

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms