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


  • Bo Li Department of Computing, The Hong Kong Polytechnic University
  • Xiaowei Wu IOTSC, University of Macau
  • Chenyang Xu Software Engineering Institute, East China Normal University College of Computer Science, Zhejiang University
  • Ruilong Zhang Department of Computer Science, City University of Hong Kong



GTEP: Social Choice / Voting, GTEP: Game Theory, GTEP: Other Foundations of Game Theory & Economic Paradigms


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 problem to submodular objective functions and Matroid rank constraints.




How to Cite

Li, B., Wu, X., Xu, C., & Zhang, R. (2023). Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule. Proceedings of the AAAI Conference on Artificial Intelligence, 37(5), 5730-5738.



AAAI Technical Track on Game Theory and Economic Paradigms