Edge Manipulations for the Maximum Vertex-Weighted Bipartite b-matching

作     者：Auricchio, Gennaro Liu, Jun Ma, Qun Zhang, Jie 

作者机构：Univ Bath Bath England Beijing Normal Univ Sch Math Sci Beijing Peoples R China Tianjin Univ Tianjin Peoples R China 

出 版 物：《ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY》 (ACM Trans. Intell. Syst. Technolog.)

年 卷 期：2025年第16卷第1期

页      面：1-26页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Leverhulme Trust EPSRC [EP/W014912/1] Beijing Natural Science Foundation 

主　　题：Algorithmic Mechanism Design Vertex Weighted Matching problems Edge Manipulations 

摘      要：In this article, we explore the Mechanism Design aspects of the Maximum Vertex-Weighted b-matching (MVbM) problem on bipartite graphs (A boolean OR T,E). The set A comprises agents, while T represents tasks. The set E, which connects A and T, is the private information of either agents or tasks. In this framework, we investigate three mechanisms-M-BFS, M-DFS, and M-G. We examine scenarios in which either agents or tasks are strategic and report their adjacent edges to one of the three mechanisms. In both cases, we assume that the strategic entities are bounded by their statements: They can hide edges, but they cannot report edges that do not exist. First, we consider the case in which agents can manipulate. In this framework, M-BFS and M-DFS are optimal but not truthful. By characterizing the Nash Equilibria induced by M-BFS and M-DFS, we reveal that both mechanisms have a Price of Anarchy (PoA) and Price of Stability (PoS) of 2. These efficiency guarantees are tight;no deterministic mechanism can achieve a lower PoA or PoS. In contrast, the third mechanism, M-G, is not optimal, but truthful and its approximation ratio is 2. We demonstrate that this ratio is optimal;no deterministic and truthful mechanism can outperform it. We then shift our focus to scenarios where tasks can exhibit strategic behavior. In this case, MBFS, M-DFS, and M-G all maintain truthfulness, making M-BFS and M-DFS truthful and optimal mechanisms. In conclusion, we investigate the manipulability of M-BFS and M-DFS through experiments on randomly generated graphs. We observe that (i) M-BFS is less prone to be manipulated by the first agent than M-DFS, and (ii) M-BFS is more manipulable on instances in which the total capacity of the agents is equal to the number of tasks.