Building a Clearinghouse Netting Batch in Python

This page builds the batch job that takes a matrix of bilateral gross obligations between transit operators and reduces it to the smallest set of net settlement transfers that leaves every operator whole. A network of a dozen operators can accumulate a hundred directed claims a day; paid gross, that is a hundred bank transfers and a hundred reconciliations. Multilateral netting collapses them to at most one payment per operator, and the batch here does it in Decimal with a conservation proof that total money paid equals total money received. It is a deep-dive within Inter-Agency Settlement Clearing, inside Revenue Reconciliation & Settlement.

The input is the obligation matrix the parent topic assembles; the individual claims inside it originate upstream — corridor shares from Prorating Shared-Corridor Revenue Across Operators and cross-operator transfer payouts, among others. This batch does not care where a claim came from; it cares only that the matrix nets to zero and that the transfers it emits reproduce every operator’s net position exactly.

Netting Flow: Gross Graph to Net Graph

A gross obligation matrix is a directed graph where every edge is a claim. Multilateral netting first collapses each operator’s inbound and outbound edges into one signed net position, then rebuilds the minimal graph that realizes those positions — debtors pay creditors directly, and any circular debt simply cancels. A cycle of mutual obligations that would have moved cash three times settles with a single transfer, or none.

The reduction is bounded: netting $N$ operators always settles in at most $N - 1$ transfers, because each transfer zeroes out at least one operator’s position. The batch does not search for a provably global minimum — that is NP-hard once you weight transfers by cost — but the greedy debtor-to-creditor match reaches the $N - 1$ bound in practice, and for a clearinghouse the operative win is going from a dense claim matrix to a sparse payment list, not shaving a last transfer.

Step 1 — Collapse the Gross Matrix to Net Positions

The batch takes the bilateral gross matrix as a mapping from (debtor, creditor) to a Decimal cent amount. Every operator’s net position is what it is owed minus what it owes; creditors come out positive, debtors negative. Before doing anything with the positions, assert they sum to zero — a matrix that does not conserve money cannot be settled, and catching it here is far cheaper than discovering it after transfers are cut.

from __future__ import annotations

import logging
from collections import defaultdict
from dataclasses import dataclass
from decimal import Decimal
from typing import Mapping

logger = logging.getLogger("transit.settlement.netting")

ZERO = Decimal("0")


class NettingError(Exception):
    """Base exception for the netting batch."""


class ConservationError(NettingError):
    """Gross matrix or emitted transfers failed to conserve money."""


@dataclass(frozen=True)
class Transfer:
    payer: str
    payee: str
    amount_cents: Decimal


def net_positions(matrix: Mapping[tuple[str, str], Decimal]) -> dict[str, Decimal]:
    """Collapse a directed gross obligation matrix into one signed net
    position per operator (creditor positive, debtor negative)."""
    positions: dict[str, Decimal] = defaultdict(lambda: ZERO)
    for (debtor, creditor), amount in matrix.items():
        if amount < ZERO:
            raise NettingError(f"Gross amount {amount} for {debtor}->{creditor} must be non-negative.")
        if debtor == creditor:
            continue  # a self-claim never moves money
        positions[debtor] -= amount   # owing reduces position
        positions[creditor] += amount  # being owed raises it

    total = sum(positions.values(), ZERO)
    if total != ZERO:
        raise ConservationError(f"Gross matrix nets to {total} cents, not zero.")
    return dict(positions)

Folding the matrix in a single pass is what makes the conservation check trustworthy: every cent is added to exactly one creditor and subtracted from exactly one debtor, so a non-zero sum can only mean a malformed input. Positions that come out at exactly zero — operator B in the diagram — are settled operators that neither pay nor receive.

Step 2 — Greedy Debtor-to-Creditor Settlement

With signed positions in hand, the minimal transfer set is produced by repeatedly matching the operator that owes the most against the operator that is owed the most, moving the smaller of the two amounts, and retiring whichever side reaches zero. Two heaps keep the largest debtor and largest creditor at the front. Each iteration zeroes at least one operator, so the loop runs at most $N - 1$ times.

import heapq
from typing import List


def compute_net_transfers(matrix: Mapping[tuple[str, str], Decimal]) -> List[Transfer]:
    """Reduce a bilateral gross obligation matrix to a minimal set of net
    settlement transfers, preserving total paid == total received."""
    positions = net_positions(matrix)

    # Min-heaps holding negative magnitudes, so the front is the largest debt / credit.
    debtors: list[tuple[Decimal, str]] = []    # (position, op) with position < 0
    creditors: list[tuple[Decimal, str]] = []  # (-position, op) with position > 0
    for op, amt in positions.items():
        if amt < ZERO:
            heapq.heappush(debtors, (amt, op))     # amt is negative; pops the largest debt first
        elif amt > ZERO:
            heapq.heappush(creditors, (-amt, op))  # negate so the largest credit pops first

    transfers: List[Transfer] = []
    while debtors and creditors:
        neg_debt, debtor = heapq.heappop(debtors)      # neg_debt <= 0
        neg_cred, creditor = heapq.heappop(creditors)  # neg_cred <= 0
        debt = -neg_debt   # positive magnitude the debtor still owes
        cred = -neg_cred   # positive magnitude the creditor is still owed

        pay = min(debt, cred)
        transfers.append(Transfer(payer=debtor, payee=creditor, amount_cents=pay))

        debt_left = debt - pay
        cred_left = cred - pay
        if debt_left > ZERO:
            heapq.heappush(debtors, (-debt_left, debtor))
        if cred_left > ZERO:
            heapq.heappush(creditors, (-cred_left, creditor))

    _assert_conservation(positions, transfers)
    logger.info("Netted %d operators into %d transfers.", len(positions), len(transfers))
    return transfers


def _assert_conservation(positions: Mapping[str, Decimal], transfers: List[Transfer]) -> None:
    """Prove the transfers reproduce every net position and balance overall."""
    realized: dict[str, Decimal] = defaultdict(lambda: ZERO)
    paid = ZERO
    for tr in transfers:
        if tr.amount_cents <= ZERO:
            raise ConservationError(f"Non-positive transfer {tr.payer}->{tr.payee}.")
        realized[tr.payer] -= tr.amount_cents
        realized[tr.payee] += tr.amount_cents
        paid += tr.amount_cents

    for op, want in positions.items():
        if realized.get(op, ZERO) != want:
            raise ConservationError(
                f"Operator {op} net {realized.get(op, ZERO)} != required {want}."
            )
    received = sum(tr.amount_cents for tr in transfers)
    if paid != received:
        raise ConservationError(f"Total paid {paid} != total received {received}.")

Because every amount stays a Decimal and min never fabricates a fraction, the transfers reproduce the net positions to the cent. The _assert_conservation pass is the batch’s proof of correctness: it re-derives each operator’s realized position from the emitted transfers and refuses the batch unless every one matches its required net and the grand totals balance. A settlement that cannot prove total-in equals total-out never leaves the job.

Validation & Test Cases

Two cases matter most: a circular debt that nets away almost entirely, and a case where conservation would break if the arithmetic drifted. The cycle proves the reduction; the assertions prove nothing was invented.

from decimal import Decimal

# Cycle: A owes B 100, B owes C 100, C owes A 60 -> nets to A pays C 40.
cycle = {
    ("A", "B"): Decimal("100"),
    ("B", "C"): Decimal("100"),
    ("C", "A"): Decimal("60"),
}
transfers = compute_net_transfers(cycle)
assert transfers == [Transfer(payer="A", payee="C", amount_cents=Decimal("40"))]
# Three gross claims collapsed to a single transfer.
assert len(transfers) == 1

# Perfect cycle: equal mutual debts settle with zero cash movement.
perfect = {("A", "B"): Decimal("50"), ("B", "C"): Decimal("50"), ("C", "A"): Decimal("50")}
assert compute_net_transfers(perfect) == []

# Conservation across a wider matrix: total paid equals total received.
wide = {
    ("A", "B"): Decimal("300"),
    ("A", "C"): Decimal("120"),
    ("B", "C"): Decimal("80"),
    ("C", "A"): Decimal("50"),
}
result = compute_net_transfers(wide)
# A is the only net debtor: owes 300 + 120 = 420, owed 50 -> net -370.
# B nets +220, C nets +150; A's payments fan out to both creditors.
total_out = sum(t.amount_cents for t in result)
assert total_out == Decimal("370")
assert len(result) <= 2  # at most N-1 transfers for 3 active operators

# Broken matrix: a negative gross amount is rejected outright.
try:
    compute_net_transfers({("A", "B"): Decimal("-10")})
    raise AssertionError("expected NettingError")
except NettingError:
    pass

The cycle case is the one that sells multilateral netting: three separate bank transfers become one, and the perfect cycle needs no cash at all. The wide case checks the invariant that actually protects a clearinghouse — the sum of every payment out equals the sum of every payment in, 320 cents either way — so no run can quietly move a net cent into or out of the system.

Edge Cases & Gotchas

• Already-balanced operators. An operator whose credits exactly cancel its debits nets to zero and must appear in neither heap; pushing a zero position would emit a spurious zero-amount transfer.
• Single dominant debtor. When one operator owes everyone, the greedy match fans its position out across creditors in descending order — still bounded by $N - 1$ transfers, one per creditor it must satisfy.
• Rounding is upstream. This batch assumes whole-cent Decimal inputs. If the matrix carries fractional cents from a bad proration, the netting arithmetic stays exact but the conservation of a broken input is meaningless — reject fractional cents at the matrix boundary, not here.
• Determinism under ties. Two debtors owing the identical amount are ordered by the heap’s tuple comparison, which falls through to the operator id. Keep that stable so a re-run produces the same payment list and an auditor sees identical transfers.

Integration Note

This batch is the settlement-producing stage of Inter-Agency Settlement Clearing: the parent engine assembles and conservation-checks the gross obligation matrix, and this job turns that matrix into the payment list the clearinghouse actually executes. Its closest sibling is Prorating Shared-Corridor Revenue Across Operators, which produces many of the claims inside the matrix; because that proration guarantees each corridor’s shares sum exactly to the collected fare, the matrix arrives here already conserving money, and this batch’s zero-sum assertion is the second, independent check that a proration or transfer bug never reaches a bank instruction.

FAQ

Related

• Inter-Agency Settlement Clearing — the parent topic that assembles the gross matrix this batch nets.
• Prorating Shared-Corridor Revenue Across Operators — the sibling that produces many of the claims inside the matrix.
• Ledger & Audit Trail Design — where the emitted transfers and their source matrix are persisted for audit.
• Daily Variance Reconciliation — the daily check that must close clean before a period is netted.
• Transfer Window Logic — the origin of the cross-operator transfer payouts that become obligations in the matrix.

Part of Inter-Agency Settlement Clearing, within Revenue Reconciliation & Settlement.