双人合作的在线雪橇租赁问题

以往的文献只研究了单人雪橇租赁问题,本文将雪橇租赁问题扩展到了双人合作情形.研究了两个在线决策者的合作博弈模型,给出了TBS策略和BCS策略,并求出了双方收益分配的纳什均衡解.结论显示,TBS策略具有最小竞争比,但基于该策略的合作却不稳定,需要契约维持;BCS策略不具有最小竞争比,却是占优策略,基于该策略的合作是稳定的。因此存在合作可能的情况下,选择BCS策略的合作总比非合作要好。文章第4节详细的比较了TBS策略和BCS策略。   此外,文章还得到了一个有意思的发现,随着参与人的增加,竞争比是有可能不上升的.这一发现与经典的在线问题(如k-server问题)的结论不一样,在k-server问题中,随着参与者(服务器)的增加,竞争比会呈线性提高》。

Two-people Cooperated On-line Ski Problem

In this paper, a model of two-people cooperated on-line ski problem, which is an extension of classical problem in the area of on-line algorithms analysis, is studied. Firstly, TBS strategy and BCS strategy, together with their profit-sharing Nash equilibrium solution, are given. Two main results are concluded from these two strategies. I)The TBS strategy has lower-bounding competitive ratio; however, the cooperation based on it is not stable and a contract is badly in need. On the contrary, the BCS strategy do not has lower-bounding competitive ratio but it leads to stable cooperation. II)In every case, cooperation based on BCS strategy results in a better profit than non-cooperated case. In Section 4, a comparison between TBS and BCS is given.    In addition, we give the first results of online ski problem for which multiple participant versions admit no growing Competitive Ratios than their single participant counterparts. This is typically not the case for the classical on-line problem, such as the k-server problem, where the competitive ratio necessarily grows linearly with k.