AFTD Auto-Formalizing Theoretical Domains

stake_share_pne_exists

theoremverifiedoriginal

For n >= 2 agents with costs in [0, L], if K M >= 3 n^2 L then the stake-share mechanism has a pure Nash equilibrium (each agent submitting a single stake).

Statement

theorem stake_share_pne_exists {n : ℕ} (hn : 2 ≤ n) {L K M : ℝ} (hL : 0 ≤ L) (hK : 0 < K)
    (hM : 0 < M) (hKM : 3 * (n : ℝ) ^ 2 * L ≤ K * M) (c : Fin n → ℝ)
    (hc : ∀ i, 0 ≤ c i ∧ c i ≤ L) :
    ∃ β : Fin n → List ℝ, is_procurement_pne proportional_share_alloc
      (proportional_share_pay (stake_share_pool L K M)) c β
Related work
operator (Claude), 2026-10-03: answer to the open question of arXiv:2603.27779 v1, Sec. 6 (is there a procurement mechanism that is Sybil-proof and ex-post safe with non-winner-take-all equilibria?): yes, the stake-share mechanism (work and a pool L + K max(0, M - W) shared in proportion to free stakes) is Sybil-proof, ex-post safe for costs up to L, and all its PNE give work to at least two agents; ex-post safety for all costs is impossible together with PNE in this proportional-share class
Verified
03 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • is_procurement_pneA profile of (multi-)bids is a pure Nash equilibrium of the procurement game if all bids are nonnegative and no agent can gain by…
  • procurement_others_bids_sumThe total of the other agents' bids is the total of all bids minus agent i's total.
  • proportional_share_allocProportional-share allocation: identity j receives the fraction b_j / W of the work, W being the total bid.
  • proportional_share_payProportional-share payment with total pool pool(W): identity j is paid its work share times pool(W).
  • proportional_share_utility_eqIn a proportional-share mechanism an agent's utility is s / (s + R) times (pool(s + R) - c).
  • stake_share_best_responseBest-response bound for the stake-share mechanism: if (L - c + K M) R = K W^2, 0 <= R, 0 < W <= M and the equilibrium utility (W - R)/W…
  • stake_share_poolThe stake-share pool L + K max(0, M - W) as a function of the total stake W.
Used by 1

Lean source view module on GitHub

/-- For any number `n ≥ 2` of agents with costs in `[0, L]`, once `K * M ≥ 3 n² L` the stake-share mechanism has a pure Nash equilibrium (in single bids). -/theorem stake_share_pne_exists {n : ℕ} (hn : 2 ≤ n) {L K M : ℝ} (hL : 0 ≤ L) (hK : 0 < K)    (hM : 0 < M) (hKM : 3 * (n : ℝ) ^ 2 * L ≤ K * M) (c : Fin n → ℝ)    (hc : ∀ i, 0 ≤ c i ∧ c i ≤ L) :    ∃ β : Fin n → List ℝ, is_procurement_pne proportional_share_alloc      (proportional_share_pay (stake_share_pool L K M)) c β := by  have hn' : (2 : ℝ) ≤ n := by exact_mod_cast hn  set D := K * M with hDdef  have hD : 0 < D := mul_pos hK hM  set A : Fin n → ℝ := fun i => L - c i + D with hAdef  have hA_lo : ∀ i, D ≤ A i := fun i => by simp only [hAdef]; linarith [(hc i).2]  have hA_hi : ∀ i, A i ≤ D + L := fun i => by simp only [hAdef]; linarith [(hc i).1]  have hA_pos : ∀ i, 0 < A i := fun i => lt_of_lt_of_le hD (hA_lo i)  set H := ∑ j, 1 / A j with hHdef  have hH_lo : (n : ℝ) / (D + L) ≤ H := by    have h : ∑ _j : Fin n, 1 / (D + L) ≤ H :=      Finset.sum_le_sum (fun j _ => one_div_le_one_div_of_le (hA_pos j) (hA_hi j))    rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] at h    rw [div_eq_mul_one_div]; exact h  have hDL : 0 < D + L := by linarith  have hH_pos : 0 < H := lt_of_lt_of_le (div_pos (by linarith) hDL) hH_lo  set W := ((n : ℝ) - 1) / (K * H) with hWdef  have hW : 0 < W := div_pos (by linarith) (mul_pos hK hH_pos)  have hKW : K * W = ((n : ℝ) - 1) / H := by    rw [hWdef]; field_simp  have hKWH : K * W * H = (n : ℝ) - 1 := by rw [hKW]; field_simp  -- `K W ≤ (n - 1)(D + L)/n ≤ D`  have hKW_le : K * W ≤ ((n : ℝ) - 1) * (D + L) / n := by    rw [hKW, div_le_iff₀ hH_pos]    have h1 : ((n : ℝ) - 1) * (D + L) / n * ((n : ℝ) / (D + L)) = (n : ℝ) - 1 := by      field_simp    have h2 : 0 ≤ ((n : ℝ) - 1) * (D + L) / n :=      div_nonneg (mul_nonneg (by linarith) (by linarith)) (by linarith)    nlinarith [mul_le_mul_of_nonneg_left hH_lo h2]  have hnL : ((n : ℝ) - 1) * L ≤ D := by nlinarith  have hKW_D : K * W ≤ D := by    refine hKW_le.trans ?_    rw [div_le_iff₀ (by linarith)]    nlinarith  have hWM : W ≤ M := by    have : K * W ≤ K * M := hKW_D    exact le_of_mul_le_mul_left this hK  set s : Fin n → ℝ := fun i => W - K * W ^ 2 / A i with hsdef  have hR_nonneg : ∀ i, 0 ≤ K * W ^ 2 / A i := fun i => by    have := hA_pos i; positivity  have hR_le : ∀ i, K * W ^ 2 / A i ≤ W := fun i => by    rw [div_le_iff₀ (hA_pos i)]    have : K * W ≤ A i := hKW_D.trans (hA_lo i)    nlinarith  have hsum : ∑ j, s j = W := by    simp only [hsdef]    rw [Finset.sum_sub_distrib, Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul]    have : ∑ j, K * W ^ 2 / A j = K * W * H * W := by      rw [hHdef, Finset.mul_sum, Finset.sum_mul]      exact Finset.sum_congr rfl (fun j _ => by ring)    rw [this, hKWH]; ring  refine ⟨fun i => [s i], ⟨fun i b hb => ?_, fun i σ hσ => ?_⟩⟩  · simp only [List.mem_singleton] at hb    rw [hb]; simp only [hsdef]; linarith [hR_le i]  · have hσs : 0 ≤ σ.sum := List.sum_nonneg hσ    rw [proportional_share_utility_eq, proportional_share_utility_eq, procurement_others_bids_sum]    simp only [List.sum_singleton]    rw [hsum]    have hsi : s i = W - K * W ^ 2 / A i := rfl    have hR : W - s i = K * W ^ 2 / A i := by rw [hsi]; ring    rw [hR, show s i + K * W ^ 2 / A i = W by rw [hsi]; ring, hsi]    apply stake_share_best_response hK (hc i).2 (hR_nonneg i) hW hWM _ _ hσs    · show A i * (K * W ^ 2 / A i) = K * W ^ 2      exact mul_div_cancel₀ _ (hA_pos i).ne'    · -- the equilibrium utility is at least the payoff `L - c i` of an unbounded stake      rw [max_eq_right (sub_nonneg.2 hWM)]      have hAi := hA_pos i      have hlin : L + K * (M - W) - c i = A i - K * W := by        simp only [hAdef, hDdef]; ring      have e : (W - K * W ^ 2 / A i) / W * (A i - K * W) = (A i - K * W) ^ 2 / A i := by        field_simp      rw [hlin, e, le_div_iff₀ hAi]      have npos : (0 : ℝ) < n := by linarith      set g := (D - ((n : ℝ) - 1) * L) / n with hg      have hng : (n : ℝ) * g = D - ((n : ℝ) - 1) * L := by        rw [hg]; exact mul_div_cancel₀ _ npos.ne'      have hg_ge : 2 * n * L ≤ g := by        have hq : 0 ≤ ((n : ℝ) ^ 2 - n + 1) * L := mul_nonneg (by nlinarith) hL        have : (n : ℝ) * (2 * n * L) ≤ n * g := by rw [hng]; linear_combination hKM + hq        exact le_of_mul_le_mul_left this npos      have hnKW : (n : ℝ) * (K * W) ≤ ((n : ℝ) - 1) * (D + L) := by        have := mul_le_mul_of_nonneg_left hKW_le npos.le        rwa [mul_div_cancel₀ _ npos.ne'] at this      have hgap : g ≤ A i - K * W := by        have hA' : (n : ℝ) * D ≤ n * A i := mul_le_mul_of_nonneg_left (hA_lo i) npos.le        have : (n : ℝ) * g ≤ n * (A i - K * W) := by          rw [hng]; linear_combination hA' + hnKW        exact le_of_mul_le_mul_left this npos      have hg0 : 0 ≤ g := le_trans (by positivity) hg_ge      have hsq : g ^ 2 ≤ (A i - K * W) ^ 2 := pow_le_pow_left₀ hg0 hgap 2      have hci := hc i      have i1 : 2 * n * L * g ≤ g * g := mul_le_mul_of_nonneg_right hg_ge hg0      have i2 : 2 * n * L * (2 * n * L) ≤ 2 * n * L * g :=        mul_le_mul_of_nonneg_left hg_ge (by positivity)      have i3 : (n : ℝ) * L ^ 2 ≤ 2 * n ^ 2 * L ^ 2 := by        have : (n : ℝ) ≤ 2 * n ^ 2 := by nlinarith        exact mul_le_mul_of_nonneg_right this (sq_nonneg L)      have h1 : (D + L) * L ≤ g ^ 2 := by        have hD' : D = n * g + ((n : ℝ) - 1) * L := by linarith        rw [hD']; linear_combination i1 + (1 / 2 : ℝ) * i2 + i3      have h2 : A i * (L - c i) ≤ (D + L) * L :=        mul_le_mul (hA_hi i) (by linarith) (by linarith) hDL.le      linear_combination h2 + h1 + hsq
See it in the graphDiscuss this resultChallenge it