§4, pp. 14–15 — the RS-V allocation is monotone for every partition
ProvedInterdepSOS.RSV.rsv_monotonemonotone-allocationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-sampling-vickrey
Fix a partition with candidate set and any allocation rule that, at every reported signal profile, selects a feasible subset of maximizing the sum of RS-V proxy weights . If values are weakly increasing in every signal and strictly increasing in each agent's own signal, then each agent's allocation is monotone in her own report:
This establishes the allocation property used to obtain ex-post IC-IR payments for every deterministic component of RS-V.
Preamble
import Mathlib import Definitions.Def_InterdepSOS_RSV_Setting
Formal statement
namespace InterdepSOS.RSV
theorem rsv_monotone {n : ℕ} (I : Set (Finset (Fin n)))
(v : Valuation n) (hv : IsValuation v)
(sel : Finset (Fin n) → Allocation n) (hsel : IsRSVSelector I v sel)
(B : Finset (Fin n)) : IsMonotoneAlloc (sel B) := by sorry
end InterdepSOS.RSV
Source
Eden, Feldman, Fiat, Goldner, Karlin, Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue, arXiv:1903.08384v2 (2019), pp. 14–15, proof of Theorem 4.1, opening monotonicity argument
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.