Discussion of "Matching with Minimal Priority Rights" by Szilvia Pápai

Assigning a seat

Two-sided matching problems with rather different two sides are fairly common. Of course I do not mean the man-woman dichotomy, but rather schools and pupils and offices and staff members. Unlike most authors in the matching literature, Pápai uses this extra info to design a class of matching rules where the two sides are not acting the same. Here are my summary and comments as presented at the annual congress of the Hungarian Society for Economics, 20-21 December, 2011, Budapest.


In two-sided matching problems we study the grouping of elements of two sets into pairs consisting of one element from each set. The classical example is the marriage problem, but well known applications include the matching between schools and pupils or kidney donors and patients. There are arguments in favour of centralised matching algorithms. These work on the basis of preferences declared by those involved in the matching and the pairing, the actual matching is aimed at trying to satisfy these requests. The question is then which algorithms should be used. We study matching algorithms assuming that all preferences are possible, and that they should work well under all possible preference-profiles.

There are a handful of natural properties that a matching algorithm could or should satisfy. These include various versions of sincerity in declaring preferences, a concept of fairness or stability and Pareto-optimality just to mention a few. Unfortunately there is no algorithm that would satisfy all these. Pápai's main idea is that one should not entirely give up stability to get efficiency or vice versa, but slightly weaker forms of stability and efficiency may coexist for the case when the matching is between agents and objects. Objects, unlike agents, do not think, so they will not strategise, but may still have priorities. An office may have a priority for a senior staff member, or a school for a better student. On the other hand, staff members and students will have preferences, and when the incentives are such, they will misrepresent them to end up in a better position.

There are two well-known algorithms. The deferred-acceptance algorithm is stable, not sincere on both sides and is not efficient, while the top-trading cycle rule is not stable, but is sincere and efficient. Pápai introduces a new algorithm: the weak trading cycle rule. In a surprising step she first throws away some information and turns the strict preferences into weak preferences. The keeping preferences weak, she uses the deferred acceptance algorithm to reject some applicants, while the ties are broken in a separate round using the TTC rule. The main result shows that the weak trading cycle rule is the only one that satisfies the appropriately (but naturally!) weakened properties, moreover the TTC and the deferred acceptance algorithm come out as special cases.

I find the fundamental idea genial, and even though the weakened properties are complex, simply long to write down, they are still natural. For instance stability allows a bad student to have a place at a good university, if it was traded with a good student (for something the good student could not get). Besides issues of the exposition (the paper is still a draft), and potential extensions of the results, my main remark is to explore the connection with the improving cycles of Erdil and Ergin (2008), who seem to use a similar idea to resolve ties. Of course this does not diminish the merit of using such hybrid rules, which I consider the paper's main merit.

References:

Erdil, Aytek, and Haluk Ergin. 2008. "What's the Matter with Tie-Breaking? Improving Efficiency in School Choice." American Economic Review, 98(3): 669–89.

Pápai, Szilvia. 2010. "Matching with Minimal Priority Rights." manuscript.