This study delves into the intricate realm of Minimax Approval Voting, shedding light on its characteristics from both approximation and parameterized complexity perspectives. By navigating through these diverse landscapes, we offer insights into the challenges and opportunities inherent in optimizing Minimax Approval Voting scenarios. The exploration of approximation algorithms provides a nuanced understanding of the trade-offs between computational efficiency and solution quality, while the investigation into parameterized complexity unveils the tractability and inherent complexities of the voting model. Our findings contribute to the theoretical foundations of Minimax Approval Voting, offering valuable guidance for practitioners and researchers engaged in the design and analysis of voting systems.

Minimax Approval Voting, Computational Complexity, Approximation Algorithms

Andoni, A., Indyk, P., & Patrascu, M. (2006). On the Optimality of the DimensionalityReduction Method. InProceedings of 47th Annual IEEE Symposium on Foundationsof Computer Science, FOCS 2006, pp. 449–458.

Aziz, H., Bogomolnaia, A., & Moulin, H. (2017a). Fair Mixing: The Case of DichotomousPreferences.CoRR,abs/1712.02542.

Aziz, H., Brill, M., Conitzer, V., Elkind, E., Freeman, R., & Walsh, T. (2017b). JustifiedRepresentation in Approval-based Committee Voting.Social Choice and Welfare,48(2), 461–485.

Baumeister, D., Bohnlein, T., Rey, L., Schaudt, O., & Selker, A. (2016). Minisum andMinimax Committee Election Rules for General Preference Types. InProceedings of22nd European Conference on Artificial Intelligence, ECAI 2016, Vol. 285 ofFrontiersin Artificial Intelligence and Applications, pp. 1656–1657. IOS Press.

Betzler, N., Slinko, A., & Uhlmann, J. (2013). On the Computation of Fully ProportionalRepresentation.Journal of Artificial Intelligence Research,47, 475–519.

Bouchitte, V., & Todinca, I. (2001). Treewidth and Minimum Fill-in: Grouping the MinimalSeparators.SIAM Journal of Computing,31(1), 212–232.

Brams, S. J., Kilgour, D. M., & Sanver, M. R. (2007a). A Minimax Procedure for ElectingCommittees.Public Choice,132(3-4), 401–420.

Brams, S. J., Kilgour, D. M., & Sanver, M. R. (2007b). A Minimax Procedure for NegotiatingMultilateral Treaties. In Avenhaus, R., & Zartman, I. W. (Eds.),Diplomacy Games,pp. 265–282. Springer Berlin, Heidelberg.

Bredereck, R., Chen, J., Faliszewski, P., Guo, J., Niedermeier, R., & Woeginger, G. J.(2014). Parameterized Algorithmics for Computational Social Choice: Nine ResearchChallenges.Tsinghua Science and Technology,19(4), 358–373.

Byrka, J., Skowron, P., & Sornat, K. (2018). Proportional Approval Voting, Harmonick-median, and Negative Association. InProceedings of 45th International Colloquiumon Automata, Languages, and Programming, ICALP 2018, pp. 26:1–26:14.