購價租金降低下賃購平衡在線策略的最優性分析

程玲燕，何世偉

（北京交通大學運輸學院，北京　100044）

購價租金降低下賃購平衡在線策略的最優性分析

程玲燕，何世偉

（北京交通大學運輸學院，北京100044）

摘要：證明了在購價與租金隨時間降低，且決策時間未定的情況下，獲得具有上界為2的最小競爭比的近似最優在線策略，即僅當實時購買價格與已累積租金額的數量關系為相等時選擇購買。該研究分別針對購價租金恒定與一般情形兩種情況下，不同的市場崩潰時間與設備購買時間的先后關系、購買價格與累計租金的數量關系進行了分析論證，為賃購平衡策略在現實租買決策中的應用提供了理論依據。

關鍵詞：在線算法；在線租賃；賃購平衡策略；競爭比

相較于傳統的決策優化方法，在線（On-line，也稱占線、局內）算法與競爭比分析方法為在線租賃問題提供了尋求概率意義上的最優決策新視角。其中，在設備購買價格與租金為單調遞減序列的在線問題中，賃購平衡策略（renting-buyingbalancestrategy）是學者們提出的一種較為普遍且實際易執行的在線策略。現階段，對于不確定情形下租或買的決策研究，國內外相關的研究方向主要為在線算法與競爭分析方法，其研究始于Karp［1］1992年提出的“SkiRentalProblem模型”，該模型假設滑雪初學者不知道自己會滑雪多少次，因此，每次滑雪時都面臨兩種選擇：花費c成本租滑雪撬，或者花費P成本一次性購買雪撬。Karp給出了競爭比為2-c/P的最優確定性競爭策略。這類具有非常強的動態特征的租賃問題稱為在線租賃問題，實質在于在線人一直采取租賃策略直到某一時刻點采取購買策略使該決策結束。隨后，很多學者結合現實租賃問題，對該基本模型進行了擴展研究，主要思路有兩種。一種思路是將基本租賃模型推廣應用到其他現實問題中，如Fleischer［2］提出的占線優惠卡（Bahncard）模型；Al-Binali［3］把在線決策者的風險行為引入傳統競爭分析，建立了風險補償模型；Karlin等［4］將租賃模型應用于傳輸控制協議（TCP）問題；2004年朱志軍等［5］給出了一般設備租賃問題的風險補償模型；辛春林等［6］、丁黎黎等［7］將風險補償概念應用于優惠卡模型，并進行了相應的擴展研究；徐寅峰等［8］從收益率的角度，對實際問題進行了研究，并討論了基于風險補償模型的風險補償收益。另一種思路是對原模型的假設進行修正，改善決策者的決策信息，得到更優的競爭比，如Karlin等［9］討論了未來需求為隨機變量的租賃問題，給出了隨機在線算法，使競爭比達到了約1.582，近似最優；Irani等［10］研究了購買價格波動而租賃費用保持不變的情形，分別給出了確定性和隨機性算法的競爭比上下界，還第一次運用具有統計特征對象，即限定未來價格波動滿足一定條件來研究租賃問題；El-Yaniv等［11］考慮了存在利率時的在線租賃問題，給出了最優確定性算法（其競爭比大小在［3/2，2）之內）及最優隨機性算法（其競爭比大小在［4/3，1.582）之內）；隨后，Fujiwara等［12］結合指數分布概率信息研究了連續型在線租賃決策問題，并說明了競爭比大約在1.5左右；馬衛民等［13］研究了租賃價格可變情形的連續型在線租賃問題；Lotker等［14］在前人研究的基礎上對基本租賃模型進行了擴展，提出了“MuhislopeSkiRentalProblem”的模型，在該模型中，決策者不僅是“純粹的買或租”的選擇，而是在花費一定購置費的基礎上，在不同階段使用設備還要花費一定比例的使用費；張永等［15］在研究了設備價格呈離散型下降的在線租賃策略后，給出了其策略的競爭比上界；劉斌等［16］研究了具有線性交易成本的耐用性設備的在線租賃問題，假定在設備壽命周期內，使用時間結束后可以進行二手交易來降低使用成本。徐維軍等［17］結合輸入結構的分布信息研究了離散型在線租賃問題，建立了最優的離散型在線租賃決策模型，并給出了實際問題的精確解。

關于在線租賃策略研究，已有的成果主要是研究者在特定的條件下，根據自己的合理假設或推論構建在線策略，并得出其競爭比，以此得到某一類在線策略的合理性。其中，在購價租金連續下降型問題上，馬衛民等［13］、張永等［15］學者均在設備購買價格下降的情況下提出賃購平衡策略，即購買價格與累積租賃費用相等時選擇購買策略。該策略中累積租金與購買價格成比例關系，且具有競爭比上界2。而在購買價格與租金連續下降的情況下，在線人依據累積租金與購買價格具備數量關系的前提下作決策時，為何兩者相等而非其他的數量關系是具有最小競爭比的最優策略，學者們沒有相關的探討與證明。本文則在購價租金在較大時間單位內（如季度、年）隨著市場一般規律降低的情況下，證明了賃購平衡模型的最優性，為其在實際租買決策中的應用中提供了清晰的理論證明。

1　問題描述與基本假設

在傳統競爭分析［3］中，存在著一個供決策者選擇的策略集S和一個離線對手發出的序列集I。在線決策者的目的就是設計一個好的策略A∈S以應對離線對手可能發出不確定的輸入序列σ∈I。競爭分析方法與以往解決此類問題方法的最大區別在于：它在變化因素的每一個特例中都能給出一個方案，使得這一方案所得到的解與最優方案給出的解總在一定的比例之內，從而使在線問題的解始終保持在一個較優的狀態。在線算法中，決策者在事先不完全知道的情況下設計在線策略與事先完全知道未來信息時的最優離線策略進行比較。即，根據在線問題的競爭分析理論［18］，對在線策略A以及任何有限的輸入序列σ，假定CostON（σ）為在線策略A的費用，CostOPT（σ）為最優離線策略的費用，如果存在一個常數c，使得

則稱此在線策略具有競爭比c，或稱在線策略A為c競爭策略，顯然c≥1。競爭比的大小反映在線策略的性能，競爭比越小，在線策略性能越好。

某企業在市場前景無法預知的情形下，需要使用某種設備，則可知該企業有兩種方案可以選擇：

（i）租賃設備。租賃費用定義為一個在非負整數N上的序列｛r（t）｝，表示第t期的租賃費用；

（ii）一次購買設備。購買設備的費用類似地定義為一個在非負整數N上的序列｛p（t）｝，表示在第t期購買該設備的費用。

由于購買價格p（t）與租賃價格r（t）都是隨著市場規律而變化的，在較小的時間維度內（如日、月）可能上下波動，不存在顯著的降低特征；但是在較大的時間單位內（如季度、年），上兩者隨著市場的技術發展、新產品競爭等關系較大概率上會呈現出下降趨勢，這也是本文研究的現實意義所在。故這里假設r（t）為單調遞減序列，即邊際租賃費用隨著租賃時間的增加而越少。p（t）為單調遞減序列，且p（t）＞＞r（t），即任何時候的購買費用都遠遠大于當前的租賃費用。任何時間段（i，j）（i＜j，i，j＞0）內設備降價幅度小于這段時間內設備租賃費用的累計值，即，否則在線設備投資者將不會選擇購買設備策略。

購買價格和租賃費用都是隨著時間而不斷變化的連續函數。假設設備使用時期為［0，T］，記T為市場崩潰時期（CrashingTime），這與未知的市場需要相關，第T期之后不再使用該設備。T已知則為離線問題，CostOPT（T）為離線策略的最優費用；若T未知則為在線問題，CostON（T）為在線策略的費用。而在離線問題中，由于T以及設備購買價格、租賃費用變化情況均為已知，因而決策問題衍化為一個簡單數學問題：到崩潰時刻第T期為止，若，則從一開始就租賃設備；反之，若則選擇購買策略。

2　在線最優策略證明

由假設可知，當設備使用時間（即市場崩潰時期）T、購買設備的時期t購買價格及租金信息未知時，在線策略的費用CostON（T）滿足下述公式：

即，當市場崩潰時期T早于購買設備時期t時，在線策略費用為至T時期的累計租賃費用；當市場崩潰時期T晚于購買設備時刻t時，在線策略費用為至第T期的累計租賃費用與在t期設備的購買價格的總和。

2.1購價租金恒定

首先討論比較特殊的購價租金恒定的情況，可以看作是遞減速率為0的單調遞減函數，可以假定賦值p（t）≡P0。這種情況下的離線最優費用為：

其中，x是大于0的實數參數。不難發現，對于t＜t

1

，不等式

成立；對于t＞t

1

，則

成立。在這種情況下，有如下定理：

定理1當累積租賃費用與購買費用相等時購買策略具有最小的競爭比2［13］。

證明由于崩潰時期T未知，所以分兩種情況來證明：

情況1T＜t1。因為第t1期還未到來設備已無需使用，因此購買策略不會發生，得到競爭比：

可視為離線策略。

情況2T≥t1。易知。租賃設備至第t1期，然后購買設備。x取值不同，在線策略的選擇也有區別，故按x的不同取值計算其競爭比：

（1）x＞1，即在線策略為當累積租賃費用大于購買價格x倍時選擇購買設備，則顯然離線最優策略為一開始就購買設備。此時的競爭比為：

因為x＞1，所以競爭比為x無限取1時得到最小值2。

（2）x≤1，即在線策略為當累積租賃費用小于購買價格x倍時選擇購買設備，由于崩潰時間T的未知，此時離線最優策略又分為兩種情況：

i.購買設備，此時的競爭比為：

因為x＜1，所以競爭比為x無限取0時最小，即在線策略為一開始就購買設備，這種購買時刻確定的策略也就不能稱之為在線策略，為無效在線策略。

ii.租賃設備，此時的競爭比為：

因為x≤1，所以競爭比當x＝1時取到最小值2。

綜上所述，當x＝1，即累積費用與購買費用相等時競爭比最小，得其上界為2，即在線策略的競爭力最強。事實上，在實際經濟活動中可能并不會出現某一期結束時累積租金恰好等于當期的購買價格，這里不妨近似為當購買價格與累積租賃費用的正差額最小的時候選擇購買策略。

定理1得證，即在購價租金恒定的情況下，若在線策略為購價與累積租金成正比，則兩者相等，即賃購平衡時達到最小競爭比。

2.2一般情形

當設備的購價租金根據市場一般規律降低時，同樣設計如下策略：租賃設備至第t1期然后購買設備，其中t1滿足下式：

易得，對于t＜t1，不等式

成立；對于t＞t1，則成立。在這種情況下，有如下定理：

定理2當累積租賃費用與當時購買費用相等時購買策略具有最小的競爭比2［13］。

證明由于崩潰時期T未知，所以分兩種情況來證明：

情況1T＜t1。因為第t1期還未到來設備已無需再使用，因此在線決策者不會選擇購買策略，得到競爭比：

可視為離線策略。

情況2t1≤T≤t2。其中假定t2滿足。易知，按照不同x取值計算其競爭比：

（1）x＞1，即在線策略為當累積租賃費用大于當時購買價格x倍時選擇購買設備，則顯然離線最優策略為一開始就購買設備。此時的競爭比為：

因為x＞1，所以競爭比為x無限取1時得到最小值2。

（2）x≤1，即在線策略為當累積租賃費用小于當時購買價格x倍時選擇購買設備，顯然此時離線最優策略應該為一開始就租賃設備，競爭比為：

因為x≤1，所以競爭比當x＝1時取到最小值2。

（1）x＞1，即在線策略為當累積租賃費用大于當時購買價格x倍時購買設備，則顯然離線最優策略為一開始就購買設備。此時的競爭比為：

因為x＞1，所以競爭比為x無限取1時得到最小值2。

（2）x≤1，即在線策略為當累積租賃費用小于當時購買價格x倍時購買設備，由于崩潰時間T的未知，此時離線最優策略又分為兩種情況：

i.購買設備，此時的競爭比為：

因為x≤1，所以競爭比為x無限取0時最小，即在線策略為一開始就購買設備，但是這種購買時刻確定的策略也就不能稱之為在線策略，為無效在線策略。

ii.租賃設備，此時的競爭比為：

因為x≤1，所以競爭比當x＝1時取到最小值2。

綜上所述，當x＝1，即累積費用與當時購買費用相等時競爭比為2，在線策略的競爭力最強。事實上，在實際中可能并不會出現某一期累積租金恰好等于當期的購買價格。這里不妨近似為當時購買價格與累積租賃費用的正差額最小的時候選擇購買策略。

定理2得證。即在購價租金降低的情況下，若在線策略為當購價與累積租金成不確定性比例關系，則兩者相等，即賃購平衡時達到最小競爭比。

由上述的證明可得，在購買價格恒定和一般購價租金遞減的情形下，購買價格與累積租賃費相等（實際中可采用正差額最小）時選擇購買策略是最具競爭力的在線策略，即t1滿足實際中可采用，此策略稱為租賃購買平衡策略（近似平衡），也可簡稱為賃購平衡策略［13］，采取購買策略的時刻稱之為費用平衡點。

3　結語

在線設備租買是現實中在線決策者們面臨的重要問題，也是在線算法與競爭比方法著重研究的方向。根據市場競爭的正常規律，購買價格與租金在較大時間單位內隨時間降低的可能性很大。本文在此假設下，利用在線算法及競爭比，證明了賃購平衡策略（近似），即實時購買價格與累積租賃費用相等（實際中可為正差額最小）時選擇購買策略是最具競爭力的在線策略，并得出賃購平衡策略的競爭比上界。而本文只證明了在無利率情況下賃購平衡策略的最優性，卻沒有考慮利率情況下此策略的合理性與最優性。另外，現實生活中設備購買價格與租金的波動情況遠不止單調遞減，而購價與累積租金之間存在比例關系也是一個比較理想的假設。如何在更加復雜的情況下，將購價、租金、利率、折舊、風險補償以及通貨膨脹等因素一并加以考慮，研究出更加合理、現實的在線策略，有待于今后進一步的探討研究。

參考文獻：

［1］KARPRm.Onlinealgorithmsversusofflinealgorithms：Howmuchisitworthtoknowthefuture［M］//Proc.IFIP12thWorldComputerCongress.Amsterdam，Netherlands：North-HollandPublishingCo.，1992：416-429.

［2］FLEISCHERR.Onthebahncardproblem［J］.TheoreticalComputerScience，2001，268（1）：161－174.

［3］AL-BINALIS.Arisk-rewardframeworkforthecompetitiveanalysisoffinancialgames［J］.Algorithmica，1999，25（1）：99－115.

［4］KARLINAR，KENYONC，RANDALLD.DynamicTCPacknowledgmentandotherstoriesaboute/（e-1）［J］.Algorithmica，2003，36（3）：209－224.

［5］朱志軍，徐寅峰，徐維軍.局內租賃問題的風險補償模型及其競爭分析［J］.管理科學學報，2004，7（3）：64－68.

［6］辛春林，徐寅峰，衣方磊.基于預期的占線特殊優惠卡問題與競爭分析［J］.管理工程學報，2007，21（4）：14－18.

［7］丁黎黎，康旺霖.占線Bahncard問題的風險補償模型［J］.管理科學學報，2008，11（4）：38－43.

［8］徐寅峰，徐維軍，盧致杰.存在市場利率條件下的占線租賃策略研究［J］.系統工程，2005，23（3）：29－34.

［9］KARLINAR，MANAEESmS，McGEOGHLA，etal.Competitiverandomizedalgorithmsfornon-uniformproblem［EB/OL］.［2015-07-12］.https：//www.researchgate.net/publication/220780194＿Competitive＿Randomized＿Algorithms＿for＿Non-Uniform＿Problems.

［10］IRANIS，RAMANATHAND.Theproblemofrentingversusbuying［EB/OL］.［2015-07-12］.http：//citeseerx.ist.psu.edu/viewdoc/download？doi＝10.1.1.44.8179＆amp%3Brep＝rep1＆amp%3Btype＝pdf＆origin＝publication＿detail.

［11］EL-YANIVR，KANIELR，LINIALN.Competitiveoptimalon-lineleasing［J］.Algorithmica，1999，25（1）：116-140.

［12］FUJIWARAH，IWAMAK.Average-casecompetitiveanalysesforski-rentalproblems［J］.Algorithmica，2005，42（1）：95－107.

［13］馬衛民，陳國青.價格連續型局內設備賃購問題的競爭分析［J］.系統工程理論與實踐，2006（4）：90－96.

［14］LOTKERZ，PATT-SHAMIRB，RAWITZD.Rent，leaseorbuy：randomizedalgorithmsformultislopeskirental［EB/OL］.［2015－07－12］.https：//www.researchgate.net/publication/220994403＿Rent＿Lease＿or＿Buy＿Randomized＿Algorithms＿for＿Multislope＿Ski＿Rental.

［15］張永，張衛國，徐維軍.設備購買價格可變的確定性在線租賃策略［J］.系統工程，2009，27（11）：52－55.

［16］劉斌，辛春林，崔文田.具有線性交易成本的耐用性設備在線租賃策略分析［J］.管理學報，2011，8（10）：1549－1552.

［17］徐維軍，徐寅峰，盧致杰.具有幾何分布統計特征的在線租賃競爭分析［J］.預測，2005，24（2）：46－51.

［18］SLEATORDD，TARJANRE.Amortizedefficiencyoflistupdateandpagingrules［J］.CommunicationsoftheACM，1985，28（2）：202－208.

Optimalityanalysisofrenting-buyingbalanceonlinestrategyfordecreaseofpriceandrent

CHENGLing-yan，HEShi-wei

（SchoolofTrafficandTransportation，BeijingJiaotongUniversity，Beijing100044，China）

Abstract：Weprovethatbuyingstrategyshouldbeappliedonlyifreal-timepriceequalstoaccumulatedrentamounttoobtainapproximatelyoptimalonlinestrategywiththesmallestcompetitiveratiowhoseupper-boundis2underthedecreaseofpurchasepriceandrentwithtimeandindefinitedecisiontime.Weanalyzeserialrelationshipbetweendifferentmarketcrushingtimeandequipmentbuyingtimeandquantitativerelationshipbetweenpurchasepriceandaccumulatedrentforsuchtwocasesasconstantpriceandrentandgeneralsituation.Ourconclusionwillprovideatheoreticalreferencefortheapplicationofrenting-buyingbalancestrategyinpracticalrent-buydecision.

Keywords：onlinealgorithm；onlineleasing；renting-buyingbalancestrategy；competitiveratio

中圖分類號：U294.1；TB114.1

文獻標識碼：A

文章編號：1002-4026（2016）01-0076-07

DOI：10.3976/j.issn.1002－4026.2016.01.013

收稿日期：2015-11-03

基金項目：中國鐵路總公司科技研究開發計劃（2014X010-D）

作者簡介：程玲燕（1992－），女，碩士研究生，研究方向為在線租買決策、運輸組織現代化等。Email：13120824＠bjtu.edu.cn