Eq. (4), p. 17 — R₂(C) as a ratio of quadratic forms in x^C with θij and r̂ij
ProvedMultiPurchase.Hardness.eq_4assortment-optimizationchoice-modelsmulti-purchasep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider a BundleMVL-2 instance with products , revenues , weights , and no-purchase weight . For let if and otherwise, and set
Then the expected revenue of is
This rewrites the revenue as a ratio of two quadratic forms in the indicator vector of , the form used in the Compare-Step and in the hardness proof.
Formalization Note The identity is stated for every instance, without the well-formedness conditions: it is an algebraic identity between two expressions for the same numerator and denominator (Lean's division by zero gives both sides the same value).
Preamble
import Mathlib import Definitions.Def_CookPvsNP_defs import Definitions.Def_ProjSchedTW_Complexity_Encoding import Definitions.Def_MultiPurchase_Hardness_Model
Formal statement
namespace MultiPurchase.Hardness
/-- Eq. (4), p. 17, second form: with `x^C_i` the indicator of `C`, `θᵢᵢ = V{i}`,
`θᵢⱼ = V{i,j}/2` and `r̂ᵢᵢ = rᵢ`, `r̂ᵢⱼ = rᵢ + rⱼ` (`i ≠ j`),
`R₂(C) = ∑_{i∈W} ∑_{j∈W} r̂ᵢⱼ θᵢⱼ x^C_i x^C_j / (v0 + ∑_{i∈W} ∑_{j∈W} θᵢⱼ x^C_i x^C_j)`. -/
theorem eq_4 (I : Instance) (C : Finset (Fin I.n)) :
I.R2 C = (∑ i, ∑ j, I.rhat i j * I.theta i j * xC C i * xC C j) /
(I.v0 + ∑ i, ∑ j, I.theta i j * xC C i * xC C j) := by sorry
end MultiPurchase.Hardness
Source
Tulabandhula, Sinha, Karra & Patidar, Multi-Purchase Behavior: Modeling, Estimation and Optimization, arXiv:2006.08055v2, p. 17 (PDF 17), eq. (4), second equality
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.