hierarchical-matching-systems

階層型マッチングシステム

このスキルでは、階層型マッチングシステムのための厳密な診断手順とアーキテクチャ手順を説明します。チェックリストには必ず従ってください。マッチングのバグは、手順を省略したときに見つかりにくくなることがよくあります。

クイックリファレンス

• アルゴリズムの選択：references/decision-guide.mdを参照してください
• アルゴリズムの詳細：references/algorithms.mdを参照してください

---

1. 問題分類チェックリスト

作業を始める前に、問題を分類してください。該当する項目をすべてチェックしてください。

□ 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)

分類によってアルゴリズムの系統が決まります。アーキテクチャについてはセクション2、デバッグについてはセクション3に進んでください。

---

2. アーキテクチャ手順

新しいマッチングシステムを設計するときは、以下のフェーズを順番に進めてください。

Phase 2.1: 要件の変換

各ビジネス要件を形式的な制約に変換してください。

ビジネス要件	制約の種類	形式的な表現
「各生徒に学校を1校割り当てる」	容量	`
「学校には定員がある」	容量	`
「きょうだいは同じ学校に通う」	結合	school(s1) = school(s2) if siblings(s1,s2)
「生徒XはYに通えない」	除外	(X, Y) ∉ matches
「居住者を優先する」	優先順位	rank(resident) < rank(non-resident)

チェックリスト：

□ 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: アルゴリズムの選択

references/decision-guide.mdを使ってアルゴリズムを選択してください。以下を確認してください。

□ 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: データモデルの設計

エンティティ、関係、および選好の表現方法を定義してください。

□ 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: インターフェースの契約

入力、出力、不変条件を指定してください。

入力の契約：

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

出力の契約：

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

不変条件：

□ 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: テスト戦略

実装前に検証方法を定義してください。

□ 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. デバッグ手順

マッチングに関する問題には、以下の診断手順に従ってください。手順を省略しないでください。

Phase 3.1: 症状の分類

症状のカテゴリを特定してください。

症状	カテゴリ	移動先
同じ入力で結果が異なる	不安定性	3.2
マッチングがビジネスルールに違反する	制約違反	3.3
マッチングは技術的には有効だが「不適切」	選好との不一致	3.4
入れ子または階層データでエラーが発生する	階層のバグ	3.5
大規模な処理でパフォーマンスが低下する	パフォーマンス	3.6

Phase 3.2: 不安定性の診断

非決定的なマッチングの根本原因：

□ 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)

検証：

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

Phase 3.3: 制約違反の診断

診断手順：

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

よくある失敗パターン：

パターン	症状	修正方法
遅すぎる適用	中間状態は有効だが、最終状態は無効	チェックを早い段階に移す
適用範囲の不足	一部のエンティティには制約が適用されるが、ほかには適用されない	すべてのケースを列挙する
ソフト制約とハード制約の混同	「より良い」マッチングのために制約に違反する	ハード制約として分類し直す
古いデータ	古くなった値に対して制約を適用する	チェック前にデータを更新する

Phase 3.4: 選好との不一致の診断

マッチングは有効でも、意図した優先順位が反映されていない場合：

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

スコア関数のチェックリスト：

□ 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: 階層走査の診断

複数レベルのマッチングに関する問題の場合：

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

よくある階層のバグ：

バグ	症状	修正方法
伝播の欠落	子が親の制約を無視する	継承ロジックを追加する
二重カウント	同じエンティティが複数回重み付けされる	集計時に重複を排除する
レベルのスキップ	間違ったレベルでマッチングする	レベル検証を追加する
孤立データの処理	親に紐付かない子によってエラーが発生する	孤立データのポリシーを定義する

Phase 3.6: パフォーマンスの診断

規模や速度に関する問題の場合：

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. テストと検証の手順

4.1: 正確性の特性

すべてのマッチングシステムで、以下の特性をテストしてください。

□ 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：安定性の検証（二者間マッチング）

安定マッチングでは、ブロッキングペアがないことを検証します。

# 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：制約充足の検証

□ 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：エッジケースのテストスイート

必須のテストケース：

□ 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：回帰テストの保守

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

---

5. レビューチェックリスト

マッチングシステムのコードや設計をレビューする際は、以下を確認します。

5.1：設計レビュー

□ 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：実装レビュー

□ 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：テストレビュー

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

---

付録：よくあるアンチパターン

アンチパターン	問題	解決策
先着順の貪欲な選択	順序に依存し、最適ではない	適切なアルゴリズムを使用する
スコア ＝（すべての要素の合計）	1 つの要素が支配的になる	スケールを正規化する
有効になるまで再試行	非決定的で、時間がかかる	制約の順序を修正する
グローバルな選好キャッシュ	更新後も古い情報が残る	変更時に無効化する
エンティティの文字列照合	大文字・小文字や空白による不具合	正規 ID を使用する
同点判定での浮動小数点数の等価比較	非決定的になる	許容誤差または整数を使用する
再帰的な階層走査	スタックオーバーフローのリスク	明示的なスタックを使って反復処理する
N² の選好行列	メモリ使用量が爆発的に増加する	疎な表現を使用する