name: hierarchical-matching-systems
description: >
Expertise in architecting, implementing, reviewing, and debugging hierarchical matching systems.
Use when working with: (1) Two-sided matching (Gale-Shapley, hospital-resident, student-school),
(2) Assignment/optimization problems (Hungarian algorithm, bipartite matching),
(3) Multi-level hierarchy matching (org charts, taxonomies, nested categories),
(4) Entity resolution and record linkage across hierarchies.
Triggers: debugging match quality issues, reviewing matching algorithms, translating business
requirements into constraints, validating match correctness, architecting new matching systems,
fixing unstable matches, resolving constraint violations, diagnosing preference misalignment.

Hierarchical Matching Systems

This skill provides rigid diagnostic and architectural procedures for hierarchical matching systems. Follow checklists exactly—matching bugs often hide in skipped steps.

Quick Reference

• Algorithm selection: See references/decision-guide.md
• Algorithm details: See references/algorithms.md

1. Problem Classification Checklist

Before any work, classify the problem. Check ALL that apply:

□ TWO-SIDED: Both sides have preferences (students↔schools, workers↔jobs)
□ ONE-SIDED: Only one side has preferences (tasks→workers, items→bins)
□ HIERARCHICAL: Entities exist at multiple levels (org→dept→team→person)
□ WEIGHTED: Matches have costs/scores to optimize
□ CONSTRAINED: Hard limits exist (capacity, exclusions, required pairings)
□ STABLE: Solution must resist defection (no blocking pairs)
□ OPTIMAL: Solution must minimize/maximize objective function
□ FUZZY: Entities may partially match (entity resolution, deduplication)

Classification determines algorithm family. Proceed to Section 2 for architecture or Section 3 for debugging.

2. Architecture Procedure

Follow these phases in order when designing a new matching system.

Phase 2.1: Requirements Translation

Convert each business requirement into formal constraints:

Checklist:

□ List ALL business requirements
□ Classify each as: capacity | coupling | exclusion | ordering | soft preference
□ Identify conflicts between requirements (document tradeoffs)
□ Distinguish HARD constraints (must satisfy) from SOFT (optimize toward)
□ Validate translations with stakeholder examples

Phase 2.2: Algorithm Selection

Use references/decision-guide.md to select algorithm. Verify:

□ Algorithm handles all HARD constraints
□ Algorithm can optimize SOFT constraints (or document gaps)
□ Complexity acceptable for data size (see references/algorithms.md)
□ Stability requirements met (if two-sided)
□ Optimality requirements met (if weighted)

Phase 2.3: Data Model Design

Define entities, relationships, and preference representation:

□ Entity schema for each side (attributes, identifiers)
□ Preference representation (ranked list | score matrix | pairwise comparisons)
□ Constraint encoding (how exclusions/couplings are stored)
□ Hierarchy representation (if multi-level: tree | DAG | adjacency list)
□ Tie-breaking rules (deterministic ordering for equal preferences)

Phase 2.4: Interface Contracts

Specify inputs, outputs, and invariants:

Input Contract:

□ Preference format and validation rules
□ Constraint format and validation rules
□ Required vs optional fields
□ How missing preferences are handled (reject | default rank | exclude)

Output Contract:

□ Match format (pairs | assignment map | ranked list)
□ Unmatched entity handling (explicit list | null matches | error)
□ Match metadata (scores, stability proof, constraint satisfaction report)

Invariants:

□ Determinism: same input → same output (document randomness if any)
□ Completeness: all entities matched OR explicitly unmatched
□ Validity: all matches satisfy hard constraints

Phase 2.5: Testing Strategy

Define validation before implementation:

□ Unit tests for preference parsing and constraint validation
□ Property tests: stability, optimality, constraint satisfaction
□ Edge cases: empty inputs, single entity, all tied preferences
□ Regression tests from known-good examples
□ Performance benchmarks at target scale

3. Debugging Procedure

Follow this diagnostic sequence for any matching issue. Do not skip steps.

Phase 3.1: Symptom Classification

Identify the symptom category:

Phase 3.2: Instability Diagnosis

Root causes of non-deterministic matches:

□ RANDOMNESS: Check for unseeded RNG in tie-breaking
   → Fix: Use deterministic tie-breaker (lexicographic ID, timestamp)

□ FLOATING POINT: Check score comparisons for floating point issues
   → Fix: Use epsilon comparison or integer scores

□ HASH ORDERING: Check if iteration order depends on hash maps
   → Fix: Sort keys before iteration

□ PARALLEL RACE: Check for concurrent modifications
   → Fix: Synchronize or use sequential processing

□ INPUT ORDERING: Check if algorithm is order-sensitive
   → Fix: Canonicalize input order (sort by ID)

Verification:

□ Run matching 10x with identical inputs
□ Diff all outputs
□ If any differ, add logging to identify divergence point

Phase 3.3: Constraint Violation Diagnosis

Diagnostic sequence:

1. □ IDENTIFY: Which specific constraint is violated?
   → List the violated constraint and the violating match

2. □ TRACE: Where should constraint be enforced?
   → Map constraint to code location (filter | validation | algorithm step)

3. □ VERIFY ENCODING: Is constraint correctly represented?
   → Print constraint data structure, verify against requirement

4. □ VERIFY ENFORCEMENT: Is constraint checked at right time?
   → Add logging before/after enforcement point

5. □ CHECK ORDERING: Is constraint checked before conflicting decisions?
   → Trace decision sequence, verify constraint checked first

6. □ CHECK COMPLETENESS: Are all instances covered?
   → Enumerate all entities that should be constrained

Common failure patterns:

Phase 3.4: Preference Misalignment Diagnosis

When matches are valid but don't reflect intended priorities:

1. □ EXTRACT: Get the actual preference data used
   → Log/print the exact preference structure at match time

2. □ COMPARE: Check against expected preferences
   → Side-by-side diff with business-stated priorities

3. □ TRACE TRANSFORMATION: Follow preference from input to algorithm
   → Log at each transformation step (parsing, normalization, scoring)

4. □ CHECK SCORING: Verify score calculation
   → Manual calculation for 2-3 example cases

5. □ CHECK AGGREGATION: If multi-criteria, verify combination
   → Test each criterion independently, then combined

6. □ CHECK NORMALIZATION: Verify scale/range handling
   → Check for min/max, z-score, or rank normalization bugs

Scoring function checklist:

□ Direction correct (higher = better or lower = better, consistently)
□ Scale appropriate (no single factor dominating)
□ Missing values handled (null → 0? → excluded? → default?)
□ Ties handled explicitly (not left to floating point chance)
□ Edge cases: extreme values, all same values, single candidate

Phase 3.5: Hierarchy Traversal Diagnosis

For multi-level matching issues:

1. □ VISUALIZE: Draw the hierarchy with the problematic match
   → Tree diagram showing all levels and the match path

2. □ CHECK INHERITANCE: Do child constraints inherit from parent?
   → Verify constraint propagation rules

3. □ CHECK AGGREGATION: How do child preferences roll up?
   → Verify aggregation function (sum | max | weighted | majority)

4. □ CHECK LEVEL INTERACTION: Can matches cross levels?
   → Document allowed/forbidden cross-level matches

5. □ CHECK TRAVERSAL ORDER: Top-down or bottom-up?
   → Verify algorithm processes levels in intended order

6. □ CHECK PARTIAL MATCHES: Can a parent match without all children?
   → Document completeness requirements per level

Common hierarchy bugs:

Phase 3.6: Performance Diagnosis

For scale and speed issues:

1. □ PROFILE: Identify the slow component
   → Time each phase: input parsing, preference building, matching, output

2. □ COMPLEXITY CHECK: Verify actual vs expected complexity
   → Log iteration counts, compare to theoretical O(n)

3. □ MEMORY CHECK: Profile memory usage
   → Watch for preference matrix explosion (n² space)

4. □ ALGORITHM FIT: Verify algorithm appropriate for scale
   → See references/algorithms.md for complexity comparison

5. □ CACHING: Check for redundant computation
   → Log cache hits/misses for preference lookups

6. □ BATCH VS STREAMING: Check processing model
   → Full recomputation vs incremental updates

4. Testing & Validation Procedure

4.1: Correctness Properties

Test these properties for every matching system:

□ DETERMINISM: run(input) = run(input) (10 trials minimum)
□ COMPLETENESS: all entities either matched or explicitly unmatched
□ VALIDITY: all matches satisfy all hard constraints
□ STABILITY (if applicable): no blocking pairs exist
□ OPTIMALITY (if applicable): objective function at expected value

4.2: Stability Verification (Two-Sided Matching)

For stable matching, verify no blocking pairs:

# Pseudocode - verify no blocking pair exists
for each unmatched_pair (a, b):
    if a prefers b over current_match(a):
        if b prefers a over current_match(b):
            FAIL: blocking pair found (a, b)

□ Enumerate all non-matched pairs
□ Check mutual preference for each
□ Report any blocking pairs found
□ For large instances, sample-check (document coverage)

4.3: Constraint Satisfaction Verification

□ List all hard constraints
□ For each match, verify against each constraint
□ Generate constraint satisfaction report
□ Flag any violations with specific match and constraint

4.4: Edge Case Test Suite

Mandatory test cases:

□ Empty input (no entities on one or both sides)
□ Single entity (one-to-one degenerate case)
□ All identical preferences (maximum tie scenario)
□ Mutually exclusive preferences (everyone wants same thing)
□ Impossible constraints (unsatisfiable, should error clearly)
□ Maximum capacity (all slots exactly filled)
□ Minimum capacity (barely enough slots)
□ Self-referential (can entity match itself? test boundary)
□ Circular preferences (A→B→C→A)

4.5: Regression Test Maintenance

□ Capture real production cases that revealed bugs
□ Minimize to smallest reproducing example
□ Document expected behavior explicitly
□ Run on every change to matching logic

5. Review Checklist

When reviewing matching system code or design:

5.1: Design Review

□ Problem correctly classified (Section 1)
□ Algorithm appropriate for problem class (references/decision-guide.md)
□ All business requirements mapped to constraints (Section 2.1)
□ Hard vs soft constraints clearly distinguished
□ Tie-breaking is deterministic and documented
□ Hierarchy semantics defined (if applicable)

5.2: Implementation Review

□ Preference representation matches algorithm requirements
□ Constraints enforced at correct point in algorithm
□ No hidden randomness (unseeded RNG, hash iteration)
□ Floating point comparison handled correctly
□ Edge cases handled (empty, single, ties)
□ Error messages identify specific constraint violations

5.3: Testing Review

□ All properties from 4.1 tested
□ Edge cases from 4.4 covered
□ Performance benchmarked at realistic scale
□ Regression tests exist for past bugs

Appendix: Common Anti-Patterns