In the weighted bipartite matching problem, the goal is to find a maximum-weight matching
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 offers only a ratio logarithmic in the number
of online vertices. We close this gap, showing that truthfulness does not impose any additional
bounds.
12/10/2018