TY - GEN
T1 - Improved Truthful Rank Approximation for Rank-Maximal Matchings
AU - Zhang, Jinshan
AU - Liu, Zhengyang
AU - Deng, Xiaotie
AU - Yin, Jianwei
N1 - Publisher Copyright:
© 2024, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2024
Y1 - 2024
N2 - In this work, we study truthful mechanisms for the rank-maximal matching problem, in the view of approximation. Our result reduces the gap from both the upper and lower bound sides. We propose a lexicographically truthful (LT) and nearly Pareto optimal (PO) randomized mechanism with an approximation ratio 2e-12e-2≈1.77. The previous best result is 2. The crucial and novel ingredients of our algorithm are preservation lemmas, which allow us to utilize techniques from online algorithms to analyze the new ratio. We also provide several hardness results in variant settings to complement our upper bound. In particular, we improve the lower bound of the approximation ratio for our LT and PO mechanism to 18 / 13 ≈ 1.38. To the best of our knowledge, it is the first time to obtain a lower bound by utilizing the linear programming approach along this research line.
AB - In this work, we study truthful mechanisms for the rank-maximal matching problem, in the view of approximation. Our result reduces the gap from both the upper and lower bound sides. We propose a lexicographically truthful (LT) and nearly Pareto optimal (PO) randomized mechanism with an approximation ratio 2e-12e-2≈1.77. The previous best result is 2. The crucial and novel ingredients of our algorithm are preservation lemmas, which allow us to utilize techniques from online algorithms to analyze the new ratio. We also provide several hardness results in variant settings to complement our upper bound. In particular, we improve the lower bound of the approximation ratio for our LT and PO mechanism to 18 / 13 ≈ 1.38. To the best of our knowledge, it is the first time to obtain a lower bound by utilizing the linear programming approach along this research line.
UR - http://www.scopus.com/inward/record.url?scp=85181981026&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-48974-7_36
DO - 10.1007/978-3-031-48974-7_36
M3 - Conference contribution
AN - SCOPUS:85181981026
SN - 9783031489730
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 637
EP - 653
BT - Web and Internet Economics - 19th International Conference, WINE 2023, Proceedings
A2 - Garg, Jugal
A2 - Klimm, Max
A2 - Kong, Yuqing
PB - Springer Science and Business Media Deutschland GmbH
T2 - 19th InternationalConference on Web and Internet Economics, WINE 2023
Y2 - 4 December 2023 through 8 December 2023
ER -