When do stable matchings exist under complementary preferences and misalignment?

Complementarity breaks the substitutability guarantee

Standard many-to-one matching theory assumes substitutable preferences: workers can stand in for one another, so a firm's demand for one worker does not depend on which others it hires. Under that assumption, stable matchings exist and Deferred Acceptance converges. This paper studies the opposite case, complementarity, where workers need one another. The motivating examples are peer effects, team formation where a team only becomes valuable once a particular member joins, transportation where a trip is realized only if every segment of the route is secured, and service chaining for distributed AI services where the service exists only if all processing steps run.

Under complementarity the classical theory generally does not apply, and a stable matching need not exist at all. The paper's model is many-to-one and two-sided: firms hold utility over entire coalitions of workers, workers hold utility over the allocations they belong to, and crucially the two sides' utilities are given independently. That independence is what separates this setting from prior work in which a division rule such as Nash bargaining aligns the two sides' rankings. In wage negotiation, for instance, workers want high wages while the firm wants low payments, so their evaluations of the same coalition are reversed and the earlier alignment condition fails.

An anchor worker plus Transitive Alignment

The first condition is the anchor assumption: for each firm there exists a worker contained in every feasible coalition of that firm. The paper calls this worker the anchor worker. The anchor makes any two feasible coalitions of the same firm comparable and plays a central role in the later convergence proof, specifically in the monotonicity of the potential function. The authors note the assumption is mild because it can always be satisfied for any instance by adding a dummy worker dedicated to each firm; if that dummy's preferences agree with the metaranking, Transitive Alignment is preserved and no stable matching of the original instance is lost.

The second condition is Transitive Alignment. It requires a weak order, a metaranking, over all allocations such that for every worker and every pair of allocations that worker belongs to, the worker's utility comparison agrees with the metaranking. On allocations sharing common workers, all shared workers must order them the same way, so Transitive Alignment implies the pairwise alignment of earlier work restricted to comparisons among workers. It imposes no restriction on firm utilities, which makes it strictly weaker than pairwise alignment. The paper notes that when all workers' utilities can be written as a single common function of the allocation, that function is itself a metaranking and Transitive Alignment holds trivially, and that for finite instances the metaranking can be decided and constructed in polynomial time.

Neither condition alone suffices. The paper gives a counterexample in which Transitive Alignment holds but no anchor exists and no stable matching exists, and a second in which the anchor condition and worker-side pairwise alignment hold but Transitive Alignment fails because worker preferences are cyclic, again leaving no stable matching. Together they are sufficient: the paper proves that under the anchor condition and Transitive Alignment, every instance of the misaligned coalitional matching problem admits at least one stable matching. The authors also show the conditions are sufficient but not necessary, via an example with neither condition in which a stable matching nonetheless exists.

CDAR lets rejected coalitions be proposed again

CDAR stands for Combinatorial Deferred Acceptance with Reproposals. It is based on the firm-proposing Deferred Acceptance algorithm, and the essential difference is that it permits reproposals, which arise because under complementary preferences a coalition rejected at one point may later become acceptable. Firms propose their best not-yet-proposed coalition; the algorithm records the rejection set, the workers in that coalition who do not prefer it to their current allocation. If the rejection set is empty, the allocation is registered after releasing the firm's old coalition and unmatching rival firms that employed workers in the new coalition.

The reproposal rule is the key mechanism. A rejected coalition is removed from the proposed list, and thereby becomes eligible for reproposal, only at the moment all workers in its rejection set have become free. Reproposal is not permitted while even one rejector remains assigned, because that worker may prefer their current allocation and permitting a reproposal would let a blocking pair persist. The algorithm uses only local operations: it does not enumerate coalitions explicitly and does not construct the metaranking.

The convergence proof constructs an N-digit potential function that reads the firms' metaranking ranks as digits of a number in base m+1, where m is the number of equivalence classes of the metaranking. The paper proves CDAR terminates in finite time and outputs a stable matching. It also shows, by a reduction, that CDAR outputs a pairwise stable matching in the earlier pairwise-aligned setting, so this framework covers that class. On complexity, the paper reports that for general instances the number of feasible coalitions per firm can be exponential, making selection of the best not-yet-proposed coalition the dominant cost; in applications where feasible coalitions are implicitly defined as paths on a graph, each iteration can be processed without explicit enumeration by applying Yen's algorithm.

Pareto optimality among stable matchings needs strict preferences

The paper extends a known result to the complementary setting: under strict preferences, any stable matching is Pareto optimal within the set of stable matchings, and in particular so is the output of CDAR. Pareto optimality here is defined over the set of stable matchings only, not over all matchings, and payoffs are defined uniformly for firms and workers.

The strictness matters. The paper shows that when ties exist, a stable matching may fail to be Pareto optimal. A lemma formalizes why: if one stable matching Pareto dominates another, then for any dominating agent there must be some other agent whose payoff is unchanged, so a violation of Pareto optimality can arise only in the presence of ties. The authors suggest mitigating ties with an extended two-digit payoff that gives first priority to the original payoff and breaks ties by a secondary utility value, but they state that even this extended payoff does not necessarily remove all ties.

In traffic routing both conditions hold by construction

The paper maps the framework onto vehicle-route assignment for traffic safety. A firm is a vehicle, a worker is a spatio-temporal slot, a coalition is a feasible route, and the anchor worker is the vehicle's departure slot. Firm utility is negative arrival time and worker utility is the negative total pedestrian count along the route. Two vehicles collide if their routes occupy the same slot, and a feasible route must be collision-free with the routes of other matched vehicles. Because the vehicle's departure slot is necessarily contained in every feasible route, the anchor condition holds automatically by construction; because the slot utility is a function common to all slots, it is itself a metaranking and Transitive Alignment holds automatically by construction.

The numerical verification uses a 5x5 grid road network with 25 intersections and 40 links, synthetic data with vehicle counts N in {5, 10, 20, 30, 40, 50, 100} and 10 random seeds, and per-link pedestrian counts drawn uniformly from 0 to 10. Each vehicle's departure slot was routed through a dedicated dummy node with a zero-length dummy edge and zero pedestrian count, guaranteeing the anchor condition by construction. For all N and all seeds, CDAR terminated in finite time and output a stable matching.

Two comparisons stand out. First, running time: for N at least 30 the measured running time falls below the theoretical upper bound of Theorem 4, and fitting the actual number of iterations yields O(N^4.8), below the bound O(N^m). Second, an ablation: a Deferred Acceptance variant with reproposals disabled always terminates because it proposes each coalition at most once, but its output retains blocking pairs, and the number of residual blocking pairs increases monotonically with N. CDAR always has zero residual blocking pairs.

The guarantee is sufficient, not necessary, and scope-bound

The anchor condition and Transitive Alignment are sufficient conditions for existence, not necessary ones, and the paper demonstrates this with an instance satisfying neither condition that still admits a stable matching. So the framework identifies a class where existence and computation are guaranteed, not the full boundary of when stable matchings exist.

The complexity result for the traffic application is stated under an additional structural assumption, departure-only collision resolution, in which collisions are resolved only by delaying the departure time at the anchor slot and no waiting occurs at intermediate intersections. Under that assumption the total complexity is polynomial in N for fixed m, and because the pedestrian count range is determined by the network and independent of the number of vehicles, m does not grow with N, so on any fixed network CDAR runs in time polynomial in N. The paper describes this as slice-wise polynomial (XP) in m. The numerical verification is synthetic and confined to the 5x5 grid network; the authors list strategic manipulability and fairness analysis, expansion to service chaining and wage negotiation, and validation with real data as future work.

Check the anchor and the metaranking before trusting the guarantee

For a reader deciding whether this framework applies to a given assignment problem, the paper's own variables give a concrete checklist. First, is there a worker contained in every feasible coalition of each firm? In traffic routing the departure slot answers this automatically; in other settings the paper notes a dummy worker can be added to satisfy it without losing stable matchings of the original instance. Second, do workers' preferences admit a common metaranking over the allocations they belong to? This holds trivially when all workers' utilities are a single common function of the allocation, as with the negative pedestrian count in the traffic case, and it can be decided and constructed in polynomial time for finite instances.

The most decision-relevant distinction in the paper is between the two conditions and what each buys. The anchor condition alone does not guarantee stability, and Transitive Alignment alone does not either; only together do they guarantee that every instance admits a stable matching and that CDAR finds one. The second distinction is between existence and construction: earlier work proved existence under pairwise alignment but gave no procedure, and this paper's contribution is an algorithm that uses only local operations, without enumerating coalitions or building the metaranking. The third is the reproposal rule itself, which the ablation shows is not cosmetic: disabling it leaves blocking pairs that grow with the number of vehicles, while CDAR leaves none.

Sources used in this answer