论文标题
改进了在线争夺解决方案，以搭配吉格经济的匹配和申请
Improved Online Contention Resolution for Matchings and Applications to the Gig Economy
论文作者
论文摘要
通过在零工经济中的应用，我们研究了\ emph {顺序定价问题}的近似算法。输入是个人$ i $和jobs $ j $之间的两分图$ g =（i，j，e）$。该平台的价值为$ v_j $，用于与单个工人相匹配的工作$ j $。为了找到匹配，该平台可以按任何顺序考虑边缘$（i j）\ in E $，并进行一次性take-it-it-it-it-it-或leave-it提供价格$π_{ij} = W $的$ i $ $ i $。工人以已知概率$ p_ {ijw} $接受要约；在这种情况下，工作和工人是不可撤销的。提供最大化收入和/或社会福利的最佳优惠方法是什么？ 已知最佳算法是计算的NP-HARD（即使只有一个作业）。考虑到这一点，我们通过用于匹配的新的随机订单在线争夺方案（RO-OCRSS）设计有效的最佳策略近似值。我们的主要结果是在两部分图中具有0.456平衡的RO-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR-OR。这些算法在$ \ frac {1} {2}（1-e^{ - 2}）\ [BGMS21]的大约0.432 $的最新界限上有所改善，尽管适用于更大的限制性设置，但在匹配的相关性差距上的最著名的下限也有所改善。由于我们的OCR结果，我们为顺序定价问题获得了$ 0.456 $ - 售价算法。我们将结果进一步扩展到只有有限次数的工人，并通过改进的算法来解决该问题的改进结果，并显示如何实现良好的随机探测问题。
Motivated by applications in the gig economy, we study approximation algorithms for a \emph{sequential pricing problem}. The input is a bipartite graph $G=(I,J,E)$ between individuals $I$ and jobs $J$. The platform has a value of $v_j$ for matching job $j$ to an individual worker. In order to find a matching, the platform can consider the edges $(i j) \in E$ in any order and make a one-time take-it-or-leave-it offer of a price $π_{ij} = w$ of its choosing to $i$ for completing $j$. The worker accepts the offer with a known probability $ p_{ijw} $; in this case the job and the worker are irrevocably matched. What is the best way to make offers to maximize revenue and/or social welfare? The optimal algorithm is known to be NP-hard to compute (even if there is only a single job). With this in mind, we design efficient approximations to the optimal policy via a new Random-Order Online Contention Resolution Scheme (RO-OCRS) for matching. Our main result is a 0.456-balanced RO-OCRS in bipartite graphs and a 0.45-balanced RO-OCRS in general graphs. These algorithms improve on the recent bound of $\frac{1}{2}(1-e^{-2})\approx 0.432$ of [BGMS21], and improve on the best known lower bounds for the correlation gap of matching, despite applying to a significantly more restrictive setting. As a consequence of our OCRS results, we obtain a $0.456$-approximate algorithm for the sequential pricing problem. We further extend our results to settings where workers can only be contacted a limited number of times, and show how to achieve improved results for this problem, via improved algorithms for the well-studied stochastic probing problem.
