AFTD Auto-Formalizing Theoretical Domains

op_1719_bivalued_efx_sub_mms_two_agents_two_ratio

theoremverifiedoriginal

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.

  1. 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.

    lines 1–9

    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⟩
    
  2. 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}.

    lines 10–21

    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
    
  3. 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}.

    lines 22–49

    uses Finset.sum_pair

    lemma 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
    
  4. 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).

    lines 50–55

    uses Finset.sum_singleton

    lemma 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]
    
  5. 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.

    lines 56–59

    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
    
  6. 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`).

    lines 60–94

    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_23

    lemma 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
    
  7. 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).

    lines 95–119

    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_trans

    lemma 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
    
  8. 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`).

    lines 120–134

    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

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