基于收益率的在線租賃策略及其競爭分析

摘 要：本文考慮成本和收益兩個因素，從收益率的角度研究商業用房在線合租問題。首先，給出了問題離線情形的最優解；其次，針對一方退出合租而新合租者到來時刻不可預知的在線情形，為未退出者設計了在線等待策略，得到了策略的競爭比，并且證明了其是最優確定性競爭策略；最后，基于風險補償模型，對該問題進行了進一步分析。

關鍵詞：商業用房；合租；收益率；在線策略；競爭分析

中圖分類號：C931 文獻標識碼：A 文章編號：1003-5192(2011)02-0051-06

Online Rental Problem Based on Benefit-cost Ratio

and Its Competitive Analysis

XU Yin-feng1，2，3， CAO Yong-feng1，2，3， NI Guan-qun1，2，3

(1.School of Management， Xi’an Jiaotong University， Xi’an 710049， China; 2.The State Key Lab for Manufacturing Systems Engineering， Xi’an 710049， China; 3.Ministry of Education Key Lab for Process Control Efficiency Engineering， Xi’an 710049， China)

Abstract:This paper studies the online commercial building co-rental problem in the view of benefit-cost ratio. Firstly， the optimal strategy for the offline case is deduced. And then the paper designs an online waiting strategy for the online case and gets its competitive ratio. Finally， the paper analyses the problem based on the risk-reward framework.

Key words:commercial building; co-rental problem; benefit-cost ratio; online strategy; competitive analysis

1 引言

租賃是一種應用非常廣泛的融資方式，在租賃過程中存在著大量的不確定性因素，比如經營收益、相關政策等，這些外界不確定往往導致租賃最優決策的改變，因此針對各種不確定因素，研究者做了大量研究，而與本文聯系比較密切的研究角度及方法是在線算法和競爭分析。揭示租賃問題的在線特點以及用競爭分析的方法進行研究的經典模型是Karp［1］提出的“Ski Rental Problem”模型。該模型假設滑雪初學者不知道自己會滑雪多少次，因此，每次滑雪時都面臨兩種選擇：花費c成本租滑雪撬，或者花費P成本一次性購買雪撬。Karp 給出了競爭比為2-c/P的最優確定性競爭策略。隨后，很多學者結合現實租賃問題，對該基本模型進行了擴展研究，主要思路有兩種。一種思路是將基本租賃模型推廣應用到其他現實問題中，如Fleischer［2］提出的在線優惠卡模型；辛春林［3］、丁黎黎等［4，5］將風險補償概念應用于優惠卡模型，并進行了相應的擴展研究；2003年Karlin［6］將租賃模型應用于TCP問題。另一種思路是對原模型的假設進行修正，改善決策者的決策信息，得到更優的競爭比。比如1994年Karlin［6］討論了未來需求為隨機變量的租賃問題，給出了隨機在線算法，使競爭比達到了e/(e-1)；2002年Fujiwara［8］研究了輸入概率分布為指數分布的情形，并說明了競爭比大約在1.5左右；2005年徐維軍［9，10］等研究了未知信息具有幾何分布特征的租賃問題，使競爭比達到了1.45836； Irani［11］、徐維軍［12］討論了存在費用波動情形下的租賃策略；EI-Yaniv［13］和徐寅峰［14］等分別討論了考慮利率因素的在線租賃策略；Al-Binali［15］把在線決策者的風險行為引入傳統競爭分析，建立了風險補償模型；2008年Lotker等人［16，17］在前人的研究基礎上對基本租賃模型進行了擴展，提出了“Multislope Ski Rental Problem”的模型，在該模型中，決策者不僅是“純粹的買或租”的選擇，而是在花費一定購置費的基礎上，在不同階段使用設備還要花費一定比例的使用費，作者針對購置費遞增的情形，給出了一個e/(e-1)-競爭的隨機策略，而對于購置費不變的情形，給出了一個簡單的e-競爭的隨機策略。

以往的在線租賃問題基本上沒有從收益率（收益與成本之比）的角度進行研究，主要原因是以往模型要么只考慮消費型租賃［18］，即租賃的物品提供的是純消費，使用效益難以衡量，因此研究者只從成本角度進行分析，并給出相應的競爭策略；要么僅從收益角度分析，總之沒有把租賃成本和租賃期的收益結合在一起進行研究。在一般經營活動中，短期的盈利與虧損并不是投資者最關心的問題，相反，投資者更注重長期穩定的投資收益率，這就需要在研究中將成本與收益結合來考察問題。而收益率的概念實際上包含了利潤的內涵，當收益率大于1時，利潤為正，當收益率小于1時，利潤為負。因此，本文從收益率角度研究了一類比較現實的租賃問題——商業用房合租。在現實中，存在一類普遍的商業用房合租現象：經營者為了以較小的成本實現規模經營，常會采取合租商業房的形式經營。在經營中，各經營者的業績不盡相同，虧損者會隨時退出合租。一方退出后，未退出者需要在當期做出一起退出還是繼續租用等待新合租者的抉擇。本文在新合租者到來信息無法預知的假設下，利用在線策略與競爭分析的方法，從收益率的角度，對商業用房合租問題進行了研究，并討論了基于風險補償模型的風險補償收益，為現實經濟生活中的商業用房租賃者提供了值得參考的理論依據。

2 問題描述與基本假設

本文研究的商業用房合租問題描述如下。兩個經營者（A和B）在t0=0時刻合租一套合同期到tn=n的商業用房，各自經營，平均支付房租，單位時間的房租為h，A的單位收益為r。如果在合同期內有一方退出，不妨設B在tb=b（要求0

若ta已知，該問題是一個離線問題，兩種決策的效果容易比較，而現實中A往往無法預知ta，此時在B退出后，A如何決策使得結果盡可能好，則為該離線問題對應的在線問題。以往處理類似問題時，一般假設ta服從某種概率分布，尋求期望意義下的最優，但對于這種不確定性較強的問題，就失去了可行性。在線策略與競爭分析為研究這樣的不確定性問題提供了方法，競爭分析就是在新合租者到來時刻ta無法預知的情況下，為決策者A設計一種在線策略，使得其在線值與對應的離線最優值的比值總在一定的范圍之內。以往競爭分析大都是單從成本或者收益角度衡量在線策略的競爭性，本文從實際商業活動出發，從收益率角度對商業用房合租問題進行了競爭分析。設BenefitS為策略S的收益，CostS為對應的成本，則策略S的收益率為βS=BenefitSCostS，很顯然收益率越大越好。如果對于任意的ta，在線策略S的收益率βS(ta)與離線最優策略OPT的收益率βOPT(ta)=BenefitOPT(ta)CostOPT(ta)，總滿足βOPT(ta)≤αβS(ta)，則稱該在線策略是α-競爭的，α越小表示在線策略越有競爭性，它是衡量策略競爭性優劣的依據。如果某一個在線策略的競爭比滿足α*=infS(α)，則稱S*為該問題的最優在線策略，并稱α*為問題的最優競爭比。

需要說明的是，本文中對B的退出時刻b和違約費用c#8226;h的要求可以由具體的合同來約定，可以將c稱為最小租房時間。為便于精簡論證過程，在后面的計算中以i表示ti，并給出模型的基本假設如下：

假設1 單位房租h以及A的單位經營收益r不隨時間而變化；

假設2 新到的合租者不會在本合同期內退出；

假設3 h/2

3 離線最優策略

在新合租者到來時期a可預知的情形下，決策者A只需要比較與B一起退出和等待新合租者兩種策略的收益率大小即可做出決策，收益率大的策略為占優策略。

若A與B在時刻b一起退出，此時A的收益為Benefit1=br，成本為Cost1=(b+c)h/2，因此收益率為β1=2br(b+c)h。如果A一直等到合同期結束，則需要根據新合租者到來時刻分兩種情況討論：①在合同期內沒有新合租者到來，即a>n，此時A的收益為Benefit21=nr，成本為Cost21=(n-b/2)h，因此收益率為β21=2nr/(2n-b)h；②在合同期內有新合租者到來，即a≤n，此時A的收益為Benefit22=nr，成本為Cost22=(n+a-b)h/2，因此收益率為β22=2nr/(n+a-b)h。對離線情形的收益率進行比較分析，我們給出如下離線策略S0和定理1。

離線策略S0：(1)當c∈［0，n/4］時，如果a>n，且b∈［Z1，Z2］，決策者A與B同時退出，否則A一直租到合同期結束；如果a≤n，若有b∈［Z1，Z2］，且a>a0，決策者A與B同時退出，否則A一直租到合同期結束，其中，Z1=(n-n2-4nc)/2，Z2=(n+n2-4nc)/2。(2)當c>n/4時，決策者A一直租到合同期結束。

定理1 離線策略S0是最優離線策略。

證明 對于定理1，我們分a>n與a≤n兩部分來證明。

第一部分：即證明a>n時的決策。

在B退出后沒有新合租者到來（a>n）的情形下，離線決策者A根據β1與β21的大小有兩個選擇，顯然地，當β1≥β21時A會與B一起退出，否則A會一直租到合同期結束。

由符號定義與關系β1≥β21，我們可以得到不等式b2-nb+nc≤0，而該不等式在c∈［0，n/4］時有解，且令其解集為［Z1，Z2］。得到如下結論：

如果在B退出后沒有新合租者到來（即有a>n），那么當c∈［0，n/4］且B退出時刻b滿足不等式（1）時，離線決策者A會與B同時退出，否則A會一直租到合同期結束。

Z1=n-n2-4nc2≤b≤n+n2-4nc2=Z2（1）

同時，由以上分析可以看出，只要合同中規定的c>n/4，離線決策者的最佳決策就是一直租到合同期結束，因此我們在后續討論中僅需考慮c≤n/4時的決策。

第二部分：即證明c≤n時的決策。

在B退出后有新合租者到來（a≤n）的情形下，我們令β1≥β22，當b滿足不等（1）式（即b∈［Z1，Z2］），可以得到a≥b+nbc，令a0=b+cn/b，也即此時若新合租者在a0時刻之后到來（即a≥a0），A會與B一起退出，否則A會一直租到合同期結束。

綜合兩部分的證明，即定理1得證。

由以上的證明我們可以看出，若c∈［0，n/4］，則一定有Z1<2cn/2），決策者A應一直租房到合同期結束。

我們以收益率為依據對決策進行分析，將決策分為三部分討論。由于存在違約金，如果B很早退出（bZ2），決策者等待的成本較小，租用到合同期結束的收益率相對較大；而當b∈［Z1，Z2］時，需要根據其他具體信息進一步討論。僅從成本或收益的角度研究的文章一般會在某一時點將決策分為不同的兩部分，這正區別于本文基于收益率概念的討論，也是本文研究的特別之處。

4 在線策略及競爭分析

在線情形下，B退出后，A無法預知新合租者何時到來，但仍要在當期做出決策。由離線策略定理1的結論可知，當c>n/4時，決策者A一直租到合同期結束，因此我們僅需討論c∈［0，n/4］的問題。同樣，當c∈［0，n/4］時，無論合同期內是否有新合租者到來，只要b［Z1，Z2］，最優策略都是一直租到合同期結束。那么在線決策者在這種情況下的最優策略也是一直租房到合同期結束，顯然，離線情形與在線情形的收益率之比為1。因此，我們只需要分析討論在b∈［Z1，Z2］時的在線策略S0。由以上分析，我們給出如下確定性等待策略，以及定理2。

等待策略S0：B在b時刻退出后，若Z1

定理2 等待策略S0的競爭比為max［2+2c-ba0n，2+2c-bbn］，且該策略為最優確定性在線策略。

證明 為證明定理2，我們先給出一個一般策略S：決策者A等待至w=k#8226;a0時刻再退出，其中b≤ka0≤n，a0=b+cn/b。通過分析可以給出確定性在線等待策略S0，并證明其是最優的確定性在線策略。

根據對離線最優決策特點的分析，我們按B退出的不同時刻，分b≤2c和b>2c兩種大情形討論，同時用α及其上標(標識兩種大情形)與下標（標識各Case）表示各情形下離線收益率與在線收益率的比。

情形1 Z1

當Z1

Case 1 w

因為合同期內不會有新合租者到來，離線決策者會與B同時退出，其收益率為βOPT1=2br/(b+c)h。離線決策者與在線決策者的收益率之比為

α11=βOPT1βS1=b(w-b/2+c)w(b+c)

=bb+c+b(c-b/2)k(b+c)a0

=bb+c［1+2c-b2ka0］（2）

當k取最大值時，取到最小值min α11=bb+c［1+2c-b2n］，即一直等待新合租者的在線策略較優。

Case 2 w

Case 2.1 a>a0，有b≤ka0≤n，離線決策者和B一起退出，有α12.1=bb+c［1+2c-b2ka0］，在k=na0時，取得最小的min α12.1=bb+c［1+2c-b2n］，即一直等待新合租者的在線策略較優。

Case 2.2 a0>a，有b/a0

α12.2=2nn+a-b-b-2cka0(n+a-b)

它隨k的增加單調減，所以當a=b時，在k=1，取得最小的min α12.2=2+2c-ba0n，即A等待到a0時刻的在線策略較優。

Case 3 a≤w≤n：在線決策者能等到新合租者到來，其在線收益率為βS3=2nr/(n+a-b)。

對于離線決策者，需要討論兩種子情形：

Case 3.1 a0

由于2nrn+a-b≥wr(w-b/2+c)h，與Case2中的子情形類似分析可知α3.1≤α12.1。

Case 3.2 a≤a0，離線策略與在線策略的收益率相同，α3.2=1。

所以，在Case3的情形下，有

α13.1=max{1，α3.1}=α3.1≤α12.1

綜上所述，當Z1

α1=max min［α11，α12.1，α12.2，α13.1］

=2+(2c-b)/a0n

有如下結論：當Z1

情形2 2c

與情形1的討論相似，根據新合租者到來的不同時刻，當2c

Case 1 w

Case 2 w

Case 2.1 a>a0，有b≤ka0≤n，此時在k=b/a0，即A與B同時退出時，取得最小的min α22.1=bb+c［1+2c-b2b］。

Case 2.2 a0>a，有b/a0

綜上所述，在2c

因此，綜合對情形1與情形2的討論分析，有

αS0=max［1，α1，α2］=max［2+2c-ba0n，2+2c-bbn］

根據競爭比的定義，我們證明了確定性等待策略S0的競爭比為αS0，且該策略為最優確定性在線策略。

定理2得證。

該結論與現實情況相符合，由于存在違約金，因此需要根據違約金的大小以及合租者B的退出時刻，來確定決策者A的選擇。從收益率的角度進行分析討論，需要考慮決策期內收益與成本的比值，該比值越大越好。因此，本文的討論對于追求資金有穩定收益率的企業和個人經營具有一定的現實意義。

5 在線風險補償收益

在現實經營活動中，決策者時常會對無法預知的信息有所預期。根據Al-Binali［15］提出的在線風險補償概念，在前節討論的模型中加入風險補償因素，如果經營者對新合租者的到來時刻有預期，并且敢于冒一定的風險，若預期成功就有可能得到更優的競爭比結果，相反，如果預期失敗則會面臨更大風險。

令αS為策略S的競爭比，將風險策略S的風險定義為其競爭比與最優競爭比的比值αSα*，它反映了策略S對最優策略的最大機會成本。令F為預期新合租者到來序列，如果在線決策者預期正確，則定義α^S=supFβOPT（F）βS（F）為約束競爭比，風險策略S的補償收益為fS=α*/α^S，表示在預期成功競爭比的改善情況。

對于本文研究的問題，我們只需要考慮c∈［0，n/4］，并且Z1a0。

在這里，我們設決策者的在線風險策略S^為等待到w^=k′a0時刻退出，決策者可以做出如下預期：

設預期（1）成功，為了使收益率盡可能大，采取等待新合租者到w^≥a0時刻的策略，當w^>a0，風險會擴大，收益率不會增大。因此，在線決策者的風險競爭策略為w^=a0，此時約束競爭比為α^S^1=1，預期補償收益為2+(2c-b)/a0n。

設預期（2）成功，在這種預期下，為了獲得比無預期時更好的競爭比，A會與B同時退出，而一旦選擇此策略，離線對手為了使其處于最壞情形，會讓新合租者立刻到來。在線決策者的風險競爭策略集為{w^|b≤w^

α^S^2=maxβOPTβS^=max2b(w^-b/2+c)w^(b+c)

=maxbb+c［1+2c-b2k′a0］=bb+c［1+2c-b2b］（3）

預期補償收益為

fS^=［2+2c-ba0n］bb+c［1+2c-b2b］（4）

若預期失敗，最壞情形是a=a0，w^=a0-ε，此時，βOPT=2nr/(n+a0-b)，βS^=w^r/［(w^-b/2+c)h］，競爭比為

2nn+a0-b-b-2c(a0-ε)(n+a0-b)

說明當預期錯誤的時候，決策就存在風險，競爭比反而會變大。

由以上的分析，可以看出，當決策者對未來信息有一定預期，并且在預期正確的時候，會得到改進的競爭比bb+c［1+2c-b2b］，并且可以獲得相應的風險補償收益。

6 結論

隨著經濟發展，政府鼓勵和引導中小投資者自主經營，規模小的經營者為了能以較少的成本形成規模經營，常常共同租賃一處商鋪經營，這正是本文研究的問題。本文考慮成本和收益，從收益率角度首先對離線情形的收益率進行分析，給出了離線最優策略；其次，對于新合租者到來不確定的在線情形，利用在線策略與競爭分析的方法給出了競爭比為max［2+2c-ba0n，2+2c-bbn］的確定性在線策略；最后討論了決策者對未來信息有預期情形下的風險補償收益。本文的討論對現實經濟活動中的相關租賃問題有一定的借鑒意義。

在文中討論的商業用房合租問題中，我們假設新合租者到來后就不會退出，這可以通過協議來約束，而且即便存在新合租者又退出的情形，也可以通過與本文類似的討論給出在線策略。現實中，B退出時應該會給與A一定的補償，在這種情況下與本文所得到的結果是相似的。另外，我們討論的經營者的收入是恒定的，也沒有考慮新的合同期可能帶來的收益。如何能夠更貼近實際進行相關問題的拓展研究，有待于在今后進行討論。

參 考 文 獻：

［1］ Karp R. On-line algorithms versus off-line algorithms: how much is it worth to know the future［A］. Proceedings of the IFIP 12th World Computer Congress［C］. Elsevier Science， Amsterdam， 1992. 416-421.

［2］Fleischer R. On the bahncard problem［J］. Theoretical Computer Science， 2001， 268(1): 161-174.

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

［4］丁黎黎，康旺霖.占線Bahncard問題的風險補償模型［J］.管理科學學報， 2008，(4):38-43.

［5］丁黎黎，劉新民，康旺霖.可退占線優惠卡問題及其競爭分析［J］.系統工程，2009，27(2):51-55.

［6］Karlin A R， Kenyon C， Randall D. Dynamic TCP acknowledgment and other stories about e/(e-1)［J］. Algorithmica， 2003， 36(3): 209-224.

［7］Karlin A R， Manasse M S， McGeogh L， et al.. Competitive randomized algorithms for nonuniform problems［J］. Algorithmica， 1994， 11(6): 542-571.

［8］Fujiwara H， Iwama K. Average-case competitive analysis for ski-rental problems［M］.Berlin Springer-Verlag Heidelberg， 2002. 476-488.

［9］徐維軍，徐寅峰，盧致杰.具有幾何分布統計特征的在線租賃問題研究［J］.預測，2005，24(2):46-51.

［10］Xu Y F， Xu W J. Competitive algorithms for online leasing problem in probabilistic environments［J］. Lecture Notes in Computer Science， 2004， 3174: 725-730.

［11］Irani S， Ramanathan D. The problem of renting versus buying［Z］. Personal Communication， 1998.

［12］徐維軍，張衛國，胡茂林.租金費用和購買價格連續可變的在線租賃競爭策略分析［J］.中國管理科學，2006，14(2):94-99.

［13］El-Yaniv R， Kaniel R， Linial N. Competitive optimal on-line leasing［J］. Algorithmica， 1999， 25: 116-140.

［14］徐寅峰，徐維軍，盧致杰.存在市場利率條件下的占線租賃策略研究［J ］.系統工程，2005，23(2):29-34.

［15］Al-Binali S. A risk-reward framework for the competitive analysis of financial games［J］. Algorithmica， 1999， 25: 99-115.

［16］Lotker Z， Patt-Shamir B， Rawitz D. Rent， lease or buy: randomized algorithms for multislope ski rental［A］.In Albers S， Weil P， eds. Proceedings of the 25th International Symposium on the Theoretical Aspects of Computer Science［C］. LABRI， Bordeaux， 2008. 503-514.

［17］Lotker Z， Patt-Shamir B， Rawitz D. Ski rental with two general options［J］. Information Processing Letters， 2008， 108: 365-368.

［18］劉斌，崔文田，辛春林.住房租賃占線算法及其競爭策略［J］.系統工程，2007，(6):53-56.