In the optimal cohort partition problem, a planner seeks to distribute a heterogeneous population of individuals into a fixed number of distinct groups to optimize their objective. This problem is prevalent across a wide range of applications, including assigning students to classes, forming teams of experts in organizations, maximizing biodiversity, and designing contests among teams.
In this work, we approach partition problems from a majorization theory perspective and make two main contributions. At a conceptual level, we present a majorization-theoretic optimization framework for objectives that take a part-additive form, i.e., they can be written as a function of the summation vector of a partition. We show that the optimization of several common objectives reduces to a part-additive problem and characterize the structure of the optimal cohort partition policy across various objectives and applications.
At an application level, we focus on a common educational task---how to optimally partition students into classes in the presence of peer effects---and derive theoretical guarantees and new insights for this problem, thus making a theoretical contribution to the chiefly empirical literature on peer effects in education. In particular, we employ the workhorse empirical model, namely the linear-in-means (LIM) model, and study two different behavioral microfoundations proposed in the literature: the LIM spillover model and the LIM conformist model. We theoretically characterize the optimal partition for four distinct objectives---performance, welfare, diversity, and inequality.
We derive several policy-relevant insights. First, in both behavioral models, we show that as the planner's highest priority shifts from the top-performing class to the middle-performing class and then to the least-performing class, the optimal partition becomes progressively less assortative, ranging respectively from fully assortative to upper-uniform and then to fully uniform. Second, we show that, while both behavioral models yield identical optimal partition policies with respect to performance, diversity, and inequality, the welfare-optimal partition policy differs between the two LIM microfoundational models. Within the same behavioral model though, trade-offs are not always inevitable. For example, when student behavior aligns with the LIM conformist model and the planner weakly prioritizes the performance of the least-achieving classes, the uniform partition is optimal in most practical scenarios and across all four objectives. Third, we find that the uniform partition, despite achieving lower inequality than any integral partition, does not achieve perfect equality. We further illustrate these theoretical findings using calibrated simulations with student data from a novel dataset of public high schools.
Finally, we showcase how our theoretical framework extends beyond educational contexts by studying the optimal assignment of experts to teams, the design of Tullock contests, and non-linear peer effect models.