Deterministic and Universal Truthful Mechanism for Fair Matching
摘要
This study addresses the bipartite graph weight maximum matching problem with a focus on achieving fairness. We introduce a deterministic truthful mechanism and a universal truthful mechanism tailored for fair matching, striving for an asymptotically lexicographically optimal solution. To tackle this, we employ a transformation function that reduces the original problem to a weight maximum matching problem, alongside an iterative algorithm based on TMHA and RTMHA (TMHA means Truthful Matroid House Allocation and RTMHA means Random Truthful Mechanism for Matroid House Allocation [18], they are both extensions of serial dictatorship and random serial dictatorship to cases where agents have ties.). Our approach yields an approximation ratio of at most 2 for deterministic truthful mechanisms and at most 1.58 for universally truthful mechanisms, while also requiring polynomial time complexity. By offering a balanced solution, our method contributes to equitable outcomes in matching scenarios.