On Extensions of Partial Priorities in School Choice

We consider a school choice matching model where priorities for schools are represented by binary relations that may not be total orders. Even in that case, it is necessary to construct total orders from the priority relations to execute several mechanisms. We focus on the extensions of the priority relations, because a matching that is stable for any extension profile is also stable for the profile of priority relations. We introduce a class of algorithms for deriving one of the extensions of acyclic priority relations and characterize them utilizing the class. We show that if the priorities are partial orders, then for each stable matching for the profile of priority relations, an extension profile for which it is also stable exists. Furthermore, if multiple stable matchings ranked by Pareto dominance exist, there is an extension for which all of these matchings are stable. We provide several applications of these results