stake_share_pne_exists_and_non_winner_take_all
theoremverifiedoriginal
For 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 equilibrium gives positive work to at least two agents.
Statement
theorem stake_share_pne_exists_and_non_winner_take_all {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 β) ∧
∀ β : Fin n → List ℝ, 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 7
- 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…
- 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).
- stake_share_pne_existsFor 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…
- stake_share_pne_non_winner_take_allIn 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…
- stake_share_poolThe stake-share pool L + K max(0, M - W) as a function of the total stake W.
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.
/-- For every number of agents and every floor `L`, the stake-share mechanism with `K M ≥ 3 n² L` has, for every cost profile in `[0, L]`, a pure Nash equilibrium, and every pure Nash equilibrium gives positive work to at least two agents. -/theorem stake_share_pne_exists_and_non_winner_take_all {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 β) ∧ ∀ β : Fin n → List ℝ, 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 β := ⟨stake_share_pne_exists hn hL hK hM hKM c hc, fun β hβ => stake_share_pne_non_winner_take_all hK hM (by omega) c (fun i => (hc i).2) β hβ⟩