is_envy_free_with_subsidy
def
An allocation with nonnegative payments p is envy-free if v_i(A_i) + p_i ≥ v_i(A_j) + p_j for all agents i, j.
Statement
def is_envy_free_with_subsidy {m n : ℕ} (v : Fin n → Finset (Fin m) → ℝ) (σ : Fin m → Fin n) (p : 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
- Built on 1
- 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.
- Used by 5
- 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…
- 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…
- is_envy_free_with_subsidy_perm_leIf (σ, p) is envy-free with subsidies, then for every permutation π of agents, ∑_i v_i(A_{π(i)}) ≤ ∑_i v_i(A_i).
- scaled_common_ratio_bivalued_efx_fpo_envyfreeable_zero_goodsWhen m = 0, the empty allocation Fin.elim0 and zero subsidy vector 0 satisfy EFX, envy-freeness with subsidies, and fractional Pareto…
Lean source view module on GitHub
/-- The allocation `σ` with payments `p ≥ 0` is envy-free: `v i (A j) + p j ≤ v i (A i) + p i` for all agents `i`, `j`. -/ def is_envy_free_with_subsidy {m n : ℕ} (v : Fin n → Finset (Fin m) → ℝ) (σ : Fin m → Fin n) (p : Fin n → ℝ) : Prop := (∀ i, 0 ≤ p i) ∧ ∀ i j, v i (bundle_of σ j) + p j ≤ v i (bundle_of σ i) + p i