Back to activities
DS4DM Coffee Talk

Maximum Matching with Consecutive Acceptance Intervals


Apr 24, 2023   11:00 AM — 12:00 PM

Szilvia Papai Concordia University, Canada

Szilvia Papai

Presentation on YouTube.

We consider a one-to-one matching market where each agent is to be matched to an object from the set of acceptable objects for this agent, and the acceptable set is consecutive with respect to a fixed “objective” ranking of the objects. The profile of consecutive acceptance intervals is assumed to be commonly known. Each agent has a strict individual preference ranking over the objects in her acceptance interval, which is independent of the common ranking of the objects and assumed to be private information. We first study maximum matchings, which depend on the consecutive interval profile only, and propose a simple algorithm for finding a maximum matching at an arbitrary interval profile. We also characterize maximum matchings for arbitrary acceptance intervals. We then investigate serial dictatorships and show first that for some interval profiles there is no serial dictatorship which always yields a maximum matching. We characterize all the interval profiles for which such a maximum serial dictatorship exists and find all the maximum serial dictatorships in terms of agent permutations that produce a maximum matching. These rules are Pareto-optimal and group-strategyproof.

Federico Bobbio organizer
Defeng Liu organizer
Léa Ricard organizer


Hybrid activity at GERAD
Zoom et salle 4488
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour

Montréal Québec H3T 1J4

Associated organization