离散天数的滑雪租赁笔记得到不同的确定性竞争比。本节采用连续时间和不同的同时事件惯例;比较结论前请先比较模型。
在线算法要在不知道任务还会持续多久时作决定。使用时间短,租用资源较便宜;使用时间长,购买可避免重复收费。困难在于作出购买决定时,剩余使用时间尚未揭晓。
滑雪租买模型用两种价格抽出这个问题,让我们完整比较:最佳确定性纯乘法竞争比是 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。若某策略对每个固定输入时间都保证更小因子,平均那项保证就会与此计算矛盾。下界分布没有让算法预先知道已实现的行程时间。