op_1719_bivalued_efx_sub_mms_two_agents_two_ratio
For two agents and item values in {1, 2}, there exists an additive instance with a complete EFX allocation in which some agent obtains strictly less than her 1-out-of-2 maximin share, so has_bivalued_efx_sub_mms_instance 2 2 2 holds.
Statement
theorem op_1719_bivalued_efx_sub_mms_two_agents_two_ratio :
has_bivalued_efx_sub_mms_instance 2 2 2- Related work
- arXiv:2611.15582
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- maximin_shareThe 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.
- 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.
- is_efx_goodsAn allocation is EFX if for every pair of distinct agents i and j, and every good g in j's bundle, agent i values her own bundle at least…
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
Read back from the Lean
There exists a natural number $m$ (a number of goods), a valuation function $u : \text{Fin } 2 \to \text{Fin } m \to \mathbb{R}$, an allocation function $\sigma : \text{Fin } m \to \text{Fin } 2$, and an agent $i \in \text{Fin } 2$ such that: 1. For every agent $j \in \text{Fin } 2$ and every good $g \in \text{Fin } m$, $u(j, g) = 1$ or $u(j, g) = 2$; 2. The allocation $\sigma$ is EFX (envy-free up to any good) for $u$: for all distinct agents $i', j' \in \text{Fin } 2$ and every good $g$ in $j'$'s bundle ($\sigma(g) = j'$), agent $i'$'s additive valuation of $j'$'s bundle with $g$ removed is less than or equal to agent $i'$'s additive valuation of their own bundle; and 3. Agent $i$'s additive valuation of their assigned bundle $\{g \in \text{Fin } m \mid \sigma(g) = i\}$ is strictly less than their 2-maximin share, which is the supremum over all partitions $P : \text{Fin } m \to \text{Fin } 2$ of the minimum over $k \in \text{Fin } 2$ of the additive valuation of $\{g \in \text{Fin } m \mid P(g) = k\}$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem shows that for two agents and item values in {1, 2}, an EFX allocation does not guarantee an agent her 1-out-of-2 maximin share. The counterexample uses 4 items where both agents value items 0 and 1 at 1, and items 2 and 3 at 2. Allocating {0, 1} to agent 0 and {2, 3} to agent 1 is EFX because removing either item of value 2 from agent 1's bundle leaves a value of 2, matching agent 0's bundle value. However, agent 0 could partition the items into {0, 2} and {1, 3}, each worth 3, meaning agent 0's maximin share is at least 3, strictly exceeding her allocated value of 2.
Define the valuation function u, the allocation σ, and a candidate partition P.
We construct a counterexample with 2 agents and 4 goods. The valuation function u assigns value 1 to goods 0 and 1, and value 2 to goods 2 and 3 for both agents. The allocation σ gives bundle {0, 1} to agent 0 and bundle {2, 3} to agent 1. The partition P assigns goods by their index modulo 2 into bundles {0, 2} and {1, 3}, with integer arithmetic (`omega`) verifying that the remainder modulo 2 is strictly less than 2.
def op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u : Fin 2 → Fin 4 → ℝ := fun _ g => if g.val < 2 then 1 else 2 def op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_σ : Fin 4 → Fin 2 := fun g => if g.val < 2 then 0 else 1 def op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_P : Fin 4 → Fin 2 := fun g => ⟨g.val % 2, by omega⟩
Compute the explicit bundles assigned by the allocation σ and the partition P.
By finite set decidability (`decide`), the bundles under allocation σ are σ(0) = {0, 1} and σ(1) = {2, 3}, while the bundles under partition P are P(0) = {0, 2} and P(1) = {1, 3}.
lemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b0 : bundle_of op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_σ 0 = {0, 1} := by decide lemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b1 : bundle_of op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_σ 1 = {2, 3} := by decide lemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_p0 : bundle_of op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_P 0 = {0, 2} := by decide lemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_p1 : bundle_of op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_P 1 = {1, 3} := by decide
Evaluate the additive valuation of each relevant two-item bundle.
For any agent i, we compute the additive valuation of the pairs {0, 1}, {2, 3}, {0, 2}, and {1, 3}. In each case, `Finset.sum_pair` rewrites the sum over the pair into the sum of the two elements, yielding 1 + 1 = 2 for {0, 1}, 2 + 2 = 4 for {2, 3}, and 1 + 2 = 3 for both {0, 2} and {1, 3}.
uses
Finset.sum_pairlemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_01 (i : Fin 2) : additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u i) {0, 1} = 2 := by dsimp [additive_valuation, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u] have : (0 : Fin 4) ≠ 1 := by decide rw [Finset.sum_pair this] norm_num lemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_23 (i : Fin 2) : additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u i) {2, 3} = 4 := by dsimp [additive_valuation, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u] have : (2 : Fin 4) ≠ 3 := by decide rw [Finset.sum_pair this] norm_num lemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_02 (i : Fin 2) : additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u i) {0, 2} = 3 := by dsimp [additive_valuation, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u] have : (0 : Fin 4) ≠ 2 := by decide rw [Finset.sum_pair this] norm_num lemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_13 (i : Fin 2) : additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u i) {1, 3} = 3 := by dsimp [additive_valuation, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u] have : (1 : Fin 4) ≠ 3 := by decide rw [Finset.sum_pair this] norm_num
The additive valuation of any singleton bundle equals the item's individual value.
By unfolding the definition of additive valuation and rewriting with `Finset.sum_singleton`, the valuation of any singleton {g} for agent i simplifies directly to u_i(g).
uses
Finset.sum_singletonlemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_singleton (i : Fin 2) (g : Fin 4) : additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u i) {g} = op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u i g := by dsimp [additive_valuation] rw [Finset.sum_singleton]
Establish exhaustive case analyses for indices in Fin 2 and Fin 4.
Linear arithmetic (`omega`) proves that any index in Fin 2 is either 0 or 1, and any index in Fin 4 is 0, 1, 2, or 3.
lemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin2_cases (i : Fin 2) : i = 0 ∨ i = 1 := by omega lemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin4_cases (g : Fin 4) : g = 0 ∨ g = 1 ∨ g = 2 ∨ g = 3 := by omega
The allocation σ is envy-free up to any good (EFX).
We verify that no agent envies the other after removing any single item. By case analysis on distinct agents i and j, the only cases are (0, 1) and (1, 0). For agent 0 facing agent 1's bundle {2, 3}, removing either item 2 or item 3 leaves a singleton of value 2, which does not exceed agent 0's bundle value of 2. For agent 1 facing agent 0's bundle {0, 1}, removing either item leaves value 1, which is strictly less than agent 1's bundle value of 4. Decisions on non-membership are discharged by finite set evaluation (`decide`).
uses
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin2_cases,op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b0,op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b1,op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin4_cases,op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_singleton,op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_01,op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_23lemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_efx : is_efx_goods op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_σ := by intro i j hij g hg rcases op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin2_cases i with rfl | rfl <;> rcases op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin2_cases j with rfl | rfl · contradiction · rw [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b0, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b1] at * rcases op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin4_cases g with rfl | rfl | rfl | rfl · exfalso; revert hg; decide · exfalso; revert hg; decide · have : ({2, 3} : Finset (Fin 4)).erase 2 = {3} := by decide rw [this, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_singleton, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_01] dsimp [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u]; norm_num · have : ({2, 3} : Finset (Fin 4)).erase 3 = {2} := by decide rw [this, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_singleton, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_01] dsimp [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u]; norm_num · rw [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b0, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b1] at * rcases op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin4_cases g with rfl | rfl | rfl | rfl · have : ({0, 1} : Finset (Fin 4)).erase 0 = {1} := by decide rw [this, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_singleton, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_23] dsimp [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u]; norm_num · have : ({0, 1} : Finset (Fin 4)).erase 1 = {0} := by decide rw [this, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_singleton, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_23] dsimp [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u]; norm_num · exfalso; revert hg; decide · exfalso; revert hg; decide · contradiction
Agent 0's 1-out-of-2 maximin share is at least 3.
The maximin share is the supremum over all 2-partitions of the minimum bundle value. For the specific partition P, agent 0 values both bundles P(0) = {0, 2} and P(1) = {1, 3} at 3, so the infimum over bundles is at least 3 (`le_ciInf`). Since the set of partitions is finite, the range of minimum values is bounded above (`Finite.bddAbove_range`), and thus the supremum over all partitions is at least the value achieved by P (`le_ciSup`). By transitivity (`le_trans`), 3 ≤ maximin_share(u_0, 2).
uses
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin2_cases,op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_p0,op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_02,op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_p1,op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_13,le_ciInf,Finite.bddAbove_range,le_ciSup,le_translemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_mms_bound : 3 ≤ maximin_share (additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u 0)) 2 := by dsimp [maximin_share] have h1 : 3 ≤ ⨅ k : Fin 2, additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u 0) (bundle_of op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_P k) := by apply le_ciInf intro k rcases op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin2_cases k with rfl | rfl · rw [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_p0, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_02] · rw [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_p1, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_13] have h2 : (⨅ k : Fin 2, additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u 0) (bundle_of op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_P k)) ≤ ⨆ P : Fin 4 → Fin 2, ⨅ k, additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u 0) (bundle_of P k) := by have hb : BddAbove (Set.range (fun P : Fin 4 → Fin 2 => ⨅ k, additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u 0) (bundle_of P k))) := Finite.bddAbove_range _ exact le_ciSup hb op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_P exact le_trans h1 h2
There exists a bivalued EFX instance where an agent receives strictly less than her maximin share.
We instantiate `has_bivalued_efx_sub_mms_instance 2 2 2` with 4 goods, valuations u, allocation σ, and agent 0. Every item valuation is in {1, 2} by definition of u. The allocation σ is complete and EFX by `op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_efx`. Finally, agent 0 receives bundle σ(0) = {0, 1} with valuation 2, which is strictly less than her maximin share of at least 3 (`linarith` using `op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_mms_bound`).
uses
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_efx,op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b0,op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_01,op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_mms_bound/-- For two agents and ratio R = 2, there exists a complete EFX allocation where some agent receives strictly less than her 1-out-of-2 maximin share. -/ theorem op_1719_bivalued_efx_sub_mms_two_agents_two_ratio : has_bivalued_efx_sub_mms_instance 2 2 2 := by dsimp [has_bivalued_efx_sub_mms_instance] refine ⟨4, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_σ, 0, ?_, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_efx, ?_⟩ · intro j g dsimp [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u] split_ifs · left; rfl · right; rfl · rw [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b0, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_01] linarith [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_mms_bound]
Finset.sum_pair- The sum of a function over a two-element set {a, b} with a ≠ b equals f(a) + f(b).
Finset.sum_singleton- The sum of a function over a singleton set {a} equals f(a).
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin2_cases- Every element of Fin 2 is either 0 or 1.
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b0- The bundle allocated to agent 0 under σ is {0, 1}.
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b1- The bundle allocated to agent 1 under σ is {2, 3}.
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin4_cases- Every element of Fin 4 is 0, 1, 2, or 3.
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_singleton- The additive valuation of any singleton bundle {g} equals the individual value u_i(g).
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_01- The additive valuation of bundle {0, 1} is 2 for any agent.
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_23- The additive valuation of bundle {2, 3} is 4 for any agent.
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_p0- The bundle with index 0 in partition P is {0, 2}.
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_02- The additive valuation of bundle {0, 2} is 3 for any agent.
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_p1- The bundle with index 1 in partition P is {1, 3}.
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_13- The additive valuation of bundle {1, 3} is 3 for any agent.
le_ciInf- A value c is at most the infimum of f over a nonempty domain if c ≤ f(x) for all x.
Finite.bddAbove_range- The range of a function from a finite type to a preorder is bounded above.
le_ciSup- Any value in the range of a function that is bounded above is at most the supremum of the function.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_efx- The allocation σ is envy-free up to any good (EFX) under valuations u.
op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_mms_bound- Agent 0's 1-out-of-2 maximin share under valuation u_0 is at least 3.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
def op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u : Fin 2 → Fin 4 → ℝ := fun _ g => if g.val < 2 then 1 else 2def op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_σ : Fin 4 → Fin 2 := fun g => if g.val < 2 then 0 else 1def op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_P : Fin 4 → Fin 2 := fun g => ⟨g.val % 2, by omega⟩lemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b0 : bundle_of op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_σ 0 = {0, 1} := by decidelemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b1 : bundle_of op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_σ 1 = {2, 3} := by decidelemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_p0 : bundle_of op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_P 0 = {0, 2} := by decidelemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_p1 : bundle_of op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_P 1 = {1, 3} := by decidelemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_01 (i : Fin 2) : additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u i) {0, 1} = 2 := by dsimp [additive_valuation, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u] have : (0 : Fin 4) ≠ 1 := by decide rw [Finset.sum_pair this] norm_numlemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_23 (i : Fin 2) : additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u i) {2, 3} = 4 := by dsimp [additive_valuation, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u] have : (2 : Fin 4) ≠ 3 := by decide rw [Finset.sum_pair this] norm_numlemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_02 (i : Fin 2) : additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u i) {0, 2} = 3 := by dsimp [additive_valuation, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u] have : (0 : Fin 4) ≠ 2 := by decide rw [Finset.sum_pair this] norm_numlemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_13 (i : Fin 2) : additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u i) {1, 3} = 3 := by dsimp [additive_valuation, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u] have : (1 : Fin 4) ≠ 3 := by decide rw [Finset.sum_pair this] norm_numlemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_singleton (i : Fin 2) (g : Fin 4) : additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u i) {g} = op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u i g := by dsimp [additive_valuation] rw [Finset.sum_singleton]lemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin2_cases (i : Fin 2) : i = 0 ∨ i = 1 := by omegalemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin4_cases (g : Fin 4) : g = 0 ∨ g = 1 ∨ g = 2 ∨ g = 3 := by omegalemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_efx : is_efx_goods op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_σ := by intro i j hij g hg rcases op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin2_cases i with rfl | rfl <;> rcases op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin2_cases j with rfl | rfl · contradiction · rw [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b0, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b1] at * rcases op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin4_cases g with rfl | rfl | rfl | rfl · exfalso; revert hg; decide · exfalso; revert hg; decide · have : ({2, 3} : Finset (Fin 4)).erase 2 = {3} := by decide rw [this, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_singleton, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_01] dsimp [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u]; norm_num · have : ({2, 3} : Finset (Fin 4)).erase 3 = {2} := by decide rw [this, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_singleton, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_01] dsimp [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u]; norm_num · rw [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b0, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b1] at * rcases op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin4_cases g with rfl | rfl | rfl | rfl · have : ({0, 1} : Finset (Fin 4)).erase 0 = {1} := by decide rw [this, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_singleton, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_23] dsimp [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u]; norm_num · have : ({0, 1} : Finset (Fin 4)).erase 1 = {0} := by decide rw [this, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_singleton, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_23] dsimp [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u]; norm_num · exfalso; revert hg; decide · exfalso; revert hg; decide · contradictionlemma op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_mms_bound : 3 ≤ maximin_share (additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u 0)) 2 := by dsimp [maximin_share] have h1 : 3 ≤ ⨅ k : Fin 2, additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u 0) (bundle_of op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_P k) := by apply le_ciInf intro k rcases op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_fin2_cases k with rfl | rfl · rw [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_p0, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_02] · rw [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_p1, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_13] have h2 : (⨅ k : Fin 2, additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u 0) (bundle_of op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_P k)) ≤ ⨆ P : Fin 4 → Fin 2, ⨅ k, additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u 0) (bundle_of P k) := by have hb : BddAbove (Set.range (fun P : Fin 4 → Fin 2 => ⨅ k, additive_valuation (op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u 0) (bundle_of P k))) := Finite.bddAbove_range _ exact le_ciSup hb op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_P exact le_trans h1 h2/-- For two agents and ratio R = 2, there exists a complete EFX allocation where some agent receives strictly less than her 1-out-of-2 maximin share. -/theorem op_1719_bivalued_efx_sub_mms_two_agents_two_ratio : has_bivalued_efx_sub_mms_instance 2 2 2 := by dsimp [has_bivalued_efx_sub_mms_instance] refine ⟨4, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_σ, 0, ?_, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_efx, ?_⟩ · intro j g dsimp [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_u] split_ifs · left; rfl · right; rfl · rw [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_b0, op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_sum_01] linarith [op_1719_bivalued_efx_sub_mms_two_agents_two_ratio_mms_bound]