An Optimal Truthful Mechanism for the Online Weighted Bipartite Matching Problem
An Optimal Truthful Mechanism for the Online Weighted Bipartite Matching Problem
复制标题
DOI：
10.1137/1.9781611975482.120
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Rebecca Reiffenhäuser
中科院分区：
文献类型：
--
作者：
Rebecca Reiffenhäuser
在加权双元图匹配问题中，目标是在具有非负边权的双元图中找到最大权匹配。我们考虑的是其在线版本，其中第一个顶点集是事先已知的，但第二个顶点集的顶点会一个接一个地出现。第一组顶点被解释为物品，第二组顶点被解释为投标人。到达时，每个投标人顶点都会显示所有相邻边的权重，算法必须决定将哪些边加入到匹配中。我们引入了一种最优的、电子竞争的真实机制，其假设条件是投标者以随机顺序到达（秘书模型）。研究表明，原始秘书问题的 e 上下限可以扩展到其他各种问题，甚至是具有丰富组合结构的问题，加权双方格匹配就是其中之一。但是，一旦各自的算法偏离了原始的简单阈值形式，迄今为止的求真机制都无法达到合理的竞争比率。Krysta 和 Vocking [19] 最著名的加权双顶匹配机制只提供了在线顶点数量的对数比率。我们缩小了这一差距，证明了真实性并没有施加任何额外的约束。我们的证明技术是这一领域的新技术，基于对机制固有独立性的观察。本文所提供的见解本身就很有趣，而且似乎为其他问题（无论是否具有真实性）提供了有前途的工具。
In the weighted bipartite matching problem, the goal is to find a maximum-weight matching in a bipartite graph with nonnegative edge weights. We consider its online version where the first vertex set is known beforehand, but vertices of the second set appear one after another. Vertices of the first set are interpreted as items, and those of the second set as bidders. On arrival, each bidder vertex reveals the weights of all adjacent edges and the algorithm has to decide which of those to add to the matching. We introduce an optimal, e-competitive truthful mechanism under the assumption that bidders arrive in random order (secretary model). It has been shown that the upper and lower bound of e for the original secretary problem extends to various other problems even with rich combinatorial structure, one of them being weighted bipartite matching. But truthful mechanisms so far fall short of reasonable competitive ratios once respective algorithms deviate from the original, simple threshold form. The best known mechanism for weighted bipartite matching by Krysta and Vocking [19] offers only a ratio logarithmic in the number of online vertices. We close this gap, showing that truthfulness does not impose any additional bounds. The proof technique is new in this surrounding, and based on the observation of an independency inherent to the mechanism. The insights provided hereby are interesting in their own right and appear to offer promising tools for other problems, with or without truthfulness.