is_propm_orientation
def
An orientation is PROPm if every agent's value for her bundle plus her PROPm slack d_i is at least her proportional share.
Statement
def is_propm_orientation {m n : ℕ} (ends : Fin m → Fin n × Fin n) (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop
- Defined in
- Fair Orientations: Proportionality and Equitability, arXiv:2602.18098 v2, Sec. 2 (relevant items, proportional share PROP_i = sum_{e in E_i} v_i(e)/n_e); PROPm as introduced at IJCAI 2021, with the maximin value restricted to relevant items as PROPX is in Def. 2.2; formalized by the operator (Claude), 2026-10-03
- Verified
- 03 Oct 2026
- Axioms
- none listed
- Built on 4
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
- orientation_maximin_valueThe PROPm slack d_i: the maximum over other agents j of agent i's least value for a relevant edge held by j.
- orientation_prop_shareThe proportional share of agent i in a multigraph orientation instance: half her value for her incident edges (each edge is relevant to…
- Used by 2
- propm_orientation_exists_of_le_fiveEvery loopless multigraph on at most five agents with nonnegative additive valuations admits a PROPm orientation (with the PROPm slack…
- propm_orientation_of_out_degree_twoIf the simple graph underlying a loopless multigraph has an orientation with every out-degree at most two, then for nonnegative additive…
Lean source view module on GitHub
/-- The orientation `σ` is PROPm: every agent `i` has `v_i(π_i) + d_i ≥ PROP_i`. -/ def is_propm_orientation {m n : ℕ} (ends : Fin m → Fin n × Fin n) (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop := ∀ i, orientation_prop_share ends u i ≤ additive_valuation (u i) (bundle_of σ i) + orientation_maximin_value ends u σ i