Lemma 3.1, p. 13 — random zeroing retains at least 1/(d+1) of a d-SOS value
ProvedInterdepSOS.RSV.lemma_3_1p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-samplingsos-valuations
Let be a nonnegative -SOS valuation, with . Keep agent 's signal fixed, choose a subset of the other agents uniformly at random, and set all signals outside to zero. Then
This estimate relates proxy valuations obtained by random signal suppression to the original valuation and is reused in the paper's welfare bounds.
Formalization Note The printed lemma omits the range of . The condition is necessary: a constant positive valuation satisfies the -SOS increment condition for negative , but violates the claimed bound when .
Preamble
import Mathlib import Definitions.Def_InterdepSOS_RSV_Setting
Formal statement
namespace InterdepSOS.RSV
theorem lemma_3_1 {n : ℕ} (w : Signal n → ℝ) (hw : ∀ s, 0 ≤ w s)
(d : ℝ) (hd_nonneg : 0 ≤ d) (hd : IsDSOS d w) (i : Fin n)
(s : Signal n) :
1 / (d + 1) * w s ≤
(2 ^ (n - 1) : ℝ)⁻¹ *
∑ A ∈ (Finset.univ.erase i).powerset, w (keepOn (insert i A) s) := by sorry
end InterdepSOS.RSV
Source
Eden, Feldman, Fiat, Goldner, Karlin, Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue, arXiv:1903.08384v2 (2019), p. 13, Lemma 3.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.