proportional_share_no_pne_of_safe_all_costs
theoremverifiedoriginal
If a proportional-share mechanism is ex-post safe for every nonnegative cost, then no profile with at least one agent and nonnegative costs is a pure Nash equilibrium.
Statement
theorem proportional_share_no_pne_of_safe_all_costs (pool : ℝ → ℝ)
(hsafe : ∀ c, 0 ≤ c →
is_ex_post_safe_procurement_for proportional_share_alloc (proportional_share_pay pool) c)
{n : ℕ} (hn : 0 < n) (c : Fin n → ℝ) (hc : ∀ i, 0 ≤ c i) (β : Fin n → List ℝ) :
¬ is_procurement_pne proportional_share_alloc (proportional_share_pay pool) 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 8
- is_ex_post_safe_procurement_forA procurement mechanism is ex-post safe for an agent of cost c if some bidding strategy guarantees nonnegative utility against all other…
- 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_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_nonnegIf every agent bids nonnegatively, so do the others of any agent.
- 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).
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.
/-- Within proportional-share mechanisms, ex-post safety for every cost level rules out pure Nash equilibria altogether. -/theorem proportional_share_no_pne_of_safe_all_costs (pool : ℝ → ℝ) (hsafe : ∀ c, 0 ≤ c → is_ex_post_safe_procurement_for proportional_share_alloc (proportional_share_pay pool) c) {n : ℕ} (hn : 0 < n) (c : Fin n → ℝ) (hc : ∀ i, 0 ≤ c i) (β : Fin n → List ℝ) : ¬ is_procurement_pne proportional_share_alloc (proportional_share_pay pool) c β := by rintro ⟨hnn, hbr⟩ let i : Fin n := ⟨0, hn⟩ set others := procurement_others_bids β i have hR : 0 ≤ others.sum := List.sum_nonneg (procurement_others_bids_nonneg β hnn i) set u0 := procurement_agent_utility proportional_share_alloc (proportional_share_pay pool) (c i) (β i) others with hu0 set C := c i + |u0| + 1 with hC obtain ⟨mine, hmine, hall, o, ho, hpos⟩ := hsafe C (by have := abs_nonneg u0; linarith [hc i]) have hsC : 0 ≤ mine.sum := List.sum_nonneg hmine have hsCpos : 0 < mine.sum := by rcases hsC.lt_or_eq with h | h · exact h · rw [proportional_share_utility_eq, ← h, zero_div, zero_mul] at hpos; exact absurd hpos (lt_irrefl 0) have hpool : ∀ z, 0 ≤ z → C ≤ pool (mine.sum + z) := by intro z hz have := hall [z] (by simp; exact hz) rw [proportional_share_utility_eq, List.sum_singleton] at this have hp : 0 < mine.sum / (mine.sum + z) := div_pos hsCpos (by linarith) by_contra hlt; push Not at hlt have : mine.sum / (mine.sum + z) * (pool (mine.sum + z) - C) < 0 := mul_neg_of_pos_of_neg hp (by linarith) linarith set t := mine.sum + |u0| * others.sum + 1 with ht have hab := abs_nonneg u0 have htpos : 0 < t := by have := mul_nonneg hab hR; linarith have hdev := hbr i [t] (by simp; linarith) rw [proportional_share_utility_eq (pool := pool) (c := c i) (mine := [t]), List.sum_singleton] at hdev have hW : 0 < t + others.sum := by linarith have hpW : C ≤ pool (t + others.sum) := by have := hpool (|u0| * others.sum + 1 + others.sum) (by have := mul_nonneg hab hR; linarith) convert this using 2; rw [ht]; ring have hfrac : 0 ≤ t / (t + others.sum) := div_nonneg htpos.le hW.le have h1 : t / (t + others.sum) * (|u0| + 1) ≤ t / (t + others.sum) * (pool (t + others.sum) - c i) := mul_le_mul_of_nonneg_left (by linarith) hfrac have h2 : |u0| < t / (t + others.sum) * (|u0| + 1) := by rw [div_mul_eq_mul_div, lt_div_iff₀ hW] have := mul_nonneg hab hR nlinarith have h3 := le_abs_self u0 linarith