AFTD Auto-Formalizing Theoretical Domains

maximin_share

def

The maximin share of a valuation among n agents: the maximum, over partitions of the items into n bundles, of the value of the worst bundle.

Statement

noncomputable def maximin_share {m : ℕ} (v : Finset (Fin m) → ℝ) (n : ℕ) : ℝ
Defined in
Exploring Relations among Fairness Notions in Discrete Fair Division, arXiv:2502.02815 v3, Defs. 5, 7, 8, 11; formalized by the operator (Claude), 2026-10-02
Verified
02 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 9
  • complete_pmms_matroid_rank_sharp_mms_factorFor every integer n ≥ 2, every finite set of m indivisible goods, every profile of matroid-rank valuations v_1, ..., v_n on the goods, and…
  • mms_exists_monotoneEvery instance with n agents and m goods, in which every agent has a monotone valuation v_i with v_i(∅) = 0, has an MMS allocation: an…
  • has_bivalued_efx_sub_mms_instanceGiven natural numbers n, R, and d, there exists a finite additive instance with n agents where each item value is either 1 or the natural…
  • op_1719_bivalued_efx_sub_mms_two_agents_two_ratioFor two agents and item values in {1, 2}, there exists an additive instance with a complete EFX allocation in which some agent obtains…
  • mms_exists_monotone_of_leWith n ≥ 1 agents and at most n goods, monotone valuations always admit an MMS allocation (give good j to agent j); so μ(n) ≥ n.
  • pmms_fair_not_imp_mms_fairOpen problem 4 of arXiv:2502.02815 has a negative answer: for submodular goods with binary marginals and equal entitlements, pairwise MMS…
  • pmms_matroid_rank_mms_factor_two_agentsFor two agents with matroid-rank valuations, every complete pairwise maximin-share fair allocation gives each agent at least 1/(2-1) = 1…
  • mms_exists_monotone_of_partition_coverReduction to MMS partitions: if for every choice of one partition P_i of the m goods into n bundles per agent there is an allocation in…
  • mms_two_agents_four_goods_not_existsWith two agents, four goods and monotone valuations, an MMS allocation need not exist (both agents have MMS 2 in the Table 1 instance, but…

Lean source view module on GitHub

/-- The maximin share of a valuation among `n` agents (arXiv:2502.02815, Def. 7): the best worst bundle over all partitions of the items into `n` bundles. -/
noncomputable def maximin_share {m : ℕ} (v : Finset (Fin m) → ℝ) (n : ℕ) : ℝ :=
  ⨆ P : Fin m → Fin n, ⨅ k : Fin n, v (bundle_of P k)
See it in the graphDiscuss this resultChallenge it