Propositions 3–5 / proof of Theorem 1, p. 1025 — ROM's allocation and payments are feasible for the robust auction LP (5)
ProvedRobustAuction.ROM.rom_feasibleLet be a set of valuation matrices with nonnegative entries and let be the budgets. Take any choice of optimal solutions of the problems (12), (13), (14) of Algorithm ROM.a and (16), (17) of Algorithm ROM.b. Let and be the resulting allocation (20) and payments (21). Then satisfies every constraint of the robust auction design LP (5) other than the revenue constraints (5)–(6). For all :
- (7) for all ;
- ;
- (8) for every buyer and every report with ,
- (9) for all ;
- (10) for all .
The robust optimal mechanism is thus a feasible, incentive compatible, budget feasible and individually rational mechanism for every uncertainty set. This is the feasibility half of the paper's Theorem 1, whose proof states that "the feasibility follows from Propositions 3–5".
Formalization Note Nonnegative valuations and budgets are the model's standing assumptions, made explicit. No finiteness, boundedness or convexity of is assumed; the existence of the optimal solutions is part of the hypothesis. The optimality half of Theorem 1, which asserts that ROM maximizes the worst case revenue, is false as printed and is not asserted here.
import Mathlib import Definitions.Def_RobustAuction_ROM_AuctionLP import Definitions.Def_RobustAuction_ROM_Mechanism
namespace RobustAuction.ROM
/-- Propositions 3–5 combined (Bandi–Bertsimas 2014, proof of Theorem 1, p. 1025: "the
feasibility follows from Propositions 3–5"): ROM's allocation (20) and payments (21) satisfy
every constraint of the robust auction LP (5) other than the revenue constraints (5)–(6) —
(7), `x ≥ 0`, (8), (9) and (10) — for every choice of optimal solutions of (12)–(14), (16),
(17). Valuations in `U` and budgets are nonnegative (standing assumptions of the model). -/
theorem rom_feasible {n m : ℕ} (U : Set (Fin n → Fin m → ℝ)) (B : Fin n → ℝ)
(hU : ∀ u ∈ U, ∀ i j, 0 ≤ u i j) (hB : ∀ i, 0 ≤ B i)
(d : ROMData n m) (hd : IsROM U B d) :
IsFeasibleMechanism U B (alloc U d) (pay U d) := by sorry
end RobustAuction.ROM
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.