Theorem 6.1, p. 20 — k-HL is universally ex-post IC-IR and a (k+3)-approximation to the optimal welfare for SOS valuations with k signal values
ProvedInterdepSOS.KHL.theorem_6_1Consider a combinatorial auction with agents, items and a positive number of signal values, with single-dimensional signals , where the valuations satisfy the standing assumptions (nonnegative, , weakly increasing in every signal and strictly increasing in the own signal on nonempty bundles) and are SOS. Run the mechanism k-HL: with probability run Random Threshold with uniform in , otherwise Random Sampling with a uniformly random partition ; the allocations are produced by arbitrary maximizing selectors that depend on the reports only through the proxy data. Then:
- for every threshold , Random Threshold with its payments is ex-post IC and ex-post IR;
- for every , Random Sampling without payments is ex-post IC and ex-post IR;
- for every grid profile and every feasible allocation ,
Items 1–2 say that k-HL is universally ex-post IC-IR; item 3 says that its expected welfare at the truthful profile, measured with true values, is at least a fraction of the optimal welfare.
Formalization Note The approximation is stated against every feasible allocation instead of an optimum, which is equivalent and avoids a supremum. The paper's "signal space of size " is made explicit as ; at the displayed mixing weight would be negative. For , and k-HL is Random Sampling.
import Mathlib import Definitions.Def_InterdepSOS_KHL_Setting import Definitions.Def_InterdepSOS_KHL_Mechanisms
namespace InterdepSOS.KHL
theorem theorem_6_1 {n m : ℕ} (k : ℕ) (hk : 1 ≤ k) (v : Valuation n m)
(hv : IsCombValuation k v) (hsos : ∀ i T, IsSOS k (v i T))
(rtSel : ℕ → Signal n → Allocation n m) (hrt : IsRTSelector k v rtSel)
(rsSel : Finset (Fin n) → Signal n → Allocation n m) (hrs : IsRSSelector k v rsSel) :
(∀ ℓ ∈ Finset.Icc 1 (k - 1),
IsExPostIC k v (rtAlloc rtSel ℓ) (rtPay v rtSel ℓ) ∧
IsExPostIR k v (rtAlloc rtSel ℓ) (rtPay v rtSel ℓ)) ∧
(∀ B : Finset (Fin n),
IsExPostIC k v (rsAlloc rsSel B) 0 ∧ IsExPostIR k v (rsAlloc rsSel B) 0) ∧
∀ s : Signal n, InGrid k s → ∀ Tstar : Allocation n m, IsAllocOn Finset.univ Tstar →
welfare v Tstar s ≤ ((k : ℝ) + 3) * khlWelfare k v rtSel rsSel s := by sorry
end InterdepSOS.KHL
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.