Student placements under diversity constraints are a common practice globally. This paper addresses the selection of students by a single school under a one-to-one convention, where students can belong to multiple types but are counted only once based on one type. While existing algorithms in economics and computer science aim to help schools meet diversity goals and priorities, we demonstrate that these methods can result in significant imbalances among students with different type combinations. To address this issue, we introduce a new property called balanced representation, which ensures fair representation across all types and type combinations. We propose a straightforward choice function that uniquely satisfies four fundamental properties: maximal diversity, non-wastefulness, justified envy-freeness, and balanced representation. While previous research has primarily focused on algorithms based on bipartite graphs, we take a different approach by utilizing flow networks. This method provides a more compact formalization of the problem and significantly improves computational efficiency. Additionally, we present efficient algorithms for implementing our choice function within both the bipartite graph and flow network frameworks.

In this work, we examine a sequential setting of a cooperative game in which players arrive dynamically to form coalitions and complete tasks either together or individually, depending on the value created. Upon arrival, a new player as a decision maker faces two options: forming a new coalition or joining an existing one. We assume that players are greedy, i.e., they aim to maximize their rewards based on the information available at their arrival. The objective is to design an online value distribution policy that incentivizes players to form a coalition structure that maximizes social welfare. We focus on monotone and bounded cooperative games. Our main result establishes an upper bound of 3min/max on the competitive ratio for any irrevocable policy (i.e., one without redistribution), and proposes a policy that achieves a near-optimal competitive ratio of min{1/2, 3min/max}, where min and max denote the smallest and largest marginal contribution of any sub-coalition of players respectively. Finally, we also consider non-irrevocable policies, with alternative bounds only when the number of players is limited.

We study a practical centralized matching problem which assigns children to daycare centers. The collective preferences of siblings from the same family introduce complementarities, which can lead to the absence of stable matchings, as observed in the hospital-doctor matching problems involving couples. Intriguingly, stable matchings are consistently observed in real-world daycare markets, despite the prevalence of sibling applicants. We conduct a probabilistic analysis of large random markets to examine the existence of stable matchings in such markets. Specifically, we focus on scenarios where daycare centers have similar priorities over children, a common characteristic in real-world markets. Our analysis reveals that as the market size approaches infinity, the likelihood of stable matchings existing converges to 1. To facilitate our exploration, we refine an existing heuristic algorithm to address a more rigorous stability concept, as the original one may fail to meet this criterion. Through extensive experiments on both real-world and synthetic datasets, we demonstrate the effectiveness of our revised algorithm in identifying stable matchings, particularly when daycare priorities exhibit high similarity.

The COVID-19 pandemic underscored the urgent need for fair and effective allocation of scarce resources, from hospital beds to vaccine distribution. In this paper, we study a healthcare rationing problem where identical units of a resource are divided into different categories, and agents are assigned based on priority rankings. We first introduce a simple and efficient algorithm that satisfies four fundamental axioms critical to practical applications: eligible compliance, non-wastefulness, respect for priorities, and maximum cardinality. This new algorithm is not only conceptually simpler but also computationally faster than the Reverse Rejecting rules proposed in recent work. We then extend our analysis to a more general sequential setting, where categories can be processed both sequentially and simultaneously. For this broader framework, we introduce a novel algorithm that preserves the four fundamental axioms while achieving additional desirable properties that existing rules fail to satisfy. Furthermore, we prove that when a strict precedence order over categories is imposed, this rule is the unique mechanism that satisfies these properties.

Abstract The theory of two-sided matching has been extensively developed and applied to many real-life application domains. As the theory has been applied to increasingly diverse types of environments, researchers and practitioners have encountered various forms of distributional constraints. Arguably, the most general class of distributional constraints would be hereditary constraints; if a matching is feasible, then any matching that assigns weakly fewer students at each college is also feasible. However, under general hereditary constraints, it is shown that no strategyproof mechanism exists that simultaneously satisfies fairness and weak nonwastefulness, which is an efficiency (students’ welfare) requirement weaker than nonwastefulness. We propose a new strategyproof mechanism that works for hereditary constraints called the Multi-Stage Generalized Deferred Acceptance mechanism (MS-GDA). It uses the Generalized Deferred Acceptance mechanism (GDA) as a subroutine, which works when distributional constraints belong to a well-behaved class called hereditary M $$^{\natural }$$ -convex set. We show that GDA satisfies several desirable properties, most of which are also preserved in MS-GDA. We experimentally show that MS-GDA strikes a good balance between fairness and efficiency (students’ welfare) compared to existing strategyproof mechanisms when distributional constraints are close to an M $$^{\natural }$$ -convex set * .

We study a problem where each school has flexible multi-ranked diversity goals, and each student may belong to multiple overlapping types, and consumes only one of the positions reserved for their types. We propose a novel choice function for a school to select students and show that it is the unique rule that satisfies three fundamental properties: maximal diversity, non-wastefulness, and justified envy-freeness. We provide a fast polynomial-time algorithm for our choice function that is based on the Dulmage Mendelsohn Decomposition Theorem as well as new insights into the combinatorial structure of constrained rank maximal matchings . Even for the case of minimum and maximum quotas for types (that capture two ranks), ours is the first known polynomial-time approach to compute an optimally diverse choice outcome. Finally, we prove that the choice function we design for schools, satisfies substitutability and hence can be directly embedded in the generalized deferred acceptance algorithm to achieve strategyproofness and stability. Our algorithms and results have immediate policy implications and directly apply to a variety of scenarios, such as where hiring positions or scarce medical resources need to be allocated while taking into account diversity concerns or ethical principles.

We study a practical two-sided matching problem of allocating children to daycare centers, which has significant social implications. We are cooperating with several municipalities in Japan and our goal is to devise a reliable and trustworthy clearing algorithm to deal with the problem. In this paper, we describe the design of our new algorithm that minimizes the number of unmatched children while ensuring stability. We evaluate our algorithm using real-life data sets, and experimental results demonstrate that our algorithm surpasses the commercial software that currently dominates the market in terms of both the number of matched children and the number of blocking coalitions (measuring stability). Our findings have been reported to local governments, and some are considering adopting our proposed algorithm in the near future, instead of the existing solution. Moreover, our model and algorithm have broader applicability to other important matching markets, such as hospital-doctor matching with couples and school choice with siblings.

We study a fair allocation problem of indivisible items under additive externalities in which each agent also receives utility from items that are assigned to other agents. This allows us to capture scenarios in which agents benefit from or compete against one another. We extend the well-studied properties of envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) to this setting, and we propose a new fairness concept called general fair share (GFS), which applies to a more general public decision making model. We undertake a detailed study and present algorithms for finding fair allocations.

In this paper, we study a daycare matching problem in Japan and report the design and implementation of a new centralized algorithm, which is going to be deployed in one municipality in the Tokyo metropolis. There are two features that make this market different from the classical hospital-doctor matching problem: i) some children are initially enrolled and prefer to be transferred to other daycare centers; ii) one family may be associated with two or more children and is allowed to submit preferences over combinations of daycare centers. We revisit some well-studied properties including individual rationality, non-wastefulness, as well as stability, and generalize them to this new setting. We design an algorithm based on integer programming (IP) that captures these properties and conduct experiments on five real-life data sets provided by three municipalities. Experimental results show that i) our algorithm performs at least as well as currently used methods in terms of numbers of matched children and blocking coalition; ii) we can find a stable outcome for all instances, although the existence of such an outcome is not guaranteed in theory.

We present a new and rich model of school choice with flexible diversity goals and specialized seats. The model also applies to other settings such as public housing allocation with diversity objectives. Our method of expressing flexible diversity goals is also applicable to other settings in moral multi-agent decision making where competing policies need to be balanced when allocating scarce resources. For our matching model, we present a polynomial-time algorithm that satisfies desirable properties, including strategyproofness and stability under several natural subdomains of our problem. We complement the results by providing a clear understanding about what results do not extend when considering the general model.

We study the pairwise organ exchange problem among groups motivated by real-world applications and consider two types of group formulations. Each group represents either a certain type of patient-donor pairs who are compatible with the same set of organs, or a set of patient-donor pairs who reside in the same region. We address a natural research question, which asks how to match a maximum number of pairwise compatible patient-donor pairs in a fair and individually rational way. We first propose a natural fairness concept that is applicable to both types of group formulations and design a polynomial-time algorithm that checks whether a matching exists that satisfies optimality, individual rationality, and fairness. We also present several running time upper bounds for computing such matchings for different graph structures.

We study the Japanese Residency Matching Program (JRMP) in which hospitals are partitioned into disjoint regions and both hospitals and regions are subject to quotas. To achieve a balanced distribution of doctors across regions, hard bounds are imposed by the government to limit the number of doctors who can be placed in each region. However, such hard bounds lead to inefficiency in terms of wasted vacant positions. In this paper, we propose two suitable algorithms to reduce waste with minimal modification to the current system and show that they are superior to the algorithm currently deployed in JRMP by comparing them theoretically and empirically.

We study the school choice problem where each school has flexible multi-ranked diversity goals, and each student may belong to multiple overlapping types, and consumes only one of the positions reserved for their types. We propose a novel choice function and show that it is the unique rule that satisfies three fundamental properties: maximal diversity, non-wastefulness, and justified envy-freeness. We provide a fast polynomial-time algorithm for our choice function that is based on the Dulmage Mendelsohn Decomposition Theorem as well as new insights into the combinatorial structure of constrained rank maximal matchings. Even for the case of minimum and maximum quotas for types (that capture two ranks), ours is the first known polynomial-time approach to compute an optimally diverse choice outcome. Finally, we prove that the choice function we design for schools, satisfies substitutability and hence can be directly embedded in the generalized deferred acceptance algorithm to achieve strategyproofness and stability. Our algorithms and results have immediate policy implications and directly apply to a variety of scenarios, such as where hiring positions or scarce medical resources need to be allocated while taking into account diversity concerns or ethical principles.

We study the controlled school choice problem where students may belong to overlapping types and schools have soft target quotas for each type. We formalize fairness concepts for the setting that extend fairness concepts considered for restricted settings without overlapping types. Our central contribution is presenting a new class of algorithms that takes into account the representations of combinations of student types. The algorithms return matchings that are non-wasteful and satisfy fairness for same types. We further prove that the algorithms are strategyproof for the students and yield a fair outcome with respect to the induced quotas for type combinations. We experimentally compare our algorithms with two existing approaches in terms of achieving diversity goals and satisfying fairness.

In recent years, a number of new challenges have been observed in the application of matching theory. One of the most pressing problems concerns how to allocate refugees to hosts safely and in a timely manner. Currently, this placement is implemented on an ad hoc basis where the preferences of both refugees and hosts are not taken into account. Another important realization is that real-life matching markets are often subject to various distributional constraints. For example, there has been increased attention to school choice models that take account of affirmative action and diversity concerns. The objective of this research is to design efficient algorithms while satisfying desirable properties for these new emerging problems.