Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule

Bo Li; Xiaowei Wu; Chenyang Xu; Ruilong Zhang

doi:10.1609/aaai.v37i5.25711

Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule

Bo Li^*
, Xiaowei Wu^*
, Chenyang Xu^*
, Ruilong Zhang^*

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

Given a connected graph on whose edges we can build roads to connect the nodes, a number of agents hold possibly different perspectives on which edges should be selected by assigning different edge weights. Our task is to build a minimum number of roads so that every agent has a spanning tree in the built subgraph whose weight is the same as a minimum spanning tree in the original graph. We first show that this problem is NP-hard and does not admit better than ((1 - o(1)) ln k)approximation polynomial-time algorithms unless P = NP, where k is the number of agents. We then give a simple voting algorithm with an optimal approximation ratio. Moreover, our algorithm only needs to access the agents' rankings on the edges. Finally, we extend our results to submodular objective functions and Matroid rank constraints. Copyright © 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Original language	English
Title of host publication	Proceedings of the 37th AAAI Conference on Artificial Intelligence
Editors	Brian Williams, Yiling Chen, Jennifer Neville
Place of Publication	Washington, DC
Publisher	AAAI Press
Pages	5730-5738
ISBN (Print)	9781577358800 (set)
DOIs	https://doi.org/10.1609/aaai.v37i5.25711
Publication status	Published - 2023
Event	37th Association for the Advancement of Artificial Intelligence Conference on Artificial Intelligence (AAAI-23) - Walter E. Washington Convention Center, Washington, United States Duration: 7 Feb 2023 → 14 Feb 2023 https://aaai-23.aaai.org/ https://ojs.aaai.org/index.php/AAAI/index

Publication series

Name	Proceedings of the AAAI Conference on Artificial Intelligence
Number	1
Volume	37
ISSN (Print)	2159-5399
ISSN (Electronic)	2374-3468

Conference

Conference	37th Association for the Advancement of Artificial Intelligence Conference on Artificial Intelligence (AAAI-23)
Abbreviated title	AAAI23
Place	United States
City	Washington
Period	7/02/23 → 14/02/23
Internet address	https://aaai-23.aaai.org/ https://ojs.aaai.org/index.php/AAAI/index

Funding

Chenyang Xu is funded by Science and Technology Innovation 2030– “The Next Generation of Artificial Intelligence” Major Project No.2018AAA0100900. Xiaowei Wu is funded by FDCT (File no. 0143/2020/A3, SKL-IOTSC2021-2023), the SRG of University of Macau (File no. SRG2020-00020-IOTSC) and GDST (2020B1212030003). Bo Li is funded by HKSAR RGC (No. PolyU 25211321), NSFC (No. 62102333), CCF-HuaweiLK2022006, and PolyU Start-up (No. P0034420).

RGC Funding Information

RGC-funded

Access Output

10.1609/aaai.v37i5.25711

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Li, B., Wu, X., Xu, C., & Zhang, R. (2023). Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule. In B. Williams, Y. Chen, & J. Neville (Eds.), Proceedings of the 37th AAAI Conference on Artificial Intelligence (pp. 5730-5738). (Proceedings of the AAAI Conference on Artificial Intelligence; Vol. 37, No. 1). AAAI Press. https://doi.org/10.1609/aaai.v37i5.25711

@inproceedings{3114060dab0349028b8fc42419f5e37f,

title = "Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule",

abstract = "Given a connected graph on whose edges we can build roads to connect the nodes, a number of agents hold possibly different perspectives on which edges should be selected by assigning different edge weights. Our task is to build a minimum number of roads so that every agent has a spanning tree in the built subgraph whose weight is the same as a minimum spanning tree in the original graph. We first show that this problem is NP-hard and does not admit better than ((1 - o(1)) ln k)approximation polynomial-time algorithms unless P = NP, where k is the number of agents. We then give a simple voting algorithm with an optimal approximation ratio. Moreover, our algorithm only needs to access the agents' rankings on the edges. Finally, we extend our results to submodular objective functions and Matroid rank constraints. Copyright {\textcopyright} 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.",

author = "Bo Li and Xiaowei Wu and Chenyang Xu and Ruilong Zhang",

year = "2023",

doi = "10.1609/aaai.v37i5.25711",

language = "English",

isbn = "9781577358800 (set)",

series = "Proceedings of the AAAI Conference on Artificial Intelligence",

publisher = "AAAI Press",

number = "1",

pages = "5730--5738",

editor = "Brian Williams and Yiling Chen and Jennifer Neville",

booktitle = "Proceedings of the 37th AAAI Conference on Artificial Intelligence",

note = "37th Association for the Advancement of Artificial Intelligence Conference on Artificial Intelligence (AAAI-23), AAAI23 ; Conference date: 07-02-2023 Through 14-02-2023",

url = "https://aaai-23.aaai.org/, https://ojs.aaai.org/index.php/AAAI/index",

}

Li, B, Wu, X, Xu, C & Zhang, R 2023, Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule. in B Williams, Y Chen & J Neville (eds), Proceedings of the 37th AAAI Conference on Artificial Intelligence. Proceedings of the AAAI Conference on Artificial Intelligence, no. 1, vol. 37, AAAI Press, Washington, DC, pp. 5730-5738, 37th Association for the Advancement of Artificial Intelligence Conference on Artificial Intelligence (AAAI-23), Washington, District of Columbia, United States, 7/02/23. https://doi.org/10.1609/aaai.v37i5.25711

Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule. / Li, Bo; Wu, Xiaowei; Xu, Chenyang et al.
Proceedings of the 37th AAAI Conference on Artificial Intelligence. ed. / Brian Williams; Yiling Chen; Jennifer Neville. Washington, DC: AAAI Press, 2023. p. 5730-5738 (Proceedings of the AAAI Conference on Artificial Intelligence; Vol. 37, No. 1).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Multiagent MST Cover

T2 - 37th Association for the Advancement of Artificial Intelligence Conference on Artificial Intelligence (AAAI-23)

AU - Li, Bo

AU - Wu, Xiaowei

AU - Xu, Chenyang

AU - Zhang, Ruilong

PY - 2023

Y1 - 2023

N2 - Given a connected graph on whose edges we can build roads to connect the nodes, a number of agents hold possibly different perspectives on which edges should be selected by assigning different edge weights. Our task is to build a minimum number of roads so that every agent has a spanning tree in the built subgraph whose weight is the same as a minimum spanning tree in the original graph. We first show that this problem is NP-hard and does not admit better than ((1 - o(1)) ln k)approximation polynomial-time algorithms unless P = NP, where k is the number of agents. We then give a simple voting algorithm with an optimal approximation ratio. Moreover, our algorithm only needs to access the agents' rankings on the edges. Finally, we extend our results to submodular objective functions and Matroid rank constraints. Copyright © 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

AB - Given a connected graph on whose edges we can build roads to connect the nodes, a number of agents hold possibly different perspectives on which edges should be selected by assigning different edge weights. Our task is to build a minimum number of roads so that every agent has a spanning tree in the built subgraph whose weight is the same as a minimum spanning tree in the original graph. We first show that this problem is NP-hard and does not admit better than ((1 - o(1)) ln k)approximation polynomial-time algorithms unless P = NP, where k is the number of agents. We then give a simple voting algorithm with an optimal approximation ratio. Moreover, our algorithm only needs to access the agents' rankings on the edges. Finally, we extend our results to submodular objective functions and Matroid rank constraints. Copyright © 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

UR - https://www.scopus.com/pages/publications/85167869632

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85167869632&origin=recordpage

U2 - 10.1609/aaai.v37i5.25711

DO - 10.1609/aaai.v37i5.25711

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9781577358800 (set)

T3 - Proceedings of the AAAI Conference on Artificial Intelligence

SP - 5730

EP - 5738

BT - Proceedings of the 37th AAAI Conference on Artificial Intelligence

A2 - Williams, Brian

A2 - Chen, Yiling

A2 - Neville, Jennifer

PB - AAAI Press

CY - Washington, DC

Y2 - 7 February 2023 through 14 February 2023

ER -

Li B, Wu X, Xu C, Zhang R. Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule. In Williams B, Chen Y, Neville J, editors, Proceedings of the 37th AAAI Conference on Artificial Intelligence. Washington, DC: AAAI Press. 2023. p. 5730-5738. (Proceedings of the AAAI Conference on Artificial Intelligence; 1). Epub 2023 Jun 26. doi: 10.1609/aaai.v37i5.25711

Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule

Abstract

Publication series

Conference

Funding

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this