proportional_share_utility_eq
lemmaverified
In a proportional-share mechanism an agent's utility is s / (s + R) times (pool(s + R) - c).
Statement
lemma proportional_share_utility_eq (pool : ℝ → ℝ) (c : ℝ) (mine others : List ℝ) :
procurement_agent_utility proportional_share_alloc (proportional_share_pay pool) c mine
others =
mine.sum / (mine.sum + others.sum) * (pool (mine.sum + others.sum) - c)- Source
- step towards exists_sybil_proof_ex_post_safe_non_winner_take_all_procurement (Sybil-proof, ex-post safe procurement with non-winner-take-all equilibria, the open question of arXiv:2603.27779 v1, Sec. 6)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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… - 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).
- sum_range_getD_appendSumming the first |mine| entries of mine ++ others gives the sum of mine.
- procurement_agent_utilityThe utility of an agent with cost c who submits the bids
- Used by 6
- proportional_share_no_pne_of_safe_all_costsIf a proportional-share mechanism is ex-post safe for every nonnegative cost, then no profile with at least one agent and nonnegative…
- 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_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_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.
- 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.
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.
lemma proportional_share_utility_eq (pool : ℝ → ℝ) (c : ℝ) (mine others : List ℝ) : procurement_agent_utility proportional_share_alloc (proportional_share_pay pool) c mine others = mine.sum / (mine.sum + others.sum) * (pool (mine.sum + others.sum) - c) := by unfold procurement_agent_utility proportional_share_pay proportional_share_alloc have : ∀ j, (mine ++ others).getD j 0 / (mine ++ others).sum * pool (mine ++ others).sum - c * ((mine ++ others).getD j 0 / (mine ++ others).sum) = (mine ++ others).getD j 0 * ((pool (mine ++ others).sum - c) / (mine ++ others).sum) := by intro j; ring simp_rw [this] rw [← Finset.sum_mul, sum_range_getD_append, List.sum_append] ring