§3, p. 4 — on the 6-cycle every online algorithm loses an impression on some scenario (u, v, v) where OPT = 3
ProvedOnlineStochMatching.Hardness.xyy_scenarioConsider the 6-cycle instance: advertisers , impression types , edges , and arrivals. Let be any deterministic online algorithm and let be the type of the first arrival. Then there is a type such that, on the arrival sequence ,
In the paper's case the first arrival is and the algorithm assigns it to ; then : both impressions are adjacent only to and , so at most one of them can be assigned, while with hindsight , , assigns all three. The statement covers every first type and every first decision (assigning to either neighbour, or not assigning at all).
Since the algorithm's first decision depends only on , and each scenario has probability , this places a ratio on a set of scenarios of total probability , which is what drives the bound of Theorem 3.
Formalization Note The paper's "without loss of generality (from the symmetry of the 6-cycle)" is replaced by quantifying over every first type ; the algorithm's first decision is whatever it does on . The arrival sequence is written ![u, v, v].
import Mathlib import Definitions.Def_OnlineStochMatching_Hardness_Model import Definitions.Def_OnlineStochMatching_Hardness_SixCycle
namespace OnlineStochMatching.Hardness
/-- §3, p. 4 (the "(x, y, y)" argument behind Theorem 3). On the 6-cycle with `n = 3` arrivals,
for every deterministic online algorithm and every type `u` of the first arrival there is a type
`v` such that on the scenario `(u, v, v)` the algorithm assigns at most two arrivals while the
optimum assigns all three. (The paper's case: `u = x` assigned to `a`, `v = y`.) -/
theorem xyy_scenario (alg : OnlineAlg Adv Imp 3) (u : Imp) :
∃ v : Imp, ALG cycleEdge alg ![u, v, v] ≤ 2 ∧ OPT cycleEdge ![u, v, v] = 3 := by sorry
end OnlineStochMatching.Hardness
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.