Monday, July 25, 2022

Efficient school choice when schools are not players: Phil Reny in the AER

 In some school choice systems, such as in New York City, the schools (represented e.g. by the school principals) as well as the students and families are strategic players. I think the weight of the evidence in those cases clearly points to the importance of having stable matchings, to forestall various forms of strategic behavior by blocking pairs.  

But in many school choice systems the individual schools (although not necessarily the school district) are not strategic players. In those, the school choice problem can usefully be viewed as a problem of allocating objects, namely school places, and only the students and their families are participants for whom we should have incentive and welfare concerns. In these cases, pairwise stability of the matching may be a fairness consideration, but not one with critical strategic or welfare implications.  A Pareto improvement in this case is one that improves matches according to student preferences--the priorities that schools have over students are part of the mechanism, but they don't have welfare consequences.

Here's a nice recent paper by Phil Reny which considers that latter situation, and investigates an outcome that improves student welfare compared to stable matchings, while still making a substantial bow to fairness of the sort captured by stability.  His results give new insight into the mechanism proposed by Onur Kestin in his famous 2010 paper in the QJE*.

Reny, Philip J. "Efficient Matching in the School Choice Problem." American Economic Review 112, no. 6 (2022): 2025-43.

Abstract: "Stable matchings in school choice needn’t be Pareto efficient and can leave thousands of students worse off than necessary. Call a matching μ priority-neutral if no matching can make any student whose priority is violated by μ better off without violating the priority of some student who is made worse off. Call a matching priority-efficient if it is priority-neutral and Pareto efficient. We show that there is a unique priority-efficient matching and that it dominates every priority-neutral matching and every stable matching. for every student in the mechanism that selects the priority-efficient matching"

##############

*Kesten, Onur. "School choice with consent." The Quarterly Journal of Economics 125, no. 3 (2010): 1297-1348.

############

So I think we're now seeing a dialog between two approaches to improving student welfare in school choice environments in which pairwise stability (avoiding blocking pairs consisting of schools and students/families) doesn't seem critical to success (i.e. environments in which schools aren't able to participate in blocking pairs).  Reny and Kesten present a path towards doing that while paying a lot of respect to the priorities that schools have for students. (The success of the deferred acceptance algorithm even in these environments may have a lot to do with the fact that school administrators are often quite invested in the priorities that schools are specified to have over students, since these are intended to shape who goes to which schools.)

The alternative approach looks at an efficient and strategy-proof mechanism like top trading cycles  (TTC) that pays some respect to those priorities, but not at the expense of strategy-proofness, i.e. while keeping it completely safe for students/families to state their true preferences straightforwardly.

For that discussion, see this previous post:

Wednesday, December 9, 2020

***********
Update: Péter Biró alerts me to this recent paper that also relates to my concluding comments above.

Biró, P. and Gudmundsson, J., 2021. Complexity of finding Pareto-efficient allocations of highest welfare. European Journal of Operational Research, 291(2), pp.614-628.

Abstract: We allocate objects to agents as exemplified primarily by school choice. Welfare judgments of the object-allocating agency are encoded as edge weights in the acceptability graph. The welfare of an allocation is the sum of its edge weights. We introduce the constrained welfare-maximizing solution, which is the allocation of highest welfare among the Pareto-efficient allocations. We identify conditions under which this solution is easily determined from a computational point of view. For the unrestricted case, we formulate an integer program and find this to be viable in practice as it quickly solves a real-world instance of kindergarten allocation and large-scale simulated instances. Incentives to report preferences truthfully are discussed briefly.

No comments: