业务
资源配置
产业组织
营销
微观经济学
知识管理
计算机科学
经济
计算机网络
作者
Negin Golrezaei,Evan Yao
出处
期刊:Management Science
[Institute for Operations Research and the Management Sciences]
日期:2025-09-04
卷期号:72 (5): 4087-4105
被引量:10
标识
DOI:10.1287/mnsc.2022.03335
摘要
In many online platforms like ride-sharing or grocery delivery, some demand agents can wait for a short period of time for a service if they are assured of its eventual provision within an acceptable delay. We study these “partially patient” agents in the context of an online resource allocation problem, contrasting them with impatient agents who require immediate service. We utilize a relaxed notion of competitive ratio, known as the resource/feature augmented competitive ratio, allowing online algorithms to benefit from additional features not available to the optimal offline algorithm. We introduce a class of polytope-based resource allocation (POLYRA) algorithms that achieve optimal or near-optimal competitive ratios by consulting specific polytopes and maintaining feasible algorithm states within these polytopes. For two or three types of agents, these algorithms can achieve the optimal competitive ratio. For more than three types, we present a near-optimal nested POLYRA algorithm that secures at least 80% of the optimal ratio. Our theoretical findings are supported by numerical analysis, highlighting the efficiency of our algorithms beyond adversarial arrivals and the modified competitive ratio framework. This paper was accepted by Chung Piaw Teo, optimization and decision analytics. Supplemental Material: The online appendices and data files are available at https://doi.org/10.1287/mnsc.2022.03335 .
科研通智能强力驱动
Strongly Powered by AbleSci AI