On the Manipulability of Maximum Vertex-Weighted Bipartite b-Matching Mechanisms

Gennaro Auricchio; Jie Zhang

doi:10.3233/FAIA230262

On the Manipulability of Maximum Vertex-Weighted Bipartite b-Matching Mechanisms

Gennaro Auricchio, Jie Zhang

University of Bath, Department of Computer Science

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

1 Citation (SciVal)

Abstract

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.

Original language	English
Title of host publication	ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings
Editors	Kobi Gal, Kobi Gal, Ann Nowe, Grzegorz J. Nalepa, Roy Fairstein, Roxana Radulescu
Publisher	IOS Press BV
Pages	125-132
Number of pages	8
ISBN (Electronic)	9781643684369
DOIs	https://doi.org/10.3233/FAIA230262
Publication status	Published - 28 Sept 2023
Event	26th European Conference on Artificial Intelligence, ECAI 2023 - Krakow, Poland Duration: 30 Sept 2023 → 4 Oct 2023

Publication series

Name	Frontiers in Artificial Intelligence and Applications
Volume	372
ISSN (Print)	0922-6389
ISSN (Electronic)	1879-8314

Conference

Conference	26th European Conference on Artificial Intelligence, ECAI 2023
Country/Territory	Poland
City	Krakow
Period	30/09/23 → 4/10/23

Acknowledgements

We would like to thank the referees for their comments, which helped improve this paper considerably.

Funding

This project is partially supported by a Leverhulme Trust Research Project Grant (2021 – 2024). Jie Zhang is also supported by the EPSRC grant (EP/W014912/1).

Funders	Funder number
Engineering and Physical Sciences Research Council	EP/W014912/1
The Leverhulme Trust	2021 – 2024

ASJC Scopus subject areas

Artificial Intelligence

Access to Document

10.3233/FAIA230262Licence: CC BY-NC

Cite this

Auricchio, G., & Zhang, J. (2023). On the Manipulability of Maximum Vertex-Weighted Bipartite b-Matching Mechanisms. In K. Gal, K. Gal, A. Nowe, G. J. Nalepa, R. Fairstein, & R. Radulescu (Eds.), ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings (pp. 125-132). (Frontiers in Artificial Intelligence and Applications; Vol. 372). IOS Press BV. https://doi.org/10.3233/FAIA230262

On the Manipulability of Maximum Vertex-Weighted Bipartite b-Matching Mechanisms. / Auricchio, Gennaro; Zhang, Jie.
ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings. ed. / Kobi Gal; Kobi Gal; Ann Nowe; Grzegorz J. Nalepa; Roy Fairstein; Roxana Radulescu. IOS Press BV, 2023. p. 125-132 (Frontiers in Artificial Intelligence and Applications; Vol. 372).

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

Auricchio, G & Zhang, J 2023, On the Manipulability of Maximum Vertex-Weighted Bipartite b-Matching Mechanisms. in K Gal, K Gal, A Nowe, GJ Nalepa, R Fairstein & R Radulescu (eds), ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings. Frontiers in Artificial Intelligence and Applications, vol. 372, IOS Press BV, pp. 125-132, 26th European Conference on Artificial Intelligence, ECAI 2023, Krakow, Poland, 30/09/23. https://doi.org/10.3233/FAIA230262

Auricchio G, Zhang J. On the Manipulability of Maximum Vertex-Weighted Bipartite b-Matching Mechanisms. In Gal K, Gal K, Nowe A, Nalepa GJ, Fairstein R, Radulescu R, editors, ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings. IOS Press BV. 2023. p. 125-132. (Frontiers in Artificial Intelligence and Applications). doi: 10.3233/FAIA230262

Auricchio, Gennaro ; Zhang, Jie. / On the Manipulability of Maximum Vertex-Weighted Bipartite b-Matching Mechanisms. ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings. editor / Kobi Gal ; Kobi Gal ; Ann Nowe ; Grzegorz J. Nalepa ; Roy Fairstein ; Roxana Radulescu. IOS Press BV, 2023. pp. 125-132 (Frontiers in Artificial Intelligence and Applications).

@inproceedings{0b46512edf6044b683b60f7bbf4b8524,

title = "On the Manipulability of Maximum Vertex-Weighted Bipartite b-Matching Mechanisms",

abstract = "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.",

author = "Gennaro Auricchio and Jie Zhang",

year = "2023",

month = sep,

day = "28",

doi = "10.3233/FAIA230262",

language = "English",

series = "Frontiers in Artificial Intelligence and Applications",

publisher = "IOS Press BV",

pages = "125--132",

editor = "Kobi Gal and Kobi Gal and Ann Nowe and Nalepa, \{Grzegorz J.\} and Roy Fairstein and Roxana Radulescu",

booktitle = "ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings",

address = "Netherlands",

note = "26th European Conference on Artificial Intelligence, ECAI 2023 ; Conference date: 30-09-2023 Through 04-10-2023",

}

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 - https://www.scopus.com/pages/publications/85175137728

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 - 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 -

On the Manipulability of Maximum Vertex-Weighted Bipartite b-Matching Mechanisms

Abstract

Publication series

Conference

Acknowledgements

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Logistics Optimisation After Brexit and COVID-19

Cite this

On the Manipulability of Maximum Vertex-Weighted Bipartite b-Matching Mechanisms

Abstract

Publication series

Conference

Acknowledgements

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Projects

Logistics Optimisation After Brexit and COVID-19

Cite this