AFTD Auto-Formalizing Theoretical Domains

picking_sequence_outcome_round_robin_two_agents_four_items

theoremverifiedformalization

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`.

  1. 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.

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

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

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)
See it in the graphDiscuss this resultChallenge it