TY - GEN
T1 - On the Manipulability of Maximum Vertex-Weighted Bipartite b-Matching Mechanisms
AU - Auricchio, Gennaro
AU - Zhang, Jie
PY - 2023/9/28
Y1 - 2023/9/28
N2 - In this paper, we study the Maximum Vertex-weighted b-Matching (MVbM) problem on bipartite graphs in a new game-theoretical environment. In contrast to other game-theoretical settings, we consider the case in which the value of the tasks is public and common to every agent so that the private information of every agent consists of edges connecting them to the set of tasks. In this framework, we study three mechanisms. Two of these mechanisms, namely MBFS and MDFS, are optimal but not truthful, while the third one, MAP, is truthful but sub-optimal. Albeit these mechanisms are induced by known algorithms, we show MBFS and MDFS are the best possible mechanisms in terms of Price of Anarchy and Price of Stability, while MAP is the best truthful mechanism in terms of approximated ratio. Furthermore, we characterize the Nash Equilibria of MBFS and MDFS and retrieve sets of conditions under which MBFS acts as a truthful mechanism, which highlights the differences between MBFS and MDFS. Finally, we extend our results to the case in which agents' capacity is part of their private information.
AB - In this paper, we study the Maximum Vertex-weighted b-Matching (MVbM) problem on bipartite graphs in a new game-theoretical environment. In contrast to other game-theoretical settings, we consider the case in which the value of the tasks is public and common to every agent so that the private information of every agent consists of edges connecting them to the set of tasks. In this framework, we study three mechanisms. Two of these mechanisms, namely MBFS and MDFS, are optimal but not truthful, while the third one, MAP, is truthful but sub-optimal. Albeit these mechanisms are induced by known algorithms, we show MBFS and MDFS are the best possible mechanisms in terms of Price of Anarchy and Price of Stability, while MAP is the best truthful mechanism in terms of approximated ratio. Furthermore, we characterize the Nash Equilibria of MBFS and MDFS and retrieve sets of conditions under which MBFS acts as a truthful mechanism, which highlights the differences between MBFS and MDFS. Finally, we extend our results to the case in which agents' capacity is part of their private information.
UR - http://www.scopus.com/inward/record.url?scp=85175137728&partnerID=8YFLogxK
U2 - 10.3233/FAIA230262
DO - 10.3233/FAIA230262
M3 - Chapter in a published conference proceeding
AN - SCOPUS:85175137728
T3 - Frontiers in Artificial Intelligence and Applications
SP - 125
EP - 132
BT - ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings
A2 - Gal, Kobi
A2 - Gal, Kobi
A2 - Nowe, Ann
A2 - Nalepa, Grzegorz J.
A2 - Fairstein, Roy
A2 - Radulescu, Roxana
PB - IOS Press BV
T2 - 26th European Conference on Artificial Intelligence, ECAI 2023
Y2 - 30 September 2023 through 4 October 2023
ER -
