FAILURE MAP
← Case archive

FA-12786 / Voting rule computation / Open access

Locking a ranked pair closes an indirect preference cycle · case 01

Locking a ranked pair closes an indirect preference cycle.

Verified by executionVariant 1 · 6 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Every ordered pairwise victory is locked without checking whether its loser already reaches its winner.

VERIFIED REPAIR

Process ordered victories in order, locking an edge only when no path runs from loser back to winner.

Unsuccessful approach: Rejecting only direct reverse edges misses cycles spanning three or more candidates.

Case contract

Given n candidates indexed 0..n-1 and unique directed victories already ordered by strength and a predetermined tie order, return locked edges in processing order. Reject any edge that would introduce a directed cycle. This models only the ranked-pairs locking stage.

Why this case matters

A deterministic toy ballot model makes the stated counting convention executable.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(n, victories):
    return [list(edge) for edge in victories]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
chain=[[i,i+1] for i in range(N+2)]
check('long indirect cycle is rejected', solve(N+3,chain+[[N+2,0]]), chain)
check('acyclic transitive edge remains', solve(3,[[0,1],[1,2],[0,2]]), [[0,1],[1,2],[0,2]])
check('empty victories', solve(N+1,[]), [])
check('reverse contest rejected', solve(2,[[0,1],[1,0]]), [[0,1]])
check('rejected edge cannot affect later reachability', solve(4,[[0,1],[1,2],[2,0],[2,3],[3,0]]), [[0,1],[1,2],[2,3]])
check('disconnected components', solve(4,[[0,1],[2,3]]), [[0,1],[2,3]])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
long indirect cycle is rejected[[0, 1], [1, 2], [2, 3], [3, 0]][[0, 1], [1, 2], [2, 3]]Failed
acyclic transitive edge remains[[0, 1], [1, 2], [0, 2]][[0, 1], [1, 2], [0, 2]]Passed
empty victories[][]Passed
reverse contest rejected[[0, 1], [1, 0]][[0, 1]]Failed
rejected edge cannot affect later reachability[[0, 1], [1, 2], [2, 0], [2, 3], [3, 0]][[0, 1], [1, 2], [2, 3]]Failed
disconnected components[[0, 1], [2, 3]][[0, 1], [2, 3]]Passed

SHA-256 / 3afe95f1884afee6b576bc9b163efe17f36e7882b0a77f121da0c671912b099f

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(n, victories):
    locked=[]
    for a,b in victories:
        if [b,a] not in locked: locked.append([a,b])
    return locked
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
chain=[[i,i+1] for i in range(N+2)]
check('long indirect cycle is rejected', solve(N+3,chain+[[N+2,0]]), chain)
check('acyclic transitive edge remains', solve(3,[[0,1],[1,2],[0,2]]), [[0,1],[1,2],[0,2]])
check('empty victories', solve(N+1,[]), [])
check('reverse contest rejected', solve(2,[[0,1],[1,0]]), [[0,1]])
check('rejected edge cannot affect later reachability', solve(4,[[0,1],[1,2],[2,0],[2,3],[3,0]]), [[0,1],[1,2],[2,3]])
check('disconnected components', solve(4,[[0,1],[2,3]]), [[0,1],[2,3]])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
long indirect cycle is rejected[[0, 1], [1, 2], [2, 3], [3, 0]][[0, 1], [1, 2], [2, 3]]Failed
acyclic transitive edge remains[[0, 1], [1, 2], [0, 2]][[0, 1], [1, 2], [0, 2]]Passed
empty victories[][]Passed
reverse contest rejected[[0, 1]][[0, 1]]Passed
rejected edge cannot affect later reachability[[0, 1], [1, 2], [2, 0], [2, 3], [3, 0]][[0, 1], [1, 2], [2, 3]]Failed
disconnected components[[0, 1], [2, 3]][[0, 1], [2, 3]]Passed

SHA-256 / f54cd7500b86c7e6dcac9f8ce41cda36059d041e6c1c1a42f8b1dc2e26d37d71

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(n, victories):
    graph=[[] for _ in range(n)]; locked=[]
    for a,b in victories:
        pending=[b]; seen=set()
        while pending:
            node=pending.pop()
            if node in seen: continue
            seen.add(node)
            pending.extend(graph[node])
        if a not in seen:
            graph[a].append(b)
            locked.append([a,b])
    return locked
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
chain=[[i,i+1] for i in range(N+2)]
check('long indirect cycle is rejected', solve(N+3,chain+[[N+2,0]]), chain)
check('acyclic transitive edge remains', solve(3,[[0,1],[1,2],[0,2]]), [[0,1],[1,2],[0,2]])
check('empty victories', solve(N+1,[]), [])
check('reverse contest rejected', solve(2,[[0,1],[1,0]]), [[0,1]])
check('rejected edge cannot affect later reachability', solve(4,[[0,1],[1,2],[2,0],[2,3],[3,0]]), [[0,1],[1,2],[2,3]])
check('disconnected components', solve(4,[[0,1],[2,3]]), [[0,1],[2,3]])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
long indirect cycle is rejected[[0, 1], [1, 2], [2, 3]][[0, 1], [1, 2], [2, 3]]Passed
acyclic transitive edge remains[[0, 1], [1, 2], [0, 2]][[0, 1], [1, 2], [0, 2]]Passed
empty victories[][]Passed
reverse contest rejected[[0, 1]][[0, 1]]Passed
rejected edge cannot affect later reachability[[0, 1], [1, 2], [2, 3]][[0, 1], [1, 2], [2, 3]]Passed
disconnected components[[0, 1], [2, 3]][[0, 1], [2, 3]]Passed

SHA-256 / 00293b4c3be9edb542766dc116f1274f7c95e504b9e64304e3105af558f0bcb3

Verification & scope

Abstract counting rules only; excludes jurisdictional law, ballot authentication and election operations. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:39:00.125020+00:00.

Case digest / 8c3a13985df0b9adb280b287f20db936b45f01e88c7a848dcda3bfc531310308