stake_share_pne_non_winner_take_all
theoremverifiedoriginal
In the stake-share mechanism with K, M > 0 and all costs at most L, every pure Nash equilibrium (with at least one agent) gives positive work to at least two agents.
Statement
theorem stake_share_pne_non_winner_take_all {L K M : ℝ} (hK : 0 < K) (hM : 0 < M) {n : ℕ}
(hn : 0 < n) (c : Fin n → ℝ) (hc : ∀ i, c i ≤ L) (β : Fin n → List ℝ)
(hβ : is_procurement_pne proportional_share_alloc
(proportional_share_pay (stake_share_pool L K M)) c β) :
is_non_winner_take_all_profile proportional_share_alloc β- 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 11
- is_non_winner_take_all_profileA bid profile is not winner-take-all if at least two distinct agents receive a positive amount of work.
- 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_agent_allocationThe total work an agent receives: the sum of the allocations to its identities.
- procurement_agent_utilityThe utility of an agent with cost c who submits the bids
mine(one per identity) while all other identities bidothers: the sum over… - procurement_others_bidsThe list of all bids of agents other than i in a profile where each agent submits a list of bids.
- 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_allocation_eqIn a proportional-share mechanism an agent's total work is s / (s + R), s its total bid and R the others' total.
- 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_poolThe stake-share pool L + K max(0, M - W) as a function of the total stake W.
- Used by 2
- exists_sybil_proof_ex_post_safe_non_winner_take_all_procurementThere is a procurement mechanism that is Sybil-proof, ex-post safe for all costs at most 1, whose pure Nash equilibria (for costs at most…
- stake_share_pne_exists_and_non_winner_take_allFor n >= 2 agents with costs in [0, L] and K M >= 3 n^2 L, the stake-share mechanism has a pure Nash equilibrium, and every pure Nash…
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.
/-- In the stake-share mechanism every pure Nash equilibrium gives positive work to at least two agents, provided every agent's cost is at most the pool floor `L`. -/theorem stake_share_pne_non_winner_take_all {L K M : ℝ} (hK : 0 < K) (hM : 0 < M) {n : ℕ} (hn : 0 < n) (c : Fin n → ℝ) (hc : ∀ i, c i ≤ L) (β : Fin n → List ℝ) (hβ : is_procurement_pne proportional_share_alloc (proportional_share_pay (stake_share_pool L K M)) c β) : is_non_winner_take_all_profile proportional_share_alloc β := by obtain ⟨hnn, hbr⟩ := hβ have hs : ∀ j, 0 ≤ (β j).sum := fun j => List.sum_nonneg (hnn j) set S := ∑ j, (β j).sum with hS have hoth : ∀ j, (procurement_others_bids β j).sum = S - (β j).sum := procurement_others_bids_sum β have halloc : ∀ j, procurement_agent_allocation proportional_share_alloc (β j) (procurement_others_bids β j) = (β j).sum / S := by intro j; rw [proportional_share_allocation_eq, hoth]; ring_nf have hutil : ∀ j σ, procurement_agent_utility proportional_share_alloc (proportional_share_pay (stake_share_pool L K M)) (c j) σ (procurement_others_bids β j) = σ.sum / (σ.sum + (S - (β j).sum)) * (stake_share_pool L K M (σ.sum + (S - (β j).sum)) - c j) := by intro j σ; rw [proportional_share_utility_eq, hoth] by_contra hcon have hcon' : ∀ i j, i ≠ j → 0 < (β i).sum / S → (β j).sum / S ≤ 0 := by intro i j hij hi by_contra hj exact hcon ⟨i, j, hij, by rw [halloc]; exact hi, by rw [halloc]; linarith⟩ rcases (Finset.sum_nonneg (fun j _ => hs j) : 0 ≤ S).lt_or_eq with hSpos | hSzero · -- some agent is active; it must be the only one obtain ⟨i, hi⟩ : ∃ i, 0 < (β i).sum := by by_contra h push Not at h have : S ≤ 0 := Finset.sum_nonpos (fun j _ => h j) linarith have hzero : ∀ j, j ≠ i → (β j).sum = 0 := by intro j hj have h1 := hcon' i j (Ne.symm hj) (div_pos hi hSpos) have h2 : (β j).sum ≤ 0 := by by_contra h3; push Not at h3; have := div_pos h3 hSpos; linarith linarith [hs j] have hSi : S = (β i).sum := by rw [hS, Finset.sum_eq_single i (fun j _ hj => hzero j hj) (by simp)] set t := min (β i).sum M / 2 with ht have htpos : 0 < t := by rw [ht]; exact div_pos (lt_min hi hM) two_pos have htle : t < (β i).sum := by have := min_le_left (β i).sum M; rw [ht]; linarith have htM : t < M := by have := min_le_right (β i).sum M; rw [ht]; linarith have hdev := hbr i [t] (by simp; linarith) rw [hutil, hutil, hSi, sub_self, add_zero, add_zero, List.sum_singleton, div_self (ne_of_gt htpos), div_self (ne_of_gt hi), one_mul, one_mul] at hdev unfold stake_share_pool at hdev rw [max_eq_right (by linarith : (0 : ℝ) ≤ M - t)] at hdev have : max 0 (M - (β i).sum) < M - t := by apply max_lt <;> linarith nlinarith · -- nobody is active: any agent profits from a small stake let i : Fin n := ⟨0, hn⟩ have hall : ∀ j, (β j).sum = 0 := by intro j have := (Finset.sum_eq_zero_iff_of_nonneg (fun j _ => hs j)).mp hSzero.symm j (by simp) exact this have hdev := hbr i [M / 2] (by simp; linarith) have hS0 : S = 0 := hSzero.symm rw [hutil, hutil, hS0, hall i, sub_zero, add_zero, add_zero, List.sum_singleton, div_self (by linarith : M / 2 ≠ 0), one_mul, zero_div, zero_mul] at hdev unfold stake_share_pool at hdev rw [max_eq_right (by linarith : (0 : ℝ) ≤ M - M / 2)] at hdev have := hc i nlinarith