Abstract

In this article, we explore the Mechanism Design aspects of the Maximum Vertex-Weighted-matching (MVbM) problem on bipartite graphs [ . The set comprises agents, while represents tasks. The set , which connects and , is the private information of either agents or tasks. In this framework, we investigate three mechanisms—M , M , and M . 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 optimal but not truthful. By characterizing the Nash Equilibria induced by M and M are and M ,we reveal that both mechanisms have a Price of Anarchy ( ) and Price of Stability ( are tight; no deterministic mechanism can achieve a lower or ) of 2. These efficiency guarantees . In contrast, the third mechanism, M , 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, M , M ,and M all maintain truthfulness, making M and M truthful and optimal mechanisms. In conclusion, we investigate the manipulability of M through experiments on randomly generated graphs. We observe that (i) M and M is less prone to be manipulated by the first agent than M , and (ii) M is more manipulable on instances in which the total capacity of the agents is equal to the number of tasks.1
Original languageEnglish
JournalACM Transactions on Intelligent Systems and Technology
Early online date6 Nov 2024
DOIs
Publication statusPublished - 20 Jan 2025

Funding

G. Auricchio and J. Zhang are partially supported by a Leverhulme Trust Research Project Grant (2021–2024). J. Zhang is also supported by the EPSRC grant (EP/W014912/1). J. Liu is supported by Beijing Natural Science Foundation (No. 1232011).

FundersFunder number
The Leverhulme Trust2021–2024
Engineering and Physical Sciences Research CouncilEP/W014912/1
Beijing Municipal Natural Science Foundation 1232011

Fingerprint

Dive into the research topics of 'Edge Manipulations for the Maximum Vertex-Weighted Bipartite b-matching'. Together they form a unique fingerprint.

Cite this