is_orientation
def
An allocation of the edges of a multigraph is an orientation if every edge goes to one of its two endpoints.
Statement
def is_orientation {m n : ℕ} (ends : Fin m → Fin n × Fin n) (σ : Fin m → Fin n) : Prop
- Defined in
- On the Subsidy of Envy-Free Orientations in Graphs, arXiv:2502.13671 v1, Sec. 2; formalized by the operator (Claude), 2026-10-03
- Verified
- 03 Oct 2026
- Axioms
- none listed
- Used by 6
- 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…
- multigraph_orientation_subsidy_not_le_oneFor three agents on a multigraph with monotone valuations, a total subsidy of n - 2 = 1 does not always suffice for an envy-free…
- 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…
- propm_mem_betweenUnder an orientation, an edge incident to i that is held by another agent j lies in the parallel class of i and j.
- multigraph_orientation_subsidy_four_agentsThere is a four-agent multigraph with monotone graph valuations, normalised so the largest marginal is 1, in which every envy-free…
- multigraph_orientation_subsidy_three_halvesThere is a three-agent multigraph with monotone graph valuations, normalised so the largest marginal is 1, in which every envy-free…
Lean source view module on GitHub
/-- The allocation `σ` is an orientation of the multigraph whose edge `e` joins `(ends e).1` and `(ends e).2`: every edge goes to one of its two endpoints. -/ def is_orientation {m n : ℕ} (ends : Fin m → Fin n × Fin n) (σ : Fin m → Fin n) : Prop := ∀ e, σ e = (ends e).1 ∨ σ e = (ends e).2