Lemma 2.3, p. 12 — simultaneous signal increments preserve the d-SOS bound
ProvedInterdepSOS.RSV.lemma_2_3interdependent-valuesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sos-valuations
Let be a nonnegative -SOS function on nonnegative signal profiles. Partition the coordinates into and its complement . Hold the coordinates in at , then increase them by the nonnegative vector . If coordinatewise, the gain at the higher complementary profile is bounded by times the gain at the lower one:
The lemma extends the one-coordinate -SOS condition to simultaneous changes in any chosen set of coordinates.
Preamble
import Mathlib import Definitions.Def_InterdepSOS_RSV_Setting
Formal statement
namespace InterdepSOS.RSV
theorem lemma_2_3 {n : ℕ} (w : Signal n → ℝ) (hw : ∀ s, 0 ≤ w s)
(d : ℝ) (hd : IsDSOS d w) (A : Finset (Fin n))
(s y s' : Signal n) (hss' : ∀ j, j ∉ A → s j ≤ s' j) :
w (fun j => if j ∈ A then s j + y j else s' j) -
w (fun j => if j ∈ A then s j else s' j) ≤
d * (w (fun j => if j ∈ A then s j + y j else s j) - w 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. 12, Lemma 2.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.