AFTD Auto-Formalizing Theoretical Domains

is_line_distance_preference_profile

def

There are n agents and n items, both indexed by {0, ..., n-1}; agent i sits at the real position a_i and item j at b_j. Each agent's ranking is given as a permutation pref i of {0, ..., n-1}, with pref i k the item agent i ranks k-th (so every item is ranked exactly once). The profile is a distance-ranking profile when, for every agent i and ranks k < k', the item ranked k is at most as far from a_i as the item ranked k': |a_i - b_{pref i k}| <= |a_i - b_{pref i k'}| (ties in distance may be ordered either way).

Statement

def is_line_distance_preference_profile {n : ℕ} (a b : Fin n → ℝ) (pref : Fin n → Equiv.Perm (Fin n)) : Prop
Defined in
arXiv:2611.05777 (Sublinear Metric Distortion for Matching), Sec. 1 and Sec. 6: one-sided matching of n agents to n items with ordinal rankings by distance; the probabilistic serial rule (agents rank items by distance), specialised to the real line
Verified
05 Nov 2026
Axioms
none listed
Used by 14

Read back from the Lean

Given a natural number $n$, two functions $a, b : \text{Fin } n \to \mathbb{R}$, and a family of permutations $\text{pref} : \text{Fin } n \to \text{Equiv.Perm}(\text{Fin } n)$, the predicate asserts that for every index $i : \text{Fin } n$ and all indices $k, k' : \text{Fin } n$, if $k < k'$, then $|a(i) - b(\text{pref}(i)(k))| \le |a(i) - b(\text{pref}(i)(k'))|$. In other words, for each $i$, the permutation $\text{pref}(i)$ orders the elements of $\text{Fin } n$ by non-decreasing distance between $a(i)$ and $b(\cdot)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Agents at positions `a i` and items at positions `b j` on the real line (both indexed by `Fin n`); each agent's ranking is a permutation `pref i`, with `pref i k` her `k`-th item, and it lists items by non-decreasing distance, ties broken arbitrarily. -/
def is_line_distance_preference_profile {n : ℕ} (a b : Fin n → ℝ) (pref : Fin n → Equiv.Perm (Fin n)) : Prop :=
  ∀ i : Fin n, ∀ k k' : Fin n, k < k' → |a i - b (pref i k)| ≤ |a i - b (pref i k')|
See it in the graphDiscuss this resultChallenge it