Display (4), p. 15 — expected RS-V proxy contribution of one agent
ProvedInterdepSOS.RSV.display_4p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-sampling-vickreywelfare-approximation
Let every agent have a nonnegative, weakly increasing value that is strictly increasing in her own signal, and suppose each valuation is -SOS. For any agent and truthful profile , let be her RS-V proxy weight when the candidate set is . Averaging uniformly over all partitions gives
This per-agent estimate supplies the contribution summed over a feasible comparator in the proof of Theorem 4.1.
Preamble
import Mathlib import Definitions.Def_InterdepSOS_RSV_Setting
Formal statement
namespace InterdepSOS.RSV
theorem display_4 {n : ℕ} (v : Valuation n) (hv : IsValuation v)
(d : ℝ) (hd : ∀ i, IsDSOS d (v i)) (i : Fin n) (s : Signal n) :
v i s / (d + 1) * (1 / 2 : ℝ) ≤
avgB (fun B => if i ∈ B then rsvWeight v B s i else 0) := 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. 15, proof of Theorem 4.1, display (4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.