Equation (5.11) — the fair contention rule selects every requester with probability c_j ≥ 1 − 1/e
ProvedConsumerUtilityApprox.UnitDemand.eq_5_11consumer-utilitymechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be announced request probabilities with for every item . Fix an item and a buyer who requests , and let every other buyer request independently with probability . Under the fair rule (sole requester selected; otherwise requester with probability , uniformly if ), the probability that is selected is
It holds for every buyer, including a deviating buyer whose own announced differs from its actual request, which is what makes equal service probabilities possible.
Differences from the source:
- encoding: the conditional probability Pr(i selected for j | i requests j), others requesting independently → the sum over the sets A of other requesters of ∏_{k≠i}(Q_kj or 1 − Q_kj) times fairSelProb Q j (insert i A) i; reason: the conditional law of the other requesters given i's request
Preamble
import Mathlib import Definitions.Def_MultiItemRev_BundlingOpt_Model import Definitions.Def_ConsumerUtilityApprox_UnitDemand_Model import Definitions.Def_ConsumerUtilityApprox_UnitDemand_Mechanisms open MeasureTheory ProbabilityTheory open scoped NNReal ENNReal open MultiItemRev.BundlingOpt
Formal statement
namespace ConsumerUtilityApprox.UnitDemand
theorem eq_5_11 {n m : ℕ} (hn : 1 ≤ n) (hm : 1 ≤ m) (Q : Fin n → Fin m → ℝ)
(hQ : ∀ k j, 0 ≤ Q k j ∧ Q k j ≤ 1) (hfeas : ∀ j, ∑ k, Q k j ≤ 1)
(j : Fin m) (i : Fin n) :
(∑ A ∈ (Finset.univ.erase i).powerset,
(∏ k ∈ Finset.univ.erase i, if k ∈ A then Q k j else 1 - Q k j) *
fairSelProb Q j (insert i A) i) = selectionConst Q j ∧
1 - Real.exp (-1) ≤ selectionConst Q j := by sorry
end ConsumerUtilityApprox.UnitDemand
Source
Goldner, Lundy, Tsilivis, A Constant-Factor Approximation to Multidimensional Consumer Utility, arXiv:2610.10516 (version of November 3, 2026, sha256 94e0dd44…), p. 26, equation (5.11) (= (C.10), Appendix C.5, pp. 49–50)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.