離散日數的滑雪租賃筆記得到不同的確定性競爭比。本節採用連續時間和不同的同時事件慣例;比較結論前請先比較模型。
線上算法要在不知道任務還會持續多久時作決定。使用時間短,租用資源較便宜;使用時間長,購買可避免重複收費。困難在於作出購買決定時,剩餘使用時間尚未揭曉。
滑雪租買模型用兩種價格抽出這個問題,讓我們完整比較:最佳確定性純乘法競爭比是 2;精心選擇的隨機策略則達到 e/(e−1)。本節會推導該分佈及匹配下界,同時固定時間先後慣例,並說明對手能否觀察算法的隨機選擇。
說清算法知道甚麼,以及何時付費
把租金率正規化為每單位時間一個成本單位。購買價為 B>0,之後繼續使用免費。行程總時間 T>0 未知;在結束前,算法只知道仍需使用,沒有其他預測資訊。沒有轉售價值、退款或折扣。
若算法打算在 τ∈[0,∞] 購買,成本是
Cτ(T)=min{T,τ}+B1{T>τ}.若 T=τ,先處理結束通知,所以不購買。τ=∞ 表示永不購買。事先知道時間的離線最優成本為
OPT(T)=min{T,B}.隨機策略的純乘法競爭比至多為 c,表示
E硬幣[C(T)]≤cOPT(T)對每個固定的 T>0.期望取自策略本身的私人隨機選擇,定義不容許額外相加常數。對手固定 T,不依賴那些選擇;這是本節使用的不觀察隨機選擇的輸入模型。
不容許附加常數,在這個單次行程問題中很重要。若可任意加上一個與 B 相若的量,整筆購買成本都可能被隱藏。我們直接比較上式的乘法保證。
每個確定性策略都有固定的首次購買時間:想像行程永遠不結束,在那一刻以前,每個仍在繼續的行程都提供相同觀察。若先固定私人隨機種子,同一論證把隨機策略表示為隨機購買時間 τ,也可能是無窮。對固定有限行程,策略只執行到行程結束前的相同前綴。
平衡確定性策略的兩種損失
立即購買,可能在極短行程上浪費 B;永不購買,則可能在極長行程上付出無限增大的租金。有限正閾值在兩種風險之間取捨。
租到時間 B,若仍需使用便購買。此策略是 2-競爭的,而且本模型中沒有確定性策略能取得更小的純乘法競爭比。
當 τ=B,若 T≤B,成本是 T=OPT(T);若 T>B,成本是 2B=2OPT(T)。
若 0<τ<B,考慮略大於 τ、但仍小於 B 的時間,成本比趨近 (τ+B)/τ=1+B/τ>2。若 τ>B,取 T>τ,比率就是 (τ+B)/B=1+τ/B>2。τ=B 達到 2。閾值零在 T→0+ 時無界;無窮閾值則在 T→∞ 時無界。
等價地,有限正閾值的最壞上確界,在 τ≤B 時為 1+B/τ,在 τ≥B 時為 1+τ/B。由於結束先於購買,第一種可能只是極限值,而非實際最大值。
令 B=10,使用 τ=10。
時間剛好為 10,行程在購買前結束;稍超過 10,策略已同時租用及購買。因此證明必須遵守事件先後,不能假設每個確定性成本函數都連續。競爭界仍是 2。
推導隨機分佈,而非隨便選一個
嘗試讓購買時間在 [0,B] 上有連續密度 f,累積分佈為 F。固定 0<T<B,策略若已在 t<T 購買,付出 t+B;否則仍只租用。故
G(T)=E[C(T)]=∫0T(t+B)f(t)dt+T(1−F(T)).
微分得到 G′(T)=1−F(T)+Bf(T)。若希望整個短行程範圍的比率 G(T)/T 都等於 c,可要求 G′(T)=c。由 f=F′,得到微分方程 BF′−F=c−1。
用 F(0)=0 解出 F(t)=(c−1)(et/B−1)。再要求全部概率落在 [0,B],即 F(B)=1,便得到候選策略
F(t)=e−1et/B−1,f(t)=B(e−1)et/B(0≤t≤B),c=e−1e.
這是在選定密度族中構造一個候選策略。下面先驗證保證,再證明本模型的任何隨機策略都不能更好。
抽樣時可先取 (0,1) 上的均勻隨機數 R,再設 τ=Bln(1+(e−1)R),這是反累積分佈抽樣。密度是遞增的,所以在 [0,B] 均勻選時間是另一個策略。
定理 7.2.4
(所構造的閾值分佈達到 e/(e−1))
對每個固定而獨立於所抽閾值的 T>0,
E[C(T)]=e−1emin{T,B}.因此這個理想連續時間策略的競爭比恰為 e/(e−1),約 1.582。
對 0<T<B,把候選分佈代入 G′(T)=1−F(T)+Bf(T),得到 G′(T)=e/(e−1)。由 G(0)=0 積分,得 G(T)=eT/(e−1)。
對 T≥B,策略已以概率一購買;單個端點 τ=B 的概率為零。預期租用時間為
E[τ]=e−1B∫01ueudu=e−1B,因為積分等於 1。所以總期望成本為 B+E[τ]=eB/(e−1)。兩個公式在 T=B 一致,證明涵蓋每個正時間。
證明透視
為甚麼短行程上的比率恆定
這個分佈的構造使一條方程成立:對所有 0<T<B 有 G′(T)=c。證明在 B 處分段,因為兩個範圍的行為不同。對 T<B,只有多租一個時間單位的邊際成本起作用:它是 1−F(T)(策略尚未購買的概率)加上 Bf(T)(此刻購買的密度),代入所選的 F 後,兩者相加為常數 e/(e−1)。對 T≥B,策略已以概率一購買,所以成本是 B 加上期望租用時間 E[τ],積分 ∫01ueudu=1 使它同樣化為 eB/(e−1)。兩個公式在 T=B 一致,說明它們描述同一個函數;而 τ=B 的概率為零,所以同時事件慣例在這裏不起作用。
下面兩個例子以直接計算驗證定理。
取 B=1、T=1/2。在 [0,1] 上的密度 f(t)=et/(e−1) 下,期望成本為
G(21)=∫01/2(t+1)e−1etdt+21(1−F(21)).由於 (tet)′=(t+1)et,積分等於 e−1e1/2/2。又 F(1/2)=(e1/2−1)/(e−1),故第二項為 21⋅e−1e−e1/2。兩項之和是 21⋅e−1e1/2+e−e1/2=2(e−1)e≈0.791,等於 e−1eOPT(1/2),與定理一致。
例題 7.2.6
(恰為一個收支平衡時間的行程與極短的行程)
仍取 B=1。當 T=1 時,閾值 τ 幾乎必然小於 1(τ=1 的概率為零),所以策略一定購買,付出 E[τ]+1=1/(e−1)+1=e/(e−1)≈1.582,離線成本為 1;同時事件慣例在此無關。對極短的行程 T=0.01,策略在結束前購買的概率為 F(0.01)=(e0.01−1)/(e−1)≈0.0058,所以幾乎總是只租用。其期望成本為 eT/(e−1)≈0.0158,相對 0.01,比率仍是 e/(e−1):以微小的概率付出全價 1,恰好使期望落在直線 eT/(e−1) 上。
到此為止的證明並未說明隨機化本身就是改善的原因,下一個例子說明了這一點。
反例模式
均勻隨機化的最壞比率仍是 2
若 τ 在 [0,B] 均勻分佈,對 0<T<B 有
E[C(T)]=2T−2BT2.相對離線成本的比率為 2−T/(2B),在 T→0+ 時趨近 2。對 T≥B,期望成本為 3B/2。所以均勻隨機化沒有改善最壞競爭比 2。真正有用的是分佈對所有固定時間的平衡,而不只是作出隨機選擇。
把獨立輸入時間平均,證明最優性
定理 7.2.7
(沒有隨機策略能優於 e/(e−1))
設本模型中的隨機策略(可能有時永不購買)對每個固定的 T>0 都滿足 E[C(T)]≤cOPT(T),其私人隨機性獨立於 T。則 c≥e/(e−1)。
假設某策略對每個固定時間都保證因子 c,私人隨機性不依賴該時間。為分析下界,另引入與它獨立的隨機行程,密度為 (0,∞) 上的 g(t)=e−t/B/B,存活概率為 Pr(T>s)=e−s/B。
對固定有限 τ,寫成 min{T,τ}=∫0τ1{T>s}ds。把這個非負恆等式取平均,得到
ET[min{T,τ}]=∫0τe−s/Bds=B(1−e−τ/B).購買成本的期望為 BPr(T>τ)=Be−τ/B。兩項相加為 B,對每個固定有限閾值都一樣。無窮閾值也平均花費 B,因為它全程租用,而這個指數行程的平均時間正是 B。
條件於獨立隨機閾值後,任何閾值混合策略的平均線上成本都為 B。成本非負,容許交換取平均的次序。離線期望則是
ET[OPT(T)]=∫0Be−s/Bds=B(1−e−1).若策略對每個固定時間都滿足 c-競爭不等式,把它按這個獨立時間分佈平均,必有
B≤cB(1−e−1),c≥1−e−11=e−1e.這證明本模型中每個隨機策略的下界,包括有機會永不購買的策略。結合已構造的上界,便確立最優比率。
證明透視
為甚麼同一個時間分佈能擊敗每個閾值
下界依賴一條恆等式:在平均為 B 的指數分佈下,每個固定閾值的期望成本都是 B。租用項 B(1−e−τ/B) 隨 τ 增加,購買項 Be−τ/B 則以恰好補償的速率減少,所以沒有任何閾值可以利用這個分佈。這就是閾值混合策略沒有幫助,也是策略的私人硬幣可視為獨立於行程的原因。基準一側是另一個計算,E[OPT]=B(1−e−1),用到 OPT=min{T,B}。真正起作用的假設是保證對每個固定行程都成立;若保證只對部分行程成立,取平均便甚麼也得不到。成本非負,容許交換取平均的次序。
指數行程分佈只是一個證明工具。實際競爭保證仍然要求每個固定時間都成立,並不假設真實行程依此分佈。任何更好的逐一時間保證,按任意獨立輸入分佈平均後也必須成立;下界正是利用這一點。
對手看到隨機選擇後,問題便改變
策略保證先固定 T,再對私人隨機性平均。若 T 取決於已實現的購買時間,不能原樣套用。
反例模式
觀察購買後不久就結束,破壞了獨立性
假設觀察者等策略在 τ 購買,然後於 T=τ+B/10 結束行程。線上成本恆為 τ+B,期望是 eB/(e−1)。離線期望滿足
E[OPT(T)]≤E[τ]+B/10=e−1B+B/10<B.所以在這個相關實驗中,線上期望成本嚴格大於 (e/(e−1))E[OPT(T)]。時間透過已觀察到的購買,依賴私人隨機閾值,違反了不觀察隨機選擇的輸入假設,並不反駁固定時間定理。
轉用策略前,先說清模型
若租金率為 r>0、購買價為 P>0,收支平衡時間是 B=P/r,單位是時間。把金錢成本除以 r,就回到租金率一、購買成本為 B 的模型。當租金率不等於一時,把價格誤作時間會得到錯誤閾值。
離散租用期、折扣、轉售價值、時間預測或其他觀察,都會改變可用策略或成本。本節精確常數屬於已指定的連續時間、無退款模型。計算工作與抽樣精度亦不同於競爭成本;理想連續隨機變量本身是數學算法的一部分。
練習與解答
快速檢查
(租用每單位時間收 2,購買價為 10。求確定性收支平衡購買時間,並按本節同時事件慣例,計算時間 4、5、6 的策略與離線成本。)
解答 · 答案
時間閾值是 10/2=5。時間 4 和 5 只租用,成本分別為 8、10,也等於離線成本。時間 6 時,先租 5 個時間單位,再購買,成本 2(5)+10=20,離線成本則為 10,所以比率依次是 1、1、2。使用時間閾值 10,會混淆價格單位與時間單位。
快速檢查
(對最優隨機策略,求 Pr(τ≤B/2),推導反累積分佈抽樣式及購買時間中位數。均勻選時間是相同分佈嗎?)
解答 · 答案
概率為 (e1/2−1)/(e−1)=1/(e+1),小於 1/2。由 R=(eτ/B−1)/(e−1) 解出 τ=Bln(1+(e−1)R)。取 R=1/2,得中位數 Bln((e+1)/2);因為 (e+1)/2>e,它大於 B/2。均勻購買時間的中點概率是 1/2,最壞競爭比亦不同,反例已說明。
快速檢查
(對密度 f 的策略,觀察者看到購買後設定 T=τ+B/10。求期望線上成本,並解釋它與離線期望之比為何可超過固定時間競爭因子。)
解答 · 答案
期望線上成本為 B+E[τ]=eB/(e−1)。但 E[OPT(T)]≤B/(e−1)+B/10<B,所以兩個期望之比大於 e/(e−1)。這裏的時間與策略的隨機選擇相關;已證定理先固定時間,再對那些選擇平均。根據已觀察購買來設定時間,改變了概率實驗。
快速檢查
(在下界證明中,取平均為 B 的指數行程及固定購買時間 τ=B/2。求期望租用、購買與離線成本,並說明隨機混合購買時間會怎樣。)
解答 · 答案
期望租用成本為 B(1−e−1/2),購買成本為 Be−1/2,相加是 B。離線期望為 B(1−e−1),所以比率是 1/(1−e−1)=e/(e−1)。
每個固定閾值,包括永不購買,在這個獨立行程分佈下都平均花費 B。因此,與行程獨立的隨機混合亦平均花費 B。若某策略對每個固定輸入時間都保證更小因子,平均那項保證就會與此計算矛盾。下界分佈沒有讓算法預先知道已實現的行程時間。