Abstract We study the problem of determining whether a given random matching can be implemented as a lottery over weakly stable deterministic matchings – a property known as ex-post stability. This concept arises in randomized allocation mechanisms such as school choice, where stability in each realized outcome is essential for fairness. Despite its importance in practice, the computational complexity of verifying ex-post stability has remained unresolved. We settle this question by showing that testing ex-post stability is NP-complete, even under highly restricted conditions – specifically, when both sides have dichotomous preferences or one of the sides has strict preferences. On the positive side, we present an integer programming formulation that finds a decomposition of a random matching with maximum weight on stable matchings. We also consider stronger versions of ex-post stability (in particular robust ex-post stability and ex-post strong stability) and prove that they can be tested in polynomial time.

Abstract To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient–donor pools. We consider a recently introduced credit system. In each round, countries are given an initial “fair” allocation of the total number of kidney transplants. This allocation is adjusted by a credit function yielding a target allocation. The goal is to find a solution that approaches the target allocation as closely as possible, to ensure long-term stability of the international pool. As solutions, we use maximum matchings that lexicographically minimize the country deviations from the target allocation. We perform, for the first time, a computational study for a large number of countries. For the initial allocations we use two easy-to-compute solution concepts, the benefit value and the contribution value, and four classical but hard-to-compute concepts, the Shapley value, nucleolus, Banzhaf value and tau value. By using state-of-the-art software we show that the latter four concepts are now within reach for IKEPs of up to fifteen countries. Our experiments show that using lexicographically minimal maximum matchings instead of ones that only minimize the largest deviation from the target allocation (as previously done) may make an IKEP up to 54% more balanced.

Matching games naturally generalize assignment games, a well-known class of cooperative games. Interest in matching games has grown recently due to some breakthrough results and new applications. This state-of-the-art survey provides an overview of matching games and extensions, such as b-matching games and partitioned matching games; the latter originating from the emerging area of international kidney exchange. In this survey we focus on computational complexity aspects of various game-theoretical solution concepts, such as the core, nucleolus and Shapley value, when the input is restricted to a matching game or one of its variants.

Two-sided matching is an important research area that has had a major impact on the design of real-world matching markets. One consistent feature in many of the real-world applications is that they impose new feasibility constraints that lead to research challenges. We survey developments in the field of two-sided matching with various constraints, including those based on regions, diversity, multi-dimensional capacities, and matroids.

In recent years, a growing number of students are being assigned to schools through centralized clearinghouses. The success of such clearinghouses crucially relies on the use of a stable matching mechanism [10,12]. The matching market design literature finds that a designer who wishes to implement a stable allocation has limited scope for further design. First, the rural hospital theorem determines that the same positions are filled in all stable allocations [7,9]. Second, the set of stable allocations has the consensus property: all students prefer the outcome of the student-proposing deferred acceptance mechanism (henceforth) to any other stable allocation [4,8]. Third, empirical and theoretical studies suggest that all students, save for a handful, receive the same assignment in all stable allocations [e.g., 1, 2, 5 , 6, 11]. This last finding implies that schools have limited incentive to collect information and to misreport their preferences [3].

Abstract We consider the two-sided stable matching setting in which there may be uncertainty about the agents’ preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model—for each agent, there is a probability distribution over linear preferences, (2) compact indifference model—for each agent, a weak preference order is specified and each linear order compatible with the weak order is equally likely and (3) joint probability model—there is a lottery over preference profiles. For each of the models, we study the computational complexity of computing the stability probability of a given matching as well as finding a matching with the highest probability of being stable. We also examine more restricted problems such as deciding whether a certainly stable matching exists. We find a rich complexity landscape for these problems, indicating that the form uncertainty takes is significant.

The assignment problem is one of the most well-studied settings in multi-agent resource allocation. Aziz, de Haan, and Rastegari (2017) considered this problem with the additional feature that agents’ preferences involve uncertainty. In particular, they considered two uncertainty models neither of which is necessarily compact. In this paper, we focus on three uncertain preferences models whose size is polynomial in the number of agents and items. We consider several interesting computational questions with regard to Pareto optimal assignments. We also present some general characterization and algorithmic results that apply to large classes of uncertainty models.

The college admission problem (CAP) has been studied extensively in the last 65 years by mathematicians, computer scientists and economists following the seminal paper of Gale and Shapley (1962). Their basic algorithm, the so called deferred acceptance mechanism always returns a student optimal stable matching in linear time, and it is indeed widely used in practice. However, there can be some special features which may require significant adjustments on this algorithm, or the usage of other techniques, in order to satisfy all the objectives of the decision maker. The college admissions problem with ties and equal treatment policy is solvable with an extension of the Gale and Shapley algorithm, but, if there are further constraints, such as lower quotas, there exist no efficient way to find a stable solution. Both of these features are present in the Hungarian higher education matching scheme and a simple heuristic is used to compute the cutoff scores. Integer programming is a robust technique that can provide optimal solutions even when we have multiple requirements. In this paper we develop and test a new IP formulation for finding stable solutions for CAP with ties and equal treatment policy. This formulation is more general than the previously studied ones, and it has better performance, as we demonstrate with simulations, mostly because of its pure binary nature.