Theorem 1, proof, Claim (3): the algorithm produces an almost feasible dual solution
ProvedBJNAdAuctions.Basic.almost_dual_feasiblead-auctionsonline-algorithmsp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1primal-dual
Let be such that for all , and run the Allocation Algorithm with and any tie-breaking rule. Then for every buyer , with the final packing vector and the total amount charged to :
- the bids allocated to exceed its budget by at most one bid,
- the profit extracted from is at least a fraction of them,
This is the third claim of the proof of Theorem 1: the run's is feasible for the packing LP up to one bid per buyer, and the revenue loses at most a factor against its packing value.
Formalization Note is ⨆ j, inst.b i j over the finite type Fin m; for it is , which is also the value of the left-hand side.
Preamble
import Mathlib import Definitions.Def_BJNAdAuctions_Basic_Instance import Definitions.Def_BJNAdAuctions_Basic_AllocationAlgorithm
Formal statement
namespace BJNAdAuctions.Basic
/-- Theorem 1, proof, Claim (3) in quantitative form (pp. 7–8): with `c = (1 + R)^(1/R)`, where
every bid is at most `R` times its buyer's budget, each buyer `i` receives allocated bids
`∑_j b(i, j) y(i, j)` of total at most `B(i) + max_j b(i, j)`, and the amount charged to `i` is at
least `(1 - R) ∑_j b(i, j) y(i, j)`. -/
theorem almost_dual_feasible {I : Type*} [Fintype I] [Nonempty I] {m : ℕ} (inst : Instance I m)
(R : ℝ) (hR : 0 < R) (hbR : ∀ i j, inst.b i j ≤ R * inst.B i)
(sel : (I → ℝ) → Fin m → I) (i : I) :
∑ j, inst.b i j * (run inst ((1 + R) ^ (1 / R)) sel).y i j ≤ inst.B i + (⨆ j, inst.b i j) ∧
(1 - R) * ∑ j, inst.b i j * (run inst ((1 + R) ^ (1 / R)) sel).y i j ≤
(run inst ((1 + R) ^ (1 / R)) sel).spent i := by sorry
end BJNAdAuctions.Basic
Source
Buchbinder, Jain & Naor, Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue, ESA 2007, DOI 10.1007/978-3-540-75520-3_24, pp. 7-8, Theorem 1, proof, Claim (3) and the inequalities closing its proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.