AFTD Auto-Formalizing Theoretical Domains

has_fractional_matching

def

Given finite types V and C, a profile prof : V → LinearOrder C assigning a linear order to each voter v in V, voter weights p : V → ℝ, candidate weights q : C → ℝ, and a candidate a : C, has_fractional_matching prof p q a asserts the existence of a function w : V → C → ℝ such that for all v and c, 0 ≤ w v c, whenever 0 < w v c candidate c is weakly below a under the linear order prof v (that is, (prof v).le c a), for every voter v the sum of w v c over all c in C equals p v, and for every candidate c the sum of w v c over all v in V equals q c.

Statement

def has_fractional_matching {V C : Type*} [Fintype V] [Fintype C]
    (prof : V → LinearOrder C) (p : V → ℝ) (q : C → ℝ) (a : C) : Prop
Defined in
arXiv:2610.26535 Section 2.2
Verified
24 Oct 2026
Axioms
none listed
Used by 1
  • is_rank_score_veto_coreGiven a nonempty finite voter type V, a finite candidate type C with decidable equality, a scoring vector s : Fin (Fintype.card C) → ℚ, an…

Read back from the Lean

Given finite types $V$ and $C$, a function prof assigning to each $v \in V$ a linear order on $C$, functions $p : V \to \mathbb{R}$ and $q : C \to \mathbb{R}$, and an element $a \in C$, has_fractional_matching prof p q a asserts that there exists a function $w : V \to C \to \mathbb{R}$ such that: 1. For all $v \in V$ and $c \in C$, $w(v, c) \ge 0$; 2. For all $v \in V$ and $c \in C$, if $w(v, c) > 0$, then $c \le a$ with respect to the linear order prof v; 3. For all $v \in V$, $\sum_{c \in C} w(v, c) = p(v)$; and 4. For all $c \in C$, $\sum_{v \in V} w(v, c) = q(c)$.

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

/-- Existence of a fractional perfect matching in the domination graph of candidate a. -/
def has_fractional_matching {V C : Type*} [Fintype V] [Fintype C]
    (prof : V → LinearOrder C) (p : V → ℝ) (q : C → ℝ) (a : C) : Prop :=
  ∃ w : V → C → ℝ,
    (∀ v c, 0 ≤ w v c) ∧
    (∀ v c, 0 < w v c → (prof v).le c a) ∧
    (∀ v, ∑ c : C, w v c = p v) ∧
    (∀ c, ∑ v : V, w v c = q c)
See it in the graphDiscuss this resultChallenge it