picking_sequence_outcome_round_robin_two_agents_four_items
Example 3.8 of arXiv:2610.23040: with two agents reporting a > b > c > d and b > c > d > a, Round-Robin gives {a, c} to agent 1 and {b, d} to agent 2.
Statement
theorem picking_sequence_outcome_round_robin_two_agents_four_items : picking_sequence_outcome (round_robin_sequence 2 4) (fun i : Fin 2 => if i = 0 then Equiv.refl (Fin 4) else ⟨![1, 2, 3, 0], ![3, 0, 1, 2], by decide, by decide⟩) = ![{0, 2}, {1, 3}]
- Formalizes
- Sanity lemma for picking_sequence_outcome: Example 3.8 of arXiv:2610.23040.
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- picking_sequence_outcomeThe allocation returned by the picking-sequence mechanism PS_π: agents act in the order seq, and at each turn the active agent takes its…
- round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
The proof, explained
The theorem verifies Example 3.8 of arXiv:2610.23040, which states that Round-Robin on four items between two agents with preference orders 0 > 1 > 2 > 3 and 1 > 2 > 3 > 0 allocates items {0, 2} to agent 0 and {1, 3} to agent 1. The picking sequence is [0, 1, 0, 1], and the agents iteratively select their most-preferred available items. Because all sets, rankings, and sequences are finite, the result is proved entirely by finite evaluation via `decide`.
Round-Robin allocation on four items between two agents yields {0, 2} for agent 0 and {1, 3} for agent 1. automation
Both the well-definedness of agent 1's preference permutation (checking that the inverted list is a two-sided inverse) and the execution of the Round-Robin sequence `[0, 1, 0, 1]` under `picking_sequence_outcome` are finite computations over `Fin 2` and `Fin 4`. The `decide` tactic evaluates the fold over the sequence directly to confirm the resulting allocation.
else ⟨![1, 2, 3, 0], ![3, 0, 1, 2], by decide, by decide⟩) = ![{0, 2}, {1, 3}] := by first | (simp_all; done) | omega | decide | linarith | positivity | (aesop; done)
- The proof script uses a fallback search `first | (simp_all; done) | omega | decide | linarith | positivity | (aesop; done)`; the first tactic that succeeds is `decide`.
- The two inline occurrences of `by decide` on line 4 establish that the lookup tables `![1, 2, 3, 0]` and `![3, 0, 1, 2]` are mutual inverses, proving that agent 1's preference ranking is a well-defined permutation (`Equiv`) on `Fin 4`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem picking_sequence_outcome_round_robin_two_agents_four_items : picking_sequence_outcome (round_robin_sequence 2 4) (fun i : Fin 2 => if i = 0 then Equiv.refl (Fin 4) else ⟨![1, 2, 3, 0], ![3, 0, 1, 2], by decide, by decide⟩) = ![{0, 2}, {1, 3}] := by first | (simp_all; done) | omega | decide | linarith | positivity | (aesop; done)