Team-Draft Interleaving (Online Ranking Eval)

Background

Interleaving is the gold-standard online ranking evaluation: build a single mixed result list by alternately drawing from rankers A and B (random first-mover per query), then attribute clicks to whichever ranker contributed each shown doc. Higher statistical power per session than parallel A/B at the same traffic.

Problem statement

Implement team_draft_interleave(list_a, list_b, k, rng_seed=0):

1. Toss a coin for who drafts first.
2. The first-up ranker contributes its next unseen doc; the second-up ranker then contributes its next unseen doc.
3. Repeat until the interleaved list has $k$ docs or both rankers are exhausted.

Return (interleaved, contributors). contributors[i] is "A" or "B".

Input

• list_a, list_b — ranked doc-id sequences from rankers A and B.
• k — int >= 0, output cap.
• rng_seed — int, the coin-flip RNG seed.

Output

Returns a tuple (interleaved: list, contributors: list[str]) with len(interleaved) == len(contributors).

Examples

Example 1 — length cap respected

Input:  list_a=[1,2,3], list_b=[3,4,5], k=4
Output: len(interleaved) <= 4

Example 2 — no duplicates

Input:  partially-overlapping lists
Output: every doc appears at most once

Example 3 — reproducible with seed

Input:  same seed
Output: identical interleaving

Constraints

• Doc IDs are hashable.
• Skip docs already added (dedup) when both rankers offer the same item.
• Returns Python lists.

Notes

• Why team-draft. Each shown doc is attributed to exactly one ranker → unbiased credit assignment for clicks. Naive "round-robin" overweights the first list when both rankers agree.
• Statistical power. A team-draft session yields a paired comparison signal that's roughly 2–4× more powerful than parallel A/B at the same traffic.