PaperlayerView exact revision on arXiv

Source-linked AI summary

Computing Stable Matchings under Complementarities and Preference Misalignment

Tatsuya Iwase, Bahar Rastegari, Sebastian Stein, Enrico H. Gerding

arXiv:2610.06337v1cs.GT

TL;DR

Complementary preferences can make stable matchings fail to exist, while existing approaches leave gaps for peer effects, preference misalignment, or constructive algorithms. The paper introduces conditions for existence and a Deferred Acceptance-style algorithm with reproposals. It proves finite-time convergence and stable output, and shows Pareto optimality among stable matchings under strict preferences.

  • Problem

    Complementary preferences, including peer effects, can leave stable matchings nonexistent, and constructive methods for two-sided misaligned settings are lacking.

    Source: §1 · p. 1

  • Method

    The paper combines an anchor condition with Transitive Alignment and proposes CDAR, a Deferred Acceptance-style algorithm that permits reproposals.

    Source: §1 · p. 2, §2.5 · p. 3

  • Results

    CDAR converges in finite time and outputs a stable matching; under strict preferences, its output is Pareto optimal among stable matchings.

    Source: §1 · p. 2, Conclusion · p. 7

  • Takeaways & Limitations

    The framework’s conditions hold by construction for the traffic application, where CDAR outputs stable matchings.

    Source: §1 · p. 2

    When ties exist, a stable matching may fail to be Pareto optimal.

    Source: §4 · p. 7

Abstract

from arXiv · show

We study many-to-one, two-sided stable matching problems in which preferences are complementary and firms and workers may rank the same allocation differently. Here a coalition is a group of workers that can be jointly matched with a firm. With complementary preferences, a stable matching need not exist. We show that a stable matching exists for every instance when two conditions hold. The first requires each firm to have an anchor worker who is included in every feasible coalition that can be matched with that firm. The second is Transitive Alignment, which means there must be an overall ranking across different coalitions that is consistent with the workers' preferences. We propose CDAR (Combinatorial Deferred Acceptance with Reproposals), a Deferred Acceptance-style algorithm that permits reproposals, and prove its finite-time convergence and its output of a stable matching by constructing an $N$-digit potential function. Moreover, we show that, under strict preferences, the output of CDAR is Pareto optimal among stable matchings. The proposed framework naturally captures applications such as vehicle-route assignment for traffic safety and the misaligned interests of labor and management in wage negotiation.

1 Introduction

Complementary preferences make stable matching uncertain, while existing frameworks do not fully cover independently ranked worker–firm allocations or provide a constructive procedure. The paper supplies sufficient conditions for stability and introduces an algorithm that constructs a stable matching under those conditions.

1 Introduction

  • Complementarity makes stable matching existence uncertain, and prior theory often assumes substitutability or excludes peer effects.Under substitutability, stable matching existence and Deferred Acceptance convergence are guaranteed; with complementary preferences, stability may fail to exist.Source: §1 · p. 1
  • Pycia’s framework requires pairwise alignment induced by a division rule, excluding cases where workers and firms independently value the same coalition differently.Wage negotiation is an example: workers prefer higher wages while firms prefer lower payments.Source: §1 · p. 1
  • The Pycia framework provides no construction procedure, while prior constructive methods do not extend to two-sided settings or may require infeasible coalition enumeration.The paper identifies this gap as an obstacle to implementation in real problems.Source: §1 · pp. 1–2
  • The paper generalizes the framework to misaligned preferences and proves that the anchor condition plus Transitive Alignment suffices for stable matching existence.CDAR uses local operations without explicitly enumerating coalitions or constructing the metaranking.Source: §1 · p. 2
  • An N-digit potential function proves CDAR terminates in finite time and returns a stable matching; under strict preferences, its output is Pareto optimal among stable matchings.The paper also reports that CDAR outputs stable matchings in its traffic application, where the conditions hold by construction.Source: §1 · p. 2

2 Model

The model treats firms as choosing feasible worker coalitions while workers evaluate their allocations in light of coalition membership. Stability excludes mutually beneficial firm–coalition deviations; the paper then gives conditions that guarantee stable matchings and contextualizes them with applications.

2 Model

  • The model generalizes the Pycia framework to firm–worker settings with independently specified preferences.It illustrates concepts through the example of a firm hiring a team.Source: §2 · p. 2

2.1 Agents, Coalitions, and Utilities

  • Firms evaluate whole coalitions, while workers evaluate allocations that include their coalition peers, allowing peer effects and preference misalignment.The utilities are independent; the paper gives a zero-sum-like multi-LLM example in which firm utility reflects worker token budgets.Source: §2.1 · p. 2

2.2 Matching

  • A matching assigns at most one feasible coalition to each firm and consistently assigns each employed worker to that firm.Source: §2.2 · pp. 2–3

2.3 Stability and Blocking Pairs

  • A matching is stable exactly when no feasible firm–coalition allocation is preferred by the firm and every coalition member to their current allocations.A blocking pair is such a mutually desirable deviation.Source: §2.3 · p. 3

2.4 Anchor Assumption

  • Each firm’s anchor worker belongs to every feasible coalition, supporting comparability in the convergence proof.Firms may share an anchor; the results still hold even if some firms then receive no coalition.Source: §2.4 · p. 3

2.5 Transitive Alignment and Stability Conditions

  • Transitive Alignment requires a shared cross-coalition order consistent with workers’ rankings, but imposes no agreement requirement on firm preferences.Together with the anchor condition, it guarantees at least one stable matching; it is weaker than pairwise alignment.Source: §2.5 · pp. 3–4
  • Neither condition alone guarantees stability, and the conditions are sufficient rather than necessary.The examples show no stable matching when the anchor fails despite TA, or when TA fails despite an anchor; another instance has a stable matching despite failure of both conditions.Source: §2.5 · pp. 3–4
  • In vehicle-route assignment, a vehicle is a firm, a feasible route is a coalition, and its departure slot supplies an anchor while shared route-cost preferences satisfy TA.The paper also identifies service chaining and labor–management wage negotiation as settings covered by the framework.Source: §2.5 · pp. 4–5

3 Algorithm

CDAR extends firm-proposing deferred acceptance to complementary preferences by allowing rejected coalitions to be proposed again. Under the anchor condition and Transitive Alignment, it terminates with a stable matching; its complexity is polynomial in the number of vehicles on a fixed traffic network.

3 Algorithm

  • CDAR terminates in finite time and returns a stable matching under the anchor condition and Transitive Alignment.These guarantees are established through its convergence and stability results.Source: §3 · p. 5, §3.2 · pp. 5–6

3.1 Algorithm

  • CDAR permits a rejected coalition to be proposed again once every worker in its rejection set is unassigned.Reproposal is withheld while any rejector remains assigned, because that worker may still prefer their current allocation.Source: §3.1 · p. 5

3.2 Convergence and Stability

  • An N-digit potential function strictly increases with each update and is bounded above, establishing finite termination.The digits encode sorted firm ranks in base m + 1, so a higher digit dominates all lower digits.Source: §3.2 · p. 5

3.3 Computational Complexity

  • CDAR is slice-wise polynomial in m and runs in time polynomial in N on a fixed network.For traffic, under departure-only collision resolution, total complexity is polynomial in N for fixed m; Yen’s algorithm can process path proposals without explicit coalition enumeration.Source: §3.3 · p. 6
  • CDAR also converges to a pairwise stable matching for instances satisfying Pycia’s pairwise alignment condition.The paper establishes this result by reducing those instances to its framework.Source: §3.3 · p. 6

4 Pareto Optimality

Under strict preferences, every stable matching is Pareto optimal among stable matchings, including CDAR’s output. With ties, stable matchings may fail to be Pareto optimal.

4 Pareto Optimality

  • The Pareto-optimality comparison is restricted to stable matchings, and a violation for CDAR’s output can arise only when ties are present.The proof characterizes what must hold when one stable matching Pareto dominates another: some agent receives the same payoff in both.Source: §4 · pp. 6–7
  • With no ties in agents’ payoffs, every stable matching is Pareto optimal within the set of stable matchings, including CDAR’s output.The proof uses the absence of a dominating agent to rule out any stable matching that Pareto dominates it.Source: §4 · p. 7
  • When ties exist, a stable matching may fail to be Pareto optimal.The paper notes that even extended payoffs, which prioritize original payoff and use a secondary utility to break ties, may not remove all ties.Source: §4 · p. 7

5 Numerical Verification in the Traffic Application

On synthetic traffic instances, CDAR terminated and returned stable matchings for every tested vehicle count and seed. The experiments also compare its running time with a theoretical bound and test the role of reproposals.

Experimental setup

  • The synthetic setup guaranteed the anchor condition by construction, and its common score −H satisfied Transitive Alignment.Instances used a 5 × 5 grid road network, with 10 random seeds per vehicle count and no upper limit on candidate routes K.Source: §5 · p. 7

Results

  • For every tested vehicle count and seed, CDAR terminated in finite time and output a stable matching.Figure 2 compares running time with the theoretical bound and shows the blocking-pair comparison for reproposals.Source: §5 · p. 7, Figure 2 · p. 7
  • For N ≥30, CDAR’s running time fell below the plotted bound, and the fitted iteration count was O(N^4.8), below the bound O(N m).The bound curve used K = 1 and |V| = 25, with m = 80; its proportionality constant was fitted as c ≈3.41 × 10−31.Source: §5 · p. 7
  • Without reproposals, deferred acceptance left blocking pairs whose number increased monotonically with N; CDAR had 0 residual blocking pairs.The comparison disabled the reproposal step; the CDAR zero-blocking-pair result follows from Theorem 3.Source: §5 · p. 7, Figure 2 · p. 7

Conclusion

The paper establishes stable-matching existence under the anchor condition and Transitive Alignment and proposes CDAR to construct stable outcomes. It also reports strict-preference Pareto optimality and traffic-instance verification.

Conclusion

  • The anchor condition and Transitive Alignment guarantee at least one stable matching for every instance in the firm-worker misalignment setting.The paper’s traffic experiments also report that these conditions hold by construction in that application.Source: Conclusion · p. 7
  • CDAR permits reproposals and is proved to converge in finite time to a stable matching; under strict preferences, its output is Pareto optimal among stable matchings.The convergence proof constructs an N-digit potential function.Source: Conclusion · p. 7
  • Future work includes strategic manipulability and fairness, broader applications such as service chaining and wage negotiation, and validation with real data.Source: Conclusion · p. 7

Appendix C Appendix: Correspondence to Service Chaining

The framework maps service-chain assignment to a firm-worker matching problem. The ingress node is an anchor, while a common resource-consumption score can satisfy Transitive Alignment under stated conditions.

Appendix C Appendix: Correspondence to Service Chaining

  • A service chain is a sequence of processing functions assigned to network nodes, and it has complementary structure because every function must be secured.Source: Appendix C · p. 9
  • In the correspondence, firms are service requests, workers are network nodes or links, and coalitions are feasible chains; the ingress node is the anchor.Firm utility is negative latency, while worker utility is negative resource consumption.Source: Appendix C · p. 9
  • Transitive Alignment holds when resource consumption depends on the chain rather than request type, making the common score −ρ a metaranking.The passage gives dominant link bandwidth capacity with negligible request differences as an example.Source: Appendix C · p. 9

Appendix D Appendix: Proof of Proposition 1

The proof applies the paper’s conditions to Pycia’s framework, establishing finite-time convergence of CDAR and a stable output. It also shows that a Pareto-dominating alternative to a stable matching would create a blocking pair unless ties are present.

Appendix D Appendix: Proof of Proposition 1

  • In Pycia’s framework, the existing metaranking supplies Transitive Alignment, and choosing the firm itself as anchor satisfies the anchor condition.Thus the paper’s lemmas and theorems imply CDAR converges in finite time and outputs a stable matching.Source: Appendix D · p. 9
  • A Pareto-dominating matching with no tied payoffs among the relevant agents would create a blocking pair, contradicting stability.The proof assumes a dominating agent has a strict payoff gain while every agent weakly improves.Source: Appendix D · p. 9
  • If the dominating agent is a worker, strict gains for the destination firm and its coalition in the alternative matching make that pair block.The proof’s contradiction applies when none of those agents has equal payoffs across the two matchings.Source: Appendix D · p. 9
  • If the dominating agent is a firm, strict gains for every worker in its alternative coalition likewise make that firm-coalition pair block.Therefore, the proof’s potential exception to Pareto optimality requires ties.Source: Appendix D · p. 9

Appendix F Appendix: Violation of Pareto Optimality Caused by Ties

The example shows how ties can leave CDAR’s stable output Pareto-dominated by another stable matching. The alternative improves two firms’ payoffs while leaving all other agents’ payoffs unchanged.

Appendix F Appendix: Violation of Pareto Optimality Caused by Ties

  • The example’s worker utilities contain ties, including equal payoffs for worker b across three firm-coalition allocations.The firms’ feasible coalitions and utilities specify the setting in which the tie-based example is constructed.Source: Appendix F · p. 9
  • In the example, µ assigns A to {a} and B to {b}, while µ′ swaps them; µ′ has no blocking pair, raises πA and πB, and leaves all other agents’ payoffs unchanged.Source: Appendix F · p. 10
  • The CDAR output has no blocking pair, yet the alternative also has no blocking pair and Pareto-dominates it.The other agents’ payoffs are unchanged.Source: Appendix F · p. 10

Appendix G Appendix: Proof of the Complexity in the Traffic Application

The complexity proof bounds candidate generation and collision resolution per firm, then uses a strictly increasing finite potential to bound the number of iterations. Departure delays alone can make each candidate route feasible after finitely many trials.

Appendix G Appendix: Proof of the Complexity in the Traffic Application

  • O(rN) departure-delay increases suffice to resolve collisions for a route of length r, where r ≤ |V|.A collision occurs when vehicles attempt to occupy the same slot at the same time; the lemma bounds the delay trials under Assumption 2.Source: Application · p. 10
  • O(K(|V|^3 + N|V|)) is the per-firm cost of enumerating K node sequences and determining delays for each candidate.The enumeration costs O(K|V|^3), and delay determination costs O(KN|V|).Source: Application · p. 10
  • The potential strictly increases after each matching update, so its bounded number of possible values bounds the iteration count.The potential sorts the firms’ values into an N-digit number whose digits range from 0 to m; the proof treats m as constant.Source: Application · p. 10

Appendix H Appendix: Details of reproducibility

The reproducibility details specify the simulation’s random-seed procedure and computing environment, and identify Table 1 as the parameter list.

Appendix H Appendix: Details of reproducibility

Loading 2610.06337v1…