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