AFTD Auto-Formalizing Theoretical Domains

exists_sybil_proof_ex_post_safe_non_winner_take_all_procurement

theoremverifiedoriginal

There 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 1) are never winner-take-all, and which has such an equilibrium (costs 1/5 and 9/10).

Statement

theorem exists_sybil_proof_ex_post_safe_non_winner_take_all_procurement :
    ∃ alloc pay : List ℝ → ℕ → ℝ,
      is_sybil_proof_procurement alloc pay ∧
      (∀ c, c ≤ 1 → is_ex_post_safe_procurement_for alloc pay c) ∧
      (∀ n, 0 < n → ∀ (c : Fin n → ℝ), (∀ i, c i ≤ 1) → ∀ β,
        is_procurement_pne alloc pay c β → is_non_winner_take_all_profile alloc β) ∧
      is_procurement_pne alloc pay ![1/5, 9/10] ![[24/35], [18/35]]
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_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_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…
  • is_sybil_proof_procurementA procurement mechanism is Sybil-proof if, for every cost and every multi-bid strategy, some single bid does at least as well against…
  • 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_sybil_proofEvery proportional-share mechanism is Sybil-proof: a single bid equal to the sum of an agent's bids gives the same utility.
  • stake_share_ex_post_safeWith K > 0 and M > 0, the stake-share mechanism is ex-post safe for every agent whose cost is at most L.
  • 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.
  • stake_share_two_agent_pneWith pool 1 + max(0, 2 - W) and costs 1/5 and 9/10, the stakes 24/35 and 18/35 form a pure Nash equilibrium.

Lean source view module on GitHub

/-- Answer to the open question of arXiv:2603.27779 (Sec. 6): a procurement mechanism that is Sybil-proof, ex-post safe for every cost up to the floor `1`, whose pure Nash equilibria are never winner-take-all, and which has such an equilibrium. -/
theorem exists_sybil_proof_ex_post_safe_non_winner_take_all_procurement :
    ∃ alloc pay : List ℝ → ℕ → ℝ,
      is_sybil_proof_procurement alloc pay ∧
      (∀ c, c ≤ 1 → is_ex_post_safe_procurement_for alloc pay c) ∧
      (∀ n, 0 < n → ∀ (c : Fin n → ℝ), (∀ i, c i ≤ 1) → ∀ β,
        is_procurement_pne alloc pay c β → is_non_winner_take_all_profile alloc β) ∧
      is_procurement_pne alloc pay ![1/5, 9/10] ![[24/35], [18/35]] :=
  ⟨proportional_share_alloc, proportional_share_pay (stake_share_pool 1 1 2),
    proportional_share_sybil_proof _,
    fun _ hc => stake_share_ex_post_safe one_pos two_pos hc,
    fun _ hn c hc β hβ => stake_share_pne_non_winner_take_all one_pos two_pos hn c hc β hβ,
    stake_share_two_agent_pne⟩
See it in the graphDiscuss this resultChallenge it