ROM dual lemma (star): the reservation-price budget inequality
ProvedRobustAuction.ROM.rom_feasible_star_dual_lemmaLet be a set of valuation matrices with nonnegative entries and let be the budgets. Let be any choice of optimal solutions of the problems (12), (14) and (13) of Algorithm ROM.a (i.e. IsROMa U B d: , inner-feasible at with maximal inner value, the (14) minimizers , and the dual-feasible optimal of (13)). With the reservation prices of (15), for every buyer :
This is the key dual-lemma step in Bandi-Bertsimas (2014), Optimal Design for Multi-Item Auctions, proof of Proposition 3: it feeds the budget-feasibility constraint (9) of the feasibility of ROM's allocation and payments. It follows from the formalized hypotheses by LP complementary slackness on the primal-dual pair of (13): both and minimize over (so ), is primal-optimal, and complementary slackness gives for all ; the inequality then collapses to with .
import Mathlib import Definitions.Def_RobustAuction_ROM_AuctionLP import Definitions.Def_RobustAuction_ROM_Mechanism
namespace RobustAuction.ROM
/-- The (star) dual lemma for ROM (Bandi-Bertsimas 2014, step in the proof of
Proposition 3, used for the budget-feasibility half (9) of the feasibility of ROM):
for every buyer `i`,
`sum_j x*_ij * r*_ij <= B_i + theta*_i * sum_j x*_ij * utilde^i_j`,
where `r*_ij = xi*_j + z_ij * eta*_i + z_ij * theta*_i` are the reservation prices (15)
and `utilde^i_j = ut i i j` is the (14) minimizer. It is a corollary of the
formalized hypotheses `IsROMa` (dual feasibility and optimality of (13), (12)'s
inner-feasibility at `z`, and the (14) minimizers) plus nonnegativity of `U` and `B`,
via LP complementary slackness on the primal-dual pair of (13). -/
theorem rom_feasible_star_dual_lemma {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) (hROMa : IsROMa U B d) :
∀ i, Finset.sum Finset.univ (fun j => d.xs i j * rStar d i j) ≤
B i + d.θ i * Finset.sum Finset.univ (fun j => d.xs i j * d.ut i i j) := by
sorry
end RobustAuction.ROM