AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it