论文标题
探索在线匹配市场的竞争比与差异之间的权衡
Exploring the Tradeoff between Competitive Ratio and Variance in Online-Matching Markets
论文作者
论文摘要
在本文中，我们提出了一个基于在线匹配的模型，以研究在各种在线匹配市场中引起的分配问题，包括在线建议，乘车平台和众包市场。它的特征是每个分配都可以请求一组随机的资源并产生一个随机的实用程序，并且两个（成本和实用程序）可以彼此任意相关。我们提出了两个基于线性编程的参数化策略，以研究总实用程序的\ emph {竞争比}（cr）与匹配总数（未加权版本）上的\ emph {差异}之间的权衡。第一个（SAMP）是根据从千里眼最佳的分布进行采样边缘，而第二个（ATT）具有时间自适应的衰减框架，从而改善了先进的竞争性比率结果。我们还考虑了大型预算假设下的问题，并表明SAMP在竞争比率方面取得了渐近的最佳性能。
In this paper, we propose an online-matching-based model to study the assignment problems arising in a wide range of online-matching markets, including online recommendations, ride-hailing platforms, and crowdsourcing markets. It features that each assignment can request a random set of resources and yield a random utility, and the two (cost and utility) can be arbitrarily correlated with each other. We present two linear-programming-based parameterized policies to study the tradeoff between the \emph{competitive ratio} (CR) on the total utilities and the \emph{variance} on the total number of matches (unweighted version). The first one (SAMP) is to sample an edge according to the distribution extracted from the clairvoyant optimal, while the second (ATT) features a time-adaptive attenuation framework that leads to an improvement over the state-of-the-art competitive-ratio result. We also consider the problem under a large-budget assumption and show that SAMP achieves asymptotically optimal performance in terms of competitive ratio.
