论文标题
批处理和最佳多阶段分配
Batching and Optimal Multi-stage Bipartite Allocations
论文作者
论文摘要
在在线市场中实时匹配需求的实时匹配的几种应用中，该平台允许一些延迟批量需求并提高效率。在这些应用程序的激励下，我们研究了对抗性到达下批处理与效率低下之间的最佳权衡。作为我们的基本模型，我们考虑了在对抗性环境中的顶点加权B匹配的K阶段变体，在线顶点在舞台上和K批处理中 - 与在线到达相反。这个问题的主要结果是最佳（1-（1-1/k）^k） - 竞争性（分数）匹配算法，改善了以其在线变体而闻名的经典（1-1/e）竞争比（Mehta等，2007; Aggarwal等，2011）。我们还将此结果扩展到具有自由分配的多阶段配置分配的丰富模型（Devanur等，2016），该模型是由视频流平台中的展示广告激励的。 我们的主要技术是开发工具，以改变各个阶段算法的“贪婪”和“对冲”之间的权衡。我们依靠特定的基于凸编程的匹配家庭，该匹配匹配以不同阶段的供应方式在供应之间分配需求，同时仔细修改了跨阶段所得匹配的平衡性。更确切地说，我们确定一系列具有降低程度的多项式序列，以用作最大重量匹配线性程序的严格凹入正规化，以形成这些凸面程序。在每个阶段，我们的算法返回相应的正则最佳解决方案作为此阶段的匹配（通过求解凸程序）。使用这些凸面程序的结构属性并递归地将正规化器连接在一起，我们开发了一个新的多阶段原始二重二重框架来分析竞争比率。我们进一步表明该算法具有最佳竞争力。
In several applications of real-time matching of demand to supply in online marketplaces, the platform allows for some latency to batch the demand and improve the efficiency. Motivated by these applications, we study the optimal trade-off between batching and inefficiency under adversarial arrival. As our base model, we consider K-stage variants of the vertex weighted b-matching in the adversarial setting, where online vertices arrive stage-wise and in K batches -- in contrast to online arrival. Our main result for this problem is an optimal (1-(1-1/K)^K)- competitive (fractional) matching algorithm, improving the classic (1-1/e) competitive ratio bound known for its online variant (Mehta et al., 2007; Aggarwal et al., 2011). We also extend this result to the rich model of multi-stage configuration allocation with free-disposals (Devanur et al., 2016), which is motivated by the display advertising in video streaming platforms. Our main technique is developing tools to vary the trade-off between "greedy-ness" and "hedging" of the algorithm across stages. We rely on a particular family of convex-programming based matchings that distribute the demand in a specifically balanced way among supply in different stages, while carefully modifying the balancedness of the resulting matching across stages. More precisely, we identify a sequence of polynomials with decreasing degrees to be used as strictly concave regularizers of the maximum weight matching linear program to form these convex programs. At each stage, our algorithm returns the corresponding regularized optimal solution as the matching of this stage (by solving the convex program). Using structural properties of these convex programs and recursively connecting the regularizers together, we develop a new multi-stage primal-dual framework to analyze the competitive ratio. We further show this algorithm is optimally competitive.
