is_line_distance_preference_profile
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
- probabilistic_serial_line_three_agents_le_of_first_choices_12Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 1 first and item 2 second. For three agents…
- probabilistic_serial_line_three_agents_le_of_first_choices_20Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 2 first and item 0 second. For three agents…
- probabilistic_serial_line_distortion_ge_sharpSharpness half of OP-1158: for every n >= 2 and every real c < n there are n agents and n items at real positions with positive minimum…
- is_line_distance_preference_profile_of_const_itemsSanity check: when all items sit at one point, every profile of rankings is a distance-ranking profile.
- probabilistic_serial_equispaced_distortion_le_two_agentsFor two agents at real locations and two equispaced items at 0 and 1, the probabilistic serial cost under any distance preference profile…
- probabilistic_serial_line_distortion_le_of_item_wait_leIf on an instance (agents at a, items at b, distance rankings pref) every item's waiting cost is at most OPT, then the probabilistic…
- probabilistic_serial_line_three_agents_le_of_first_choices_21Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 2 first and item 1 second. For three agents…
- probabilistic_serial_equispaced_distortion_le_three_agentsFor three agents at real locations and three equispaced items at 0, 1, and 2, the probabilistic serial cost under any distance preference…
- probabilistic_serial_line_distortion_le_two_agentsCase n = 2 of OP-1158: for two agents at real positions a_0, a_1 and two items at real positions b_0, b_1, with each agent ranking the…
- probabilistic_serial_line_three_agents_le_of_first_choices_10Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 1 first and item 0 second. For three agents…
- probabilistic_serial_line_cost_le_add_item_waitFor n agents at real positions a and n items at real positions b, each agent ranking the items by distance (ties broken arbitrarily), the…
- probabilistic_serial_line_three_agents_le_of_first_choices_01Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 0 first and item 1 second. For three agents…
- probabilistic_serial_line_three_agents_le_of_first_choices_02Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 0 first and item 2 second. For three agents…
- probabilistic_serial_line_distortion_le_three_agentsCase n = 3 of OP-1158: for three agents at real positions a_0, a_1, a_2 and three items at real positions b_0, b_1, b_2, with each agent…
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')|